Почему алгоритм умножения линейного времени Кнута не «рассчитывает»?

13

На странице википедии об алгоритмах умножения упоминается интересная работа Дональда Кнута . По сути, это включает в себя объединение умножения с преобразованием Фурье с предварительно вычисленной таблицей умножений логарифмического размера. Это бежит в линейном времени.

Статья действует так, будто этот алгоритм почему-то не считается «истинным» алгоритмом умножения. Что еще более важно, это открытый вопрос, может ли умножение быть выполнено в одно и то же O(n lg n)время!

Какие детали этого алгоритма лишают его права считаться «истинным» алгоритмом умножения?

Мои догадки:

  • Предварительный расчет таблицы занимает больше, чем линейное время. С другой стороны, это все еще можно сделать n lg nвовремя, так что это может показаться впечатляющим.
  • Случайный доступ как-то не разрешен. Но тогда почему другие алгоритмы могут использовать такие вещи, как хеш-таблицы и указатели?
  • Это как-то неправильно масштабируется, когда вы увеличиваете размер слова машины, например, если у вас есть 256-битный компьютер, который выполняет 256-битное умножение в одной инструкции, тогда нет смысла в этом алгоритме, пока у вас не будет более 2 ^ 256 элементов. С другой стороны, мы беспокоимся об обратном аккерманновском множителе в объединении-поиске.
  • «Есть ли линейный алгоритм умножения времени?» Вопрос тайно с точки зрения какой-то более слабой машины, но на это только намекают.
Крейг Гидни
источник
Это может быть актуально: en.wikipedia.org/wiki/Transdichotomous_model
R .. GitHub ОСТАНОВИТЕ, ПОМОГАЕТ ЛЬДУ

Ответы:

16

О(журналN)NО(NжурналNжурналжурналN)

ССΩ(NжурналN)Ω(NжурналN)

Для обсуждения «правильной» модели для практического умножения больших целых чисел, посмотрите недавнюю статью Фюрера . Он пришел к выводу в пользу «практического» алгоритма Шёнхаге – Штрассена (их два, а другой обладает лучшей битовой сложностью, но на практике работает хуже; Фюрер решает эту проблему в статье).

Юваль Фильмус
источник
2
Благодарю за разъяснение. У меня нет копии TAOCP, поэтому все, что мне нужно было сделать, это то, что было в статье в вики (я вижу, вы уже отредактировали ее, чтобы исправить проблему).
Крейг Гидни,