Дано - нечетное составное n. Требуется привести n к виду
n = 1 + 2^kq, где q - нечетное.

Прототип функции должен выглядеть так:

void do_n(unsigned n, unsigned *k, unsigned *q) -> т.е. функция должна вернуть k и q для данного n.

Уравнение можно немножко перевернуть. Изменить его к виду:

q = (n - 1)/2^k, где k пробегает значения от 0 до ??? - пока не додумался :( Далее q проверяется на нечетность.
Задача - оптимизировать по скорости.

q = n-1
while (q is even)
{
q = q shr 1
}

(пока чисто алгоритмически :)

Я сказал, что функция ДОЛЖНА вернуть k и q для данного n.
А ты что написал? Тут просто большой простор для оптимизации. И надо дотумкать до какого k крутить цикл...

Для начала пусть будет так:

	dec  eax
	xor  ecx,ecx

@@:	add  ecx, 1 ; на PIV быстрее чем inc ecx
	mov  edx, eax
	shr  eax, 1
	ja   @b

	mov  q, edx
	dec  ecx
	mov  k, ecx

С 1 на входе не совсем ясно, у меня приводится к виду:

1+2⁰*0

но 0 - это чётное число.

Смысл тут простой - считается количество множителей 2. Думаю это можно ускорить если как-нибудь сразу выдельть 2^k, но пока не знаю как :(

volodya
Извиняюсь, это спросонья :))

  mov eax, n
  xor ecx, ecx ; - это будет k
  dec eax
  jnp @@exit
  jz @@err    ; - если n > 1 на входе то это можно убрать
  bsf ecx, eax
  shr eax, ecx
@@exit:
  ; q = eax
  ; k = ecx
@@err: 
  ; как реагировать на 0??

	mov  eax, n
	dec  eax

	bsf  ecx, eax
	shr  eax, cl

	mov  q, eax
	mov  k, ecx

О, это уже есть, я думаю долго :)

S_T_A_S_
Только сдвигать то вправо надо :))

Да у меня что-то глюки с копированием кода из olly :)

Кстати, непонятно ещё, какой вариант будет быстрее - bsf инструкция тормозная (особенно на athlon),
а на PIV shr eax, cl медленно выполняется.
imho тут от самих чисел будет зависить.

S_T_A_S_
Нужно просто посчитать время выполнения для варианта с циклом и с bsf

DaemoniacaL

Во-во, но это нужно сделать для всех возможных чисел, учесть вероятность появления каждого из них.. (дальше у меня нехватка математических терминов/знаний, может какие-нибудь там дисперсии :0).

Например для чисела вида 2ⁿ-1 цикл будет явно быстерее, чем те 2 команды,
а для 2ⁿ+1 - медленнее.

S_T_A_S_
Кстати bsf не такой уж и медленный, время его выполнения зависит от числа, и составляет от 6 до 42 тактов для 486.
shr - reg, cl = 3 такта..

видимо все таки без цикла будет быстрее

Дык таких процев уже нет давно :)

На athlon и PIV bsf - 8 тактов, в то время как итерация цикла ~ 1-2 такта при правильном предсказании.
Вот с shr на PIV проблема -сама команда 4 такта (против 1 на P3), и судя по всему сдвиги > 1 он вообще хреново делает :( документация у них странная стала - половина цифр отсутствует :/

Короче, нужно код компилить и смотреть под профайлером на конкретной задаче, тут только от того, что функцию заинлайнить уже прирост должен быть заметный.

Да, господа, впечатлен :) Я тут с тренировки пришел. Только как раз подумал, что надо не 2 в степень возводить, а подсчитывать количество итераций как при делении в столбик :)
S_T_A_S_, только я не совсем понимаю, что значит: считается количество множителей 2
Множитель-то, в конечном итоге, один!

А-а! Понял!

@@:	add  ecx, 1 ; на PIV быстрее чем inc ecx
	mov  edx, eax
	shr  eax, 1
	ja   @b

Количество делений на 2! Как в столбик :)
Да, и еще. Где тут цикл?

	mov  eax, n
	dec  eax

	bsf  ecx, eax
	shr  eax, cl

	mov  q, eax
	mov  k, ecx