Grands entiers en C #

Question

Actuellement, je emprunter du java.math.BigInteger à partir des bibliothèques J # décrites ici . N'ayant jamais utilisé de bibliothèque pour travailler avec de grands entiers auparavant, cela semble lent, de l'ordre de 10 fois plus lent, même pour les nombres de longueur ulong . Quelqu'un a-t-il de meilleures bibliothèques (de préférence gratuites) ou ce niveau de performance est-il normal?

Answer 1

À partir de .NET 4.0, vous pouvez utiliser la classe System.Numerics.BigInteger. Voir la documentation ici: http: // msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx

Une autre alternative est la classe IntX .

  

IntX est une précision arbitraire   bibliothèque d'entiers écrite en C # pur   2.0 avec algorithmes de multiplication / division rapides - O (N * log N)   la mise en oeuvre. Il fournit tous les   opérations de base sur des entiers comme   addition, multiplication, comparaison,   décalage binaire etc.

Answer 2

F # est également livré avec un. Vous pouvez l'obtenir à Microsoft.FSharp.Math .

Answer 3

La classe System.Numerics.BigInteger dans .NET 4.0 est basée sur Microsoft.SolverFoundation.Common.BigInteger de Microsoft Research.

La classe BigInteger de Solver Foundation semble très performante. Je ne suis pas sûr de la licence sous laquelle elle est publiée, mais vous pouvez l’obtenir ici (télécharger et installez Solver Foundation et trouvez le fichier Microsoft.Solver.Foundation.dll).

Answer 4

Je pense que vous pouvez optimiser l'implémentation si vous effectuez toutes les opérations sur BigInts qui vont renvoyer des résultats inférieurs à un type natif (par exemple, int64) sur les types natifs et ne traiter que le grand tableau si vous allez débordement.

modifier Cette mise en œuvre sur codeproject ne semble que 7 fois plus lente ... Mais avec la au-dessus de l'optimisation, vous pouvez obtenir une performance presque identique à celle des types natifs pour les petits nombres.

Answer 5

Voici plusieurs implémentations de BigInteger en C #. J'ai utilisé l'implémentation BigInteger de Mono, fonctionne assez rapidement (je l'ai utilisé dans CompactFramework)

Château gonflable

Mono

Answer 6

Je ne suis pas sûr de la performance, mais IronPython a également une classe BigInteger. C'est dans l'espace de noms Microsoft.Scripting.Math.

Answer 7

Oui, ce sera lent et la différence de 10 fois correspond à ce à quoi je m'attendais. BigInt utilise un tableau pour représenter une longueur arbitraire, et toutes les opérations doivent être effectuées manuellement (par opposition à la plupart des opérations mathématiques qui peuvent être effectuées directement avec la CPU)

Je ne sais même pas si le codage manuel à l’assemblage vous apportera un gain de performances supérieur à 10x, ce qui est tout à fait proche. Je chercherais d'autres moyens de l'optimiser - parfois, en fonction de votre problème de calcul, vous pouvez effectuer quelques petites astuces pour le rendre plus rapide.

Answer 8

J'ai utilisé Biginteger lors d'un travail précédent. Je ne sais pas quel type de performance a besoin de vous. Je ne l'ai pas utilisé dans une situation exigeante en performances, mais je n'ai jamais eu de problèmes avec.

Answer 9

Cela peut sembler une suggestion étrange, mais avez-vous déjà testé le décimal pour voir à quelle vitesse cela fonctionne?

La plage décimale est & # 177; 1.0 & # 215; 10 ^ & # 8722; 28 à & # 177; 7,9 & # 215; 10 ^ 28, il peut donc ne pas être assez grand, mais il est plus grand qu'un ulong.

Il devait y avoir une classe BigInteger dans .NET 3.5, mais il a été coupé .

Answer 10

Cela ne vous aidera pas, mais il était supposé être une classe BigInteger dans .Net 3.5; il a été coupé, mais d'après les déclarations faites à PDC, il sera en .Net 4.0 Ils ont apparemment passé beaucoup de temps à l’optimiser. Les performances devraient donc être bien meilleures que celles que vous obtenez actuellement.

De plus, cette question est essentiellement une copie de Comment puis-je représenter un très grand nombre entier dans .NET?

Answer 11

Voir les réponses dans cette fil . Vous devrez utiliser l’une des bibliothèques / classes de grand entier tierces disponibles ou attendre C # 4.0, qui inclura un type de données BigInteger natif.

Answer 12

Cela semble très prometteur. Il s’agit d’un C # Wrapper sur GMP .

http://web.rememberingemil.org/Projects/GnuMpDotNet/GnuMpDotNet/GnuMpDotNet.html

Il existe également d'autres options BigInteger pour .Net ici en particulier, Mpir.Net

Answer 13

Vous pouvez également utiliser le Math.Gmp.Native . Nuget package que j'ai écrit. Son code source est disponible sur GitHub . Une documentation est disponible ici . Il expose à .NET toutes les fonctionnalités de la bibliothèque GMP , connue sous le nom d'arithmétique à précision arbitraire hautement optimisée. bibliothèque.

Les entiers de précision arbitraire sont représentés par le mpz_t type. Les opérations sur ces entiers commencent toutes par le préfixe mpz _ . Pour des exemples, mpz_add ou mpz_cmp . Des exemples de code source sont donnés pour chaque opération.