Grandi numeri interi in C #

Question

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

Answer 1

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

Un'altra alternativa è la classe IntX .

  

IntX è una precisione arbitraria   libreria di interi scritta in C # puro   2.0 con algoritmi di moltiplicazione / divisione fast - O (N * log N)   implementazione. Fornisce tutto il   operazioni di base su numeri interi come   addizione, moltiplicazione, confronto,   spostamento bit per bit ecc.

Answer 2

F # viene fornito anche con uno. Puoi scaricarlo su Microsoft.FSharp.Math .

Answer 3

La classe System.Numerics.BigInteger in .NET 4.0 si basa su Microsoft.SolverFoundation.Common.BigInteger di Microsoft Research.

La classe BigInteger di Solver Foundation sembra molto performante. Non sono sicuro di quale licenza venga rilasciata, ma puoi ottenerlo qui (download e installa Solver Foundation e trova Microsoft.Solver.Foundation.dll).

Answer 4

Suppongo che potresti ottimizzare l'implementazione se esegui tutte le operazioni su BigInts che restituiranno risultati più piccoli di un tipo nativo (es. int64) sui tipi nativi e gestirai il grande array solo se stai per troppo pieno.

modifica Questa implementazione su codeproject , sembra solo 7 volte più lenta ... Ma con il sopra l'ottimizzazione si potrebbe ottenere per eseguire quasi identicamente ai tipi nativi per piccoli numeri.

Answer 5

Ecco alcune implementazioni di BigInteger in C #. Ho usato l'implementazione di BigInteger di Mono, funziona abbastanza velocemente (l'ho usato in CompactFramework)

Castello gonfiabile

Mono

Answer 6

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

Answer 7

Sì, sarà lento e la differenza di 10 volte riguarda ciò che mi aspetterei. BigInt utilizza un array 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 nell'assemblaggio ti darà un grande guadagno in termini di prestazioni rispetto a 10 volte, è dannatamente vicino. Cercherei altri modi per ottimizzarlo - a volte a seconda del tuo problema di matematica ci sono piccoli trucchi che puoi fare per renderlo più veloce.

Answer 8

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

Answer 9

Può sembrare uno strano suggerimento, ma hai testato decimale per vedere quanto velocemente funziona?

L'intervallo decimale è & # 177; 1.0 & # 215; 10 ^ & # 8722; 28 a & # 177; 7.9 & # 215; 10 ^ 28, quindi potrebbe non essere ancora abbastanza grande, ma è più grande di un ulong.

Doveva esistere una classe BigInteger in .NET 3.5, ma è stato tagliato .

Answer 10

Questo non ti aiuterà, ma doveva esserci una classe BigInteger in .Net 3.5; è stato tagliato, ma dalle dichiarazioni rilasciate a PDC, sarà in .Net 4.0. Apparentemente hanno speso molto tempo a 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 intero molto grande in .NET?

Answer 11

Vedi le risposte in questo thread. Dovrai utilizzare una delle librerie / classi di interi di grandi dimensioni di terze parti disponibili o attendere C # 4.0 che includerà un tipo di dati nativo BigInteger.

Answer 12

Sembra molto promettente. È un wrapper C # su GMP .

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

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

Answer 13

Puoi anche utilizzare Math.Gmp.Native Pacchetto Nuget che ho scritto. Il suo codice sorgente è disponibile su GitHub e la documentazione è disponibile qui . Espone a .NET tutte le funzionalità della libreria GMP che è nota come aritmetica di precisione arbitraria altamente ottimizzata biblioteca.

I numeri interi di precisione arbitraria sono rappresentati dal mpz_t tipo. Le operazioni su questi numeri interi iniziano tutte con il prefisso mpz_ . Ad esempio, mpz_add o mpz_cmp . Vengono forniti esempi di codice sorgente per ciascuna operazione.