寻找小于x的10的最大幂的最快方法

Question

有没有什么快速的方法可以找到小于给定数字的10的最大幂？

目前，我正在使用这个算法，但每当我看到它时，我内心的某种东西就会消失：

10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) )   // C

我可以分别用一个循环实现简单的log10和pow函数来解决我的问题，但我仍然想知道十进制数是否有一些魔力。

Answer 1

另一种算法是：

i = 1;
while((i * 10) < x)
    i *= 10;

Answer 2

Log和power都是昂贵的操作。如果您想要更快，您可能需要在表中查找IEEE二进制指数，以获得10的近似幂，然后检查尾数是否强制更改+1。这应该是3或4个整数机器指令(或者O(1)加上一个相当小的常量)。

给定表：

  int IEEE_exponent_to_power_of_ten[2048]; // needs to be 2*max(IEEE_exponent)
  double next_power_of_ten[600]; // needs to be 2*log10(pow(2,1024)]
  // you can compute these tables offline if needed
  for (p=-1023;p>1023;p++) // bounds are rough, see actual IEEE exponent ranges
  {  IEEE_exponent_to_power_of_ten[p+1024]=log10(pow(2,p)); // you might have to worry about roundoff errors here
     next_power_of_ten[log10(pow(2,p))+1024]=pow(10,IEEE_exponent_to_power_of_ten[p+1024]);
  }

那么你的计算应该是：

  power_of_ten=IEEE_exponent_to_power_of_10[IEEE_Exponent(x)+1023];
  if (x>=next_power_of_ten[power_of_ten]) power_of_ten++;
  answer=next_power_of_ten[power_of_ten];

你可能真的需要把这段代码写成汇编程序，这样才能挤出最后一个时钟。

但是，如果您坚持在python中执行此操作，解释器开销可能会占用log/exp时间，这可能无关紧要。

那么，你是想要快速，还是想要短文？

编辑12/23: OP现在告诉我们他的"x“是整数。在假设它是64 (或32)位整数的情况下，我的建议仍然有效，但显然没有"IEEE_Exponent“。大多数处理器都有一个"find first 1“指令，它会告诉你值的左边(最重要的)部分的0位的个数，例如，前导0；你很可能在本质上是64 (或32)减去这个值的2的幂。给定指数= 64 -前导零，你就有了两个指数的幂，而算法的其余大部分基本上没有变化(修改留给读者)。

如果处理器没有find-first-one指令，那么最好的选择可能是使用平衡判别树来确定10的幂。对于64位，这样的树最多需要18次比较才能确定指数(10^18 ~ 2^64)。

Answer 3

创建一个10次方的数组。在其中搜索小于x的最大值。

如果x相当小，您可能会发现线性搜索比二进制搜索提供了更好的性能，部分原因是分支错误预测更少。