I was taught a different way to calculate exponents using mod and recursion, but I don't fully understand it. The method is: To do b^e
, we can break it down like so:
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.
For example: 2^2, b=2, e=2
.
q = 2/2 = 1
r = 2mod2 = 0
r=0, therefore 2^2 = 2^1^2
I am trying to code this.
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
But the code does not end any time when e!=0
, for example, pow (-2) 4
or pow 1 1
goes on forever. Any idea why?
If you try evaluating pow b 2
by hand you'll quickly see why. Since divMod 2 2 = (1, 0)
, we expand from pow b 2
to pow (pow b 1) 2
. Note that this is also of the form pow b' 2
, with b' = pow b 1
. So we just get an infinite chain:
pow b 2
=
pow (pow b 1) 2
=
pow (pow (pow b 1) 1) 2
=
pow (pow (pow (pow b 1) 1) 1) 2
=
...
There's a couple ways to solve it. You could add a base case for e == 2
, or instead of recursively calling pow
twice you could just do the multiplication yourself (as in replacing pow foo 2
with foo * foo
in your existing code).