algorithm - Fastest way to find the largest power of 10 smaller than x

Question

Is there any fast way to find the largest power of 10 smaller than a given number?

I'm using this algorithm, at the moment, but something inside myself dies anytime I see it:

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

I could implement simple log10 and pow functions for my problems with one loop each, but still I'm wondering if there is some bit magic for decimal numbers.

score 7 · Accepted Answer

7

另一种算法是：

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

于 2010-12-22T21:11:59.900 回答

score 6 · Accepted Answer

日志和电源是昂贵的操作。如果您想要快速，您可能需要在表中查找 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”。大多数处理器都有一个“查找第一个”指令，它会告诉您值左侧（最高有效）部分的 0 位数，例如前导零；你很可能这本质上是 64（或 32）减去 2 的幂的值。给定指数 = 64 - 前导零，你有两个指数的幂，算法的其余部分基本上没有变化（修改留给读者）。

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

score 4 · Accepted Answer

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

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

score 3 · Accepted Answer

据我所知，渐近最快的方法涉及重复平方。

func LogFloor(int value, int base) as int
    //iterates values of the form (value: base^(2^i), power: 2^i)
    val superPowers = iterator
                          var p = 1
                          var c = base
                          while c <= value
                              yield (c, p)
                              c *= c
                              p += p
                          endwhile
                      enditerator

    //binary search for the correct power
    var p = 0
    var c = 1
    for val ci, pi in superPowers.Reverse()
        if c*ci <= value
            c *= ci
            p += pi
        endif
    endfor

    return p

该算法在 N 中取对数时间和空间，这与 N 的表示大小成线性关系。[时间限制可能有点差，因为我乐观地简化了]

请注意，我假设了任意大的整数（注意溢出！），因为在处理 32 位整数时，简单的 times-10-until-over 算法可能足够快。

score 1 · Accepted Answer

我认为最快的方法是 O(log(log(n))^2)，while 循环需要 O(log(log(n)) 并且它可以是递归调用有限时间（我们可以说 O(c) 在哪里看到是常数），第一次递归调用需要 log(log(sqrt(n))) 时间秒需要 .. 并且 sqrt(sqrt(sqrt....(n)) < 10 中的 sqrt 数是 log(log( n)) 和常数，因为机器的限制。

    static long findPow10(long n)
    {
        if (n == 0)
            return 0;

        long i = 10;
        long prevI = 10;
        int count = 1;

        while (i < n)
        {
            prevI = i;
            i *= i;
            count*=2;
        }

        if (i == n)
            return count;

        return count / 2 + findPow10(n / prevI);
    }

score 1 · Accepted Answer

1

在 Python 中：

10**(len(str(int(x)))-1)

于 2016-06-22T16:25:01.110 回答

score 0 · Accepted Answer

鉴于这是与语言无关的，如果你能得到这个数字重要的 2 的幂，例如 x*2^y 中的 y （这是数字的存储方式，尽管我不确定我是否见过以我使用过的任何语言访问 y 的简单方法）然后如果

z = int(y/(ln(10)/ln(2)))

（一个浮点除法）

10^z 或 10^(z+1) 将是您的答案，尽管 10^z 仍然不是那么简单（希望得到纠正）。

score 0 · Accepted Answer

我使用 C++ 中的以下变体对这些方法进行计时，以将值a作为一个size_t类型（内联提高了性能，但不改变相对顺序）。

尝试1：乘以直到找到数字。

size_t try1( size_t a )
{
  size_t scalar = 1ul;
  while( scalar * 10 < a ) scalar *= 10;
  return scalar;
}

尝试 2：多路 if（也可以使用查找表进行编程）。

size_t try2( size_t a )
{
  return ( a < 10ul ? 1ul :
   ( a < 100ul ? 10ul :
   ( a < 1000ul ? 100ul :
   ( a < 10000ul ? 1000ul :
   ( a < 100000ul ? 10000ul :
   ( a < 1000000ul ? 100000ul :
   ( a < 10000000ul ? 1000000ul :
   ( a < 100000000ul ? 10000000ul :
   ( a < 1000000000ul ? 100000000ul :
   ( a < 10000000000ul ? 1000000000ul :
   ( a < 100000000000ul ? 10000000000ul :
   ( a < 1000000000000ul ? 100000000000ul :
   ( a < 10000000000000ul ? 1000000000000ul :
   ( a < 100000000000000ul ? 10000000000000ul :
   ( a < 1000000000000000ul ? 100000000000000ul :
   ( a < 10000000000000000ul ? 1000000000000000ul :
   ( a < 100000000000000000ul ? 10000000000000000ul :
   ( a < 1000000000000000000ul ? 100000000000000000ul :
   ( a < 10000000000000000000ul ? 1000000000000000000ul :
         10000000000000000000ul )))))))))))))))))));
 }

尝试 3：修改自 @Saaed Amiri 的 findPow10，它使用平方比尝试 1 更快地找到非常大的幂。

size_t try3( size_t a )
{
  if (a == 0)
    return 0;
  size_t i, j = 1;
  size_t prev = 1;
  while( j != 100 )
  {
    i = prev;
    j = 10;
    while (i <= a)
    {
      prev = i;
      i *= j;
      j *= j;
    }
  }
  return prev;
}

尝试 4：根据@Ira Baxter 使用计数前导零指令索引的查找表。

static const std::array<size_t,64> ltable2{
1ul, 1ul, 1ul, 1ul, 1ul, 10ul, 10ul, 10ul,
100ul, 100ul, 100ul, 1000ul, 1000ul, 1000ul,
1000ul, 10000ul, 10000ul, 10000ul, 100000ul,
100000ul, 100000ul, 1000000ul, 1000000ul,
1000000ul, 1000000ul, 10000000ul, 10000000ul,
10000000ul, 100000000ul, 100000000ul,
100000000ul, 1000000000ul, 1000000000ul,
1000000000ul, 1000000000ul, 10000000000ul,
10000000000ul, 10000000000ul, 100000000000ul,
100000000000ul, 100000000000ul, 1000000000000ul,
1000000000000ul, 1000000000000ul, 1000000000000ul,
10000000000000ul, 10000000000000ul, 10000000000000ul,
100000000000000ul, 100000000000000ul, 100000000000000ul,
1000000000000000ul, 1000000000000000ul, 1000000000000000ul,
1000000000000000ul, 10000000000000000ul, 10000000000000000ul,
10000000000000000ul, 100000000000000000ul, 100000000000000000ul,
100000000000000000ul, 100000000000000000ul, 1000000000000000000ul,
1000000000000000000ul };
size_t try4( size_t a )
{
  if( a == 0 ) return 0;
  size_t scalar = ltable2[ 64 - __builtin_clzl(a) ];
  return (scalar * 10 > a ? scalar : scalar * 10 );
}

时序如下（gcc 4.8）

for( size_t i = 0; i != 1000000000; ++i) try1(i)    6.6
for( size_t i = 0; i != 1000000000; ++i) try2(i)    0.3
for( size_t i = 0; i != 1000000000; ++i) try3(i)    6.5
for( size_t i = 0; i != 1000000000; ++i) try4(i)    0.3
for( size_t i = 0; i != 1000000000; ++i) pow(10,size_t(log10((double)i)))
                                                   98.1

lookup/multiway-if 胜过 C++ 中的一切，但要求我们知道整数是有限大小的。对于循环结束值的较小值，对于较大的节拍，try3比在此测试中要慢。在 python 中，事情变得困难，因为整数不受限制，所以我会结合起来快速处理数字到一个固定的限制，然后处理可能非常大的数字。try1try3try1try2try3

在 python 中，我认为使用列表推导式查找可能比多路-if 更快。

# where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]

algorithm - Fastest way to find the largest power of 10 smaller than x

8 回答 8

Related

Reference