Calculando uma ordem rodada de magnitude

Question

Para um projeto simples que eu tenho que fazer um grande número (por exemplo, 4294967123) legível, por isso estou escrevendo apenas os primeiros dígitos com um prefixo (4294967123 -> 4,29 g, 12345 -.> 12.34K etc)

O código (simplificado) se parece com isso:

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

Ele funciona, mas eu acho que há uma solução mais elegante / melhor do que calcular o logaritmo precisão total, arredondando-lo e convertê-lo para baixo para um int novamente.

Outras soluções Pensei:

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

(Isto é significativamente mais lento, mas mais fácil de ler)

Os números são distribuídos entre acordo com a Lei de Benford e o número devem ser tratados como sem sinal bit-série 64, como deve haver nenhum erro de arredondamento perto de 10 ^ x (por exemplo, em python math.log(1000,10) retornos 2.999996, que fica com piso de 2) . Existe alguma rápido, outra maneira exata que eu estou ausente?

Answer 1

Seu código log10 / chão é perfeitamente legível, e seu custo desempenho provavelmente será ofuscado pelo que da seqüência de formatação que serão posteriormente fazendo em sua saída.

No entanto, suponha que você realmente precisa do desempenho ...

Note-se que log10 (x) == log2 (x) / log 2 (10) == log2 (x) * 1 / log2 (10)

1 / log2 (10) é uma constante

log2 (x) podem geralmente ser realizada de forma barata na calha inteira em arquitecturas modernas usando instruções tais como CLZ ou um pouco twiddling corte , produzindo um número entre 0 e 63 para um número inteiro de 64-bit. Que se encaixa em 6 bits, deixando-nos até 58 bits depois do ponto utilizável radix para aritmética de ponto fixo em um tipo de 64-bit.

Assim, podemos então usar aritmética de ponto fixo para encontrar o 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;
}

A implementação de integer_log2 é compilador / dependente de plataforma; por exemplo. no GCC / PowerPC, é

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

Esta abordagem pode ser generalizada para encontrar o logaritmo de qualquer base, basta calcular a constante apropriada como descrito acima.

Answer 2

Este é o método mais fácil e simples que posso pensar ... e talvez ele vai ser um pouco mais rápido do que calcular o 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

Do not fiddle com o número, em vez s (n) printf o número em um cadeia utilizando "% E", em seguida, substituir de forma adequada para E + 00 E + 03 E + 09 (Etc) (IIRC, você só deve obter poderes de 3 com notação científica -. Que é o que você quer)

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) é confuso em C.

sed seria algo como

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

Answer 4

Converter o número em uma string e usar o comprimento cordas. Isso não é mais rápido, certamente, mas vai ser muito preciso. Você pode, em seguida, vá em frente e usar a string diretamente para construir o resultado por corte-lo adequadamente.

Answer 5

Em primeiro lugar, se você precisar formatar um zero, você não quer ser tomado o logaritmo do que isso. Em segundo lugar, você quer algo muito, para que você não quer, por exemplo, "1000M" para 999800000. Em terceiro lugar, você provavelmente vai querer arredondamento.

Eu sugiro que você usar algo como isto pseudocódigo:

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