Карондеев

Метод Карацубы

Битовая сложность

• Mn = O(nlog23) = O(n1.585)

11

Метод Тоома-Кука

Битовая сложность

• Mn = O(n1+ )

12

Метод Шёнхаге-Штрассена

13

Метод Шёнхаге-Штрассена

Основная идея

•Представление числа как многочлена:

1310 = 11012 = x3 + x2 + 1

14

Метод Шёнхаге-Штрассена

Основная идея

•Представление числа как многочлена

•Быстрое преобразование Фурье

15

Быстрое преобразование Фурье

Сеть бабочка

16

Сеть бабочка

17

Метод Шёнхаге-Штрассена

Битовая сложность

• Mn = O(n·log2 n·log2log2 n)

18

Метод Фюрера

Битовая сложность

• Mn = O(n·log2 n·2O(log2*n))

19

Сравнение методов

в столбик:

Mn = O(n2)

метод Карацубы:

Mn = O(nlog23)

 метод Тома-Кука:

Mn = O(n·log2n·log2log2n)

 методы на основе БПФ:

Mn = O(n·(log2n)c), где с ≥ 1

20