Calcolo di un ordine di grandezza rotondo

Question

Per un progetto semplice devo rendere leggibili numeri grandi (ad es. 4294967123), quindi sto scrivendo solo le prime cifre con un prefisso (4294967123 - > 4.29G, 12345 - > 12.34K ecc.)

Il codice (semplificato) è simile al seguente:

const char* postfixes=" KMGT";
char postfix(unsigned int x)
{
     return postfixes[(int) floor(log10(x))];
}

Funziona, ma penso che ci sia una soluzione più elegante / migliore rispetto al calcolo del logaritmo di precisione, arrotondandolo e trasformandolo nuovamente in un int.

Altre soluzioni a cui ho pensato:

int i=0;
for(; x >= 1000 ; ++i) x/=1000;
return postfixes[i];

(Questo è significativamente più lento, ma più facile da leggere)

I numeri sono distribuiti secondo la legge di Benford e il numero deve essere trattato come un numero di 64 bit senza segno, poiché non dovrebbe esserci alcun errore di arrotondamento vicino a 10 ^ x (ad es. in python math.log (1000,10 ) restituisce 2.999996, che viene portato a 2). C'è qualche altro modo veloce e preciso che mi manca?

Answer 1

Il tuo codice log10 / floor è perfettamente leggibile e il suo costo di prestazione sarà probabilmente ridotto da quello della formattazione della stringa che successivamente eseguirai sul tuo output.

Tuttavia, supponiamo che dovessi davvero aver bisogno della performance ...

Nota che log10 (x) == log2 (x) / log2 (10) == log2 (x) * 1 / log2 (10)

1 / log2 (10) è una costante

log2 (x) di solito può essere eseguito a buon mercato nella pipeline intera su architetture moderne usando istruzioni come CLZ o un bit twiddling hack , producendo un numero compreso tra 0 e 63 per un numero intero a 64 bit. Questo si adatta a 6 bit, lasciandoci fino a 58 bit dopo il punto di radice utilizzabile per l'aritmetica a punto fisso in un tipo a 64 bit.

Quindi possiamo quindi usare l'aritmetica a virgola fissa per trovare il log10:

unsigned long long integer_log10( unsigned long long _in )
{
    unsigned long long log10fp6x58 = 0x134413509f79ff0llu; // (unsigned long long) (double(1llu<<58) / log2(10.0))
    return (((integer_log2(_in)) * log10fp6x58)+(1llu<<57)) >> 58;
}

L'implementazione di integer_log2 dipende dal compilatore / dalla piattaforma; per esempio. su GCC / PowerPC, è

unsigned long long integer_log2( unsigned long long _in )
{
    return 63 - __cntlzd(_in);
}

Questo approccio può essere generalizzato per trovare il logaritmo di qualsiasi base, è sufficiente calcolare la costante appropriata come descritto sopra.

Answer 2

Questo è il metodo più diretto e semplice che mi viene in mente ... e forse sarà un po 'più veloce rispetto al calcolo del logaritmo:

postfixes = {{1e12, "T"},
             {1e9,  "G"},
             {1e6,  "M"},
             {1e3,  "K"}}

for each postfix in postfixes{
    if(x > postfix.value){
        return (x / postfix.value) + postfix.letter;
    }
}

return x;

Answer 3

Non armeggiare con il numero, invece s (n) stampa il numero in a stringa usando "% E " ;, quindi sostituisci opportunamente E + 00 E + 03 E + 09 (ecc.) (IIRC, dovresti ottenere poteri di 3 solo con notazione scientifica - che è quello che vuoi).

char number_buff[30];
snprintf(number_buff, 29, "%E", x);
char *powered_number_string = substitute_powers(number_buff);

char * substitute_powers (const char * number_buff) è disordinato in C.

sed sarebbe qualcosa di simile

-e s / E + 0 // -e s / E + 3 / K / -e s / E + 6 / M / -e s / E + 9 / G /

Answer 4

Converti il ??numero in una stringa e usa la lunghezza delle stringhe. Questo non è certamente più veloce, ma sarà molto preciso. Puoi quindi continuare e utilizzare direttamente la stringa per creare il risultato tagliandolo in modo appropriato.

Answer 5

Prima di tutto, se hai bisogno di formattare uno zero, non vuoi prendere il logaritmo di quello. In secondo luogo, vuoi qualcosa di carino, quindi non vuoi, ad esempio, "1000 M" per 999.800.000. Terzo, probabilmente vuoi arrotondare.

Ti suggerisco di usare qualcosa di simile a questo pseudocodice:

function format(long x by value)
int p=5, char suf
if x<100000 then return string(x)
if x>=10000000000000 then
   x/=100000000
   p+=8
if x>=1000000000 then
   x/=10000
   p+=4
if x>=10000000 then
   x/=100
   p+=2
if x>=1000000 then
   x/=10
   p+=1
x+=5
if x>=100000 then
   x/=10
   p+=1
switch(p/3)
   6: suf='E'
   5: suf='P'
   4: suf='T'
   3: suf='G'
   2: suf='M'
   1: suf='K'
switch(p mod 3)
   2: return format("000 A",x/1000,suf)
   1: return format("00.0 A",x/10000,(x%10000)/100,suf)
   0: return format("0.00 A",x/100000,(x%100000)/100,suf)
end function