Ho una stringa di lunghezza arbitraria che rappresenta un valore intero decimale e conversione di questa stringa in un grande numero intero in formato binario unita (non BCD, più di 64 bit).quanti byte devono mantenere in N cifre decimali
Sto cercando una buona stima semplice quanti byte terrà cifre decimali N di sicuro senza l'utilizzo di aritmetica in virgola mobile.
Senza usare aritmetica in virgola mobile: Per N cifre decimali, è necessario
(98981 * N)/238370 + 1
byte. 98981/238370 è una buona approssimazione razionale (dall'alto) a (il 9 th convergente), la divisione intera tronca, quindi aggiungere 1. La formula è stretta per N < 238370, il numero di byte necessario per rappresentare 10^N - 1 è esattamente indicato da ciò, sovrastima per N un multiplo di 238370 e molto grandeN. Se non hai troppa paura di allocare troppo il byte dispari, puoi anche utilizzare (267 * N)/643 + 1, (49 * N)/118 + 1, (5 * N)/12 + 1 oppure, sprecando circa il 10% di spazio, (N + 1)/2.
Come sottolinea @Henrick Hellström, in Delphi si dovrebbe usare l'operatore div per la divisione in interi (manca il tag delphi).
Per chiarezza, l'operatore/risulterà in una divisione in virgola mobile. Utilizzare l'operatore div. –
Si potrebbe essere cercate fixed point arithmetic
Il valore massimo di un tipo a virgola fissa è semplicemente il valore più grande che può essere rappresentato nel tipo intero sottostante, moltiplicato per il fattore di scala ; e allo stesso modo per il valore minimo. Ad esempio, considerare un tipo di punto fisso rappresentato come un numero intero con bit b nel formato a complemento di due, con un fattore di scala di 1/2 (ovvero gli ultimi bit di f sono bit di frazione): il minimo rappresentabile il valore è -2b-1/2f e il valore massimo è (2b-1-1)/2f.
Questi bit sono necessari: ceil(N/log10(2)). Arrotondare al prossimo multiplo di 8, cioè, ceil((N/log10(2))/8)+1 byte.
Aggiungerei un bit di sicurezza per tenere conto degli errori di arrotondamento. – CodesInChaos
Senza aritmetica in virgola mobile: poiché log10 (2) = ~ 3.3, puoi semplicemente calcolare 'N * 3.5/8 = (N * 3 + N/2)/8'. @CodeInChaos: 'ceil' dovrebbe radunare. In ogni caso, la formula solo intero sovrastimerà. – zvrba
Penso che una semplice stima può essere basata sul fatto che 10 bit contengono sicuramente 3 cifre decimali. – kludg
((size_t)ceil(N/log10(2)) + CHAR_BIT - 1)/CHAR_BIT
Ora, 1/log10(2) ~ = 3.32 può essere approssimata come 10.0/3 = 3.3(3).
Così, senza virgola mobile sarebbe al massimo (((size_t)N*10+2)/3 + CHAR_BIT - 1)/CHAR_BIT C byte.
orologio per overflow quando N è grande.
1) La tua libreria big int ha una funzione 'Length'? 2) Perché vuoi evitare il virgola mobile? – CodesInChaos
Dipenderà da come viene memorizzato. Per la codifica standard, ogni cifra utilizza 4 bit, quindi nBytes = (nDigits + 1)/2. Dovresti anche considerare l'uso della compressione, anche della compressione in memoria, con un algoritmo veloce. Il rapporto varierà, ma risparmierai sicuramente spazio. Vedi anche se i tuoi dati potrebbero avere alcuni pattern, come la memorizzazione di un delta tra i valori (dopo l'ordinamento ad es.), Che aumenterà ancora di più la compressione. –