Каков самый быстрый способ рассчитать e до 2 триллионов цифр?

Я хочу рассчитать e до 2 трлн (2 000 000 000 000) цифр. Это около 1,8 TiB чистого e. Я только что реализовал алгоритм расширения серии taylor, используя GMP (код можно найти здесь).

Несчастливо он падает при суммировании более 4000 терминов на моем компьютере, возможно потому, что у него заканчивается память.

Каково современное состояние при вычислении e? Какой алгоритм является самым быстрым? Любые версии с открытым исходным кодом, на которые стоит обратить внимание? Пожалуйста, не упоминайте y-cruncher, он закрыл источник.

Ответ 1

Поскольку я являюсь автором y-cruncher, которую вы упомянули, я добавлю свои 2 цента.

Для такой большой задачи два самых больших препятствия, которые необходимо решить, следующие:

Память
Сложность во время выполнения

Память

2 триллиона цифр - крайний - мягко говоря. Это удвоит текущую запись Двоичное расщепление в расширении серии Тейлора e.

Большое умножение на основе FFT

К счастью, GMP уже использует большое умножение на основе FFT. Но ему не хватает двух важных функций:

Внекорневое (swap) вычисление для использования диска, когда памяти недостаточно.
Он не распараллелен.

Второй момент не так важен, так как вы можете просто ждать дольше. Но для всех практических целей вам, вероятно, придется развернуть свои собственные. И это то, что я сделал, когда писал y-cruncher.

Тем не менее, есть много других недостатков, о которых необходимо позаботиться:

Окончательное деление потребует быстрого алгоритма, такого как метод Ньютона.
Если вы собираетесь вычислять в двоичном формате, вам нужно сделать преобразование радикса.
Если для вычисления потребуется много времени и много ресурсов, вам может потребоваться реализовать отказоустойчивость для обработки отказов оборудования.

Ответ 2

Поскольку у вас есть цель, сколько цифр вы хотите (2 триллиона), вы можете оценить, сколько терминов вам нужно вычислить e на это число цифр. Из этого вы можете оценить, сколько лишних цифр точности вам нужно отслеживать, чтобы избежать ошибок округления на 2 триллионном месте.

Если мои расчеты из приближения Стирлинга верны, то ответное значение от 10 до 2 трлн составляет около 100 млрд. факториалов. Так что о том, сколько сроков вам понадобится (100 миллиардов). История немного лучше, чем это, тем не менее, потому что вы начнете удалять много чисел при вычислении терминов задолго до этого.

Так как e вычисляется как сумма обратных факториалов, все ваши члены являются рациональными и, следовательно, они выражаются как повторяющиеся десятичные числа. Таким образом, десятичное расширение ваших членов будет (a) показателем, (b) не повторяющейся частью и (c) повторяющейся частью. Могут быть некоторые преимущества, которые вы можете использовать, если вы посмотрите на условия таким образом.

В любом случае, удачи!