[Haskell-cafe] In other words is there a good place to post stuff
like the following?
caseyh at istar.ca
caseyh at istar.ca
Wed Jun 23 15:19:08 EDT 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
More information about the Haskell-Cafe
mailing list