Привести число к виду 1 + 2^k * q

Дано - нечетное составное 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 крутить цикл...

 

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

Код (Text):

1.     dec  eax
2.     xor  ecx,ecx
3.  
4. @@: add  ecx, 1 ; на PIV быстрее чем inc ecx
5.     mov  edx, eax
6.     shr  eax, 1
7.     ja   @b
8.  
9.     mov  q, edx
10.     dec  ecx
11.     mov  k, ecx

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



1+2⁰*0



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



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

 

volodya

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

Код (Text):

1.  
2.   mov eax, n
3.   xor ecx, ecx ; - это будет k
4.   dec eax
5.   jnp @@exit
6.   jz @@err    ; - если n > 1 на входе то это можно убрать
7.   bsf ecx, eax
8.   shr eax, ecx
9. @@exit:
10.   ; q = eax
11.   ; k = ecx
12. @@err:
13.   ; как реагировать на 0??
14.  
15.  

 

Код (Text):

1.     mov  eax, n
2.     dec  eax
3.  
4.     bsf  ecx, eax
5.     shr  eax, cl
6.  
7.     mov  q, eax
8.     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

Множитель-то, в конечном итоге, один!

 

А-а! Понял!

Код (Text):

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

Количество делений на 2! Как в столбик

Да, и еще. Где тут цикл?

Код (Text):

1.     mov  eax, n
2.     dec  eax
3.  
4.     bsf  ecx, eax
5.     shr  eax, cl
6.  
7.     mov  q, eax
8.     mov  k, ecx

 

volodya

Цикл в первом варианте => ja @b

 

Цикл в первом варианте => ja @b



Не понял!



Во-во, но это нужно сделать для всех возможных чисел, учесть вероятность появления каждого из них



Имеется в виду асимптотическая плотность? Это можно посчитать... В топике о факторизации я давал линк на конспект по теории чисел. Там объясняется как это делать.

 

volodya

а разве прыгать пока условие истинно и выполнять один и тот же кусок кода - не цикл?

 

Одному из нас пора идти спать

Ты хочешь сказать так?

Код (Text):

1.  
2.     mov  eax, n
3.     dec  eax
4. @@:
5.     bsf  ecx, eax
6.     shr  eax, cl
7.         ja @b
8.  
9.     mov  q, eax
10.     mov  k, ecx
11.  

 

На мой взгляд лучше вместо ja использовать jp.. все таки нам четность важна