-- 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