Каково ограничение типа значения BigInteger в C#?

Как описано в MSDN BigInteger это:

Неизменяемый тип, представляющий произвольно большое целое число, значение которого в теории не имеет верхних или нижних границ.

Как я вижу, BigInteger - это ValueTypeНасколько я знаю, ValueType должен иметь максимальный размер 16 байтов.

MSDN идет дальше, говоря:

OutOfMemoryException может быть выброшено для любой операции, которая вызывает слишком большое значение BigInteger.

и больше:

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

Как он мог хранить такие большие значения, как большие double.MaxValue + double.MaxValue? Мне сказали, что это имеет ReferenceType объекты внутри него, но все, что я могу найти здесь в его определении в VisualStudio, это ValueTypes.

Каков его реальный предел? И даже если его нет, как ему "в качестве типа значения" удается хранить весь этот объем данных?

Источник

4 ответа

Решение

Как я вижу, BigInteger - это ValueType, насколько я знаю, ValueType должен иметь максимальный размер 16 байтов.

Нет это не правда. Это обычный предел, но вполне допустимо, чтобы тип значения брал больше, чем это. Например:

public struct Foo {
    private readonly int a, b, c, d, e; // Look ma, 20 bytes!
}

Однако я сильно подозреваю, что BigInteger фактически включает ссылку на байтовый массив:

public struct BigInteger {
    private readonly byte[] data;
    // Some other fields...
}

( Мусульманский ответ Бен Дау показывает одну текущую реализацию, использующую int а также uint[], но, конечно, детали этого намеренно скрыты.)

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

Как он может хранить такие большие значения, как double.MaxValue + double.MaxValue?

Что ж BigInteger для целых чисел, так что я бы не хотел использовать его для чего-либо общего с double... но принципиально ограничения будут заключаться в том, сколько у вас памяти и размер массива, с которым CLR может справиться. В действительности, вы будете говорить об огромных числах, прежде чем действительно достигнете предела для любого конкретного числа - но если у вас есть миллиарды меньших чисел, это, очевидно, также требует больших объемов памяти.

Источник

В качестве подтверждения ответа от Джона Скита, я посмотрел на исходный код BigInteger, На самом деле он содержит два внутренних свойства:

internal int _sign;
internal uint[] _bits;

_bits используется почти всеми закрытыми / открытыми методами в классе, которые используются для чтения / записи фактических данных.

_sign используется для сохранения знака BigInteger,

Частные методы широко используют бинарные операторы и вычисления. Вот небольшой список констант, используемых в классе, которые могут немного отражать ограничения:

private const int knMaskHighBit = -2147483648;
private const uint kuMaskHighBit = 2147483648U;
private const int kcbitUint = 32;
private const int kcbitUlong = 64;
private const int DecimalScaleFactorMask = 16711680;
private const int DecimalSignMask = -2147483648;

PS: Я должен был прокомментировать ответ JS, но комментарий слишком короткий. Чтобы просмотреть исходный код, скачайте его или декомпилируйте System.Numerics.dll,

Источник

TL;DR: максимальное значение BigInteger равно 2 ^ 68685922272.

В .Net 4.7.2 BigInteger использует массив uint для битов.

uint содержит 32 бита данных.

Максимальный размер массива определяется как internal const int MaxArrayLength = 0X7FEFFFFF;7FEFFFFFF = 2146435071

Теперь, чтобы рассчитать: максимальный размер массива x емкость каждого uint: 2146435071 x 32 = 68685922272. Но это только количество битов в BigInteger.

Это означает, что максимальное значение BigInteger: 2^68'685'922'272, что очень велико (используется ' для облегчения чтения).

Если они когда-нибудь решат увеличить максимальный размер массива, это также увеличит максимальное значение для BigInteger.

Источник

Я просто провел несколько быстрых экспериментов по этому поводу. Макс кажется около 2 ^ 65 000 000 000, но фактическая практичность 2146435071

Я получаю исключение System.OverflowException ниже по адресу 0x1F. Он переполнился между E FFFF FFE2 и F 7FFF FFE1. (или где-то между 2 ^ 64 424 509 410 и 2 ^ 66 571 993057). На самом деле это довольно близко к ответу Чабы Бенака.

      // Test 1
BigInteger test = 1;
for (int i = 0x00; i < 0xFF; i++)
    test <<= 0x7FFFFFFF;

// Test 2
BigInteger.Pow((BigInteger)2, 0x7FEFFFF0); // OK - I think - never finished
BigInteger.Pow((BigInteger)2, 0x7FEFFFFF); // Immediate OutOfMemoryException

Я также должен отметить, что хотя ~ 66 571 993 057, похоже, поддерживается. Полезность больше похожа на 2 ^ 2146435071, потому что POWER и сдвиги, похоже, не работают с POWER, превышающим 2 146 435 071 (для POW() ) или с количеством смен более 2 147 483 647. Можно сделать большие сдвиги, но это потребует нескольких раундов, снижающих эффективность. И другой элемент работает медленно на этих скоростях - одно смещение занимало около 7 секунд, а BigInteger.Pow() - не менее 5 минут.

.Net 5, AMD Threadripper, 32 ГБ ОЗУ, Windows 10 x64

Источник
Другие вопросы по тегам