Алгоритм умножения целых чисел с использованием подхода «разделяй и властвуй»?

В качестве домашнего задания я должен реализовать целочисленное умножение чисел из 1000 цифр, используя подход «разделяй и властвуй», который работает ниже O (n). Какой алгоритм я должен изучить?


algorithm biginteger divide-and-conquer
person andandandand    schedule 08.05.2011    source источник
comment
Временная сложность не может быть меньше O(n), если n — размер входных данных. Тогда вы даже не сможете прочитать весь ввод.   -  person interjay    schedule 08.05.2011
comment
Я подозреваю, что O(n) имеет в виду псевдополиномиальное время, то есть он действительно хочет чего-то лучшего, чем O(2^n). Многие простые алгоритмы удовлетворяют этому требованию, но вы можете получить дополнительную оценку за реализацию одного из приведенных в ответах.   -  person hammar    schedule 08.05.2011
comment
Вы уверены, что не ошиблись с O(n * n) ? Если тогда у вас есть 1) алгоритм Карацубы, который работает за O (n ^ (log3 / log2)) и 2) методы БПФ за O (n log n) (технически это O (n * log ^ * n)). Проще всего закодировать Карацубу.   -  person Alexandre C.    schedule 08.05.2011
comment
Ошибка в постановке задачи. Я уже написал учителю, спасибо.   -  person andandandand    schedule 08.05.2011

Ответы (2)


arrow_upward
2
arrow_downward

алгоритм Шёнхаге-Штрассена — один из самых быстрых известных алгоритмов умножения. Это занимает O(n log n log log n) времени.

алгоритм Фюрера – это самый быстрый из известных алгоритмов умножения больших чисел, который требует O (n*log n * 2O(log*n)) раз.

Я не думаю, что какой-либо алгоритм умножения может занять меньше или даже равно O (n). Это просто невозможно.

person Prasoon Saurav    schedule 08.05.2011
comment
здорово ! в 2003 году это был мой студенческий проект. Я реализовал Карацубу и БПФ над вещественными числами (не Шёнхаге, это O(n log^* n) ), что гораздо проще заставить работать, если вы не освоили алгебру. Рад видеть, что есть что-то новое в этой области. Кстати вы смешали две сложности. Шонхаге Штрассен — O(n log n log log n). Кроме того, Fürer не совсем O (n log n), это O (n log n 2 ^ (log ^ * n)), согласно Википедии. - person Alexandre C.; 08.05.2011

arrow_upward
1
arrow_downward

Взгляните на алгоритм Карацубы. Он включает в себя этап рекурсии, который можно легко смоделировать с помощью принципа «разделяй и властвуй».

person Mihai Oprea    schedule 08.05.2011