## Three Powering Algorithms

### March 3, 2015

The linear-time function just multiplies the base number as many times as necessary:

```(define (pow-linear b e)   (if (zero? e) 1     (* b (pow-linear b (- e 1)))))```

That function is written recursively so that tracing the function will show that it is linear:

```> (trace pow-linear) (pow-linear) > (pow-linear 2 16) |(pow-linear 2 16) | (pow-linear 2 15) | |(pow-linear 2 14) | | (pow-linear 2 13) | | |(pow-linear 2 12) | | | (pow-linear 2 11) | | | |(pow-linear 2 10) | | | | (pow-linear 2 9) | | | | |(pow-linear 2 8) | | | | | (pow-linear 2 7) | | | |(pow-linear 2 6) | | | |(pow-linear 2 5) | | | |(pow-linear 2 4) | | | |(pow-linear 2 3) | | | |(pow-linear 2 2) | | | |(pow-linear 2 1) | | | |(pow-linear 2 0) | | | |1 | | | |2 | | | |4 | | | |8 | | | |16 | | | |32 | | | |64 | | | | | 128 | | | | |256 | | | | 512 | | | |1024 | | | 2048 | | |4096 | | 8192 | |16384 | 32768 |65536 65536```

The logarithmic-time function squares the base at each step, including in the final product that steps where the corresponding bit of the exponent is odd:

```(define (pow-logarithmic b e)   (cond ((zero? e) 1)         ((even? e) (pow-logarithmic (* b b) (/ e 2)))         (else (* b (pow-logarithmic (* b b) (/ (- e 1) 2))))))```

``` ```

```> (trace pow-logarithmic) (pow-logarithmic) > (pow-logarithmic 2 16) |(pow-logarithmic 2 16) |(pow-logarithmic 4 8) |(pow-logarithmic 16 4) |(pow-logarithmic 256 2) |(pow-logarithmic 65536 1) | (pow-logarithmic 4294967296 0) | 1 |65536 65536```

The constant-time function uses logarithms, and is subject to floating-point error:

```(define (pow-constant b e)   (exp (* (log b) e)))```

``` ```

```> (trace pow-constant) (pow-constant) > (pow-constant 2 16) |(pow-constant 2 16) |65535.99999999998 65535.99999999998```

You can run the program at http://ideone.com/UUEp0c.

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)?