使用递归和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

如果您尝试手工评估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，您可以自己进行乘法(例如，在现有代码中用foo * foo替换pow foo 2(。

Answer 2

您还需要为e为2时提供一个基本案例：

pow b 2 = b * b

没有此，您的递归就不会结束，因为它变成了pow (pow b 1) 2，您就不会到达任何地方。

Answer 3

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

有关修复程序，请参见下面的代码。递归调用的论点最多是当前的论点，因此递归必须停止。

在旁注上，该算法已有2000多年的历史，起源于古印度。请以所有适当的尊重来对待它:-)https://mathoverflow.net/questions/107708/origin-of-square-and-andiply-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)