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

About these ads

Tags: addition, bonsai, code, Haskell, kata, programming praxis, square