qualsiasi documento che dice esattamente quale intervallo di numeri sono progettati per .NET BigIntegers?

12

Sto giocando con .NET BigInteger e sostanzialmente I mi chiedo quale numero - una risposta stimata andrebbe bene - è il punto di deviazione della curva di (il grafico di (aumento del tempo richiesto per le operazioni) vs (valore di BigInteger)) ?

o sono progettati senza tale deviazione in modo tale che se tracciamo l'aumento del tempo richiesto per le operazioni rispetto al valore di BigInteger da 1 a infinito, avremo una curva regolare fino in fondo?

ad esempio, supponendo che gli array siano progettati con la capacità di gestire 50 articoli. questo significa che se ho 1 elemento, le operazioni sono f (1) tempo. e quando ho 2 elementi, le operazioni sono f (2) volte. se ho 50 articoli, le operazioni sono f (50). ma poiché è progettato per gestire solo 50 oggetti, le operazioni eseguite quando abbiamo 51 elementi saranno g (51) dove g (51) > f (51).

If implemented properly the complexity of BigInteger arithmetic should be a smooth curve. For example the time complexity of multiplication should be O(NM) where N is the number of digits in the first multiplicand, and M is the number of digits in the second multiplicand. Of course there are practical limits in that you could pick N and M so large that the numbers wouldn't fit in your machine.

C'è qualcuno / qualcuno che conosce documenti che sostengono che sia implementato come tale?

    
posta Pacerier 02.08.2011 - 18:30
fonte

6 risposte

7

Qualsiasi numero che potrebbe essere maggiore di ULong.MaxValue o inferiore a Long.MinValue deve essere rappresentato utilizzando BigInteger.

Se NOT (Long.MinValue < = X < = ULong.MaxValue) Then BigInteger

BigInteger è troppo grande per numeri che i normali primitivi possono gestire.

Ad esempio, se il numero intero non rientra nell'intervallo di Long, probabilmente dovresti usare BigInteger. Questi casi sono molto rari e l'utilizzo di queste classi ha un overhead significativamente più alto rispetto alle loro controparti primitive.

Ad esempio, long è largo 64 bit e può contenere l'intervallo: -9,223,372,036,854,775,808 a 9,223,372,036,854,775,80. ulong può contenere da 0 a 18.446.744.073,709,551,615. Se i tuoi numeri sono più grandi o più piccoli, BigInteger è la tua unica opzione

L'unica volta che li ho visti usati in un'applicazione reale era un'applicazione starchartting.

Vedi anche: Primitive Ranges in .NET

    
risposta data 02.08.2011 - 18:43
fonte
4

In un certo senso il punto di BigInteger non è tanto la dimensione assoluta quanto la precisione illimitata. Anche i numeri in virgola mobile possono essere molto grandi, ma hanno una precisione limitata. BigInteger consente di eseguire operazioni aritmetiche senza preoccuparsi di errori di arrotondamento o di overflow. Il prezzo che paghi è che è centinaia di volte più lento dell'aritmetica con numeri interi o numeri in virgola mobile.

Come altri hanno sottolineato, ulong può contenere da 0 a 18.446.744.073,709,551,615, e fintanto che rimani in quell'intervallo puoi fare l'aritmetica esatta. Se passi anche 1 oltre tale intervallo otterrai un overflow, quindi la risposta alla tua domanda è BigInteger se hai bisogno di calcoli aritmetici esatti e c'è qualche possibilità che qualsiasi risultato intermedio superi 18.446.744.073,709,551,615.

La maggior parte dei problemi di scienza, ingegneria e finanza possono convivere con le approssimazioni forzate da numeri in virgola mobile e non possono permettersi il costo in termini di tempo dell'aritmetica di BigInteger. La maggior parte dei calcoli commerciali non può vivere con le approssimazioni dell'aritmetica in virgola mobile, ma funziona nell'intervallo compreso tra 0 e 18,446,744,073,709,551,615, quindi è possibile utilizzare l'aritmetica ordinaria. BigInteger è necessario quando si usano algoritmi dalla teoria dei numeri che include cose come la crittografia (si pensi a numeri primi di 50 cifre). A volte viene utilizzato anche in applicazioni commerciali quando sono necessari calcoli esatti, la velocità non è troppo importante e l'impostazione di un corretto sistema di punti decimali è troppo problematica.

Se implementato correttamente, la complessità dell'aritmetica di BigInteger dovrebbe essere una curva fluida. Ad esempio, la complessità temporale della moltiplicazione dovrebbe essere O (NM) dove N è il numero di cifre nel primo multiplo e M è il numero di cifre nel secondo multiplo. Naturalmente ci sono dei limiti pratici in quanto potresti scegliere N e M così grandi che i numeri non si adattano alla tua macchina.

Se cerchi google "Computational complex of biginteger" otterrai più riferimenti di quanti ne puoi scuotere. Uno che parla direttamente alla tua domanda è questo: Confronto di due pacchetti aritmetici di precisione arbitraria .

    
risposta data 02.08.2011 - 21:52
fonte
4

Limite di memoria

BigInteger si basa su array int per l'archiviazione. Assumendo ciò, il limite teorico per il numero massimo, che BigInteger è in grado di rappresentare, può essere ricavato dalla dimensione massima dell'array disponibile in .net. C'è un argomento SO sugli array qui: Individuazione della quantità di memoria che posso allocare per un array in C # .

Supponendo di conoscere la dimensione massima dell'array, possiamo stimare il numero massimo, che BigInteger può rappresentare: (2 ^ 32) ^ max_array_size, dove:

  • 2 ^ 32 - numero massimo nella cella dell'array (int)
  • max_array_size - dimensione massima consentita di array int che è limitata dalla dimensione dell'oggetto di 2 GB

Questo dà un numero con 600 milioni di cifre decimali.

Limite delle prestazioni

Per quanto riguarda le prestazioni, BigInteger utilizza l'algoritmo Karatsuba per la moltiplicazione e l'algoritmo lineare per l'aggiunta. La complessità della moltiplicazione è ,ciòsignificachesiridimensioneràabbastanzabeneancheperigrandinumeri( Grafico di complessità ), tuttavia è ancora possibile colpire la penalizzazione delle prestazioni in base alla dimensione della RAM e la cache del processore.

Finora, dato che la dimensione massima del numero è limitata a 2 GB, sul dispositivo di discesa non si noterà un gap prestazionale imprevisto, ma il funzionamento su numeri di 600 milioni di cifre sarà comunque lento.

    
risposta data 02.08.2011 - 23:16
fonte
1

Il limite è la dimensione della tua memoria (e il tempo che hai). Quindi, puoi avere numeri veramente grandi. Come detto da Kevin, nella crittografia si devono moltiplicare o esponenziare i numeri con alcune migliaia di cifre (binarie), e questo è possibile senza problemi.

Naturalmente, spesso gli algoritmi diventano più lenti man mano che i numeri diventano più grandi, ma non così tanto più lentamente.

Quando si utilizzano numeri nell'intervallo di cifre minime, si potrebbe voler pensare ad altre soluzioni, tuttavia, poiché anche il calcolo con esse diventa lento.

    
risposta data 02.08.2011 - 20:41
fonte
0

Ci sono alcuni usi all'interno della comunità scientifica (cioè la distanza tra galassie, il numero di atomi in un campo di erba, ecc.)

    
risposta data 02.08.2011 - 18:36
fonte
0

Come suggerisce la risposta di kevin cline, i BigNumbers sono stati aggiunti alle librerie .NET in primo luogo perché erano necessari come base per molti algoritmi crittografici moderni (firme digitali, crittografia a chiave pubblica / privata, ecc.). Molti algoritmi di crittografia moderni implicano calcoli su valori interi con dimensioni fino a diverse migliaia di bit. Poiché la classe BigNumber descrive una classe ben definita e utile, ha deciso di renderla pubblica (piuttosto che mantenerla come un dettaglio interno delle API crittografiche).

    
risposta data 02.08.2011 - 22:37
fonte

Leggi altre domande sui tag