Переполнение алгоритма Карацубы
Я изучал алгоритм Карацубы в Википедии и остановился на этом разделе, который смутил меня.. Почему в этом алгоритме есть переполнение, я не понимаю, какие шаги он предпринял для решения этой проблемы. Вот скриншот моей проблемы
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... и установите знак результата в зависимости от исходных знаков.
Для получения более подробной информации смотрите эти: