# Shootout/Recursive

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A ShootoutEntry for the recursive benchmark

The spec is as follows:

```Each program should use the same na�ve recursive-algorithms to calculate
3 simple numeric functions: ackermann, fibonnaci and tak.

Ack(x,y)
x = 0     = y+1
y = 0     = Ack(x-1,1)
otherwise = Ack(x-1, Ack(x,y-1))

Fib(n)
n < 2     = 1
otherwise = Fib(n-2) + Fib(n-1)

Tak(x,y,z)
y < x     = Tak(Tak(x-1.0,y,z),Tak(y-1.0,z,x),Tak(z-1.0,x,y))
otherwise = z

For this benchmark, the fibonnaci and tak implementations should either
provide separate functions - one for integer calculation and one for
double calculation - or provide a function that uses integer calculation
with integer parameters and double calculation with double parameters.
```

So the trick is that we need to be polymorphic on Double and Int for fib and tak.

## Benchmarks

Debian/Linux x86, N=11 ||Entry||Time|| ||Current || 4.948 || ||Unboxed || 4.785 ||

## Proposed entry

I didn't think the code was fast enough. Careful inspection of the Core revealed some funny constructs. So I rewrote the heavily called loops the way I wanted them. Result, around 5% faster.

```--
-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
--
-- Haskell Wiki page for Shootout entries - http://haskell.org/hawiki/ShootoutEntry
-- Contributed by Don Stewart
--
-- Compilation:
--    ghc -o d D.hs -O2 -fexcess-precision -optc-O3 -optc-ffast-math -fglasgow-exts
-- -fexcess-precision is important. ack and fibr have been carefully unboxed.
--

import System; import Text.Printf; import GHC.Exts

main = do (n@(I# i),a@(D# d)) <- getArgs >>= readIO . head >>= \n -> return (n,27+fromIntegral n)
let (m3,m2,m) = (m*3, m*2, n-1)
putStrLn \$ "Ack(3," ++ show n ++ "): " ++ show (I# (ack 3# i))
printf "Fib(%f): %f\n" a (D# (fibr d))
putStrLn \$ "Tak("++show m3++","++show m2++","++show m++"): "++
show (tak m3 m2 m)
putStrLn \$ "Fib(3): "           ++ show (fib 3 :: Int)
putStrLn \$ "Tak(3.0,2.0,1.0): " ++ show (tak 3 2 1 :: Double)

ack x y = if x ==# 0# then y +# 1# else ack (x -# 1#) (if y ==# 0# then 1# else ack x (y -# 1#))

fib  n = if n < 2 then 1 else fib (n-2) + fib (n-1)
fibr n = if n <## 2.0## then 1.0## else fibr (n -## 2.0##) +## (fibr (n-## 1.0##))

tak x y z = if y >= x then z else tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y)
```

## Current entry

Currently ranked: [(cpu, 6th), (mem, 4th), (loc, 1st)]

Taken from existing ackermann and takfp entries, with a standard fib. -O2 -optc-O3 -fexcess-precision

```--
-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
--
-- Based on code contributed by:
-- Bryn Keller, Don Stewart, Einar Karttunen and Greg Buchholz
--
--    ghc -o d D.hs -O2 -optc-O3 -fexcess-precision
--
-- -fexcess-precision is important
--
-- fib and tak are polymorphic in their arguments. The type signatures ensure
-- that arguments and result types match, as per the spec.
--

import System; import Text.Printf

main = do (n,m,a) <- getArgs >>= readIO . head >>= \n -> return (n,n-1,27 + fromIntegral n)
let (m3,m2) = (m*3, m*2)
putStrLn \$ "Ack(3," ++ show n ++ "): " ++ show (ack 3 n)
printf "Fib(%f): %f\n" a (fib a :: Double)
putStrLn \$ "Tak("++show m3++","++show m2++","++show m++"): "++show (tak m3 m2 m :: Int)
putStrLn \$ "Fib(3): "           ++ show (fib 3 :: Int)
putStrLn \$ "Tak(3.0,2.0,1.0): " ++ show (tak 3.0 2.0 1.0 :: Double)

ack :: Int -> Int -> Int
ack 0 y = y+1
ack x y = ack (x-1) \$ if y == 0 then 1 else ack x (y-1)

fib :: (Ord a, Num a) => a -> a
fib n = if n < 2 then 1 else fib (n-2) + fib (n-1)

tak x y z = if y >= x then z else tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y)
```