Довга арифметика: відмінності між версіями

Алгоритм використовує операції поділу, поелементного множення, інтерполяції та сполуки, такі ж як і в алгоритмах Карацуби. Параметр k контролює поділ вхідних даних на 2 ^k частин, причому розміром M = N / 2 ^k кожна. Це накладає обмеження на N. Воно має ділитися без остачі.

Всі обчислення, поточкового перемноження виконуються по модулю 2 ^{N '}, де N' = 2 * M + k + 3 — число, округлене до добутку числа 2 ^k на процесорний розмір елементів в бітах. Результат інтерполяції можна представити в наступному вигляді, де вибір N 'дозволяє проводити розрахунки без усікання.

Як і в попередніх алгоритмах, для того, що б вирішити дану систему, можна використовувати наступні точки: g ^ i, де і змінюється від 0 до 2 ^k −1, а g = 2 ^{(2N '/ 2 ^k)}. g є 2 ^k-им коренем одиниці по модулю 2 ^{N '} +1. Ці точки гарантують, що система буде дозволена. Таким чином в Фур'є перетворенні використовуються тільки зрусув, додавання і заперечення.