На днях нужно было разобраться с этим алгоритмом, но беглый поиск в google ничего путнего не дал. На Хабре тоже нашлась только одна статья, которая мне не особо помогла. Разобравшись, попробую поделиться с общественностью в доступной форме:
AzaMath — Cистемы счисления (включая кастомные) + арифметика произвольной точности на PHP
Возникла недавно задача, связанная с конвертацией между различными позиционными системами счисления.
В качестве реального применение обычно выступают сервисы для сокращения URL, использующие системы base36/base62 или, например, хранение большого количества огромных чисел в том же base62 для экономии памяти.
Поискав среди существующих решений, понял, что ни одно из них не устраивает, в связи с чем, решил подготовитьбиблиотеку-компонент для различных математических задач в фреймворке.
Получилась AzaMath — библиотека для конвертации между системами счисления (включая кастомные) + удобная арифметика произвольной точности.
В качестве реального применение обычно выступают сервисы для сокращения URL, использующие системы base36/base62 или, например, хранение большого количества огромных чисел в том же base62 для экономии памяти.
Поискав среди существующих решений, понял, что ни одно из них не устраивает, в связи с чем, решил подготовить
Получилась AzaMath — библиотека для конвертации между системами счисления (включая кастомные) + удобная арифметика произвольной точности.
Реализация длииииииинной арифметики на C++
Sandbox
В большинстве современных языков программисту уже не нужно заботиться о числах, с которыми процессор непосредственно манипулировать не может. Где-то, как в Python или Haskell, поддержка длинных целочисленных типов встроена прямо в ядро языка, где-то, как в Java или C#, реализована в виде отдельных классов. Но в стандартной библиотеке языка C++ длинные числа до сих пор не поддерживаются. Поэтому я решил написать её сам.
Длинная арифметика от Microsoft
Введение
Известно, что компьютер может оперировать числами, количество бит которых ограниченно. Как правило, мы привыкли работать с 32-х и 64-х разрядными целыми числами, которым на платформе .NET соответствуют типы Int32 (int) и Int64 (long) соответственно.
А что делать, если надо представить число, такое как, например, 29! = 8841761993739701954543616000000? Такое число не поместится ни в 64-х разрядный, ни тем более 32-х разрядный тип данных. Именно для работы с такими большими числами существует длинная арифметика.
Длинная арифметика — в вычислительной технике операции (сложение, умножение, вычитание, деление, возведение в степень и т.д.) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, используя базовые аппаратные средства работы с числами меньших порядков.
Гипотеза Бёрча — Свиннертон-Дайера
Эта примечательная гипотеза связывает поведение функции L там, где в настоящее время неизвестно, определена ли она, и порядок группы Ш, про которую неизвестно, конечна ли она!
J.T.Tate, The arithmetic of elliptic curves, Inventiones mathematicae 23 (1974)
Оригинал
(Краткая справка насчёт актуальности цитаты 40-летней давности: после Уайлса и Ко таки стало известно, что функцию L можно определить на всей комплексной плоскости. Конечность группы Ш в общем случае остаётся неизвестной.)This remarkable conjecture relates the behaviour of a function L at a point where it is not at present known to be defined to the order of a group Ш which is not known to be finite!
Остаётся обсудить возможность ошибки. В качестве предосторожности против внутренних ошибок компьютера можно прогнать все вычисления дважды или делать проверки внутри программы. Более того, компьютеры — в отличие от людей — устроены так, что их ошибки обычно чересчур велики, чтобы их не заметить. Мы уверены, что в наших результатах нет подобных ошибок. С другой стороны, при кодировании замысловатой схемы вычислений в компьютерную программу неизбежны программистские ошибки. Большинство из них обнаруживаются ещё до основных запусков, из-за того, что программа виснет или выдаёт нелепые результаты. Но программа, которую считается работающей, всё ещё может содержать логические ошибки, проявляющиеся при редких стечениях обстоятельств: и действительно, большинство компьютеров подвержено аномалиям, из-за которых те иногда ведут себя не так, как должны по спецификациям. В сущности, наша программа для этапа (ii) оказалась неточной и пропустила очень небольшое количество эквивалентностей, которые должна была найти.
По этим причинам мы считаем, что не стоит автоматически доверять результатам, полученным на компьютере. В некоторых случаях их можно проверить за счёт свойств, которые по существу не были задействованы в вычислениях и которые вряд ли пережили бы возможную ошибку. (Например, таблицу значений гладкой функции, полученную без использования интерполяции, можно проверить вычислением разностей соседних значений.) Но если подобные проверки недоступны, не стоит полностью доверять результатам, пока они не были независимо подтверждены другим программистом на другом компьютере. Мы не думаем, что это задаёт чрезмерный стандарт во время, когда компьютеры становятся столь широко доступны; и мы уверены, что низкие стандарты уже привели к публикации и вере в неверные результаты.
B.J.Birch and H.P.F.Swinnerton-Dyer, Notes on elliptic curves. I, Journal für die reine und angewandte Mathematik 212 (1963)
Оригинал
It remains to discuss the question of error. One can take precautions against machine errors either by running all the calculations twice or by checks included in the program. Moreover, machines — unlike human beings — are so designed that the errors they make are usually too gross to be overlooked. We are satisfied that there are in our results no undetected errors of this sort. On the other hand, in translating an elaborate scheme of calculation into a machine program one is bound to make mistakes. Most of these are found before the program is used for production runs; they show up because the program grinds to a halt or produces ridiculous results. But a program which is believed to work may still contain logical errors which only have an effect in rare circumstances: and indeed most computers have anomalies which cause them occasionally not to behave in the way that their specifications suggest. In fact, our program for stage (ii) was imperfect in that a very few equivalences were missed by the machine.
For these reasons we believe that results obtained from a computer should not be automatically trusted. In some cases they can be checked because they have properties which were not essentially used in the course of the calculation and which would be unlikely to survive if an error had been made. (For example, if a table of a smooth function has been calculated without the use of interpolation, it can be checked by differencing.) But if checks of this sort are not available, results should not be fully trusted until they have been independently reproduced by a different programmer using a different machine. We do not think this sets an unreasonable standard, now that computers are becoming so widely available; and we are satisfied that lower standards have already led to a number of untrue results being published and believed.
For these reasons we believe that results obtained from a computer should not be automatically trusted. In some cases they can be checked because they have properties which were not essentially used in the course of the calculation and which would be unlikely to survive if an error had been made. (For example, if a table of a smooth function has been calculated without the use of interpolation, it can be checked by differencing.) But if checks of this sort are not available, results should not be fully trusted until they have been independently reproduced by a different programmer using a different machine. We do not think this sets an unreasonable standard, now that computers are becoming so widely available; and we are satisfied that lower standards have already led to a number of untrue results being published and believed.
Под катом не будет формулировки гипотезы; знающие выражения вроде «Euler product» и «holomorphic continuation» (и в смысле языка, и в смысле обозначаемых понятий) могут прочитать пятистраничный pdf с сайта института Клэя. Под катом — некоторая попытка пояснить, на каком направлении развития математической мысли вообще находится гипотеза Бёрча — Свиннертон-Дайера. А также — как можно досчитать до больших чисел вроде тех, что показаны на КДПВ, менее чем за секунду.
Алгоритмы быстрого вычисления факториала
Sandbox
Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 * 2 * 3 *… * N. Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр.
Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику. Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.
Наивный алгоритм
Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:
На моей машине эта реализация работает примерно 1,6 секунд для N=50 000.
Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.
Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику. Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.
Наивный алгоритм
Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:
static BigInteger FactNaive(int n)
{
BigInteger r = 1;
for (int i = 2; i <= n; ++i)
r *= i;
return r;
}
На моей машине эта реализация работает примерно 1,6 секунд для N=50 000.
Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.
Обобщение задачи Брокара
Sandbox
История
Гильберт в 1900 году на II Международном конгрессе математиков в Париже отметил практическую важность теории чисел. Решение абстрактных задач часто приводило к появлению нового математического аппарата. Ярким примером служит Великая Теорема Ферма, в ходе доказательства которой в конце XX-ого века были исследованы мероморфные функции, применяющиеся современными инженерами-конструкторами на авто- и авиазаводах, а также IT-специалистами в рамках имитационного моделирования. Задачи о "красивых числах" — простых близнецах и совершенных числах, считавшиеся в Древней Греции практически бесполезными, теперь обеспечивают современную криптографию устойчивыми алгоритмами генерации ключей.
В 1913 году Рамануджан популяризирует неопределённое уравнение:
Ранее оно фигурировало в работах Анри Брокара. Как утверждают историки, два математика занялись изучением указанного уравнения независимо друг от друга. Очевидно, факториал растёт быстрее квадрата, поэтому первые решения можно быстро получить перебором значений n.
Arbitrary Precision — удобная C++ библиотека для работы с длинными целыми числами
Sandbox
Вопреки тому, что авторских C++ библиотек для длинных целых очень много, мне было трудно найти решение, которое было бы простым в использовании на всех этапах (интеграция зависимости, разработка, релиз с зависимостями). Авторские библиотеки имеют одну или несколько проблем реализации: используют
в качестве базы счисления, нужна компиляция исходников, не оттестированные, неполный интерфейс (отсутствуют побитовые операторы), не кроссплатформенные.
В данной статье описывается ранняя версия библиотеки, которая предлагает реализацию длинных целых чисел с поведением, как у базовых типов. Философия - простота, гибкость и надёжность.