使用递归和 mod 计算指数的算法

Question

有人教我用 mod 和递归计算指数的不同方法，但我并不完全理解。方法是：要做到b^e，我们可以这样分解：

  q = e div 2
  r = e mod 2
then e = 2q+r, and r could be 0 or 1.

If r=0:

    b^e = (b^q)^2

If r=1:

    b^e = (b^q)^2 * b

base case: b^0 = 1.

例如：2^2, b=2, e=2.

q = 2/2 = 1
r = 2mod2 = 0

r=0, therefore 2^2 = 2^1^2

我正在尝试对此进行编码。

pow :: Integer -> Integer -> Integer
pow b e
    | e == 0 = 1
    | r == 0 = pow (pow b q) 2
    | r == 1 = b * pow (pow b q) 2
  where
    (q, r) = divMod e 2

但是当e!=0时，代码不会在任何时候结束，例如，pow (-2) 4或pow 1 1永远持续下去。知道为什么吗？

Answer 1

您还需要提供 e 为 2 时的基本情况：

pow b 2 = b * b

没有这个，你的递归就不会结束，因为它变成了 pow (pow b 1) 2 而你什么也得不到。

Answer 2

如果您尝试手动评估 pow b 2，您很快就会明白原因。由于 divMod 2 2 = (1, 0)，我们从 pow b 2 扩展到 pow (pow b 1) 2。请注意，这是也形式的 pow b' 2，带有 b' = pow b 1。所以我们得到了一个无限链：

pow b 2
=
pow (pow b 1) 2
=
pow (pow (pow b 1) 1) 2
=
pow (pow (pow (pow b 1) 1) 1) 2
=
...

有几种方法可以解决它。您可以为 e == 2 添加一个基本情况，或者不用递归调用 pow 两次，您可以自己进行乘法运算（如在现有代码中将 pow foo 2 替换为 foo * foo ).

Answer 3

如前面的答案所述，您的代码几乎有效，只是允许递归停止的问题。

请参阅下面的代码以了解可能的修复方法。递归调用的参数最多为当前参数的一半，因此递归将不得不停止。

附带说明一下，该算法已有 2000 多年的历史，起源于古印度。请以应有的尊重对待它:-) https://mathoverflow.net/questions/107708/origin-of-square-and-multiply-algorithm

pow :: Integer -> Integer -> Integer
pow b e
    | e == 0 = 1
    | r == 0 = let bpq = pow b q  in  bpq*bpq
    | r == 1 = let bpq = pow b q  in  bpq*bpq*b
  where
    (q, r) = divMod e 2

main = do
    let b = 3 :: Integer
    let e = 7 :: Integer
    let x = b^e
    putStrLn ("b^e     = " ++ show x)
    let y = pow b e
    putStrLn ("pow b e = " ++ show y)

使用递归和 mod 计算指数的算法

Algorithm to calculate exponent using recursion and mod

haskell

exponent