Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 90
Вот это да, буквально вчера переписывал функцию перемножения в своём модуле, а сегодня статья. Надо было мне подождать день.
Ну вот что вы делаете, математики-волшебники? Мой гуманитарный мозг просто сгорел.
Извиняюсь, я далек от С++ но во мне затаился вопрос)) чем отличается ваше решение от банального умножения *?
«Умножение длинных чисел методом Карацубы» — 100-200 разрядов на число. Большинство языков не имеют встроенных типов для их представления.
>Большинство языков
это вы имеете ввиду shell, c, c++ и дельфи? и то, по поводу второго сейчас прибегут знатоки какого-нибудь boost или stl и расскажут нам правду.
это вы имеете ввиду shell, c, c++ и дельфи? и то, по поводу второго сейчас прибегут знатоки какого-нибудь boost или stl и расскажут нам правду.
Причем здесь «shell, c, c++ и дельфи» и «boost или stl» или вы думаете, что числа там умножаются с помощью какой-то магии? Блог называется «Алгоритмы».
я думаю, что вы не удосужились прочитать на что я отвечал: там написано, что в большнстве языков нет встроенных типов для big integers. мне кажется, что такое мнение ошибочно и я знаю, что в нескольких языках такие типы есть.
кроме того, наличие встроенного типа для болших чисел, позволяет мне сделать предположение о том, что операция умножения в таких языках происхдит именно по такому алгоритму, особенно если его знает каждый студент-байтикоперекладыватель
кроме того, наличие встроенного типа для болших чисел, позволяет мне сделать предположение о том, что операция умножения в таких языках происхдит именно по такому алгоритму, особенно если его знает каждый студент-байтикоперекладыватель
Но ведь во встроенного действительно нет: basic и его вариации, Delphi, PHP (есть не встроенная хотя поставляется с оным), с, c++, javascript. Приведите, пожалуйста, ради расширения кругозора распространенный языке где есть встроенный.
Более верно будет предположить, что адекватно было бы применять не этот алгоритм, а с помощью БПФ.
Более верно будет предположить, что адекватно было бы применять не этот алгоритм, а с помощью БПФ.
Зато я удосужился прочитать на что отвечал собеседник, которому отвечали вы.
Изначальный посыл был:
Т. е. человек не видит разницы, скажем, между простым mul и представленным алгоритмом.
Еще раз, даже если библиотеки и компилятор/интерпретатор вашего языка скрывают от вас всю сущность происходящего, это отнюдь не означает, что умножения 4 байт на 4 байта производится также, как умножение 40 байт на 40 байт.
Блог называется алгоритмы, приведенный код иллюстрирует пример реализации алгоритма. С тем же успехом, он бы мог быть написан на языке, который умеет умножать тысячи разрядов из коробки. Тут алгоритм показан, а не туториал по C++.
Изначальный посыл был:
Извиняюсь, я далек от С++ но во мне затаился вопрос)) чем отличается ваше решение от банального умножения *?
Т. е. человек не видит разницы, скажем, между простым mul и представленным алгоритмом.
Еще раз, даже если библиотеки и компилятор/интерпретатор вашего языка скрывают от вас всю сущность происходящего, это отнюдь не означает, что умножения 4 байт на 4 байта производится также, как умножение 40 байт на 40 байт.
Блог называется алгоритмы, приведенный код иллюстрирует пример реализации алгоритма. С тем же успехом, он бы мог быть написан на языке, который умеет умножать тысячи разрядов из коробки. Тут алгоритм показан, а не туториал по C++.
Плюсанул. Но… ребят, у нас этот метод рассматривался на уровне одной лабораторной работы…
Вам повезло с лабораторными и, похоже, что с обучением вообще.
А вам, похоже, не повезло с умением гуглить: вводим karatsuba multiplication c++ в Google и получаем просто килотонны кода.
1. С умением гуглить у меня все нормально — как видите алгоритм был разобран.
2. Мне нужен был не код, а алгоритм. А прочитать готовы текст куда проще, чем разбирать исходник.
3. Под «беглый поиск в google ничего путнего не дал» имелось ввиду: «Русскоязычных статей с простым и детальным изложение найти не удалось (Википедию не считаю т.к. лично для меня там материал сложный). Поэтому пришлось собирать по-частям информацию из русскоязычных и англоязычных источников.»
PS не подумайте, что огрызаюсь — просто мне показалось Вы не совсем уловили суть.
2. Мне нужен был не код, а алгоритм. А прочитать готовы текст куда проще, чем разбирать исходник.
3. Под «беглый поиск в google ничего путнего не дал» имелось ввиду: «Русскоязычных статей с простым и детальным изложение найти не удалось (Википедию не считаю т.к. лично для меня там материал сложный). Поэтому пришлось собирать по-частям информацию из русскоязычных и англоязычных источников.»
PS не подумайте, что огрызаюсь — просто мне показалось Вы не совсем уловили суть.
+1, один из вопросов на экзамене — перемножить два числа Карацубой. Достаточно несложный алгоритм. Как и деления, впрочем.
Поддерживаю, это проходят на втором курсе в рамках дисциплины «Дискретная математика» или «Теоретико-численные методы»
Формула написана и в той статье на Хабре. Вы похоже не учли мой прошлый комментарий. Статья писалась «поделиться с общественностью в доступной форме» и никак не претендует на краткость и тп.
Извиняюсь. Ошибки исправлены. Спасибо.
Извиняюсь. Ошибки исправлены. Спасибо.
Это должно быть ответом на комментарий выше.
> время выполнения которых на порядок меньше
ну это не совсем верно. точнее совсем не верно. один порядок — это 10 раз. а что бы достигнуть ускорения в 10 раз число должно быть оооочень длинным.
ну это не совсем верно. точнее совсем не верно. один порядок — это 10 раз. а что бы достигнуть ускорения в 10 раз число должно быть оооочень длинным.
Даже если в обоих числах по 100 знаков, то наивное умножение потребует 100*100 операций умножения, а сложение — 100 сложения. Это не учитывая того, что операция умножения сама по себе дольше выполняется процессором.
извините, я ещё разок вас процитирую:
> Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog23. В то время, как наивный алгоритм, умножение в столбик, требует n2 операций.
> при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.
я придираюсь к вполне конкретному слову «на порядок». я понимаю, что оно может работать и быстрее чем в 10 раз, но увы точность такого измерения надо доказать. я же просто советую использовать слово «гораздо быстрее».
> Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog23. В то время, как наивный алгоритм, умножение в столбик, требует n2 операций.
> при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.
я придираюсь к вполне конкретному слову «на порядок». я понимаю, что оно может работать и быстрее чем в 10 раз, но увы точность такого измерения надо доказать. я же просто советую использовать слово «гораздо быстрее».
Даже с учетом того, что автор допустил ошибку и скорость алгоритма явно не модет быть n*log(2,3)( так как это линейная зависимость от n), прежде чем советовать что-то другим, попробуйте сами освоиться с элементарной математикой.
n*log(2,3) будет в 10 раз меньше чем n^2 уже при n=15 или 16.
но даже если взять правильную формулу, то
n^log(2,3) будет в 10 раз меньше n^2 уже при n = 100.
n*log(2,3) будет в 10 раз меньше чем n^2 уже при n=15 или 16.
но даже если взять правильную формулу, то
n^log(2,3) будет в 10 раз меньше n^2 уже при n = 100.
Наверное, в этом месте плохо построено предложение. Там где «на порядок», идет речь про сравнение операции сложения с операций умножения.
А насчет именно «на порядок» не спорую, цель была подчеркнуть отношение между ними как n^1 / n ^ 2. Просто в голове не нашлось правильного описания для данного отношения.
А насчет именно «на порядок» не спорую, цель была подчеркнуть отношение между ними как n^1 / n ^ 2. Просто в голове не нашлось правильного описания для данного отношения.
Кстати да, чего то непонятно, каким образом преобразовав 2 умножения и 1 сложение к 3 умножениям и 4 сложениям выигрывается время? Наверно нужно описать ограничение для данного утверждения?
А чем обусловлена необходимость хранить длинное число в виде массива десятичных цифр? Почему не использовать родную компьютеру двоичную систему?
В статье наоборот написано, что реально нужно использовать не десятичную систему. Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30. «Потери» памяти вприоритет у скорости решения, а не в занимаемой памяти
А насчет двоичной не совсем понятно, что Вы имеете ввиду. Выделить участок памяти и оперировать непосредственно битами? — медленно и к тому же экономия памяти в этих задачах неприоритетна — или хранить в массиве двоичные цифры? — тоже медленно и слишком расточительно (поэтому еще медленнее).
А насчет двоичной не совсем понятно, что Вы имеете ввиду. Выделить участок памяти и оперировать непосредственно битами? — медленно и к тому же экономия памяти в этих задачах неприоритетна — или хранить в массиве двоичные цифры? — тоже медленно и слишком расточительно (поэтому еще медленнее).
Мда… Пора идти спать. В общем надеюсь смысли мысли приблизительно понятен )
С каких пор оперировать битами стало медленнее, чем байтами? А Вы именно это и делаете. Вы храните массив цифр в порядке разрядов десятичного числа. Это дает лишний расход памяти в 4 раза. И в скорости Вы при такой организации данных ничего не выигрываете, а совсем наоборот.
> Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30
Вы путаете основание системы счисления с разрядностью двоичного числа
> Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30
Вы путаете основание системы счисления с разрядностью двоичного числа
«С каких пор оперировать битами стало медленнее, чем байтами?»— минимально адресуемая единица памяти в x86 — байт. Соотв. для адресации битов нужно использовать дополнительные манипуляции — это раз. Два — тут действует принцип брать максимальное за раз. Например нужно умножить два 64х разрядных числа. Процессор ето может сделать это одной командой, если начать умножать побайтно или побитно, то понадобится соотв. 8 команд умножение или 64. И это только кол-во операций умножения, а еще масса других для «соединения» результата воедино. Если не верите — проведите небольшой эксперимент — напишите парочку маленьких программ на Ассемблере.
«Это дает лишний расход памяти в 4 раза.»— откуда Вы взяли число 4? В этом случае гораздо больше. 4 будет если взять за основание системы счисления 2^16, а размер базового типа 2^64. И то это расход только на само хранение. Еще куча места выделяется во время подсчета. Кстати, такую организацию памяти придумал не я, если для Вас ето будет аргументом. Так принято хранить длинные числа.
«Вы храните массив цифр в порядке разрядов десятичного числа.»
«Вы путаете основание системы счисления с разрядностью двоичного числа»— Да нет. Обратите внимание на
#define BASE 10 //система счисления. Например, число 16400 можно представить в виде a[] = {0,0,4,6,1}, если основание системы 10. А если основание, допустим, 12000, то число примет вид a[] = {4400, 1}
> Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30
Поясните. Почему это разумно?
> «Это дает лишний расход памяти в 4 раза.»
Погорячился. В Вашей реализации в 8 раз (это учитывая только избыток на хранение одного разряда), поскольку Вы используете 32 бита для хранения числа, вмещающегося в 4. А если посчитать общее занимаемое место — избыточность данных растет экспоненциально
Насчет брать максимальное за раз — все верно. Только к Вашей организации вычислений жтот метод не имеет никакого отношения.
Поясните. Почему это разумно?
> «Это дает лишний расход памяти в 4 раза.»
Погорячился. В Вашей реализации в 8 раз (это учитывая только избыток на хранение одного разряда), поскольку Вы используете 32 бита для хранения числа, вмещающегося в 4. А если посчитать общее занимаемое место — избыточность данных растет экспоненциально
Насчет брать максимальное за раз — все верно. Только к Вашей организации вычислений жтот метод не имеет никакого отношения.
Поясните. Почему это разумно?— Пояснения в статье в разделе «Реализация на C++»;
«Только к Вашей организации вычислений жтот метод не имеет никакого отношения.»— почему же?
> Длинные числа удобно представлять в виде массивов…
> Для увеличения быстродействия желательно выбрать за основание системы счисления максимальное число в рамках базовых типов
А где обоснование? Почему удобно? С чего Вы взяли, что это увеличит быстродействие? Где это самое увеличение?
> Для увеличения быстродействия желательно выбрать за основание системы счисления максимальное число в рамках базовых типов
А где обоснование? Почему удобно? С чего Вы взяли, что это увеличит быстродействие? Где это самое увеличение?
Длинные числа удобно представлять в виде массивов.
Легкая и наглядная форма. Близка к действительному представлению числа в памяти. Автоматически резервирует место для операций умножения и сложения на возможность переполнения разряда.
Квадрат максимального числа в выбранной системе счисления должен помещаться в выбранный базовый тип. Это необходимо для хранения произведения одного разряда на другой в промежуточных вычислениях.
Выбранный базовый тип желательно брать знаковый. Это позволить избавиться от нескольких промежуточных нормализаций.
Лучше, чтобы в разряд помещалось сумма из нескольких квадратов максимального числа. Это позволит избавиться от нескольких промежуточных нормализаций.
Я с удовольствие узнаю другие методы и подходы. Подкинете?
Например, если у вас 100k десятичных знаков, то переводить их в двоичную систему вы их будете дольше, чем умножать. А потом еще результат обратно… Пример — питон, где самая долгая операция с длинными числами — вывод и ввод.
Но это в случае, если надо перемножить десятичные числа. А если просто нужна абстрактная длинная арифметика — выбор за вами. Но серьёзного выигрыша там, думаю, не будет.
Но это в случае, если надо перемножить десятичные числа. А если просто нужна абстрактная длинная арифметика — выбор за вами. Но серьёзного выигрыша там, думаю, не будет.
Это всё несущественные детали. Хоть в виде массива десятичных цифр храни, хоть в виде родных двоичных — сложность алгоритма останется той же и по расходу памяти и по времени работы.
Другое дело, что массив десятичных цифр удобнее для демонстрации (а цель статьи именно в объяснении алгоритма) и в некотором (пускай и небольшом) классе задач.
Другое дело, что массив десятичных цифр удобнее для демонстрации (а цель статьи именно в объяснении алгоритма) и в некотором (пускай и небольшом) классе задач.
Вы чудовищно заблуждаетесь. Ассимптотическая сложность, безусловно, остается прежней, но не в коем случае нельзя путать ее с вычислительной сложностью алгоритма. Мне попадались чудовищные реализации алгоритма быстрой сортировки, затратные по времени и по памяти, однако формально они были корректны и ассимптотическая сложность сохранялась. Но работали из рук вон плохо. То, что сложность алгоритма O(n) говорит, что рост количества вычислений есть линейная функция. Но к большим числам она может уйти очень быстро
Именно асимптотическую сложность я и имею в виду)
Если бы автор использовал в статье и в примере двоичную систему счисления статья бы потеряла в наглядности.
Если бы автор использовал в статье и в примере двоичную систему счисления статья бы потеряла в наглядности.
Я к тому, что представленная автором реализация, конечно, показательна, но совершенно не практична. Профессор Карацуба, насколько мне известно, разрабатывал свой метод именно в расчете на двоичную арифметику
А что Вы считаете нужно изменить, чтобы реализация была практичной ( смену алгоритма на другой не рассматриваем :) )?
Алгоритм менять не будем, он чертовски хорош :) Я считаю, что нужно использовать не суррогатное представление числа последовательностью цифр на местах разрядов, а в виде непрерывного участка памяти требуемой длины. По результатам диалога с автором думаю заняться реализацией на досуге
А как Вы это представляете себе?
Есть такой тип замечательный. void*
Я понимаю. Но в чем именно суть? Выделить кусок памяти и «бегать» по нему указателем? Это тот же массив.
Отнюдь. Массив — это последовательность независимых равноразмерных элементов. Я предлагаю хранить не массив разрядов, а непрерывное n-байтное число в двоичной системе. Можно организовать арифметику чисел размерности n.
Предлагаемый автором способ, собственно, сходится к такому хранению при основании системы счисления 2^n, где n — количество бит для хранения одной цифры разряда (то есть в реализации автора 32)
Предлагаемый автором способ, собственно, сходится к такому хранению при основании системы счисления 2^n, где n — количество бит для хранения одной цифры разряда (то есть в реализации автора 32)
Как вы собираетесь адресовывать void*?
По-моему в адресации void * проблем нет — правда много возни с адресной арифметикой и приведениями типов. Просто в конце-концов получится тоже самое.
Адресная арифметика просто не работает с типом void* за отсутствием информации о размере адресуемых элементов.
Я не понимаю, что автор комментария хотел этим сказать. Он собирается оперировать байтами или чем?
Я не понимаю, что автор комментария хотел этим сказать. Он собирается оперировать байтами или чем?
Адресная арифметика просто не работает с типом void*
адресной арифметикой и приведениями типов.
Чем это будет отличаться от того, что написано у вас? Ничем. Вы и сами так написали, что получится то же самое. Вот поэтому я у автора комментария и хочу узнать, может он что-то другое имел ввиду.
Смещение по указателю + приведение, Вам правильно сказали. Как я отмечал раньше, представление автора неизбыточно только для системы счисления с основанием, равным соответствующей степени двойки. В этом случае разницы нет. Если основание меньше — получается избыточность, растущая экспоненциально с количеством разрядов числа. Фактически эта избыточность не нужна, поскольку числа с верхней границей 2^n можно хранить в линейной памяти и обращаться к нему по указателю. Реализовать арифметические операции в этом случае проблем не составляет. Единственная проблема — это перевод числа в десятичную систему для вывода. Для представления автора, когда основание 10, это тривиально, а для всех других оснований представляет сложности. Поэтому я не вижу особого смысла переходить к таким системам счисления (2^32), никакого выигрыша это не дает
«Смещение по указателю + приведение» = массив как у автора. Плюс, похоже вы еще собираетесь делать битовые операции, что будет эквивалентно приведению к нужному основанию.
Иными словами, вы просто предлагаете способ приема числа, при котором, оно всегда будет приводится к виду, как у автора при использовании правильного основания. Но это лишь вопрос преобразования входных данных. С таким же успехом, автор мог бы строго закрепить нужное основание, а принимать числа в любом формате, хоть в ASCII строке, просто написав нужную функцию.
Иными словами, вы просто предлагаете способ приема числа, при котором, оно всегда будет приводится к виду, как у автора при использовании правильного основания. Но это лишь вопрос преобразования входных данных. С таким же успехом, автор мог бы строго закрепить нужное основание, а принимать числа в любом формате, хоть в ASCII строке, просто написав нужную функцию.
Меня больше всего напрягает, что такое представление числа неизбыточно только для основания системы счисления 2^32, а таких систем я не встречал даже в теории. Для практически значимых систем счисления избыточность просто колоссальная
А какая разница какая система счисления? Арифметика везде одинаковая. Поэтому считать нужно в которой удобно. А приведение к заданной (нужно только в случае вывода результата пользователю) делается за линию.
Разница в скорости вычислений и объеме памяти
системы счисления 2^32, а таких систем я не встречал даже в теории.
А какая разница какая система счисления?
Разница в скорости вычислений и объеме памяти
Что-то винегрет получается. Чем же тогда этот способ плох, если он отлично подходит для этой системы?
Плох тем, что только в предельном случае для системы с основанием 2^n (см. выше) является неизбыточным
Я же и спрашиваю. Чем это плохо?
Чем плоха избыточность? Тем что она не нужна
Зачем же использовать систему счисления для которой представление избыточно? Чем плоха система «основанием 2^n»
Учитывая, что n не может быть меньше 8, т.е. минимальное основание 256… Покажите мне задачу с использованием такой системы счисления. Тут как раз спрашивали, зачем нужны лишние преобразования систем счисления. Не нужны
преобразование из системы в систему за линию + мало операций умножения будет быстрее чем просто решение с большим количеством операций умножения. Еще раз:«Для практической реализации алгоритмов не имеет значение в какой системе значения. Система важна только как результирующие данные для пользователя.
> А приведение к заданной (нужно только в случае вывода результата пользователю) делается за линию
Каким образом для больших чисел?
Каким образом для больших чисел?
Мельком глянув заголовок, вспомнил пограничника Карацупа :)
На самом деле Карацуба работает не n*log23, а nlog23~n1.5. См. вики.
в статье автор пошел не снизу, а сверху, и алгоритм по изложению сразу превратился из простейшего, реализуемому обычным студентом за несколько часов, в монстра.
нам когда-то объясняли на примере двузначных чисел, а потом рекурсивно расширяли на числа любой длины, и все все схватывали на лету, и реализовывали без проблем. эту же статью куда сложнее читать
нам когда-то объясняли на примере двузначных чисел, а потом рекурсивно расширяли на числа любой длины, и все все схватывали на лету, и реализовывали без проблем. эту же статью куда сложнее читать
Спасибо. В следующий раз учту. У меня была надежда, что тем кому интересно мат. обоснование, прочтут первую часть и пример им не понадобится. А те кому это не нужно прочитают маленький кусочек текста в главе с примером, примут во внимание, что алгоритм рекурсивный и верхний уровни добавлены только для количества примеров.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Умножение длинных чисел методом Карацубы