找到10小于x的最大功率的最快方法

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

记录和电源是昂贵的操作.如果你想要快速,你可能想要在表中查找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中执行此操作,解释器开销可能会淹没日志/ exp时间,这可能无关紧要.

那么,你想要快速,还是想要短写？

EDIT 12/23:OP现在告诉我们他的"x"是不可或缺的.假设它是64(或32)位整数,我的提议仍然有效,但显然没有"IEEE_Exponent".大多数处理器都有一个"查找第一个"指令,它会告诉您左侧(最重要)部分值的0位数,例如前导零; 你很可能这实际上是64(或32)减去值的2的幂.给定exponent = 64 - leadingzeros,你有两个指数的幂,并且算法的其余部分大部分基本不变(修改留给读者).

如果处理器没有find-first-one指令,那么最好的选择是平衡判别树来确定10的幂.对于64位,这样的树将花费最多18个比较来确定指数(10 ^ 18~2 ^ 64).