## Three Powering Algorithms

### March 3, 2015

In mathematics, the powering operation multiplies a number by itself a given number of times. For instance, the powering operation `pow(2,3)` multiplies 2 × 2 × 2 = 8.

Your task is to write three functions that implement the powering operation, with time complexities O(n), O(log n) and O(1) in the exponent. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 2 Responses to “Three Powering Algorithms”

1. Graham said

```module Main where
import Data.Word

-- naive
linear :: (Num a) => a -> Word -> a
linear x n = product \$ replicate (fromIntegral n) x

-- tail recursive square & multiply
logarithmic :: (Num a) => a -> Word -> a
logarithmic x n = go x 1 n
where
go a b 0 = b
go a b k = go (a * a) (if odd k then a * b else b) (k `div` 2)

-- cheating, with errors; uses Haskell like a slide rule
constant :: (Floating a) => a -> Word -> a
constant x n = exp \$ (log x) * (fromIntegral n)

main :: IO ()
main = mapM_ print \$ map (\f -> map (f 2) [0..10]) [linear, logarithmic, constant]
```
2. Den said

I asked a question on Stack Overflow about this O(1) solution. And the author of this post just answered me. I thought it would be a good idea to also post the answer here for who may have the same question.

Question:
I am trying to understand how to implement the power operation with time complexity O(1) in the following post.

https://programmingpraxis.com/2015/03/03/three-powering-algorithms/2/

Can anyone explain why this algorithm works? And why it is O(1)?