Арифметика чисел с фиксированной запятой формата 32.32

Тема в разделе "WASM.A&O", создана пользователем Aloner, 28 сен 2009.

Страница 1 из 3
  1. Aloner

    Aloner New Member

    Публикаций:
    0
    Регистрация:
    11 апр 2008
    Сообщения:
    96
    Собственно сабж: есть у кого нить мысли(лучше код :) ) как реализовать деление, умножение таких чисел? Заранее спасибо.
     
    Aloner, 28 сен 2009
    #1
  2. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    ( (a << 32) / (b << 32) ) >> 32

    в субжевом формате все числа хранятся уже в виде (a << 32)
     
    qqwe, 28 сен 2009
    #2
  3. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    Алгоритмы все стандартные.
     
    n0name, 28 сен 2009
    #3
  4. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    ну да, или как qqwe сказал ;)
    Расширяем число до 64-битного целого.
     
    n0name, 28 сен 2009
    #4
  5. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    обманул.
    результат предполагается тоже 32.32

    ( (a << 32) / (b << 32) ) << 32

    ( (a << 32) * (b << 32) ) >> 32
    видимо, лучше
    ( ((a << 32) >> 16) * ((b << 32) >> 16) )

    + и - так и остается
     
    qqwe, 28 сен 2009
    #5
  6. Aloner

    Aloner New Member

    Публикаций:
    0
    Регистрация:
    11 апр 2008
    Сообщения:
    96
    Спасибо за ответы!
    Еще правда не опробовал. Вечерком после работы протестирую.
     
    Aloner, 28 сен 2009
    #6
  7. Aloner

    Aloner New Member

    Публикаций:
    0
    Регистрация:
    11 апр 2008
    Сообщения:
    96
    А можно на асме этот же код?
     
    Aloner, 28 сен 2009
    #7
  8. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    Ося Бендер по этому поводу говорил : "а еще лучше сразу пачку баксов" :)
     
    valterg, 28 сен 2009
    #8
  9. Aloner

    Aloner New Member

    Публикаций:
    0
    Регистрация:
    11 апр 2008
    Сообщения:
    96
    valterg
    Надежда на халяву умирает последней))qqwe
    qqwe
    1. Сдвиги нужно до 31, иначе при 32 будет всегда возвращать 0. :)
    2. У нас числа уже в виде 64-битного целого, значит для умножения и деления нужно использовать 128-битное целое будет. Вот теперь думаю как работать с 128-битным целым и будет ли это эффективнее чем вычисления на FPU( умножение/деление).
     
    Aloner, 29 сен 2009
    #9
  10. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    чтобы сдвинуть
    [edx=0 : eax=5] на 32 в [edx=5 : eax=0]
    нужно просто скопировать регистры. это такая хитрость при сдвиге на 128, 64, 32, 16, 8
    пост #5 читали? со слов "видимо лучше.."
    нет не будет. причина - основное время берет работа с памятью (не закэшированой), а не простые вычисления. если хотите больше скорости - смотрите в сторону ммх/ссе
     
    qqwe, 29 сен 2009
    #10
  11. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Aloner
    а когда надежда умирает, в муках лени просыпаются мозги. знаете, что мозг при работе выделяет эндорфины? (а при физической работе и более сильные вва). так со смертью надежды можно стать и трудоголиком, и даже вторым билли (что что, а в ленивом ожидании милости у пруда его обвинить сложно)
     
    qqwe, 29 сен 2009
    #11
  12. Aloner

    Aloner New Member

    Публикаций:
    0
    Регистрация:
    11 апр 2008
    Сообщения:
    96
    qqwe
    Что то немного друг друга непонимаем(или я :) )
    пост #5 читали? со слов "видимо лучше.."
    (a << 32) >> 16) - в этом случае выражении уже изначально равно a<<32,то есть имеем как бы ((a<<32) << 32) >> 16)?
     
    Aloner, 29 сен 2009
    #12
  13. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    1а) произведение (a2^32+b)x(c2^32+d)=ac2^64+(ad+bc)2^32+bd далее используйте команды MUL, ADD и ADC
    1б) можем воспользоваться алгоритмом Карацуба:
    1. вычислим bd – первое умножение
    2. вычислим ac – второе умножение
    3. вычислим t=(a + b)x(c+d) – третье умножение
    X*Y=(a2^32 + b)x(c2^32 + d)=ac2^64 +(t– ac– bd)2^32 + bd
    1в) алгоритм Тоома-Кука:
    1. вычислим bd – первое умножение
    2. вычислим t0=(a + b)x(c + d) – второе умножение
    3. вычислим t1=(b - a)x(d - с) – третье умножение
    Так как (t0 – t1)/2 = ad + bc и (t0 + t1)/2 - bd = ac
    поэтому X*Y=(a2^32 + b)(c2^32 + d)=((t0 + t1)/2 - bd)2^64 +(t0 – t1)2^31 + bd
    1г) Можно также использовать следующее свойство:
    X*Y=(X+Y)^2/4 – (X–Y)^2/4 = ((a + c)2^32 + b + d)^2/4 – ((a – c)2^32 + b – d)^2/4

    2) деление числа (c2^32+d) на число (a2^32+b) заключается в следующем. Вычислить такие q и r, что c=ar+q (r частное от деления c на a, а q остаток). Равенство c=ar+q означает, что c2^32+d=(ar+q)2^32+d=r(a2^32+b)+q2^32+d-rb. Число q2^32+d-rb считается остатком первоначального деления; если оно отрицатель­но, следует производить повторяющийся декремент r до тех пор, пока оно не станет положительным.
     
    Mikl___, 29 сен 2009
    #13
  14. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    при условии, что сомножетели и место под ре­зультат располагаются в памяти после­довательно вот вам код
    Код (Text):
    1. .code
    2.    mov ebx,offset X
    3.    mov eax,[ebx]
    4.    mov edi,8
    5. a2:   mov ecx,2
    6. a1:   mul dword ptr [ebx+edi]
    7.    add [ebx+16],eax
    8.    adc [ebx+20],edx
    9.    adc dword ptr [ebx+24],0
    10.    mov eax,[ebx]
    11.    add ebx,4
    12.    loop a1
    13.    sub ebx,4
    14.    sub edi,4
    15.    jnz a2
    16. .data
    17. X dq    0FFFFFFFFFFFFFFFFh;сомножители    
    18. Y dq    0FFFFFFFFFFFFFFFFh
    19. Z dq 2 dup (0)    ;место под результат
     
    Mikl___, 29 сен 2009
    #14
  15. Aloner

    Aloner New Member

    Публикаций:
    0
    Регистрация:
    11 апр 2008
    Сообщения:
    96
    Mikl___
    Огромное Спасибо. Пробую ща 1а вариант осуществить. Даже папер нашел по теме.
     
    Aloner, 30 сен 2009
    #15
  16. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    Так его реализация в #14
     
    Mikl___, 30 сен 2009
    #16
  17. Ra_

    Ra_ New Member

    Публикаций:
    0
    Регистрация:
    4 мар 2007
    Сообщения:
    289
    Дядька Mikl___ - а теперь тоже самое для 512 и 1024бит - по-моему в этом цель ТС.
    :)
     
    Ra_, 30 сен 2009
    #17
  18. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.792
    Ra_
    Написать-то я напишу, проверять-то кто-нибудь будет? Windows-калькулятор переводит в Hex-числа длиной максимум 8 байт...
     
    Mikl___, 30 сен 2009
    #18
  19. Ra_

    Ra_ New Member

    Публикаций:
    0
    Регистрация:
    4 мар 2007
    Сообщения:
    289
    Напишите, напишите обязательно - молодым криптографам окажете большую помощь.
    А проверить - найдут калькуляторы для больших чисел.
     
    Ra_, 30 сен 2009
    #19
  20. Sergey_R

    Sergey_R Member

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    138
    Вот посмотрите:
    [ur=http://window.edu.ru/window_catalog/pdf2txt?p_id=18073&p_page=1]Выполнение арифметических операций в АЛУ для чисел с фиксированной запятой.[/url]. Может наведет на мысль. ;о)
    Можно скачать небольшой 469.5 КБ pdf по теме: http://window.edu.ru/window_catalog/redir?id=40768&file=mtdukvm10.pdf
     
    Sergey_R, 30 сен 2009
    #20
Страница 1 из 3