Реализация умножения Карацубы в представлении radix-2^32 (код C)
Я пытаюсь реализовать умножение Карацубы 3-го уровня для умножения двух 256-битных операндов. Я хочу использовать radix-2^32 представления моих операндов, поэтому я реализовал умножение в школьных учебниках двух 32-разрядных операндов, которые я намерен использовать внутри моей функции умножения Карацубы. Насколько я знаю, я могу разделить свои операнды следующим образом:
level-1 :AB = A0B0 + ((A0 + A1)(B0 + B1) - A0B0 - A1B1)(x^(m/2)) + A1B1(x^m)
level-2 : A0B0 = A00B00 + ((A00 + A01)(B00 + B01) - A00B00 - A01B01)(x^m/2)) + A01B01(x^m)
level-3 : A00B00 = A000B000 + ((A000 + A001)(B000 + B001) - A000B000 - A001B001)(x^(m/2)) + A001B001(x^m)
Как вы можете видеть здесь, A и B имеют 256 бит, а A000 и B000 имеют 32 бита, которые правильно вписываются в мой unit32_t тип данных. Как я упоминал ранее, я уже реализовал умножение учебников для двух 32-битных операндов, и оно отлично работает. Вот моя проблема, на уровне 3, когда я добавляю два 32-битных операнда (A000 + A0001) и (B000 + B0001), я получаю 33-битный результат из-за переноса. Поэтому я должен умножить два 33-битных операнда и получить 66-битный результат, который не предназначен в моем случае! Итак, как я могу реализовать этот алгоритм, используя только uint32_t представление типа данных?