любой документ, в котором точно указано, для какого диапазона номеров .NET BigIntegers предназначены?

12

Я играю с .NET BigInteger и в основном мне интересно, какое число - оценочный ответ будет в порядке - это точка отклонения кривой (график (увеличение времени, необходимого для операций) против (значение BigInteger))?

или они разработаны без такого отклонения, так что, если мы нанесем график увеличения времени, необходимого для операций по сравнению со значением BigInteger с 1 до бесконечности, у нас будет плавная кривая на всем пути?

например, предполагая, что массивы спроектированы с возможностью обработки 50 элементов. это означает, что если у меня есть 1 элемент, операции выполняются за f (1) раз. и когда у меня есть 2 предмета, операции выполняются в f (2) раз. если у меня есть 50 пунктов, операции выполняются в f (50) раз. но поскольку он предназначен для обработки только 50 элементов, операции, выполняемые при наличии 51 элемента, будут иметь вид g (51), где g (51)> f (51).

При правильной реализации сложность арифметики BigInteger должна быть плавной кривой. Например, временная сложность умножения должна составлять O (NM), где N - это количество цифр в первом мультипликаторе, а M - это количество цифр во втором мультипликаторе. Конечно, есть практические ограничения в том, что вы можете выбрать N и M настолько большими, что числа не будут соответствовать вашей машине.

Есть ли / кто-нибудь знает какие-либо документы, утверждающие, что он реализован как таковой?

Pacerier
источник
3
@ Избиратели, отрицательные голоса ничего не значат, если вы не можете оставить комментарий, объясняющий, почему вопрос не является хорошим вопросом. Я проголосовал за это, поскольку я не вижу проблем с этим.
The Muffin Man
Я не понизил голос, но я не уверен, в чем здесь вопрос. Вы хотите знать сложность операций во время выполнения / памяти для больших чисел (сложение, умножение, деление и т. Д.)?
nikie
например, предполагая, что массивы спроектированы с возможностью обработки 50 элементов. это означает, что если у меня есть 1 элемент и операции выполняются в f (1) раз. и когда у меня есть 2 предмета, операции выполняются в f (2) раз. если у меня есть 50 пунктов, то операции выполняются в f (50) раз. но поскольку он предназначен для обработки только 50 элементов, операции, выполняемые при наличии 51 элемента, будут иметь вид g (51), где g (51)> f (51)
Pacerier
@ Чарльз Э. Грант да! Об этом я и говорю. вопрос в том, есть ли / кто-нибудь знает какие-либо документы, утверждающие, что он реализован как таковой?
Pacerier
@Paceier Я переместил свой комментарий к своему ответу и добавил ссылку на документ, обсуждающий именно это.
Чарльз Грант

Ответы:

7

Любое число, которое может быть больше ULong.MaxValue или меньше Long.MinValue, должно быть представлено с использованием BigInteger.

Если НЕ (Long.MinValue <= X <= ULong.MaxValue), то BigInteger

BigInteger для слишком больших чисел, чем обычные примитивы.

Например, если ваше целое число находится вне диапазона Long, вам, вероятно, следует использовать BigInteger. Эти случаи очень редки, и использование этих классов имеет значительно больше накладных расходов, чем их примитивные аналоги.

Например, longимеет ширину 64 бита и может содержать диапазон: от -9,223,372,036,854,775,808 до 9,223,372,036,854,775,80. ulong может вместить от 0 до 18,446,744,073,709,551,615. Если ваши номера больше или меньше, BigInteger - ваш единственный выбор

Единственный раз, когда я видел их в реальных приложениях, это было приложение starchartting.

Смотрите также: Примитивные диапазоны в .NET

Malfist
источник
я имею в виду, конечно, я знаю, что мы должны использовать нормальные примитивы всякий раз, когда можем. я имею в виду, я знаю, что он может поддерживать в 100 тысяч раз больше, чем ULong.MaxValue, но разработан ли он с учетом этого диапазона, или же он разработан с этим диапазоном, объявленным «необычным требованием»?
Pacerier
5
Вы не можете представить число даже на единицу больше ULong.MaxValue без использования BigInteger, так что это для этого. Любое число, которое может быть больше ULong.MaxValue, должно быть BigInteger.
Malfist
Конечно, есть способы представления чисел, больших, чем ULong.MaxValue, без использования BigInteger. я мог бы просто написать собственную структуру, которая состоит из ULong, логического и альта, я могу представить до двух раз ULong.MaxValue
Pacerier
Да, но использовать BigInteger гораздо проще, и, вероятно, он не будет намного быстрее, если не быстрее, и не будет таким же гибким, как BigInteger. Вы также можете представлять очень большие числа с помощью массива логических значений, но это слишком сложно.
Malfist
2
@ Маврик, он изменил это на совершенно другой вопрос, чем тот, на который я ответил.
Малфист
4

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

Как уже отмечали другие, ulong может содержать от 0 до 18,446,744,073,709,551,615, и пока вы находитесь в этом диапазоне, вы можете выполнять точную арифметику. Если вы выйдете даже на 1 из этого диапазона, вы получите переполнение, поэтому ответом на ваш вопрос будет использование BigInteger, если вам нужна точная арифметика, и есть вероятность, что любой промежуточный результат превысит 18 446 744 073 709 551 615.

Большинство проблем в науке, технике и финансах могут соответствовать аппроксимациям, вызванным числами с плавающей запятой, и не могут позволить себе затрат времени на арифметику BigInteger. Большинство коммерческих вычислений не могут соответствовать аппроксимации арифметики с плавающей запятой, но работают в диапазоне от 0 до 18,446,744,073,709,551,615, поэтому они могут использовать обычную арифметику. BigInteger необходим при использовании алгоритмов из теории чисел, которая включает в себя такие вещи, как криптография (представьте 50 простых чисел). Он также иногда используется в коммерческих приложениях, когда необходимы точные вычисления, скорость не так важна, а установка правильной системы с фиксированной десятичной запятой - это слишком много проблем.

При правильной реализации сложность арифметики BigInteger должна быть плавной кривой. Например, временная сложность умножения должна составлять O (NM), где N - это количество цифр в первом мультипликаторе, а M - это количество цифр во втором мультипликаторе. Конечно, есть практические ограничения в том, что вы можете выбрать N и M настолько большими, что числа не будут соответствовать вашей машине.

Если вы воспользуетесь Google «Вычислительная сложность biginteger», вы получите больше ссылок, чем можете потрясти. Тот, который прямо отвечает на ваш вопрос, это: Сравнение двух арифметических пакетов произвольной точности .

Чарльз Э. Грант
источник
4

Предел памяти

BigInteger использует массив int для хранения. Предполагая это, теоретический предел для максимального числа, которое BigInteger способен представить, может быть получен из максимального размера массива, доступного в .net. Здесь есть тема SO о массивах: определение того, сколько памяти я могу выделить для массива в C # .

Предполагая, что мы знаем максимальный размер массива, мы можем оценить максимальное число, которое BigInteger может представлять: (2 ^ 32) ^ max_array_size, где:

  • 2 ^ 32 - максимальное число в ячейке массива (int)
  • max_array_size - максимально допустимый размер массива int, который ограничен размером объекта 2 ГБ.

Это дает число с 600 миллионами десятичных цифр.

Предел производительности

Что касается производительности, BigInteger использует алгоритм Карацубы для умножения и линейный алгоритм для сложения. Сложность умножения заключается в том 3 * п ^ 1,585, что она достаточно хорошо масштабируется даже для больших чисел ( график сложности ), однако вы все равно можете снизить производительность в зависимости от объема оперативной памяти и кеша процессора.

Поскольку максимальный размер номера ограничен 2 ГБ, на спускаемой машине вы не увидите неожиданного разрыва в производительности, но работа с 600-миллионными цифрами будет очень медленной.

Валера Колупаев
источник
это замечательная информация, однако, где ваш источник, что BigInteger полагается на массивы int?
Pacerier
Я только что копался в источниках .net, используя dotPeek. Кажется, что само число хранится внутри uint [] _data структуры BigInteger.
Валера Колупаев
* Обновлено с более подробным ответом, однако я не могу найти никакого исходного кода .net, на который я могу ссылаться, кроме декомпилированных фрагментов.
Валера Колупаев
Мне кажется, что в .NET есть стандартный алгоритм умножения, который можно выяснить из ILSpy: .NET BigInteger Multiplication
Иван Кочуркин
1

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

Конечно, часто алгоритмы становятся медленнее с увеличением числа, но не намного медленнее.

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

Пауло Эберманн
источник
0

В научном сообществе есть несколько применений (например, расстояние между галактиками, количество атомов в поле травы и т. Д.)

Дейв Уайз
источник
не хамить .. но как этот ответ относится к вопросу?
Pacerier
2
Вопрос, как написано, звучит так, как будто он искал реальный пример того, почему такой тип данных должен быть создан.
Дейв Уайз
лучше перефразировать: «BigInteger действительно подходит для чисел до 10 ^ 30»?
Pacerier
Для этого я бы лучше использовал doubleили float- у вас нет необходимой точности в любом случае.
Пауло Эберманн
лучше перефразировать: «Действительно ли BigInteger подходит для чисел до 10 ^ 30, когда нам нужна точность»?
Pacerier
0

Как следует из ответа Кевина Клайна, BigNumbers были добавлены в библиотеки .NET в основном потому, что они были необходимы в качестве строительного блока для многих современных криптографических алгоритмов (цифровые подписи, шифрование с открытым / закрытым ключом и т. Д.). Многие современные криптографические алгоритмы включают вычисления целочисленных значений размером до нескольких тысяч бит. Поскольку класс BigNumber описывает четко определенный и полезный класс, они решили сделать его общедоступным (а не хранить его как внутреннюю деталь криптографических API).

Стивен С. Сталь
источник
Кстати, просто любопытно, откуда вы взяли, что BigNumbers были добавлены в библиотеки .NET в первую очередь потому, что они были необходимы в качестве строительного блока для многих современных криптографических алгоритмов (и, следовательно, должны иметь возможность поддерживать значения до нескольких тысяч бит)?
Pacerier