Меня учили другому способу вычисления показателей, используя мод и рекурсию, но я не совсем понимаю это. Метод: Чтобы сделать 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
продолжается вечно. Есть идеи почему?
Всего 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
в существующем коде).
Вам также нужно предоставить базовый случай, когда e
равно 2
:
pow b 2 = b * b
Без этого ваша рекурсия не заканчивается, потому что она становится pow (pow b 1) 2
и вы никуда не денетесь.