1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

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

Тема в разделе "WASM.A&O", создана пользователем volodya, 17 авг 2004.

  1. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Дано - нечетное составное n. Требуется привести n к виду

    n = 1 + 2<sup>k</sup>q, где q - нечетное.



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



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



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



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

    Задача - оптимизировать по скорости.
     
  2. DaemoniacaL

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    q = n-1

    while (q is even)

    {

    q = q shr 1

    }



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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Я сказал, что функция ДОЛЖНА вернуть k и q для данного n.

    А ты что написал? Тут просто большой простор для оптимизации. И надо дотумкать до какого k крутить цикл...
     
  4. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.755
    Для начала пусть будет так:
    Код (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<sup>0</sup>*0



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



    Смысл тут простой - считается количество множителей 2. Думаю это можно ускорить если как-нибудь сразу выдельть 2<sup>k</sup>, но пока не знаю как :dntknw:
     
  5. DaemoniacaL

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    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.  
     
  6. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.755
    Код (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




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

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    S_T_A_S_

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

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.755
    Да у меня что-то глюки с копированием кода из olly :)
     
  9. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.755
    Кстати, непонятно ещё, какой вариант будет быстрее - bsf инструкция тормозная (особенно на athlon),

    а на PIV shr eax, cl медленно выполняется.

    imho тут от самих чисел будет зависить.
     
  10. DaemoniacaL

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    S_T_A_S_

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

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.755
    DaemoniacaL



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



    Например для чисела вида 2<sup>n</sup>-1 цикл будет явно быстерее, чем те 2 команды,

    а для 2<sup>n</sup>+1 - медленнее.
     
  12. DaemoniacaL

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    S_T_A_S_

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

    shr - reg, cl = 3 такта..



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

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.755
    Дык таких процев уже нет давно :)



    На athlon и PIV bsf - 8 тактов, в то время как итерация цикла ~ 1-2 такта при правильном предсказании.

    Вот с shr на PIV проблема -сама команда 4 такта (против 1 на P3), и судя по всему сдвиги > 1 он вообще хреново делает :dntknw: документация у них странная стала - половина цифр отсутствует :/



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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Да, господа, впечатлен :) Я тут с тренировки пришел. Только как раз подумал, что надо не 2 в степень возводить, а подсчитывать количество итераций как при делении в столбик :)

    S_T_A_S_, только я не совсем понимаю, что значит: считается количество множителей 2

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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    А-а! Понял!


    Код (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
     
  16. DaemoniacaL

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    volodya

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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Цикл в первом варианте => ja @b



    Не понял!



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



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

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    volodya

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

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Одному из нас пора идти спать :)

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


    Код (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.  
     
  20. DaemoniacaL

    DaemoniacaL New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    42
    Адрес:
    Russia
    На мой взгляд лучше вместо ja использовать jp.. все таки нам четность важна :)