探究计算n^k的乘法次数与k的二进制交叉和的关联

我们可以利用以下恒等式实现高效的幂运算（快速幂）：

x^0 = 1
x^(2n) = (x*x)^n
x^(2n+1) = x * (x*x)^n

基于这些恒等式，我们可以写出Haskell版本的快速幂函数，它计算x^k所需的乘法次数远少于k次：

nat_pow :: Double -> Integer -> Double
nat_pow x 0 = 1
nat_pow x k
  | m == 0    = nat_pow (x*x) n  -- 当k为偶数时，转化为计算(x²)^n
  | otherwise = x * nat_pow (x*x) n  -- 当k为奇数时，转化为x*(x²)^n
  where (n,m) = k `divMod` 2  -- 拆分k为n*2+m，m是0或1

举个具体的计算例子，帮你理解这个函数的执行流程：

nat_pow x 6 = nat_pow (x²) 3            -- 第一次乘法：计算x*x得到x²
            = x² * nat_pow (x⁴) 1       -- 第二次乘法：计算x²*x²得到x⁴；第三次乘法：x²乘以递归结果
            = x² * x⁴ * nat_pow (x⁸) 0  -- 第四次乘法：计算x⁴*x⁴得到x⁸
            = x² * x⁴ * 1

另外，先明确二进制交叉和的定义：它是一个数的二进制表示中1的个数。比如：

crossSum_2 42 = 3 （因为十进制42的二进制是101010，里面有3个1）

核心问题 #

nat_pow x k执行过程中需要的乘法次数M(k)，和k的二进制交叉和Q(k)之间到底有什么深层关联？

从递推到完整关联 #

你已经推导了递推关系：

M(2k) = 1 + M(k)    -- 偶数指数：先平方底数（1次乘法），再递归计算指数折半后的幂
M(2k+1) = 1 + M(2k) -- 奇数指数：先按偶数处理，再额外乘一次当前底数
Q(2k) = Q(k)        -- 偶数的二进制末尾是0，1的个数和折半后相同
Q(2k+1) = 1 + Q(k)  -- 奇数的二进制末尾是1，1的个数比折半后多1

从这些递推式，我们可以进一步归纳出精确的定量关系：
对于任意正整数k，设L(k)为k的二进制表示的位数（比如k=6是110，位数为3），那么：

M(k) = (L(k) - 1) + Q(k)

换个更直观的说法：
快速幂的总乘法次数 = 二进制位数减1（对应每一步的平方操作次数） + 二进制中1的个数（对应每遇到一个1，需要额外执行的乘法次数）

验证一下这个结论 #

• 比如k=6：二进制是110，L(k)=3，Q(k)=2，M(k)=(3-1)+2=4，和实际执行的乘法次数一致；
• 比如k=42：二进制是101010，L(k)=6，Q(k)=3，M(k)=(6-1)+3=8，通过递推计算也能得到相同结果。

深层意义 #

这个关联的本质是快速幂的执行逻辑和二进制表示的直接对应：

1. 二进制位数减1：对应我们把指数不断折半的过程，每折半一次就要做一次平方操作，这个次数正好等于二进制位数减1；
2. 二进制交叉和（1的个数）：对应每一次遇到指数为奇数的情况，我们需要多乘一次当前的底数，而指数为奇数的次数正好等于二进制中1的个数。

所以Q(k)其实是快速幂中"额外乘法"的次数，加上平方操作的次数（由二进制位数决定），就得到了总乘法次数。

内容的提问来源于stack exchange，提问作者ngmir