Большие целые числа в C #

Question

В настоящее время я заимствую java.math.BigInteger из библиотек J #, как описано здесь . Никогда ранее не использовавшая библиотеку для работы с большими целыми числами, это кажется медленным, примерно в 10 раз медленнее, даже для чисел ulong длины. У кого-нибудь есть какие-нибудь лучшие (желательно бесплатные) библиотеки, или этот уровень производительности нормальный?

Answer 1

Начиная с .NET 4.0 вы можете использовать класс System.Numerics.BigInteger. Смотри документацию здесь: http://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx

Другой альтернативой является класс IntX .

IntX - произвольная точность библиотека целых чисел, написанная на чистом C # 2.0 с быстрым - O (N * log N) - алгоритмы умножения / деления реализация. Это обеспечивает все основные операции над целыми числами, такими как сложение, умножение, сравнение, битовое смещение и т. д.

Answer 2

F# также поставляется с одним. Вы можете получить его на Microsoft.FSharp.Math.

Answer 3

Класс System.Numerics.BigInteger в .NET 4.0 основан на Microsoft.SolverFoundation.Common.BigInteger от Microsoft Research.

Класс BigInteger Фонда Солвера выглядит очень производительно. Я не уверен, под какой лицензией она выпущена, но вы можете получить ее здесь (скачайте и установите Solver Foundation и найдите файл Microsoft.Solver.Foundation.dll).

Answer 4

Вот несколько реализаций BigInteger в C #. Я использовал реализацию MonIn BigInteger, работает довольно быстро (я использовал ее в CompactFramework)

Надувной замок

Mono

Answer 5

Я считаю, что вы могли бы оптимизировать реализацию, если вы выполняете все операции над BigInts, которые будут возвращать результаты, меньшие, чем собственный тип (например, int64), для собственных типов и иметь дело только с большим массивом, если переполнение.

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

Answer 6

Я не уверен насчет производительности, но у IronPython также есть класс BigInteger. Он находится в пространстве имен Microsoft.Scripting.Math.

Answer 7

Это может звучать как странное предложение, но вы проверили тип десятичный , чтобы увидеть, как быстро он работает?

Десятичный диапазон составляет от ± 1,0 × 10 ^ −28 до ± 7,9 × 10 ^ 28, поэтому он все еще может быть недостаточно большим, но он больше, чем ulong.

В .NET 3.5 должен был быть класс BigInteger, но его обрезали .

Answer 8

Я использовал Biginteger на предыдущей работе. Я не знаю, какие у тебя должны быть результаты. Я не использовал его в ситуации с высокой производительностью, но у меня никогда не было с этим проблем.

Answer 9

Да, это будет медленно, и разница в 10 раз примерно такая, как я ожидал. BigInt использует массив для представления произвольной длины, и все операции должны выполняться вручную (в отличие от большинства математических операций, которые могут выполняться непосредственно с процессором)

Я даже не знаю, даст ли вам ручное кодирование в сборке большую часть прироста производительности в 10 раз, это чертовски близко. Я бы искал другие способы его оптимизации - иногда, в зависимости от вашей математической задачи, есть небольшие приемы, которые можно сделать, чтобы сделать это быстрее.

Answer 10

Вы также можете использовать пакет Math.Gmp.Native Nuget, который я написал. Его исходный код доступен на GitHub , а документация доступна здесь . Он предоставляет .NET все функциональные возможности библиотеки GMP , известной как высоко оптимизированная арифметическая библиотека произвольной точности.

Целое число произвольной точности представлено типом mpz_t . Все операции над этими целыми числами начинаются с префикса mpz_. Например, mpz_add или mpz_cmp . Примеры исходных кодов приведены для каждой операции.