Как быстрее всего вычислить е до 2 триллионов цифр?

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

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

1. объем памяти
2. Сложность во время выполнения

Память

2 триллиона цифр - это экстремум, мягко говоря. Это вдвое больше, чем текущий рекорд, установленный мной и Сигеру Кондо в 2010 году. (Нам потребовалось более 9 дней, чтобы вычислить 1 триллион цифр с помощью y-cruncher.)

В обычном тексте это около 1,8 ТиБ в десятичной системе. В упакованном двоичном представлении это 773 ГиБ.

Если вы собираетесь выполнять арифметические операции с числами такого размера, вам понадобится 773 ГиБ для каждого операнда, не считая оперативной памяти.

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

Тем не менее, я сомневаюсь, что у тебя будет достаточно барана. И даже если бы вы это сделали, это было бы сильно NUMA. Таким образом, альтернативой является использование диска. Но это нетривиально, так как для повышения эффективности вам нужно рассматривать память как кеш и контролировать все данные, которые передаются между памятью и диском.

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

Здесь у нас другая проблема. Для 2 триллионов цифр вам понадобится очень быстрый алгоритм. Не просто быстрый алгоритм, а квазилинейный алгоритм времени выполнения.

Ваша текущая попытка выполняется примерно через O(N^2). Так что, даже если у вас было достаточно памяти, это не закончится за всю вашу жизнь.

Стандартный подход к вычислениям e с высокой точностью выполняется в O(N log(N)^2) и сочетает в себе следующие алгоритмы:

• Бинарное разбиение в расширении ряда Тейлора для e.
• большое умножение на основе БПФ

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

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

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

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

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

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

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

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

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