Обсуждение:Алгоритм Карацубы

Первый в истории вычислений быстрый метод

Предлагаю выкинуть это утверждение из статьи, так как его достоверность вызывает у меня большие сомнения. Оно не согласуется с табличкой, приведённой в en:Timeline of algorithms — говорят, что Гаусс знал о FFT еще в 1805 году (а Cooley & Tukey его лишь переоткрыли в 1965). FFT — это пример divide & conquer алгоритма, которые, в частности, подразумевают здесь, говоря о быстрых алгоритмах, как я понимаю.

http://www.ccas.ru/personal/karatsuba/alg.htm не считаю авторитетным источником, так как он не независимый (Е. А. Карацуба связана родством с изобретателем алгоритма). -- X7q 15:51, 19 января 2010 (UTC)

• вот еще АИ [1], указано, что Этим открылось новое направление в проблеме построения быстрых алгоритмов. - выбирайте какая формулировка больше нравится. S.J. 17:13, 19 января 2010 (UTC)

  Ну хотя бы так стоит написать, а не утверждать что это первый в истории быстрый метод. -- X7q 09:02, 20 января 2010 (UTC)

Мало ли что написано в en:Timeline of algorithms! Вы специалист по быстрым алгоритмам? Факт, что действительно есть статья трёх американских инженеров (не математиков = M.T. HEIDEMAN, D. H. JOHNSON, C. S. BURRUS), которые утверждали, что Гаусс знал FFT, не оценивая пр этом сложность вычисления, а Кули + Ко переоткрыли метод (на самом деле, кроме Кули была ещё и другая независимая компания разработавшая в то же время FFT) . Советую прочесть эту статью, а также оригинал Гаусса, Вы убедитесь, что это "фальшивка". У Гаусса нет FFT. Да и Хайдеман, Буррус и Джонсон фактически пишут, что у Гаусса есть два тригонометричесикх соотношения, из которых МОЖНО ВЫВЕСТИ FFT! Правильно! Также, как из обычного метода умножения можно вывести быстрое, так и из некоторых других соотношений (и не только Гаусса) можно вывести FFT, надо только НАЙТИ ИДЕЮ, как это сделать! Гаусс этого не делал и такую идею не находил! Возможно, не имея компьютера, он не нуждался в FFT. Не суть важно. Важно, почему эти Хайдеман, Буррус и Джонсон написали такую статью. На этот вопрос легко ответить. Дело в том, что из быстрого умножения легко получить FFT, это просто обощение идеи Карацубы, не более. И тогда получается, что русский математик сделал выдающееся открытие в математике. А есть люди, которые очень не хотят признания этого абсолютно верного факта. Просьба не выкидывать этого утверждения на основе не признанных специалистами утверждений о Гауссе, фон Нёймане и др., которые якобы первые сделали быстрые алгоритмы --- это чушь, замешанная на политике, и не имеющая отношения к математике!Issykkul 11:51, 1 февраля 2010 (UTC)

А, кстати, что именно вы понимаете под быстрыми алгоритмами? Скажем, метод Ньютона - это быстрый алгоритм или нет? А сортировка слиянием? Или симплекс-метод? -- X7q 12:55, 1 февраля 2010 (UTC)

Про политику - по моему, политикой занимаетесь вы. Вы можете привести какой-нибудь АИ, где написано, что Карацуба изобрел первый в истории быстрый метод, и притом написанный не русским автором? -- X7q 12:57, 1 февраля 2010 (UTC)

И про FFT — а что скажите про Danielson and Lanczos (1942)? Весьма уважаемая книжка «Numerical Recipes» утверждает, что они открыли как выразить DFT длины $N$ за $O(N)$ времени в виде суммы двух DFT длины $N/2$. Это фактически уже и есть FFT, осталось лишь тривиально добавить рекурсию. — X7q 13:28, 1 февраля 2010 (UTC)

О чём спор? Конечно, Карацуба --- это первый быстрый алгоритм, Колмогоров первый поставил в принципе задачу о сложности вычисления. Метод Ньютона становится быстрым, если в нём используется быстрое умножение. Есть и ещё такие методы, например, метод Гаусса АГС. С быстрым умножением этот сверхсходящийся процесс становится быстрым. Что касается сортировки --- это из другой области. Что касается FFT, почему бы Вам не узнать мнение Cooley and Tukey? Компетентно ответить мог бы Volker Strassen, и Martin Fürer, он вроде сейчас сделал самое асимптотически быстрое умножение. Насчёт того, что тривиально добавить рекурсию --- бросьте дурака валять. Алгоритм и определяется тем, как эта рекурсия делается. И нечего ссылатья на трёх нематематиков, опубликовавших свой "опус" по Гауссу в нематематическом журнале без рецензии математика. (M. T. Heideman, D. H. Johnson, and C. S. Burrus, "Gauss and the history o f the FFT," IEEE Acoustics, Speech, and Signal Processing Magazine, vol. 1, pp. 14-21, October 1984. also in Archive for History of Exact Sciences, 1985. ) Никакой математик не захочет мараться об эту чушь.

Что касается Вашей аппеляции к нерусским авторам, которые должны подтвердить, что именно Карацуба сделал первый какой-то результат --- я что-то не замечал, чтобы кого-либо из американских авторов интересовало бы мнение на эту тему русских авторов. Здесь в Вики много чего написано неверно по поводу авторства идей. Но Вики-концепция" такая, кто-то пишет статью --- пусть, это его мнение. Вы хотите написать, что Даниэльсон первый придумал быстрый метод --- напишите статью про Даниэльсона, а не правьте статью про умножение Карацубы. Тем более, что Вы явно тенденциозны.83.149.209.253 14:17, 1 февраля 2010 (UTC)

Да я как раз просто хочу того же, что и Вы — чтобы здесь в Вики не было «много чего написано неверно по поводу авторства идей». Ваше утверждение, о том что Карацуба придумал первый в истории быстрый алгоритм вызывает у меня сомнение в истинности по двум причинам: 1) у Е. А. Карацуба такая же фамилия, как и у А. А. Карацуба, поэтому делаю вывод, что она не беспристрастна в этом своём утверждении, 2) в том «опусе» утверждается про существование FFT до 1960 года.

«Опус» вполне можно считать авторитетным источником для Википедии, т.к.: Springer — весьма авторитетное издательство; журнал «Archive for History of Exact Sciences» = архив истории точных наук, рецензируемый журнал; математика — точная наука, уж кое-что рецензенты-то должны в ней понимать. Статью, согласно Google Scholar, цитируют аж 114 раз — немало.

«нечего ссылатья на трёх нематематиков» — это я даже комментировать не хочу. Вам по-моему должны быть просто стыдно делать высказывания в таком духе.

«Но Вики-концепция такая, кто-то пишет статью — пусть, это его мнение.» — неправда. Почитайте официально принятые в ВП правила — ВП:ПРОВ и ВП:НТЗ. -- X7q 15:05, 1 февраля 2010 (UTC)

Предлагаю такой компромисс - напишите, что по мнению некоторых людей/источников это был первый в истории быстрый алгоритм. -- X7q 15:08, 1 февраля 2010 (UTC)

Внимание! Этот текст подвергается вандализму со стороны пользователя Вики --- X7q!(83.149.209.253 13:43, 10 февраля 2010 (UTC))

Это не есть ВП:Вандализм. У нас просто разные мнения. А ложные обвинения в вандилизме - нарушение этикета (и, возможно, и правил) Википедии.

Я привел причины выше почему не считаю утверждение "Первый в истории вычислений быстрый метод" достоверным, поэтому его и удаляю. -- X7q 14:35, 10 февраля 2010 (UTC)

Октябрь 2010

Утверждение о том, что Гаусс знал Быстрые преобразование Фурье является фантазией и не подтверждается первоисточником (трудами Гаусса). Считаю неприемлемым ссылаться на слухи и безграмотные статьи, в том числе и безграмотные статьи в Википедии.85.140.34.84 00:12, 3 октября 2010 (UTC)

Хорошо. Другой пример - сортировку слиянием изобрели в 1945 году. Я считаю ее быстрым алгоритмом, т.к. она работает за асимптотически оптимальное время O(n log n). -- X7q 01:20, 3 октября 2010 (UTC)

Что считать быстрым алгоритмом давайте обсуждать на Обсуждение:Быстрые алгоритмы. -- X7q 01:27, 3 октября 2010 (UTC)

Ноябрь 2010

Ещё хочу добавить. У меня была беседа с американцем, вставившем в Википедию в таймтэйбл алгоритм Rарацубы не первым, а куда-то там в середине. Сначала он "прикидывался" и говорил, что вот де, алгоритм Ньютона --- быстрый. После моего возражения, что он-то быстрый, но стал таковым только после того, как Карацуба изобрёл быстрое умножение, тот выдвинул главный козырь --- статью трёх инженеров про то, что Гаусс знал FFT , а остальные его переоткрыли (не только Кули и Тюки, ещё было две независимых группы людей, в США и Германии, а идея шла от Карацубы, не от Гаусса). Так вот, на мой аргумент, что в работе Гаусса, на которые дают ссылку три автора ничего этого нет, американец согласился, что формул там нет, но утверждал, что Гаусс описал Быстрое Фурье Преобразование СЛОВАМИ (без формул) ПО ЛАТЫНИ, и поскольку мы не знаем латынь, то мы и не видим, что он сделал это первооткрытие. На самом деле, "первооткрытие" можно сделать, прочитав статью "трёх инженеров". Фактически они не утверждают, что Гаусс знал БФП. Они говорят буквально следующее, если вот такую формулу Гаусса преобразовать так-то и добавить ещё три формулы, то можно получить БФП. Можно. Можно преобразовать обычное умножение, добавить две формулы и получить быстрое умножение Карацубы --- первый быстрый алгоритм. И о чём это говорит? Если в течение 4 тысячелетий, до Карацубы, никто не сообразил, как это сделать?91.79.187.144 12:48, 20 ноября 2010 (UTC)

Кто-то убирает верное высказывание и вставляет высказывание, умаляющее значение открытия великого русского математика А.А. Карацубы (недвано умершего внезапно). В работах Гаусса нет никакого Быстрого Фурье Преобразования --- это неверное утверждение, для этого достаточно прочитать работы Гаусса (собрание его работ есть, например, в институте Математики им.Стеклова, Москва, ул.Губкина, д.8), заявление о том, что Гаусс знал FFT было сделано в безграмотной статье трёх американских инженеров (не математиков), и специалисты его отвергают. Кроме того, любые другие методы и алгоритмы становятся быстрыми только с применением быстрого умножения, умножение --- это базовая операция, если она выполняется посредством быстрого алгоритма, то и общий алгоритм --- быстрый, если нет, то НЕ быстрый. То, что в других статьях Википедии написано много неверного, сомнений нет, но это не основание коверкать верную информацию! 91.79.187.144 12:24, 20 ноября 2010 (UTC)

• Давайте перестанем ориссничать. Факты в статьях Википедии должны быть проверяемы, должны быть указаны авторитетные источники. Вы можете привести АИ в которых написано что, да, Карацуба действительно первый? Пока что я видел это в какой-то публикации Е.А.Карацубы, но я не считаю его независимым (это дочь, так что она может быть необъективна). -- X7q 18:51, 20 ноября 2010 (UTC)

Январь 2020

Привет из будущего тем, кто обсуждал этот вопрос выше. Даже если допустить, что утверждение о том, что Гаусс знал про FFT верное, я не думаю, что это является основанием умалять значимость достижения Карацубы, потому что сомнительно, что Гаусс рассматривал его как способ ускорить умножение двух чисел. Я очень сомневаюсь, что кто либо стал бы использовать его для умножения чисел «на бумаге» — это просто непрактично на тех длинах чисел, с которыми люди обычно работают, да и на en:Fast Fourier transform пишут, что он его для интерполяции использовал, а не умножения. К тому же, метод Кули — Тьюки для подсчёта быстрого преобразования Фурье был предложен в 1965 году, но использовался он, как я понимаю, для всякого рода частотного анализа. Только в 1971 году появился метод умножения Шёнхаге — Штрассена, который рассматривал возможность применения преобразования Фурье для задачи умножения двух чисел. То есть, возможность использования преобразования именно для умножения чисел достаточно долгое время не рассматривалась даже после открытия БПФ. adamant.pwn — contrib/talk 23:03, 17 января 2020 (UTC)

Октябрь 2021

Основательно поредактировал статью, навёл красоты:

• раскрасил формулы, чтобы сделать нагляднее, что куда переносится
• добавил схематическую иллюстрацию
• убрал из раздела "Примеры" информацию про скорость работы (ибо это не пример)
• поменял пример на такой, для которого показан весь процесс вычисления (ибо один шаг описывается уже в "Описании метода")
• добавил хорошую иллюстрацию примера из английской википедии

Fractalone (обс.) 14:43, 18 октября 2021 (UTC)

• К сожалению, по-моему, стало хуже, мне кажется, у меня был более понятный пример. Ваш раздел про суть метода я оставлю, а пример верну свой: да, там показан лишь один шаг, но именно в нём нужно понятно прописать суть. MBH 04:42, 14 мая 2023 (UTC)