Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Поток Научпоп доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 64
Ну вообще-то есть алгоритм О(1). Правда его бычно для малых чисел используют, но в теории ничто не мешает его использовать и для любого конечного числа чисел. Таблица умножения.
Тут явно не мешает уточнение формулировок. Всё же речь идёт о манипуляциях с цифрами в позиционных системах исчислений.
Для сравнения - умножению и делению чисел записанных римскими цифрами раньше в университетах именитые учёные (буквально - я не помню, вроде Фибоначи тот же) учились в течении лет. А в логарифмическом масштабе (оно же - экпоненциальная или “научная” нотация) умножение и деление - это одно действие сложения.
Так что чётче надо задачу формулировать!
в логарифмическом масштабе (оно же - экпоненциальная или “научная” нотация)
Научная нотация - это совсем другое
Таблица умножения.
Так любую NP-полную задачу можно свести к O(1). Достаточно простого советского справочника с ответами
Научная нотация - это совсем другое
Ну не совсем-совсем. Потому и в кавычках. Намёк на float - в котором всё и считают. Во многом потому что перемножение флоатов быстрее целых (aka с фиксированной точкой).
Достаточно простого советского …
Дело не в этом. А в том, что просто “задача перемножения чисел” в математике вообще как таковая не не то что не решается, а не ставится. Просто за ненадобностью (результат просто есть по определению операции - фактически та же таблица). Ставится задача поиска, например, десятичной записи произведения, зная десятичную запись множителей. Но это - значительно более узкая задача.
перемножение флоатов быстрее целых
Откуда вы это взяли?
Намёк на float - в котором всё и считают. Во многом потому что перемножение флоатов быстрее целых (aka с фиксированной точкой).
Перемножение реализуется аппаратно, то есть это всё одна инструкция (в современных процессорах - от 0.5 до 3 тактов).
"перемножение флоатов быстрее целых"
Но это не точно
Сдаётся мне, если число растёт, а разрядность (размер машинного слова) — нет (это очень реалистичное допущение), lookup перестаёт быть O(1) (индекс надо делить), а с ним и алгоритм.
Забавно, что вы называете здесь именно Фибоначчи: именно Леонардо Пизанский (его настоящее имя) привёз в Италию арабские цифры вместо римских. Написал об этом несколько книг-учебников, которые знакомили простых торговцев с арифметикой в десятичной системе счисления.
Леонардо был в своём проекте настолько успешен, что сейчас про эту его деятельность никто и не помнит и не знает :)
Проблема таблицы умножения, что трудоёмкость по памяти O(n²), причём n - не длина чисел в битах, а максимально возможное число.
Ну и что? Временная сложность то всё равно O(1). В теории да, но на практике доступ к памяти не является константой, а зависит от объёма памяти.
Для сравнения - умножению и делению чисел записанных римскими цифрами раньше в университетах именитые учёные (буквально - я не помню, вроде Фибоначи тот же) учились в течении лет.
Миф. Настолько устойчивый, что даже П. Александров в своей энциклопедии математики его затронул.
Человек перемножает числа, а записывает цифры. Вы запоминаете, что шестью семь — сорок два. А потом пишете или 6 × 7=4 2, или VI × VII = LX II.
Другое дело, что целых положительных чисел у римлян было мало, всего лишь несколько тысяч.
Вещей было мало, а для именованных величин (деньги, расстояние, численность войск и т.п.) были соответствующие единицы измерения.
Вы путаете таблицу умножения с алгоритмами. Сможете также “просто”, не переходя даже в уме на арабские цифры (т.е. думать число XCIII как 93 - нельзя! Это именно XCIII) разделить CXLIV на VI? Или LVII * XXIII. Или будете зубрить таблицу умножения до 4-х тысяч?
Число девяносто три является числом независимо от того, как вы его записали. Хоть кучу палочек выложили на стол. Я не могу в уме перейти на арабские цифры или какие-то ещё. При устном счёте некоторые (емнип, эйдетиками их зовут) представляют процесс счёта визуально, как будто пишут на бумаге, но я таким "читерством" не занимаюсь. :)
Если вы хотите именно алгоритм, т.е. оперирование знаками на бумаге, то я специально скобочками показывал позиции чисел в римской системе записи. Она не односимвольная, но позиционная. Всё ровно тоже самое.
Вопрос привычки и навыка. Вначале будете как первоклашка морщить лоб и шевелить губами. 😊 Потом пойдёт дело на лад.
Можно даже запрограммировать работу со строками. Так даже будет, наверное, проще понять.
Другое дело, что возможно, в основе римской системы записи всё же лежит пятитеричная система счисления. И ещё более технично считать в ней. Не проверял.
Я не могу в уме перейти на арабские цифры или какие-то ещё.
Вы именно так и делаете. Человек принципиально не може представлять числа больше 5-9 (некоторые гениии до 20) как абстрактное количестово (например тех же палочек). “1-два-три-много” , как говориться. Так что вычичсления с числами больше 20 - выполняются исключительно в символьмо виде - хоть на бумаге, хоть в уме. Или тупо заучиваются как таблица умножения (с “дополненниями”: все мы просто выучили что 15*3 = 75).
Можно даже запрограммировать работу со строками. Так даже будет, наверное, проще понять.
Никогда не интересовались как работает Вольфрам? Безо всяких нейросетей же был сделан! Чисто на строках и алгоритмах.
Другое дело, что возможно, в основе римской системы записи всё же лежит пятитеричная система счисления.
В её основе лежит стихийная устная система с нерегулярной разрядностью. То что мы сейчас называем римскими цифрами - это уж довольно “причёсаная” система. Чтобы оценить оригинальню системы можете посмотреть францзкие числительные, где 98 - это “четыре-по-двацыть-и-идесять-и-восем”. Или “без двух сто”. Римские цифры - это просто сокращённая запись таких выражений, где 4 - это “без-одного-пять”.
Цифры — это знаки. Я не эйдетик, чтобы посчитать в уме, бумагу и руку, пишущую знаки, не представляю.
"Пять" — это имя математического объекта, обладающего определёнными свойствами. А вот 5 или V, или как у шумеров, — это знак.
Ну напишите вы "по школьному" I_V - это будет один сложный символ, обозначающий число четыре.
Никаких проблем у римлян со счётом не было, среди тех, конечно, кто счёту учился. И римская запись поразрядному счёту в столбик не непреодолимое препятствие.
Старофранцузские числительные это отдельный прикол, да. Но нет ли тут подмены понятий: сами числа записывались какими знаками и по какой системе? Мы же не складываем строки "одиннадцать" и "пятнадцать".
А при чём тут нейросети были упомянуты, не уловил, ну да и ладно. :)
del
Новый алгоритм работает за время O(n × log n).
Был же уже алгоритм FFT с таким же временем работы и похожий на него NTT.
Как будто в статье не хватает каких-то деталей.
У них битовая сложность не n log n. Если вы хотите применять классический nlogn FFT Кули-Тьюки для умножения чисел (вычислили на комплексных корнях -> перемножили -> проинтерполировали), то вместе с n будет расти и точность, требуемая от этих преобразований, уже n log n не получается.
Если на основе NTT, то есть видимо Shonhage-Strassen, та же проблема: для числа длины n нужно поле хотя бы из n элементов, мультипликативная группа, при вычислении на которой из цифр длины О(1) получаются уже значения длины О(log n)
Там фактически O(n log n log log n). Ибо при сильно больших n числа не помещаются в машинное слово и там уже длинная арифметика внутри длинной арифметики вылезает.
А где и для чего практически используются числа с сотнями десятичных знаков?
очень крутая статья, прям каеф
В то же время математики не знают, можно ли некоммутативно перемножить две матрицы 3х3 быстрее, чем за 23 произведения (алгоритм с 23 произведениями известен ещё с 1976). Казалось бы, всего-то 27 значений, не сотни, не тысячи, но ответа нет...
Вспомогательные произведения
В алгоритме с 23 умножениями сначала вычисляются 23 вспомогательных произведения (обозначим их (P_1, \dots, P_{23})). Для примера вот первые два:
А также несколько вспомогательных произведений, участвующих в вычислении (c_{11}):
Вычисление результата
Результирующий элемент (c_{11}) (верхний левый угол матрицы (C = A \cdot B)) выражается через найденные произведения следующим образом:
Аналогично вычисляются и остальные 8 элементов матрицы.
Всё так, различных (неэквивалентных) некоммутативных алгоритмов с 23 умножениями огромное множество (как минимум более 70 тысяч). А вот возможен ли хотя бы один некоммутативный алгоритм с 22 умножениями пока никто не знает. При этом для случае 2x2 с 7 умножениями (алгоритм Штрассена) абсолютно все алгоритмы эквивалентны друг другу, то есть он такой один уникальный.
В коммутативном случае (когда в линейных комбинациях произведений участвуют элементы матриц A и B) известен алгоритм с 21 произведением, но такие алгоритмы нельзя использовать для рекурсивного блочного умножения, а потому исследователей интересуют именно некоммутативные алгоритмы.
А я, на всякий случай, напомню, что курс школьной математики для разных континентов разный. Включая таки мелочи как раскрытие скобок, операции с дробями и решение систем линейных уравнений. Математика многогранна. И умножать можно вообще не зная таблицы умножения. Чисто на сложении.
процессор же просто сдвигает все биты первого числа несколько раз и складывает получающиеся числа если во втором числе включен нужный бит. Сплошные сдвиги и сложения, никаких умножений, причём сдвиги на 32 и на 64 позиции процессор делает одновременно (параллельно) на аппаратном уровне, и затем сложение тоже делает частично параллельно на аппаратном уровне, человек так на листочке не умеет,
при этом Дипсик настаивает что алгоритм Карацубы таки выгоден для больших чисел: "Оптимальный диапазон для Карацубы обычно лежит в области от 1000 до 10000 бит"
причём сдвиги на 32 и на 64 позиции процессор делает одновременно (параллельно) на аппаратном уровне
Надо пояснить, что тут речь не о параллелизме в привычном программисту смысле. Речь об электрической цепи с большим ветвлением и с маленькой длиной - для того, чтобы напряжение быстрее распространялось по ней, и чтобы она могла работать на бóльших частотах.
Вот-вот, тоже сразу подумал, что умножение в двоичной арифметике - не то же самое, что и в десятичной.
Или вот в логарифмическом представлении вообще умножение чисел сводится к сложению их логарифмов:
32 × 64 = ?
log2 (32×64) = log2 (32) + log2 (64) = 5 + 6 = 11 = log2 (2^11) = log2 (2048)
32×64 = 2048
Речь в статье, очевидно, ведётся про decimal
Параллельно складывать 64 числа не так просто как кажется, даже на аппаратном уровне. Первые процессоры совершенно точно умножали итеративно.
Насколько я знаю, первой оптимизацией аппаратного умножения стал перевод одного из множителей в систему счисления по основанию 4 с базой {-1, 0, 1, 2}. Для умножения в этой системе счисления достаточно только сдвигов и смены знака, но это несколько отличается от вашего описания.
Второй оптимизацией стало использование таблицы квадратов. И она работает настолько хорошо, что складывать кучу разрядов параллельно становится просто глупо. Только вот для 64х разрядов таблицу квадратов не составить, так что там совершенно точно используется комбинация разных методов.
процессор же просто сдвигает все биты первого числа несколько раз и складывает получающиеся числа если во втором числе включен нужный бит. Сплошные сдвиги и сложения, никаких умножений
Это да, и как раз потому, что в одном умножении много сложений, операция умножения медленнее/сложнее для реализации, чем операция сложения. Но можно упростить описанным методом. Хотя, конечно, это больше имеет смысл для целых произвольной точности, либо когда числа не влезают в регистры.
А я вот слышал про китайский метод умножения
Китайский (или графический) метод умножения — это визуальный способ перемножения чисел с помощью линий. Он позволяет находить результат без использования классической таблицы умножения, заменяя её подсчетом точек пересечения
У него О(от чего?) получается?
Есть относительно простой и быстрый алгоритм за O(n log n log log n) (но это не точно). И работает он быстрее карацубы даже на совсем небольших числах. Так что это не галактический алгоритм.
Работает это через быстрое преобразование Фурье. Есть варианты и на целочисленном аналоге. Пребразуйте каждое число по отдельности, перемножте значения покомпонентно, преобразуйте назад, сделайте переносы.
И идея простая: представим каждое число в виде полинома - цифры будут коэффициентами.
Вот было у нас 
, заменим 10 на x, получим
Потом можно перемножить 2 полинома и подставить x=10. Подстановка очень проста - просто берем коэффициенты и записываем их в виде цифр. Только некоторые могут быть больше 10, и надо сделать переносы с меньших разрядов.
А произведение полиномов это известная задача, решающаяся FFT. Потому что прямое преобразование - это вычисление значений полинома в точках-корнях-из-единицы. Обратное преобразование по значениям в точках восстанавливает полином. Так что произведение полиномов просто делается в пространстве спектра - ведь значения в точках тупо перемножаются покомпонентно.
На практике, пока количество цифр поменьше чем 2^64/81 можно игнорировать log log n в оценке сложности, потому что числа в вычислениях помещаются в процессорное слово.
А почему сложность не 9*n умножений + n сложений? Ведь уникальных цифр 9, дальше только сдвиг на разряд и слодение. Можно закешировать все 9 вариантов и подставлять когда нужно.
n сложений и дают этот самый медленный O(n^2). Ведь для сложения чисел из n цифр надо O(n) операций. Ваши кеширования особо не помогают в этом наивном умножении столбиком.
https://github.com/drobotun/bigint
Арифметика длинных чисел на c++, реализовано: умножение "в столбик", метод Карацубы и FFT, деление "в столбик" и метод Ньютона-Рафсона, а также сложение, вычитание, логические операции, возведение в степень и взятие корня. Числа представлены в виде массива байт, с основанием 256.
Раз уж вы ссылку запостили, оставлю отзыв.
У вас там на каждый чих аллокация, что весьма плохо для производительности. Особенно в fft. Не надо выделять каждый раз массивы под четные/нечетные элементы. Можно передавать индекс первого элемента и шаг, например. А можно вообще на месте делать преобразование, без выделения двух массивов для входа и выхода, да еще и весь доступ к памяти будет последовательный. Этот алгоритм даже на вики описан.
Умножение/деление на короткое должно быть отдельной функцией, особенно *=. У вас там вообще даже += все число переаллоцирует, хотя это совсем не обязательно.
Gcd гораздо быстрее работает не через длинное деление, а с помощью деления на 2 и вычитания - тоже на википедии есть описание алгоритма. При чем и деление и вычитание можно делать на месте, вообще без аллокаций.
Базу стоит брать не 256, а 2^32 хотя бы. Все будет почти в 4 раза быстрее и переполнений в long long вызывать не должно, если аккуратно писать.
Как упраждение - неплохо. Но, вообще, на практике гораздо лучше использовать GMP. Оно сильно лучше вылизано. Там и оптимизации под конкретную архитектуру, и SIMD, и лучшие алгоритмы. Можно быстренько сделать c++ обертку с перегруженными арифметическими операторами, или взять любую из кучи готовых.
А я в голове считаю десятками или сотнями: 12*34 = 34*12 = 34*10 + 34*2.
Вначале перевернул чтобы меньше считать.
С детства не заладилось с таблицей умножения и умножением в столбик, хотя систему понимаю и умею пользоваться, ну не нравится, нудный и единообразный способ. И помнить всю таблицу не обязательно, можно разложить ее на более простые вычисления.
Использую гибридный вычисления, как наподобие написано в статье. Или умножаю большие числа и отнимаю поменьше, или разделяя на более простые группы, могу выдумать еще варианты на лету и разложишь сложные числа или расчеты.
Поэтому когда смотрели еще в детстве учителя они не понимали как я вычислял, если видели черновик. Оказывается я не одинок) Чтоб люблю упрощать и делать жизнь проще, а не создавать новые проблемы. И что есть 1000 и 1 решение одной проблемы и можно выбрать лучшее или более подходящее. А не только идти прямой дорогой как написано в книжке))
В системах счисления с избыточностью и неограниченным параллелизмом умножение выполняется за log(N) шагов.
Статья без упоминания этого факта, мягко говоря, не полна.
N - это само число, да? Значит этот log(N) в терминах статьи на самом деле O(N). Ибо все эти количества шагов считают от количества бит во входе, а не от значения (там вообще может быть много разных значений), так что N - это обычно длина числа.
Ну, с неограниченным параллелизмом-то и не мудрено. Да, задача умножения - черезвучайно параллельна. Даже в обычных системах счисления, и без избыточности, тоже за O(N) все делается весьма просто, ведь надо только переносы сделать вконце, что делается за O(N).
Но неограниченный параллелизм в Computer Science, это как нефальсифицируемая теория в физике. Обычно тривиально, практической пользы не несет, теоретически не интересно.
Ну, если параллелизм совсем не ограничен, то можно и за O(1) сделать, правда практического смысла тут будет ещё меньше.
Нет, N здесь тоже, как и в статье - длина числа.
В стандартной позиционной системе счисления операция сложения выполняется за O(N), т.к. бит переноса может распространяться на любое расстояние, вплоть до N, а значит параллельное сложение отдельных знаков слагаемых ничего не дает.
А в системах с избыточностью распространение переноса можно ограничить константой (есть системы, где эта константа равна 1), соответственно, сложение можно распараллелить и выполнить за один шаг, т.е. получить O(1).
То же касается и умножения числа длины N на число длины 1. В системах с избыточностью оно тоже выполняется за O(1). В обычной позиционной системе это делается за O(N), без вариантов.
В комментариях выше упоминалось, что процессорах умножение и сложение целых чисел выполняется довольно хитро и гораздо быстрее, по числу шагов, чем Карацуба. Потому что под капотом там как раз избыточные системы, только с ограниченной длиной чисел и с ограниченным параллелизмом.
Нет, N здесь тоже, как и в статье - длина числа.
Если это правда, то это уже не настолько очевидное решение. На статью не влияет, потому что бесконечный параллелизм изучаемому предмету параллелен и с ним не особо пересекается.
А в системах с избыточностью распространение переноса можно ограничить константой (есть системы, где эта константа равна 1), соответственно, сложение можно распараллелить и выполнить за один шаг, т.е. получить O(1).
Мне кажется, вы ошибаетесь. Может быть, сложение двух "нормальных" чисел обладает таким свойством, когда входные числа без (или с ограниченной) избыточностью. И потом лишняя избыточность съест переносы и не даст им прыгать по всему числу. Но в процессе умножении складываются числа, которые сами результаты умножений на цифру и других сложений, поэтому они сами уже эту избыточность могут использовать до предела.
что процессорах умножение и сложение целых чисел выполняется довольно хитро и гораздо быстрее, по числу шагов, чем Карацуба. Потому что под капотом там как раз избыточные системы,
Нет, потому что там под капотом высокий параллелизм. Не бесконечный, ибо числа ограничены.
В любом случае, рассматривать бесконечный параллелизм - небогоугодное занятие.
Нет, не ошибаюсь. Это результат, доказанный для сложения чисел, записанных в любой из избыточных форм, а не только “нормальных”. Под рукой ссылок на работы не нашлось, но если интересно, могу поискать.
Пошел почитал. Признаю, что вы были правы. Действительно все переносы локальны.
Суть идеи в том, чтобы делать перевнтивные переносы. Даже если сумма в этом разряде помещается в избыточность, надо все-равно сделать перенос заранее, чтобы пришедший справа перенос поместился и не пошел дальше. При этом число будет длинее, чем могло бы быть с учетом избыточности. Не самая интуитивная идея.
Эта хитрость, действительно, делает алгоритм сложения гораздо лучше распаралелливаемым.
Вот только для этого алгоритма вам все еще надо N^2 потоков что ставит полный крест на любом практическом применении. А с теоретической точки зрения бесконечная параллельность слишком спецефична.
Все еще не согласен, что без упоминания этого алгоритма статья не полна.
Не обязательно N^2 потоков. То, что можно сделать параллельно, можно сделать и последовательно. А значит можно использовать столько АЛУ-ядер, сколько есть. В отличие от стандартной позиционной системы, в которой складывать длинные числа вы будете на одном ядре, даже если у вас рядом таких ядер миллион простаивает.
Другими словами, неограниченный параллелизм здесь - не требование, а возможность.
Другое дело, что существующий подход к распараллеливанию вычислений длинной арифметикой не очень интересуется, и на то есть свои причины. И тут я с вами могу только согласиться: пока эти модели от широкой практики (по крайней мере, по моим данным) довольно далеки.
Но статья-то называется “Математики до сих пор не уверены, как быстрее всего перемножать числа”. А системы с избыточностью имеют прямое отношение к этой неуверенности: доказано, что это теоретически быстрее изолированно на сложении/умножении, но не доказано, что этот подход имеет преимущество перед другими подходами к распараллеливанию целевых алгоритмов (для которых арифметика - это не цель, а средство).
а все-таки, где про это почитать? Там вроде должны быть физические ограничения на логические элементы - чтобы сделать сложение/умножение за O(1), надо, чтобы NAND элементы имели O(n) входов и выходов, что линейно увеличивает паразитную ёмкость, что замедляет распространение сигнала.
Для целых чисел что-то второй день не могу нагуглить, имя автора забыл :( Там доказывалось, что достаточно двух-трех (в зависимости от четности основания, но только для оснований больше 2) избыточных цифр. Я как-то доказывал (но не публиковал, т.к. слишком незначительное улучшение по сравнению с упомянутой работой) что достаточно двух дополнительных цифр для любого основания больше 2, чтобы перенос не распространялся дальше, чем на 1 разряд.
А для действительных вот: https://keldysh.ru/abrau/2020/theses/54.pdf
Особая физика тут не нужна.
Вспомнил, Frougny. https://www.maths.tcd.ie/EMIS/journals/JIS/VOL16/Frougny/frougny3.pdf
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Математики до сих пор не уверены, как быстрее всего перемножать числа