Il modo più veloce per convertire binario a decimale?
https://stackoverflow.com/questions/1686004
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho quattro unsigned interi a 32 bit che rappresentano un unsigned a 128-bit integer, in poco endian:
typedef struct {
unsigned int part[4];
} bigint_t;
Mi piacerebbe convertire questo numero nella sua rappresentazione stringa decimale e l'output in un file.
In questo momento, sto usando una funzione bigint_divmod10 di dividere il numero per 10, tenendo traccia del resto. Chiamo ripetutamente questa funzione, in uscita il resto come una cifra, fino a che il numero è zero. E 'piuttosto lento. È questo il modo più veloce per farlo? Se è così, c'è un modo intelligente per implementare questa funzione che non sto vedendo? Ho provato guardando get_str.c di GMP, ma io lo trovo abbastanza impenetrabile.
EDIT: ecco il codice più veloce sono stato in grado di elaborare per la funzione divmod10:
static unsigned uint128_divmod10(uint128 *value)
{
unsigned int a = value->word[3];
unsigned int b = value->word[2];
unsigned int c = value->word[1];
unsigned int d = value->word[0];
unsigned int diva = a / 5;
unsigned int divb = b / 5;
unsigned int divc = c / 5;
unsigned int divd = d / 5;
value->word[3] = diva;
value->word[2] = divb;
value->word[1] = divc;
value->word[0] = divd;
unsigned int moda = a - diva*5;
unsigned int modb = b - divb*5;
unsigned int modc = c - divc*5;
unsigned int modd = d - divd*5;
unsigned int mod = 0;
mod += moda;
unsigned int carryb = mod*858993459;
mod += modb;
if (mod >= 5) {
mod -= 5;
carryb++;
}
unsigned int carryc = mod*858993459;
mod += modc;
if (mod >= 5) {
mod -= 5;
carryc++;
}
unsigned int carryd = mod*858993459;
mod += modd;
if (mod >= 5) {
mod -= 5;
carryd++;
}
uint128_add(value, carryd, 0);
uint128_add(value, carryc, 1);
uint128_add(value, carryb, 2);
if (value->word[0] & 1) {
mod += 5;
}
uint128_shift(value, -1);
return mod;
}
in cui la funzione aggiuntiva è definito come:
static void uint128_add(uint128 *value, unsigned int k, unsigned int pos)
{
unsigned int a = value->word[pos];
value->word[pos] += k;
if (value->word[pos] < a) {
// overflow
for (int i=pos+1; i<4; i++) {
value->word[i]++;
if (value->word[i]) {
break;
}
}
}
}
Soluzione
Dipende che cosa si sta facendo con i numeri. È possibile barattare fuori una leggera perdita di efficienza di spazio e di una modesta perdita di efficienza di multiprecisione aritmetico in cambio di conversione molto efficiente da e per decimale. La chiave è di fare multiprecisione aritmetica con una base che è una potenza di 10 piuttosto che una potenza di 2.
Ad esempio, si potrebbe utilizzare base di 10.000, dove si pack una cifra in una parola a 16 bit e fate la vostra aritmetica sulle cifre in interi a 32 bit. (Se siete su un computer a 64 bit è possibile fare doppio che e fare di base miliardo.) Questo tipo di codice è timewise relativamente efficiente, anche se non abbastanza veloce come usando il potere nativo di due, perché non si può prendere vantaggio di il bit di riporto sull'hardware. E non si può rappresentare come molti numeri interi nello stesso numero di bit. Ma è un mago a convertire da e verso decimale, perché si arriva a convertire i singoli cifre senza alcuna divisione lunga.
Se avete bisogno di rappresentare l'intera gamma di numeri da zero a ((1 << 128) - 1), si può ancora fare questo, ma aggiungere una cifra aggiuntiva, in modo da numeri saranno più grandi.
Se si scopre che in realtà bisogno di spazio extra / velocità (forse si sta facendo un sacco di crittografiche calcoli a 128 bit), allora il metodo di simultanous div / mod del 10 è il metodo più veloce che conosco. L'unico altro trucco è che se interi piccoli sono comuni, è possibile gestire loro appositamente. (Cioè, se i tre più significative parole di 32 bit sono tutti a zero, basta usare la divisione nativo da convertire.)
C'è un modo intelligente per implementare questa funzione che non sto vedendo?
di Dave Hanson C Interfacce e implementazioni ha un lungo capitolo sulla multiprecisione aritmetica. Dividendo un gran numero da una sola cifra è un caso particolare che ha questa implementazione efficiente:
int XP_quotient(int n, T z, T x, int y) {
int i;
unsigned carry = 0;
for (i = n - 1; i >= 0; i--) {
carry = carry*BASE + x[i];
z[i] = carry/y;
carry %= y;
}
return carry;
}
Per una piena comprensione, in realtà aiuta ad avere il libro, ma il codice sorgente è ancora molto più facile da capire che il codice sorgente GNU. E si potrebbe facilmente adattarsi in modo da utilizzare base di 10.000 (si utilizza attualmente di base a 256).
Sommario: se il collo di bottiglia è la conversione in decimale, implementare multiprecisione aritmetica con una base che è una potenza di 10 . Se la dimensione di parola nativa della macchina è 32 e si utilizza il codice C, utilizzare 10.000 in una parola a 16 bit.
Altri suggerimenti
Se i valori sono per lo meno di ULLONG_MAX (18446744073709551615) mi piacerebbe provare a utilizzare per loro sprintf(buf,"%llu",ullong_val). Scommetto che questo è piuttosto ben ottimizzato nella libreria standard, ma l'analisi di formato avrà alcuni cicli però.
In caso contrario, mi piacerebbe creare una funzione bigint_divmod1000000000 (nome migliore mod10to9 o) e l'uso che. Si avrebbe bisogno di 9 volte inferiore rispetto divide bigint_divmod10.
Tabella di ricerca di 8 bit. Si possono avere 4 tabelle di ricerca di 256 numeri. Primo é del 0-256 per LSB byte, seconda tabella è prima tabella moltiplicato per 256 e così via.
Così, quando è necessario il numero di somma fino numeri da tabella di ricerca. Quando l'aggiunta è possibile aggiungere come bunary e andare più tardi un passaggio sopra ogni byte per risolvere owerflows.
Esempio numero 0x12345678 In primo tabella di ricerca è sotto addres (0x78 = 120) così 0x010200 è il primo numero nella seconda tabella sotto (0x56 = 87) è 0x0202000106 (0x56 in DEC è 22016) nella terza tabella si Hou avrebbe 0x03040007080702 e sotto l'ultima etichetta a 0x12 avete 0x030001090809080808 (questo non adattarsi a 32 bit aritmetica, ma che si allredy sapere)
Poi riassumere questa numeri (come bumbers binari) e passare un solo passaggio, byte per byte per troppo pieno codice per il ciclo è qualcosa di simile
s=carry+val[i];
val[i]=val[i]&10
carry=s/10;
//you can put last two operations in table
Se contiamo le operazioni necessarie per questo.
1. (guardando in tabelle e aggiungendo) 4 tabelle di ricerca. 16 integrazioni (tenere a mente che quando non c'è bisogno di portare su Owerflow, becuase non possono OCUR)
2. un passaggio in ogni passaggio 3 operatins 16 gradini per passare.
passimistic limite superiore 6 * 16 = 100 operazioni.
EDIT:
Ecco il codice C ++, ed è il 30% più veloce di implementazione ingenuo.
#include <iostream>
#include <stdint.h>
#include <array>
static uint64_t lu[4][256];
constexpr uint64_t lookup_value(uint64_t n) {
uint64_t r = 0;
uint64_t t = 1;
while (n) {
uint64_t rem = n % 10;
n /= 10;
r += rem * t;
t *= 256;
}
return r;
}
void make_lu() {
uint64_t step = 1;
for (int j = 0; j < 4; ++j) {
uint64_t n = 0;
for (int i = 0; i < 256; ++i) {
lu[j][i] = lookup_value(n);
n += step;
}
step *= 256;
}
}
struct DivMod {
uint8_t div;
uint8_t rem;
};
static DivMod dm[256];
void make_dm() {
for (int i = 0; i < 256; ++i) {
dm[i].div = i / 10;
dm[i].rem = i % 10;
}
}
void init() {
make_lu();
make_dm();
}
uint64_t b2d(uint64_t n) {
uint64_t r = 0;
for (int i = 0; i < 4; ++i) {
r += lu[i][(n >> (i * 8)) & 0xff];
}
uint64_t r2 = 0;
uint64_t of = 0;
for (int i = 0; i < 8; ++i) {
uint64_t v = ((r >> (i * 8)) & 0xff) + of;
DivMod &x = dm[v];
of = x.div;
r2 += uint64_t(x.rem) << (i * 8);
}
return r2;
}
int main() {
init();
uint64_t n;
std::cin >> n;
std::cout << std::hex << b2d(n) << "\n";
return 0;
}
Per riferimento futuro, invece di attuare un tipo uint128, ho solo usato direttamente i caratteri della stringa. Questo si è rivelato essere molto più veloce che andare da stringa a uint128 e ritorno.
L'aumento di velocità più immediato verrà dalla inlining conversione piuttosto che chiamare funzioni; potrebbe essere semplice come la marcatura bigint_divmod10() linea , o utilizzando l'ottimizzazione del profilo-guida come offerto dal compilatore.
So che questa domanda è vecchio, ma voglio contribuire come nessuno ha messo un modo per evitare il ciclo di divisione. Questo si usa pow2, non ho ancora testato il punto di riferimento, ma in teoria dovrebbe essere più veloce di qualsiasi altro, e potrebbe anche essere ottimizzato in funzione pow pure.
#include <iostream>
#include <cmath>
using namespace std;
#define MathBintodec(arr,len)({int dec=0;int ci_;for(ci_=len;ci_--;)dec+=arr[ci_]*pow(2,len-ci_-1);dec;})
int main(){
int r[]={1,0,0,1,0,0};
cout<<MathBintodec(r,6)<<endl;
}
Output: 36
