[Haskell-cafe] In other words is there a good place to post stuff like the following?

23 Jun 2010


      -- Algorithms From: "Selected Papers on Design of Algorithms", Donald  
Knuth, 2010
-- Chapter 10 Addition Machines
-- Haskell version by Casey Hawthorne

-- Note this is only a skeleton of the chapter,
-- so as to wet your interest to buy the book.

-- Addition Machine

-- The only operations allowed are the following:
-- read x
-- x <- y
-- x <- x + y
-- x <- x - y
-- if x >= y
-- write x

-- Can all functional versions be tail recursive?

-----------------------------------------------------------------------
-----------------------------------------------------------------------

-- Modulus

-- Assuming without loss of generality x>=0 and y>0,
-- since one can use various identities for other cases.

-- Performs floor(x/y) subtractions.
modulusNaive x y
     | x >= y    = modulusNaive (x-y) y
     | otherwise = x


-- Can we do better?
-- Uses a doubling procedure to subtract larger multiplies of y.
-- Bounded by O(log(x/y))^2
modulusByDoubling x y
     | x >= y    = helper y y
     | otherwise = x
     where
     helper w z
         | x < z     = helper z z+z
         | otherwise = modulusByDoubling (x-w) y


-- Can we do better?
-- Want bounded by O(log(x/y)).
-- Addition Machine, so cannot divide by 2.
-- Implicitly use the Fibonacci representation of floor(x/y)
-- instead of its the binary representation.
-- F0 = 0; F1 = 1; Fn = F(n-1) + F(n-2), n >=2
-- Every nonnegative integer n can be uniquely represented in the form
-- n = F(m1) + F(m2) + ... + F(mt), m1 >> m2 >> ... >> mt >> 0
-- where t >= 0 and m >> m' means that m - m' >= 2
-- If n > 0 this representation can be found by choosing m1 such that
-- F(m1) <= n < F(m1+1)

-----------------------------------------------------------------------
-- Furthermore Fibonacci numbers grow exponentially,
-- about 69% as fast as powers of 2.
-- They have been used as power-of-2 analogs in a variety of algorithms.
-----------------------------------------------------------------------

modulusFib x y
     | x >= y    = helper x y y
     | otherwise = x
     where
     helper x y z
         | x < z     = helper x z y+z
         | otherwise = helper2 x y z

     helper2 x y z
         | x >= y    = helper2 (x-y) y z
         | y > z     = helper2 x (z-y) y
         | otherwise = x

[Haskell-cafe] In other words is there a good place to post stuff like the following?

caseyh＠istar.ca