CODEWITHSUNDEEP
haskell
Cyneon Bane
Cyneon Bane

Reputation: 21

Implementing a multiplication-counting function

I have written this:

pow :: Integer -> Integer -> Integer
pow x k = if k == 1
then x
else if k `mod` 2 == 0
then pow (x*x) (k `div` 2)
else x * pow (x*x) (k `div` 2)

Now I want to write a program which has a given k and decides how many multiplications pow x k is going to execute.

My idea was:

costpow :: Integer -> Integer
costpow 1 = 0
costpow k = if m == 0 
then   1 + costpow k
else  2 + costpow k
where ( n , m ) = k `divMod` 2

Upvotes: 0

Views: 59

Answers (2)

karakfa
karakfa

Reputation: 67467

Your recursion will never end as stated in the other post. Perhaps you can simplify a little more

costpow :: Integer -> Integer
costpow 1 = 0
costpow k = m + 1 + costpow n
       where (n,m) = k `divMod` 2

Upvotes: 0

ErikR
ErikR

Reputation: 52029

This is an infinite loop:

costpow k = ...
   ... 1 + costpow k
                   ^^^

You probably want something like 1 + costpow n instead.

Upvotes: 2

Related Questions