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