Это старые новости, но я недавно читал о крупнейших простых числах, которые около года назад было найдено 17 миллионов цифровых чисел (самое большое на сегодняшний день). Это заставило меня немного подумать, поскольку вы должны иметь возможность вычислить число, чтобы убедиться, что оно простое. Какие методы могут быть реализованы для этого? Я не знаю ни одного типа данных, который мог бы хранить эти данные и все еще позволять его вычислять. Может ли BigInt справиться с этим?
Хранение очень, очень большого числа теоретических
Ответ 1
Утверждение, что BigInteger "в теории не имеет верхних или нижних границ" неверно. В .NET 4.0 структура BigInteger внутренне представлена с использованием массива uint[]. Учитывая, что максимальное значение для uint составляет 4 294 967 295 и что максимальная длина для массива равна 2 146 425 071, текущая реализация BigInteger имеет теоретическую верхнюю границу 4 294 967 295 2,146,435,071 (при условии идеальной упаковки), Это позволяет хранить целые числа, состоящие из миллиардов цифр (включая ваш простой), но не триллионов.
Изменить. Как упоминалось в комментариях, массивы не могут превышать 2 гигабайта в общем размере, если <gcAllowVeryLargeObjects> в разрешении (для чего требуется .NET 4.5 и 64-разрядная версия). Так как тип данных uint занимает 4 байта, максимальное количество элементов в массиве ограничено 2 29.
Чтобы продемонстрировать эту верхнюю границу, все, что вам нужно сделать, это запустить следующий код, который пытается вычислить (2 30) (2 30).
var bi = BigInteger.Pow(1 << 30, 1 << 30);
В течение нескольких секунд вы получите сообщение об ошибке:
OutOfMemoryException: Array dimensions exceeded supported range.
Не вводите в заблуждение имя типа исключения; эта ошибка будет выброшена, даже если у вас много памяти для размещения всего числа. Такую же ошибку можно было бы вызвать, если вы запустите следующий фрагмент:
var s = new uint[1 << 30];
Ответ 2
MSDN утверждает, что
Тип BigInteger является неизменным типом, который представляет произвольно большое целое число, значение в теории не имеет верхних или нижних границ. p >
Так что да, он мог бы обрабатывать такое число, как это, в теории. Этот тип также предоставляет множество математических операций, которые могут работать с ним.
Ответ 3
Из документации для BigInteger.
Тип BigInteger - неизменный тип, представляющий произвольно большое целое число, значение которого в теории не имеет верхней или нижней границ.
Однако он продолжает:
поскольку он не имеет верхних или нижних границ, исключение OutOfMemoryException может быть выбрано для любой операции, которая приводит к увеличению значения BigInteger.
Итак, я думаю, что ответ есть, да, он может справиться с этим, однако у вас должна быть машина с достаточной памятью.
Ответ 4
Насколько я уже протестировал BigInt, можно обрабатывать абсолютно огромные числа. Я буквально позволяю консоли печатать номер в течение нескольких минут. Единственное ограничение - ваша память.
Ответ 5
Если вы посмотрите, как фактически выполняются операции, вы обнаружите, что нет никаких оснований ограничивать их, например. 32-битные числа (переполнения, бесконечные полиномы и т.д.). Поэтому, если вы копируете одну и ту же логику в программном обеспечении, вы можете делать что угодно с произвольно большими числами. Конечно, сделать это быстро - это совсем другое дело.