#1 28-09-2009 12:42:46

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

Собственно сабж: есть у кого нить мысли(лучше код :-) ) как реализовать деление, умножение таких чисел? Заранее спасибо.

Вне форума

#2 28-09-2009 13:05:18

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

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

в субжевом формате все числа хранятся уже в виде (a << 32)

Вне форума

#3 28-09-2009 13:05:45

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

Алгоритмы все стандартные.


То, что не удается запрограммировать на ассемблере, приходится паять.

Вне форума

#4 28-09-2009 13:06:35

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

ну да, или как qqwe сказал ;)
Расширяем число до 64-битного целого.


То, что не удается запрограммировать на ассемблере, приходится паять.

Вне форума

#5 28-09-2009 13:47:28

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

обманул.
результат предполагается тоже 32.32

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

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

+ и - так и остается

Вне форума

#6 28-09-2009 14:12:34

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

Спасибо за ответы!
Еще правда не опробовал. Вечерком после работы протестирую.

Вне форума

#7 28-09-2009 14:24:52

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

А можно на асме этот же код?

Вне форума

#8 28-09-2009 14:42:35

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

Aloner написал ранее:

А можно на асме этот же код?

Ося Бендер по этому поводу говорил : "а еще лучше сразу пачку баксов"  :-)

Вне форума

#9 29-09-2009 06:02:21

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

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

Вне форума

#10 29-09-2009 06:25:10

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

1. Сдвиги нужно до 31, иначе при 32 будет всегда возвращать  0.

чтобы сдвинуть
[edx=0 : eax=5] на 32 в [edx=5 : eax=0]
нужно просто скопировать регистры. это такая хитрость при сдвиге на 128, 64, 32, 16, 8

. У нас числа уже в виде 64-битного целого, значит для умножения и деления нужно использовать 128-битное целое будет.

пост #5 читали? со слов "видимо лучше.."

Вот теперь думаю как работать с 128-битным целым и будет ли это эффективнее чем вычисления на FPU( умножение/деление).

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

Вне форума

#11 29-09-2009 06:30:41

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

Aloner

Надежда на халяву умирает последней

а когда надежда умирает, в муках лени просыпаются мозги. знаете, что мозг при работе выделяет эндорфины? (а при физической работе и более сильные вва). так со смертью надежды можно стать и трудоголиком, и даже вторым билли (что что, а в ленивом ожидании милости у пруда его обвинить сложно)

Вне форума

#12 29-09-2009 06:56:45

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

qqwe
Что то немного друг друга непонимаем(или я :) )
пост #5 читали? со слов "видимо лучше.."
(a << 32) >> 16) - в этом случае выражении уже изначально равно a<<32,то есть имеем как бы ((a<<32) << 32) >> 16)?

Вне форума

#13 29-09-2009 07:37:08

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

Aloner написал ранее:

как реализовать деление, умножение чисел с фиксированной запятой формата 32:32?

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 до тех пор, пока оно не станет положительным.

Вне форума

#14 29-09-2009 07:49:08

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

при условии, что сомножетели и место под ре­зультат располагаются в памяти после­довательно вот вам код

.code
   mov ebx,offset X
   mov eax,[ebx]
   mov edi,8
a2:   mov ecx,2
a1:   mul dword ptr [ebx+edi]
   add [ebx+16],eax
   adc [ebx+20],edx
   adc dword ptr [ebx+24],0
   mov eax,[ebx]
   add ebx,4
   loop a1
   sub ebx,4
   sub edi,4
   jnz a2
.data
X dq	0FFFFFFFFFFFFFFFFh;сомножители    
Y dq	0FFFFFFFFFFFFFFFFh
Z dq 2 dup (0)    ;место под результат

Вне форума

#15 30-09-2009 05:49:13

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

Mikl___
Огромное Спасибо. Пробую ща 1а вариант осуществить. Даже папер нашел по теме.

Вне форума

#16 30-09-2009 07:47:57

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

Aloner написал ранее:

Пробую ща 1а вариант осуществить.

Так его реализация в #14

Вне форума

#17 30-09-2009 08:31:39

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

Дядька Mikl___ - а теперь тоже самое для 512 и 1024бит - по-моему в этом цель ТС.
:)

Вне форума

#18 30-09-2009 09:20:05

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

Ra_
Написать-то я напишу, проверять-то кто-нибудь будет? Windows-калькулятор переводит в Hex-числа длиной максимум 8 байт...

Вне форума

#19 30-09-2009 09:49:06

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

Напишите, напишите обязательно - молодым криптографам окажете большую помощь.
А проверить - найдут калькуляторы для больших чисел.

Вне форума

#20 30-09-2009 11:54:34

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

Вот посмотрите:
[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

Вне форума

#21 30-09-2009 14:52:52

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

Ra_ написал ранее:

Напишите, напишите обязательно - молодым криптографам окажете большую помощь.
А проверить - найдут калькуляторы для больших чисел.

Молодые и старые криптографы без проблем найдут исходники библиотеки bignum. Было дело : переделывал я кейген для Армадилло.

Вне форума

#22 30-09-2009 18:18:40

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

Я тоже много разных библиотек встречал, и на польских и на китайских и на англоязычных сайтах.
Помню реализацию и в журнале "Монитор". Задача несколько в другом.
Реализация на ассемблере и здесь. Ну скажем в учебном плане.
...Посадив зернышко может что-то и более значимое вырастет...

Вне форума

#23 01-10-2009 08:46:16

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

Mikl___
Так его реализация в #14 - да, в тот день сильно тормозил ))
to_all:
Всем спасибо за ответы.
Интересно, кто-нибудь в наше время использует фиксы, кроме мобильных платформ?

Вне форума

#24 01-10-2009 09:51:32

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

Sergey_R написал ранее:

Выполнение арифметических операций в АЛУ для чисел с фиксированной запятой.[/url]. Может наведет на мысль. ;о)

Просмотрел mtdukvm10.prf стр 45 "АЛУ для ускоренного умножения с фиксированной запятой", где предлагается обрабатывать по 2 бита одного из сомножителей, и в зависимости от их содержания 00, 11 - сдвигать сомножитель на 1 разряд, 01 - складывать и сдвигать, 10 - вычитать и сдвигать и сравните здесь обрабатывается по 3 бита сомножителя, здесь по 4 бита и далее по аналогии "В зависимости от задачи можно выбрать оптимальное количество разрядов X(i+n),...,X(i-1)" и свести умножение к табличному преобразованию

Вне форума

#25 02-10-2009 04:16:56

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

Ra_ написал ранее:

а теперь тоже самое для 512 и 1024 бит

64-битное умножение, используя 32-разрядную арифметику
(a0 + a1 *2&#179;&#178;)x(b0 + b1 *2&#179;&#178;)=a0b0 + (a0b1+a1b0) 2&#179;&#178;+a1b1 *2^64
результат: 4 умножения, 3 сложения, 2 сдвига
96-битное умножение, используя 32-разрядную арифметику
(a0 + a1 *2&#179;&#178; + a2 *2^64)x(b0 + b1 *2&#179;&#178; + b2 *2^64)=a0b0 + a2b2 *2^128 + (a0b1+a1b0) 2&#179;&#178;+(a2b1+a1b2)2^96+(a2b0+a1b1+a0b2)2^64
результат: 9 умножений, 8 сложений, 4 сдвига
128-битное умножение, используя 32-разрядную арифметику
(a0 + a1 *2&#179;&#178; + a2 *2^64 + a3 *2^96)x(b0 + b1 *2&#179;&#178; + b2 *2^64 + b3 *2^96)=a0b0 + a3b3 *2^192 + (a0b1+a1b0) 2&#179;&#178;+(a2b3+a3b2)2^160+(a2b0+a1b1+a0b2)2^64+(a1b3+a3b1+a2b2)2^128+(a0b3+b0a3+a1b2+a2b1)2^96
результат: 16 умножений, 15 сложений, 6 сдвигов
Не пугайтесь, до 512 бит мы не пойдем, тем более до 1024, тем не менее, налицо тенденция - от количества членов ai *2^(i*32) в многочлене равного n -- зависисимость количества умножения n&#178;, сложений n&#178; - 1, сдвигов 2n. По сравнению со сложением и сдвигом умножение достаточно медленная операция (цитирую по Зубкову) для P6 add – 1m, shl – 1m, mul – 3m – 4m – постараемся свести количество умножений к минимуму.
Так получилось, что a1b0+a0b1=a0b0+a1b1+(a0-a1)(b1-b0) сохраняем в переменных c0=a0b0 c1=a1b1 c2=a2b2 p=c0+c1+c2 тогда
(a0 + a1 *2&#179;&#178; + a2 *2^64)x(b0 + b1 *2&#179;&#178; + b2 *2^64)=с0+c2*2^128 + (p-c2+(a0-a1)(b1-b0)) 2&#179;&#178;+(p+(a0-a2)(b2-b0)) 2^64+(p-c0+(a1-a2)(b2-b1)) 2^96 количество умножений сократилось до 6
пусть c0=a0b0 c1=a1b1 c2=a2b2 с3=a3b3 p=c0+c1+c2+c3 тогда
(a0 + a1 *2&#179;&#178; + a2 *2^64+a2^96)x(b0 + b1 *2&#179;&#178; + b2 *2^64+b3*2^96)=с0+c3*2^192 + (p-c2-c3+(a0-a1)(b1-b0)) 2&#179;&#178;+(p-c0-c1+(a2-a3)(b3-b2)) 2^160+(p-c3+(a0-a2)(b2-b0)) 2^64 +(p-c0+(a1-a3)(b3-b1)) 2^128+(p+(a0-a3)(b3-b0)+(a1-a2)(b2-b1)) 2^96 количество умножений сократилось до 10. А как же умножение для 512 и 1024 бит? «Сама, сама, сама» (© «Вокзал для двоих»)

Вне форума

Board footer

Работает на FluxBB.
Перевод FluxBB RU.