Довга арифметика: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 45:
Нехай в перемножуванні бере участь два числа x і y за модулем 2 <sup> N </sup> +1: x * y mod 2 ^ N +1. Якщо ми хочемо отримати результат «чистого» перемноження без модуля, то на N варто накласти наступне обмеження: <br/>
: N> = bits (x) + bits (y) <br/>
Алгоритм використовує операції поділу,
Всі обчислення, поточечной перемноження виконуються по модулю 2 <sup> N '</sup>, де N' = 2 * M + k + 3 — число, округлене до твору числа 2 <sup> k </sup> на процесорний розмір елементів в бітах. Результат інтерполяції можна представити в наступному вигляді, де вибір N 'дозволяє проводити розрахунки без усікання.
<math> w [n] = \ sum_ {i + j = b * 2 ^ k + n} ^ {b = 0,1} (-1) ^ b * x [i] * y [i] </math >. <br/>
Як і в попередніх алгоритмах, для того, що б вирішити дану систему, можна використовувати наступні точки: g ^ i, де i змінюється від 0 до 2 <sup> k </sup> −1, а g = 2 <sup> (2N '/ 2 <sup> k </sup>) </sup>. g є 2 <sup> k </sup>-им коренем одиниці по модулю 2 <sup> N '</sup> +1. Ці точки гарантують, що
==== Other Multiplication ====
|