[REBOL] Re: RFC: Cross-language benchmark proposal
From: jan:skibinski:sympatico:ca at: 7-Nov-2002 14:50
Reposting: this time not even trying
to use plain text mode.
If the transformation below is compliant
with the contest rules then the 'ack could
be made faster. We could even handle the
case of 'ack 3 9.
Clear definition from Haskell:
------------------------
ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))
Example transformation for ack 3 3:
-----------------------------------
ack 3 3 = ack 2 (ack 3 2)
= ack 2 (ack 2 (ack 3 1))
= ack 2 (ack 2 (ack 2 (ack 3 0)))
= ack 2 (ack 2 (ack 2 (ack 2 1)))
Compliant so far? If so, then:
Implementation #1:
----------------
{Iterate implements the transformation from above}
iterate: func [f n /local x][x: 1 loop (n + 1) [x: f x] x]
boom0: func [n][n + 1]
boom1: func [x][iterate :boom0 x]
boom2: func [x][iterate :boom1 x]
boom3: func [x][iterate :boom2 x]
>> boom3 8
== 2045
time: 0:00:02.824
>> boom3 9
== 4093
time: 0:00:11.226
Implementation #2 packages the implementation #1,
but slows down quite a bit:
------------------------------------------
ack': func [
m [integer!]
n [integer!]
/local iterate boom
][
iterate: func [f n /local x][x: 1 loop (n + 1) [x: f x] x]
boom: func [
m n
/local f
][
either m = 0 [
n + 1
][
f: func [n][boom (m - 1) n]
iterate :f n
]
]
boom m n
]
>> ack' 3 8
== 2045
time: 0:00:10.446
Romano's version:
----------------
>> ack 3 8
== 2045
0:00:40.689
Regards,
Jan
Ladislav Mecir wrote:
