# [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
-- Haskell version by Casey Hawthorne

-- Note this is only a skeleton of the chapter,

-- The only operations allowed are the following:
-- 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

```