Большие целые числа в C#
В настоящее время я занимаю java.math.BigInteger из библиотек J#, как описано здесь. Никогда ранее не использовавшая библиотеку для работы с большими целыми числами, это кажется медленным, примерно в 10 раз медленнее, даже для ulong длина номера. У кого-нибудь есть лучшие (желательно бесплатные) библиотеки, или этот уровень производительности нормальный?
12 ответов
Начиная с.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 с быстрой реализацией алгоритмов умножения / деления. Он обеспечивает все основные операции над целыми числами, такие как сложение, умножение, сравнение, битовое смещение и т. Д.
F# также поставляется с одним. Вы можете получить его на Microsoft.FSharp.Math,
System.Numerics.BigInteger класс в.NET 4.0 основан на Microsoft.SolverFoundation.Common.BigInteger от Microsoft Research.
Фонд Солвера BigInteger класс выглядит очень производительным. Я не уверен, под какой лицензией она выпущена, но вы можете получить ее здесь (скачайте и установите Solver Foundation и найдите файл Microsoft.Solver.Foundation.dll).
Вот несколько реализаций BigInteger в C#. Я использовал реализацию MonIn BigInteger, работает довольно быстро (я использовал ее в CompactFramework)
Я считаю, что вы могли бы оптимизировать реализацию, если вы выполняете все операции над BigInts, которые будут возвращать результаты, меньшие, чем собственный тип (например, int64) для собственных типов, и иметь дело только с большим массивом, если вы собираетесь переполниться.
edit Эта реализация в codeproject, кажется, только в 7 раз медленнее... Но с вышеописанной оптимизацией вы могли бы заставить ее работать почти идентично родным типам для небольших чисел.
Я не уверен в производительности, но у IronPython также есть класс BigInteger. Он находится в пространстве имен Microsoft.Scripting.Math.
Да, это будет медленно, и разница в 10 раз о том, что я ожидал. BigInt использует массив для представления произвольной длины, и все операции должны выполняться вручную (в отличие от большинства математических операций, которые могут выполняться непосредственно с процессором)
Я даже не знаю, даст ли вам ручное кодирование в сборке большую часть прироста производительности в 10 раз, это чертовски близко. Я бы искал другие способы его оптимизации - иногда, в зависимости от вашей математической задачи, есть небольшие приемы, которые можно сделать, чтобы сделать это быстрее.
Это может показаться странным предложением, но вы проверили десятичный тип, чтобы увидеть, как быстро он работает?
Десятичный диапазон составляет от ±1,0 × 10^ -28 до ±7,9 × 10^28, поэтому он все еще может быть недостаточно большим, но он больше, чем ulong.
В.NET 3.5 должен был быть класс BigInteger, но его обрезали.
Я использовал Biginteger на предыдущей работе. Я не знаю, какие у тебя должны быть результаты. Я не использовал его в условиях высокой производительности, но у меня никогда не было проблем с этим.
Смотрите ответы в этой теме. Вам нужно будет использовать одну из доступных сторонних библиотек / классов больших целых чисел или дождаться C# 4.0, который будет включать собственный тип данных BigInteger.
Это выглядит очень многообещающе. Это C# Оболочка над GMP.
http://web.rememberingemil.org/Projects/GnuMpDotNet/GnuMpDotNet.html
Есть и другие варианты BigInteger для.Net, в частности, здесь Mpir.Net
Вы также можете использовать пакет Math.Gmp.Native Nuget, который я написал. Его исходный код доступен на GitHub, а документация доступна здесь. Он предоставляет.NET всю функциональность библиотеки GMP, которая известна как высоко оптимизированная арифметическая библиотека произвольной точности.
Целое число произвольной точности представлено типом mpz_t. Все операции над этими целыми числами начинаются с mpz_ префикс. Например, mpz_add или mpz_cmp. Примеры исходного кода приведены для каждой операции.
Это вам не поможет, но в.Net 3.5 должен был быть класс BigInteger; это было сокращено, но из заявлений, сделанных в PDC, это будет в.Net 4.0. Очевидно, они потратили много времени на его оптимизацию, поэтому производительность должна быть намного лучше, чем сейчас.
Кроме того, этот вопрос по сути является дубликатом Как я могу представить очень большое целое число в.NET?