Бывает так, что нужно работать ну с очень большими числами. Настолько большими, что они никак не влезают во встроенные типы. Можно для этого реализовать собственный класс, например из динамического массива целых чисел. И работать с большими числами старым добрым способом, знакомым еще со школы - имитировать умножение в столбик и т.д. Единственным ограничением на размер такого числа будет размер памяти компьютера.
Как обычно, можно не реализовывать это самостоятельно, а взять уже готовую библиотеку.
Вышеупомянутая имитация умножения в столбик - это, конечно, корректно, но как-то медленно. Поэтому люди пытаются этот момент разогнать. Для этого применяются алгоритмы, которые используются для быстрого умножения полиномов. Если вы возьмете уже готовую библиотеку работы с большими числами, то там, скорее всего, реализован такой алгоритм, а то и не один. Я чаще всего встречала упоминание Fast Fourier Transforms (сокращенно FFT) и умножение Карацубы.
Когда увидела словосочетание "Karatsuba multiplication" у меня в голове создался образ сурового японца. Ан нет, это совсем даже и не японец, его полное имя Карацуба Анатолий Алексеевич. Прямо даже как-то приятно стало.
Интересная область применения больших чисел - это работа с числами повышенной точности. Представление чисел с плавающей точкой неточно, ошибки накапливаются. Можно попытаться представить их в виде дроби, работать уже с дробями и таким образом исключить неточности.
В заключение несколько ссылок по большим числам. Из библиотек для работы с большими числами я выбрала те, которые чаще всего упоминаются. Работать я с ними не работала, поэтому более подробно о них рассказать не могу.
С++ библиотеки для работы с числами высокой точности: Arageli, NTL, GMP
Crypto++ - библиотека для криптографии, в ней предусмотрена работа с большими числами
Multiplication algorithm - страница из Википедии с описаниями различных алгоритмов умножения
General Decimal Arithmetic
А-а-афигенно. Спасибо! В мемориз!
ОтветитьУдалитьЕсть еще алгоритм Тоома-Кука. Андрей Тоом - это тоже наш человек :) хотя уже давно работает за границей
ОтветитьУдалитьЕсли честно, я немного удивлён: преобразование Фурье используется для перемножения больших чисел!?
ОтветитьУдалитьОбычно применяется для "спектрального" анализа данных: в Фурье-плоскости многие задачи обработки изображений решаются проще. И существенно ускоряет расчёты. Но чтобы числа перемножать... а можно ссылочку на алгоритм?
Если честно, я немного удивлён: преобразование Фурье используется для перемножения больших чисел!?
ОтветитьУдалитьОбычно применяется для "спектрального" анализа данных: в Фурье-плоскости многие задачи обработки изображений решаются проще. И существенно ускоряет расчёты. Но чтобы числа перемножать... а можно ссылочку на алгоритм?
Я смотрела про него в Википедии здесь: Multiplication algorithm. Есть отдельная страничка Fast Fourier transform. Хороший алгоритм, много где применяется.
Насколько мне известно, то алгоритмы использующие FFT для умножнения чисел имеют самую лучшую оценку трудоёмкости. Например в той же GMP реализован алгоритм Шёнхаге-Штрассена, а в Arageli в ближайшее время появится алгоритм основанный на идее Полларда, тоже использующий FFT. Эти алгоритмы проигрывают алгоритму Карацубы на числах маленькой длинны, но начиная с некоторого придельного значения работают быстрее. Соотвественно просто умножение в вышеупомянутых библиотеках работает по след. принципу: весь интервал премножаемых чисел делится на подинтервалы, в которых применяется наибыстрейший алгоритм. Т.е. с некоторой долей вероятности можно утверждать, что вы всегда перемножаете числа самым быстрым способом.
ОтветитьУдалитьХм, а чего мучиться, заморачиваться?
ОтветитьУдалитьХаскелл неплохо интегрируется с программами на том же С++ - можно модули, работающие с задачами, где нужны сверхбольшие числа, просто написать на Хаскелле и подвязать к основной программе на С++.
Или вообще обойтись без С++... :о))
Или вообще обойтись без С++... :о))
ОтветитьУдалитьКстати да. В Питоне вот работа с большими числами происходит вообще прозрачно для программиста.
Эх. Сейчас пытаюсь сделать шаблон для длинного целого, параметризуемый типом своих половинок. Чтобы можно было длинное целое любой размерности создать потом ...
ОтветитьУдалить