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

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

 

64-битное умножение, используя 32-разрядную арифметику
(a0 + a1 *2³²)x(b0 + b1 *2³²)=a0b0 + (a0b1+a1b0) 2³²+a1b1 *2^64
результат: 4 умножения, 3 сложения, 2 сдвига
96-битное умножение, используя 32-разрядную арифметику
(a0 + a1 *2³² + a2 *2^64)x(b0 + b1 *2³² + b2 *2^64)=a0b0 + a2b2 *2^128 + (a0b1+a1b0) 2³²+(a2b1+a1b2)2^96+(a2b0+a1b1+a0b2)2^64
результат: 9 умножений, 8 сложений, 4 сдвига
128-битное умножение, используя 32-разрядную арифметику
(a0 + a1 *2³² + a2 *2^64 + a3 *2^96)x(b0 + b1 *2³² + b2 *2^64 + b3 *2^96)=a0b0 + a3b3 *2^192 + (a0b1+a1b0) 2³²+(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², сложений n² - 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³² + a2 *2^64)x(b0 + b1 *2³² + b2 *2^64)=с0+c2*2^128 + (p-c2+(a0-a1)(b1-b0)) 2³²+(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³² + a2 *2^64+a2^96)x(b0 + b1 *2³² + b2 *2^64+b3*2^96)=с0+c3*2^192 + (p-c2-c3+(a0-a1)(b1-b0)) 2³²+(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 бит? «Сама, сама, сама» (© «Вокзал для двоих»)

 

valterg
Вы меня в чем, то обвиняете? В #13 упоминаются алгоритмы Карацуба и Тоома-Кука

Я, честно говоря, не осилил описание Тоома-Кука ни Д.Кнута во 2-ом томе ни у Уэзерелла "Этюды для программистов" глава "Насколько быстро можно выполнить умножение", поэтому и попытался своими словами

 

Ra_
Я не математик, напишу еще что-нибудь не так, забуду упомянуть классиков (не со зла, а по незнанию)

 

Можно по-подробнее и ссылки если не секрет конечно...

 

Теперь, Ra_, Ваша очередь

 

На ЕС-1022 гораздо, медленнее, мы даже успевали пообедать пока шло умножение "в столбик", а вот когда поставили ЕС-1036, тут и началось, не успеешь спирт разбавить, а она уже, сволочь, все поперемножала, IMHO наверное Пентиум с ЕС-1036 содрали

 

valterg
[offtop]Про ЕС-1022 и ЕС-1036 это стёб, в который меня ввел ваш вопрос "До Пентиума умножение выполнялось гораздо медленнее сложения. Или нет?"[/offtop]
В продолжение темы: во вложении статьи Ильи Кантора "Большие числа и операции с ними" и "Эффективное вычисление дискретного преобразования Фурье и дискретного преобразования Хартли". По поводу "итерационного подсчета обратной величины" подробно в Ахо, Хопкрофт, Ульман "Построение и анализ вычислительных алгоритмов" глава 8.2 "Умножение и деление целых чисел"

 

Mikl___
Упс, не прикрепилось, но могу сбросить в почту, если кому-то потребуется

 

статья И.Кантора "Большие числа и операции с ними"