## Programming Praxis – An Odd Way To Square

In today’s Programming Praxis exercise, our goal is to implement an algorithm to square a number using only addition and subtraction. Let’s get started, shall we?

```import Data.Bits
import Data.List```

First, the trivial O(n) algorithm. n^2 = n * n = sum (n times n)

```square :: Integer -> Integer
square n = sum \$ genericReplicate n n```

Next, an O(log n) algorithm. Create a sequence in which each element consists of the following values: an incrementing integer i, 2^i and n*2^i. Filter out all elements for which the ith bit of n is 0. Sum the n*2^i terms.

```square2 :: Integer -> Integer
square2 n = sum [a | (i,a) <- unfoldr (\(i,p,a) -> if p <= n then
Just ((i,a), (i+1,p+p,a+a)) else Nothing) (0,1,n), testBit n i]```

Some tests to see if everything is working properly:

```main :: IO ()
main = do print \$ map square  [0..10] == map (^2) [0..10]
print \$ map square2 [0..10] == map (^2) [0..10]
print \$ square (2^20) == 2^40
print \$ square2 (2^1000) == 2^2000```