Posts Tagged ‘addition’

Programming Praxis – An Odd Way To Square

February 26, 2013

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

Programming Praxis – Three Wise Men

December 28, 2012

In today’s Programming Praxis exercise, our goal is to solve a puzzle in which both the addition and multiplication of three numbers results in 65.52. Let’s get started, shall we?

Assuming each item costs at least one penny, the most expensive item can be at most 65.50. By multiplying each amount by 100 we can avoid any potential inaccuracies resulting from using floating point numbers. By stating that a must be more expensive than b we remove some duplicates and reduce the search space. Once a and b are known c follows automatically, otherwise the addition would be incorrect. Finally, we check if the multiplication works. Since all three numbers have been multiplied by 100, the result must be 65.52 * 100^3.

main :: IO ()
main = print $ head [(a,b,c) | a <- [1..6550], b <- [1..a]
                             , let c = 6552 - a - b
                             , a * b * c == 65520000]

This gives us the amounts $2.00, $0.52 and $63.00. Clearly, two of the wise men are cheapskates.

Programming Praxis – Big Numbers: Addition, Subtraction, And Multiplication

May 31, 2011

In today’s Programming Praxis exercise, we’re going to add addition, subtraction and multiplication to our big number library. Let’s get started, shall we?

Addition and multiplication are both functions of the Num typeclass, so we add the two functions (the fact that a – b is equal to a + (-b) is already present in the Num typeclass, so since we already defined negate we don’t need to define the subtraction function) in our Num instance:

instance Num BigNum where

For addition, we need to decide whether we’re adding or subtracting, which we do for each pair of digit groups. We could do this digit by digit, but I’m going to be lazy and do it per group. The conversion to and from Integers is not needed now, but will be required once the base is increased to prevent overflowing the Int type.

    a@(B l1 ds1) + b@(B l2 ds2) = B (length ds * signum l) ds where
        B l _ = if abs b > abs a then b else a
        ds = f 0 $ (if abs b > abs a then flip else id)
             (prep $ if signum l1 == -signum l2 then (-) else (+)) ds1 ds2
        prep op (x:xs) (y:ys) = op (toInteger x) (toInteger y) : prep op xs ys
        prep _  xs     ys     = map toInteger $ xs ++ ys
        f r (x:xs) = let (d,m) = divMod (r + x) base in fromIntegral m : f d xs
        f r []     = if r == 0 then [] else [fromIntegral r]

For multiplication we use the grade school method of multiplying each digit group (again, instead of per-digit) and summing them up at the end.

    (B l1 ds1) * (B l2 ds2) = B (signum l1 * signum l2 * sl) sds where
        B sl sds = sum $ mult ds1 ds2
        mult (x:xs) (y:ys) = fromIntegral (toInteger x * toInteger y) :
                             map shift (mult xs (y:ys)) ++
                             map shift (mult [x] ys)
        mult _     _  = []
        shift (B l ds) = B (l + 1) (0 : ds)

Some tests to see if everything is working properly:

main :: IO ()
main = do print $  12345678 +  987654321  == ( 999999999 :: BigNum)
          print $  12345678 -  987654321  == (-975308643 :: BigNum)
          print $ 987654321 -   12345678  == ( 975308643 :: BigNum)
          print $ -12345678 +  987654321  == ( 975308643 :: BigNum)
          print $ -12345678 -   87654321  == ( -99999999 :: BigNum)
          print $  12345678 *   87654321  == ( 1082152022374638 :: BigNum)
          print $  12345678 * (-87654321) == (-1082152022374638 :: BigNum)
          print $ -12345678 *   87654321  == (-1082152022374638 :: BigNum)
          print $ -12345678 * (-87654321) == ( 1082152022374638 :: BigNum)