Grandi numeri interi in C #

Attualmente sto prendendo in prestito java.math.BigInteger dalle librerie J # come descritto qui . Non avendo mai usato una libreria per lavorare con interi di grandi dimensioni prima, questo sembra lento, nell’ordine di 10 volte più lento, anche per numeri di lunghezza ulong lunghi. Qualcuno ha delle migliori (preferibilmente gratuite) librerie, o questo livello di prestazioni è normale?

A partire da. NET 4.0 è ansible utilizzare la class System.Numerics.BigInteger. Vedere la documentazione qui: http://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx

Un’altra alternativa è la class IntX .

IntX è una libreria di numeri interi arbitraria di precisione scritta in puro C # 2.0 con implementazione di algoritmi di moltiplicazione / divisione rapida – O (N * log N). Fornisce tutte le operazioni di base su numeri interi come addizione, moltiplicazione, confronto, spostamento bit a bit, ecc.

F# viene fornito con uno. È ansible scaricarlo in Microsoft.FSharp.Math .

La class System.Numerics.BigInteger in .NET 4.0 è basata su Microsoft.SolverFoundation.Common.BigInteger di Microsoft Research.

La class BigInteger della Solver Foundation sembra molto performante. Non sono sicuro di quale licenza sia rilasciata, ma puoi scaricarla qui (scarica e installa Solver Foundation e trova Microsoft.Solver.Foundation.dll).

Immagino che potresti ottimizzare l’implementazione se esegui tutte le operazioni su BigInts che restituiranno risultati inferiori a un tipo nativo (ad esempio int64) nei tipi nativi e gestiranno solo il grande array se stai per overflow.

modifica Questa implementazione su codeproject sembra solo 7 volte più lenta … Ma con l’ottimizzazione di cui sopra è ansible farla eseguire quasi identicamente a tipi nativi per piccoli numeri.

Qui ci sono diverse implementazioni di BigInteger in C #. Ho usato l’implementazione di BigInteger di Mono, funziona abbastanza velocemente (l’ho usato in CompactFramework)

Castello gonfiabile

Mono

Non sono sicuro delle prestazioni, ma IronPython ha anche una class BigInteger. È nello spazio dei nomi Microsoft.Scripting.Math.

Sì, sarà lento e la differenza 10x riguarda ciò che mi aspetterei. BigInt utilizza una matrice per rappresentare una lunghezza arbitraria e tutte le operazioni devono essere eseguite manualmente (al contrario della maggior parte della matematica che può essere eseguita direttamente con la CPU)

Non so nemmeno se codificarlo a mano in assembly ti darà un guadagno di prestazioni superiore a 10x, che è dannatamente vicino. Cercherò altri modi per ottimizzarlo, a volte a seconda del tuo problema di matematica ci sono piccoli trucchi che puoi fare per renderlo più veloce.

Ho usato Biginteger in un precedente lavoro. Non so che tipo di prestazioni hai bisogno. Non l’ho usato in una situazione ad alta intensità di prestazioni, ma non ho mai avuto problemi con esso.

Questo può sembrare uno strano suggerimento, ma hai provato il tipo decimale per vedere quanto velocemente funziona?

L’intervallo decimale è compreso tra ± 1,0 × 10 ^ -28 e ± 7,9 × 10 ^ 28, quindi potrebbe non essere abbastanza grande, ma è più grande di un ulong.

Doveva esserci una class BigInteger in .NET 3.5, ma è stata tagliata .

Questo non ti aiuterà, ma ci doveva essere una class BigInteger in .Net 3.5; è stato tagliato, ma dalle dichiarazioni fatte a PDC, sarà in. Net 4.0. A quanto pare hanno speso un sacco di tempo per ottimizzarlo, quindi le prestazioni dovrebbero essere molto migliori di quelle che stai ottenendo ora.

Inoltre, questa domanda è essenzialmente un duplicato di Come posso rappresentare un numero intero molto grande in .NET?

Vedi le risposte in questa discussione . Sarà necessario utilizzare una delle librerie / classi di interi interi di terze parti disponibili o attendere C # 4.0 che includa un tipo di dati BigInteger nativo.

Questo sembra molto promettente. È un wrapper C # su GMP .

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

Ci sono anche altre opzioni di BigInteger per .Net qui, in particolare, Mpir.Net