Напишите самый большой премьер

Я пытаюсь решить самую большую проблему программирования в С#. Проблема проста, распечатать или записать в файл номер: 2 ^57,885,161 - 1 (который имеет 17,425,170 цифр)

Мне удалось решить эту проблему с помощью удивительной библиотеки многоточечной арифметики GNU через Emil Stevanof.Net wrapper

var num = BigInt.Power(2, 57885161) - 1;
File.WriteAllText("biggestPrime.txt", num.ToString());

Даже если все существующие в настоящее время решения используют эту библиотеку, для меня это похоже на обман. Есть ли способ решить это в управляемом коде? Идеи? Предложения?

PS: Я уже пробовал использовать .Net 4.0 BigInteger, но он никогда не заканчивается для вычисления (я ждал 5 минут, но это уже много по сравнению с 50 секунд решения GMP).

Ответ 1

Это также более чит, чем решение, но я решил это с помощью библиотеки IntX

IntX.Pow(2, 57885161, MultiplyMode.AutoFht) - 1;

Прошло около 6 минут. Тем не менее, это не настоящий ответ. Было бы интересно увидеть что-то "реальное".

EDIT: используя секундомер С#, я понял, что расчет занимает всего 5 секунд, а процесс ToString занимает очень много времени.

Ответ 2

Если вы хотите рассчитать это число, используя только умножения (и соответствующую большую целочисленную библиотеку), вы можете посмотреть на сокращение количества выполненных вычислений. В простом случае вы можете многократно умножать на 2 (57885161 раз) до выведения 1, но мы можем сделать это со значительно меньшим количеством умножений.

Рассмотрим повторяющееся возведение в квадрат. Это дает нам 2, 2 ² (2 ²) ²= 2 ⁴ (2 ⁴) ²= 2 ⁸ и т.д. После квадратизации 25 раз мы рассчитали 2 ^{(2 ²⁵)}= 2 ^33554432.

Если мы посмотрим на двоичное представление 57885161, получим 11011100110100000111101001. I.e. что нам нужно (для 2 ^57885161) 2 ^{(2 ²⁵)} * 2 ^{(2 ²⁴)} * 2 ^{(2 ²²)} и т.д. Мы можем сохранить все необходимые полномочия 2 на нашем пути к вычислению самого высокого требуемого, а затем просто сделайте окончательные умножения. Так что 25 + 13 больших целых умножений. Затем нам просто нужно вычесть 1 для требуемого значения.

Ответ 3

То, что вам нужно сделать, является вычислительно-интенсивным. Visual С# и Visual Basic (и интерпретируемые языки в целом) не предназначены для такой вещи. Использование GMP - это правильная вещь, поскольку она реализована в чистом C и высоко оптимизирована для скорости выполнения.

Если вы решили использовать только управляемый код, то будьте терпеливы: использование .Net 4.0 BigInteger может занять до 100 раз больше времени, чем при использовании GMP. Чтобы проверить это, вы должны вычислить 2 ¹⁰⁰⁰ 2 ¹⁰⁰⁰⁰ 2 ^{100 000} 2 ^1,000,000 и 2 ^{10 000 000} и посмотреть, сколько времени требуется для вычисления каждого из этих выражений с помощью .NET Framework 4.0.

Если окажется, что необходимое время слишком велико, тогда вы можете попробовать и сделать вычисления самостоятельно. Вы должны использовать этот алгоритм для выполнения возведения в степень, а затем порт из С++ в С# моя собственная реализация умножения больших чисел или любой другой, который вы можете найти. Тем не менее, нет гарантии, что вы достигнете значительно лучшей производительности, поскольку вы все еще используете управляемый код.