Как стать автором
Обновить

Комментарии 28

Спасибо за прекрасно разобранную тему с крутыми примерами. Давно тут не было такого годного контента

Отличная статья... хороший слог и хорошая подача :)))

Отличное изложение! Обязательно продолжайте в том же духе. Цветовое выделение в формулах — вообще бомба, обычно что-то мало-мальски сложнее дискриминанта квадратного уравнения в таких статьях просто пробегаешь глазами и всё, тут же всё просто и понятно.


За рамками статьи остался алгоритм Фюрера и его варианты, а также опубликованный в 2020-м году [6] алгоритм с заявленной сложностью O(N\log N); если эта статья окажется востребована, возможно, когда-нибудь мы разберём и их.

Очень интересно, просим

image

Я согласен с другими отлично идёте

Разборчивое объяснение. До этого не мог найти ничего подобного. Везде все поверхностно, а здесь все конкретно изложено. Спасибо за ваш вклад. Побольше бы таких статей.

Я что ли один сюда зашел за способом быстрее и удобнее перемножать числа в уме?

А я знаю как быстро в уме проверить или число на 3 делится :) интересно?

Hidden text

"Суммируем" число, и если результат делится на 3, то само число делится на 3.

Например,

Число 111. 1 + 1 + 1 = 3. 3 делится на 3, значит и 111 делится на 3.

  1. 2 + 4 + 3 = 9. 9 делится на 3, значит 243 тоже делится на 3.

Давно известный прием. Интереснее вспомнить его обоснование

Он легко обосновывается через арифметику по модулю! Берем число, скажем, 123. Нам нужно выяснить, равен ли нулю его остаток от деления на три. Раскладываем по десятичным разрядам и пользуемся свойством, что 10 \equiv 1 \mod 3:

1\cdot 10^2 + 2\cdot 10 + 3 \equiv 1\cdot 1^2+2\cdot 1+3 \equiv 1+2+3\mod 3

Ну для начала потренеруйтесь fft в уме делать.

спасибо, не знал о этих методах.

недавно ребёнку пытался расписать другие методы умножения длинных произвольных чисел на такие же числа, но свалился в логарифмы для быстрой оценки какое будет число и потерялся.

т.е. если необходимо примерно вычислить быстро - через перевод в примерный логарифм, суммируешь и берёшь обратно переводишь в число.

Вот кстати если перемножать большие числа (например 10^100) в тот же столбик например то легко заметить что мы это преобразавываем в сумму произведения каждого разряда на множитель (т.е. 1 множитель разбиваем на количество цифр на листике) и легко доказать что в десятичной системе у нас будет не более 10 вариантов которые надо сложить. Т.е. предположим сложение это 1 операция, сложений у нас N, и до 10 довольно простых операций умножения (все варианты которого можно получить за 10 сложений). Сложность такого умножения выходит 10 (получение слогаемых) + N * (1 операцию выборки и 1 операцию сложения + 1 операцию сдвига на разряды) = 3N + 10.

Мне почему то кажется что при больших N можно получить сложность даже ниже чем O(N log N)

В двоичной системе счисления ещё проще, там всего 2 варианта умножения, которое делать то и не нужно.

Но вы забываете, что сложение за константу больших чисел с бумажки, это далеко не константа для железа.

Да, согласен что в этом то весь и прикол, статья написано вполне отлично, просто там про сложение написано:

По сравнению с умножениями это быстрая операция, не заслуживающая особого внимания — как и два лишних сложения в скобках

И вот для 100-значных чисел нам надо 10 сложений для расчёта таблицы и 100 условных сложений с выборкой, итого 110 операций.

А в двоичной кстати по такой же логике (для 1000 битного числа, 100 значного десятичного) - надо 0 для расчета таблицы, и примерно 500 условных сложений (предположим что единица у нас в половине случаев).

А дьявол как известно кроется в деталях как раз. На больших числах проблема как раз не умножения, а вообще операции над такими большими числами, и трансформации больших чисел в массивы конечной размерности. Хотя сложение по частям это достаточно тривиальная задача, а использование "таблицы" позволяет вообще уйти от умножения, может и получится в итоге меньше чем O(N^2), тут уже больше как раз зависит сложности реализации длинного сложения, конвертации систем, количества доступной памяти для "таблицы"

Не совсем понял. Чтобы получить произведение каждого разряда на множитель, вам уже нужно O(N^2)операций. В любом случае нужно умножить каждый разряд одного числа на каждый разряд другого.

Имелось ввиду что вариантов умножения всего 10, их можно запомнить, а затем использовать значение из таблицы, домножая/сдвигая на нужное число разрядов.

Речь о том, что количество этих "использований таблицы" будет квадратичным.

Не согласен.

123×802

Строим таблицу 123*0, 123*1, ..., 123*9. При этом при расчетах умножение можно заменить за сложение.

Результат выглядит тогда так

(table[8] << 2) + (table[0] << 1) + (table[2] << 0)

Сдвиг тут десятичный. Таблица была использована logN раз.

В двоичной системе счисления и таблица не нужна совсем. Сдвигаем один множитель вправо, другой влево на каждой итерации, добавляем к аккумулятору второй множитель, если вправо вытолкнули единицу.

Но это не подходит для длинной арифметики, потому что сдвиги и сложения будут не за константу.

Занимательный факт из алгебры: если в мультипликативной группе n элементов, то любой её элемент в степени n равен единице.

с каких это пор https://ru.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел) является занимательным фактом?

Вы не согласны с тем, что это факт, или с тем, что он занимательный?)

согласен. действительно - факт, и действительно - занимательный))

статья, кстати говоря, очень хорошая, но - где-то это я недавно слышал...а-а, на канале Савватеева. там какой-то талантливый школьник рассказывал точь-в-точь тоже самое.

(сам школьник имеет шанс далеко пойти, если попадет к нужным людям, и его не испортят торгаши), но остается вопрос - чья же это оригинальная идея? (или она уже, давно, не оригаинальная?)

Ну, сами исследования все давно опубликованы, моя оригинальная тут только подача. Хотел написать с тех пор, как статья про алгоритм за O(N\log N)вышла.

А какой алгоритм используется в блоках умножения процессоров?

// Преобразование Фурье — построение в первую очередь теоретическое; Жозеф Фурье открыл его задолго до появления компьютеров. //

Не может быть. Неужели и Лев Толстой набивал свои опусы не на лэптопе Apple?! А я думал, Ньютон выводил движение планет в Maple.

П.С. Ряды Фурье известны как минимум с Гиппарха, III век до нашей эры. Фурье (лишь) обосновал их применение к решению ряда краевых задач уравнений матфизики. Об Эйлере и не говорю.

А можно ссылку на Гиппарха? Интересно почитать

К сожалению, о Гиппархе можно судить по косвенным ошмёткам и арабским переводам, всё остальное сгорело в Александрийской библиотеке во время тогдашней спецоперации. Но идея раскладывать гелиоцентрические орбиты (именно гелио-) планет в ряды независимых круговых движений (эпициклы) быть может, была даже и до него.

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории