计算大小的圆秩序 [英] Calculating a round order of magnitude

问题描述

对于一个简单的项目，我必须作出大量的（例如4294967123）可读的，所以我只写了preFIX第一个数字（4294967123 - > 4.29G，12345 - > 12.34K等）

For a simple project I have to make large numbers (e.g. 4294967123) readable, so I'm writing only the first digits with a prefix (4294967123 -> 4.29G, 12345 -> 12.34K etc.)

在code（简体）看起来是这样的：

The code (simplified) looks like this:

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

它的工作原理，但我认为还有比计算满precision数，舍入并重新铸造它归结为一个int一个更优雅的/更好的解决方案。

It works, but I think that there's a more elegant/better solution than computing the full precision logarithm, rounding it and casting it down to an int again.

其他的解决方案我认为是：

Other solutions I thought of:

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

（这是显著慢一些，但是更容易阅读）

(This is significantly slower, but easier to read)

中的数字是根据本福德定律与数字之间的分配应被视为无符号的64位号码，应该有附近没有舍入误差10 ^ X（如在python 将Math.log（ 1000,10）返回2.999996，这将会给地板2）。
是否有我丢失的快速，准确的其他办法吗？

The numbers are distributed between according to Benford's Law and the number should be treated as unsigned 64 bit-number, as there should be no rounding error near 10^x (e.g. in python math.log(1000,10) returns 2.999996, which gets floored to 2). Is there any fast, accurate other way I'm missing?

推荐答案

您日志10 /地板code是完全可读的，其性能成本很可能会通过字符串格式化您以后将做相形见绌您输出。

Your log10/floor code is perfectly readable, and its performance cost will likely be dwarfed by that of the string formatting you will subsequently be doing on your output.

但是，假设你要的真正的所需要的性能......

However, suppose you were to really need the performance...

请注意该日志10（x）的== LOG2（X）/ LOG2（10）== LOG2（X）* 1 / LOG2（10）

Note that log10(x) == log2(x) / log2(10) == log2(x) * 1/log2(10)

1 / LOG2（10）是一个常数

1/log2(10) is a constant

LOG2（X）通常可以廉价地在整数流水线上使用，如CLZ或位指令现代建筑进行摆弄黑客，产生了64位整数0和63之间的数字。适合于6位，给我们留下高达58位可用于在64位型定点算术小数点后。

log2(x) can usually be performed cheaply in the integer pipeline on modern architectures using instructions such as CLZ or a bit twiddling hack, yielding a number between 0 and 63 for a 64-bit integer. That fits in 6 bits, leaving us up to 58 bits after the radix point usable for fixed point arithmetic in a 64-bit type.

因此​​，我们就可以使用定点运算找到log10的：

So we can then use fixed-point arithmetic to find the 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;
}

integer_log2的实现是编译器/平台的依赖;例如在GCC / PowerPC的，这是

The implementation of integer_log2 is compiler/platform-dependent; e.g. on GCC/PowerPC, it's

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

此方法可以概括为找到任何碱的对数，如上所述简单地计算合适的恒定

This approach can be generalised for finding the logarithm of any base, simply calculate the appropriate constant as described above.

这篇关于计算大小的圆秩序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！