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