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

### Like this:

Like Loading...

*Related*

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

This entry was posted on February 26, 2013 at 11:49 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

March 23, 2013 at 12:19 pm |

Would you like to enter my free programming competition? http://contestcoding.wordpress.com/