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