时间戳

首页 > 解决方案 > 使用递归和 mod 计算指数的算法

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

问题描述

我被教导了一种使用 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永远持续下去。知道为什么吗？

标签： haskellexponent

解决方案

如果您尝试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而不是递归调用两次（就像在现有代码中替换为那样）。powpow foo 2foo * foo

推荐阅读