Переполнение алгоритма Карацубы

Я изучал алгоритм Карацубы в Википедии и остановился на этом разделе, который смутил меня.. Почему в этом алгоритме есть переполнение, я не понимаю, какие шаги он предпринял для решения этой проблемы. Вот скриншот моей проблемы

Скриншот

1 ответ

Решение

Чтобы не считать положительные числа только для начинающих. давайте иметь 8 битные цифры / цифры x0,x1,y0,y1,

Когда мы применяем 8-битное умножение:

x0*y0 -> 8bit * 8bit -> 16 bit

Это даст до 16-битного результата. Верхнее значение:

FFh*FFh = FE01h
255*255 = 65025

Теперь, если мы вернемся в Карацубу, давайте

X = x0 + x1<<8
Y = y0 + y1<<8
Z = X*Y = z0 + z1<<8 + z2<<16

Теперь давайте посмотрим на битовую ширину zi

z2 = x1*y1         -> 16 bit
z1 = x1*y0 + x0*y1 -> 17 bit
z0 = x0*y0         -> 16 bit

Обратите внимание, что z1 17 бит как верхнее значение

65025+65025 = 130050

Так что каждый из zi переполняет 8бит. Чтобы справиться с этим, вы просто берете только младшие 8 бит, а остальные добавляете к старшей цифре (например, распространение Carry). Так:

z1 += z0>>8;   z0 &= 255;
z2 += z1>>8;   z1 &= 255;
z3  = z2>>8;
Z = z0 + z1<<8 + z2<<16 + z3<<24

Но обычно HW реализация умножения обрабатывает это самостоятельно и дает результат в виде двух слов вместо одного. см. не могу сделать ценность распространяться через перенос

Таким образом, результат умножения на 16 бит составляет 32 бита. Помните, что для добавления 8-битных суб-результатов вам нужно как минимум 10 бит, так как мы складываем 3 числа вместе или добавляем и размножаем их по одному с 9 битами (или 8 битами + 1 перенос).

Если вы добавляете подписанные значения к этому, вам нужен еще один бит для знака. Чтобы избежать этого, запомните знаки операндов и используйте значения abs... и установите знак результата в зависимости от исходных знаков.

Для получения более подробной информации смотрите эти:

Другие вопросы по тегам