Алгоритм расчета показателя с использованием рекурсии и мод - PullRequest
Новая
       16

Алгоритм расчета показателя с использованием рекурсии и мод

0 голосов
/ 18 мая 2019

Меня учили другому способу вычисления показателей, используя мод и рекурсию, но я не до конца понимаю.Метод: Чтобы сделать 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 продолжается вечно.Есть идеи почему?

Ответы [ 3 ]

6 голосов
/ 18 мая 2019

Если вы попытаетесь оценить 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 в существующем коде).

2 голосов
/ 18 мая 2019

Вам также необходимо предоставить базовый случай, когда e равно 2: 

pow b 2 = b * b

Без этого ваша рекурсия не заканчивается, потому что она становится pow (pow b 1) 2, а вы неникуда не денется.

1 голос
/ 19 мая 2019

Как упоминалось в предыдущих ответах, ваш код почти работает, и это всего лишь вопрос остановки рекурсии.

См. Код ниже для возможного исправления. Аргумент рекурсивного вызова составляет не более половины текущего аргумента, поэтому рекурсия должна быть остановлена.

Кстати, этому алгоритму более 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)
...