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

Question

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

11

有没有一种快速的方法来找到一个给定数字小于最大的10的幂次方？

目前我正在使用这个算法，但每次看到它都会内心崩溃：

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

我可以使用一个循环分别实现简单的log10和pow函数来解决我的问题，但我仍然想知道是否有针对十进制数字的一些位运算技巧。

- peoro

这有什么问题吗？平均执行10 **（int（math.log10（987654321987654321）））需要0.0161微秒，实际上相当令人印象深刻。 - Rafe Kettler

4

我们是在讨论整数还是浮点数？ - aronp

最快的算法可能会取决于 x 的大小。您可能需要对混合方法进行分析。 - Nick Larsen

在我的情况下，x是一个整数，但我猜它不会有太大改变（可以将浮点类型的x强制转换为整型值，反之亦然）。 - peoro

我的答案在理论上比其他人更快，对于大数字非常有用，而不是10位数。 - Saeed Amiri

8个回答

6

记录日志和求幂是代价昂贵的操作。如果您想要快速，您可能需要查找IEEE二进制指数表以获取十的近似幂次，然后检查尾数是否强制进行+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编写，解释器的开销可能会淹没对数/指数运算所需的时间，这时速度可能并不重要。

所以，您想要快速还是想要写得简短？

编辑12/23：原帖现在告诉我们他的"x"是整数。在假设它是64（或32）位整数的情况下，我的建议仍然有效，但显然没有“IEEE_Exponent”。大多数处理器都有一个“查找第一个1”的指令，可以告诉您值左侧（最高有效位）部分的0位数，例如前导零；您可能需要将其转换为64（或32）减去该值的2的幂次方。假设exponent = 64 - leadingzeros，则具有2的幂次方指数，大部分算法基本上没有改变（修改留给读者）。

如果处理器没有查找第一个1的指令，那么最好的选择可能是使用平衡判别树来确定10的幂次。对于64位，这样的树最多需要18次比较才能确定指数（10^18 ~~ 2^64）。

- Ira Baxter

不，我不会用Python做这个 - 这应该是一种语言无关的算法 - 只是想展示我的当前算法在几种语言中，以使其更清晰，但这可能是个坏主意... - peoro

2

日志和幂运算是昂贵的操作。在没有超越运算的硬件支持的情况下，这显然是正确的。但是，在消费级通用CPU（现代x86、Power、x86_64等）上，我们要谈论多慢呢？ - dmckee --- ex-moderator kitten

如果您不想使用浮点数，可以通过使用计算前导零的汇编指令来实现类似的整数方案。 - Keith Randall

即使有内置浮点数，三角函数的执行也需要一些时间。芯片供应商不再愿意告诉你任何东西的精确时钟计数，但很难相信你可以在几个时钟周期内实现高精度浮点数。我的方案只需要几个整数指令（甚至明显的浮点比较也可以通过整数指令完成，因为IEEE是如何定义的！）似乎很难被击败。这值得吗？可能不值得，除非OP在内部循环中反复执行此操作。但他没有问是否值得麻烦 :-} - Ira Baxter

不错的解决方案！我现在不打算实现它：它似乎相当复杂，但如果需要进一步优化我选择的解决方案，我会考虑实现它。 - peoro

4

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

如果x很小，你可能会发现线性搜索比二进制搜索提供更好的性能，这部分归功于较少的分支错误预测。

- Dijkstra

3

据我所知，渐进最快的方式涉及到反复平方运算。

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位整数时，朴素的乘10直到溢出算法可能已经足够快了。

- Craig Gidney

1

@Yonatan 缩进是有意的。它使迭代器块的内容保持在块分隔符的右侧。 - Craig Gidney

至于之前的解决方案，它很不错！我现在不打算实现它：它似乎相当复杂，但如果需要进一步优化我选择的解决方案，我会考虑实现它。 - peoro

1

我认为最快的方法是O(log(log(n))^2)，while循环需要O(log(log(n))的时间，它可以递归调用有限次数（我们可以说O(c)，其中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);
    }

- Saeed Amiri

1

在Python中：

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

- HaPsantran

0

我使用以下变种的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

在C++中，查找/多路if是最快的，但需要我们知道整数是有限大小的。对于循环结束值较小的情况，try3比try1慢，在处理大数字时，try3胜过try1。在Python中，由于整数没有限制，因此我会将try2与try3结合起来，快速处理固定范围内的数字，然后处理可能非常大的数字。

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

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

- Justin Finnerty

1

当你需要编写的代码开始看起来像一艘帆船的ASCII艺术品时，你应该问自己是否真的需要这种优化。 - Victor Zamanian

0

鉴于这是与语言无关的，如果您可以获得该数字所涉及的二次幂，例如 x*2^y 中的 y（这是存储该数字的方式，尽管我不确定是否有一种简单的方法来在我使用过的任何语言中访问 y），那么如果

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

(一个浮点数除法)

答案将是10^z或10^(z+1)，尽管10^z仍然不太简单（请斧正）。

- aronp

如果你能得到二的幂次方，你可以在表格（我的答案）中查找z，只需一次内存访问成本，比浮点除法便宜得多。 - Ira Baxter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anon. · Accepted Answer

7

一种替代的算法是：

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

- Anon.

1

从计算复杂度的角度来看，这是一种可怕的方法。你的方法在比特数方面是O(n)，而O(log(n))就足够了。 - Yonatan N

8

一切都是一种权衡。对于有限范围内的数字，O(n) 可以很好地运行，这个选项不需要额外的空间（与使用大型查找表、预先计算平方数列等相比）。计算复杂度并非判断算法是否“好”的唯一标准。可以相对简单地进行修改，使用平方代替朴素乘法直到接近目标，但这会涉及更多的代码，并在小输入上可能使其变慢。正确的选择取决于预期的输入数据，而不仅仅是大O性能。 - Anon.

1

最好的方法是在while循环中使用((i = i * 10) < x);或while(i<x) i*=10; 并在末尾加上count--。 - Saeed Amiri

计算复杂度并不是万能的 - 当然，但在这种情况下，他特别要求最快的方法... - Mark Mayo

我得到的大多数（全部？）答案比我的旧代码便宜得多。这个解决方案是最简单、最干净和最容易理解的。我正在实现这个方案，因为我认为对于我的平均情况（目前），它不需要迭代超过4或5次，因此快速的O(n)解决方案应该可以胜任；如果我发现还不够，我会尝试实现其他算法。 - peoro