recursion - pow(x,n) 的递归方法，用于查找乘法少于 10 次的 2^(37)

Question

pow(x,n) 的常规递归方法如下:

pow(x,n):

     = 1 ...n=0

     = 0 ...x=0

     = x ...n=1

     = x * pow (x, n-1) ...n>0

使用这种方法，2^(37) 将需要 37 次乘法。我如何修改它以将乘法次数减少到小于 10？我认为只有在功能不过分的情况下才能做到这一点。

Answer 1

使用这种方法，您只需7 次乘法 即可计算 2^(37)。

pow(x,n):

    = 1 ... n=0

    = 0 ... x=0

    = x ... n=1

    = pow(x,n/2) * pow (x,n/2) ... n = even

    = x * pow(x,n/2) * pow(x,n.2) ... n = odd

现在让我们用这种方法计算 2^(37) -

2^(37) =

     = 2 * 2^(18) * 2^(18)

     =              2^(9) * 2^(9)

     =                      2 * 2^(4) * 2^(4)

     =                                  2^(2) * 2^(2)

     =                                          2 * 2

这个函数并不过分，因此它会重复使用计算后的值。因此，计算 2^(37) 只需要 7 次乘法。