algorithm - 在基数和幂都是二进制的情况下，找到二进制值的幂的最佳算法方法是什么？

Question

假设问题是 1010^1110 那么如何通过算法得出最快的解决方案？

我得到了这样一个公式 ((1010^2)^2)^2 * (1010^2)^2 * 1010^2

Answer 1

小数次幂

您可能希望将数字扩展为 2 的幂。这是可能的，因为任何自然数都可以扩展为 2 的幂之和。例如，您可以使用:

function getPowersOf2($number)
{
   if(!$number)
   {
      return [];
   }
   $p = floor(log($number, 2));
   return array_merge([$p], getPowersOf2($number-pow(2, $p)));
}

- 生成该序列。对于 14，它将是 8 + 4 + 2，所以 2^3 + 2^2 + 2^1，结果, [3, 2, 1]。然后你就可以像这样使用它:

function getPower($base, $number)
{
   $result = 1;
   foreach(getPowersOf2($number) as $pow2)
   {
      $temp = $base;
      while($pow2--)
      {
         $temp*=$temp;
      }
      $result*=$temp;
   }
   return $result;
}

- 所以每次幂都会在最终表达式中产生一次乘法，每次乘法也会产生一次乘法。例如，如果原始功率是 14 那将是 8 操作，因为:

(x^14) = x^(8+4+2) = x^(2^3+2^2+2^1) = (((x^2)^2)^2)*((x^2)^2)*(x^2)

二元幂

很难说它是“优化” - 查看 getPowersOf2() 函数 - 里面至少有对数。但在你的情况下，你的权力已经转换。 1110 表示 1*2^3 + 1*2^2 + 1*2^1 + 0 - 这是基数定义。因此，您可以以非常简单的方式执行乘法:

function getPowerBin($base, $number)
{
   $m = count($number)-1;
   $result = 1;
   foreach($number as $bin)
   {
      if($bin)
      {
         $temp = $base;
         $pow2 = $m;
         while($pow2--)
         {
            $temp*=$temp;
         }
         $result*=$temp;
         $m--;
      }
   }
   return $result;
}

- 因此您只需遍历 power 的二进制表示(在我的例子中为数组)并查看当前的 power $m - 获得与上述函数相同的结果。

这可能有用，因为它会产生较少的乘法，但我怀疑它是否可以称为优化 - 因为它会在内部使用许多额外的东西。但就我们将基数增加多少倍而言 - 是的，它会赢。