[clean-list] Akkerman's functions

[Pieter Koopman]

--=====================_28494402==_.ALT
Content-Type: text/plain; charset="us-ascii"; format=flowed

Hi,

At 10:52 08-10-2002 +0200, Scott J, wrote:
>I tried Akkerman's functions with different parameters, to see how fast 
>the native code was.
>But I had only succes with low parameters?
>Is there something that I must adapt in CleanIde?

Actually there are two problems here:

1) The Ackermann function grows very rapidly.
A 0 y = y+1
A 1 y = y+2
A 2 y = 2*y+3
A 3 y = 2^(y+3)
A 4 y = 2^(2^..) - 3 where the powers of 2 are y+3 high
This means that:
A 4 0 = 2^(2^2)-3 = 2^4 - 3 = 16 -3 = 13
A 4 1 = 2^(2^(2^2)) - 3 = 2^(2^4) - 3 = 2^16-3 = 65536-3 = 65533
A 4 2 = 2^65536 - 3 = about 10^19728, a number of 19728 decimal digits!

All these numbers have to be constructed by increments. The result is equal 
to the number of increments to be done, indeed a lot of work. The 
implementation needs a lot of stack-space for these (strict) computations.
You can expect to be able to compute values up to A 3 y for small y and A 4 
0 and A 4 1.

2) For some reason the generated program does not report that it runs out 
of stack. We are investigating what is going wrong here.

Pieter Koopman

--=====================_28494402==_.ALT
Content-Type: text/html; charset="us-ascii"

Hi,


At 10:52 08-10-2002 +0200, Scott J, wrote:

> I tried
> Akkerman's functions with different parameters, to see how fast the
> native code was.
> But I had only succes with low
> parameters?
> Is there something that I must adapt in
> CleanIde?


Actually there are two problems here:


1) The Ackermann function grows very rapidly.

A 0 y = y+1

A 1 y = y+2

A 2 y = 2*y+3

A 3 y = 2^(y+3)

A 4 y = 2^(2^..) - 3 where the powers of 2 are y+3 high

This means that:

A 4 0 = 2^(2^2)-3 = 2^4 - 3 = 16 -3 = 13

A 4 1 = 2^(2^(2^2)) - 3 = 2^(2^4) - 3 = 2^16-3 = 65536-3 = 65533

A 4 2 = 2^65536 - 3 = about 10^19728, a number of 19728 decimal
digits!


All these numbers have to be constructed by increments. The result is
equal to the number of increments to be done, indeed a lot of work. The
implementation needs a lot of stack-space for these (strict)
computations.

You can expect to be able to compute values up to A 3 y for small y and A
4 0 and A 4 1.


2) For some reason the generated program does not report that it runs out
of stack. We are investigating what is going wrong here.


Pieter Koopman


--=====================_28494402==_.ALT--