Recursion is silly (if you can avoid it).

I recently draw attention to a toy lisp in Forth.
The example program was a scheme program that counts
how many changes in coins are possible for e.g. 100 dollarcent.
The lisp had to improved to be able to compile the program.
The improved version can hardly manage an input of 100 and takes
a noticable time, 200 and following fails.

A more sane program fills in a table where each entry is derived
from previous entries. A possibility to change for 100 cent is e.g.
adding 10 cent to the possibilities for 90 cent.
This is a kind of reversed dynamic programming.

In Forth it looks like.
\ --------------------- 8< ---------------------------
WANT VALUE
: _ 0 ; \ Don't care value
CREATE kind-of-coins 1 , 5 , 10 , 25 , 50 , 0 ,

_ VALUE limit
_ VALUE aap

\ One possibility to change 0 cent, others initially zero.
: init 1 , limit 0 DO 0 , LOOP ;

: aap[] CELLS aap + ;

\ Add possibilities for denomination to `aap
: add limit 1+ OVER DO I OVER - aap[] @ I aap[] +! LOOP DROP ;
: doit 1 ARG[] EVALUATE TO limit
HERE TO aap init
kind-of-coins BEGIN $@ DUP WHILE add REPEAT DROP
limit aap[] ? CR ;

\ --------------------- 8< ---------------------------
You may have not have to want VALUE.
$@ is another name for @+ / OUNT .
If you can't handle command line arguments, you can replace
`` 1 ARG[] EVALUATE '' with the limit you want.
Around 70 dollar you get overflow in 32 bit systems.
It is hard to measure speed in 32 bit systems,
suffice it to say that is certainly under 10 ms.

My forth (lina) is not the fastest, however

time coinsusa 1,000,000
666793341266850001
real 0m0.353s
user 0m0.281s
sys 0m0.029s

For reference this is the scheme program.
\ --------------------- 8< ---------------------------
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))

(display (count-change 100))
(newline)
\ --------------------- 8< ---------------------------

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

> Recursion is silly (if you can avoid it).

Not really.

Recursion is elegant — but actually isn't any
more efficient than iteration, and of course
it requires stack space.

And yes, most of the time (or always?) there
does exist iterative counterpart solution
--
Z.

albert@cherry.(none) (albert) writes:
>A more sane program fills in a table where each entry is derived
>from previous entries. A possibility to change for 100 cent is e.g.
>adding 10 cent to the possibilities for 90 cent.
>This is a kind of reversed dynamic programming.

What is reversed about this?

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

albert@cherry.(none) (albert) writes:

> I recently draw attention to a toy lisp in Forth.
> The example program was a scheme program that counts
> how many changes in coins are possible for e.g. 100 dollarcent.

By the way, this is a well-known problem likely very well known by
everyone in this news group. The scheme-procedure you presented is from
section 1.2.2 in

Structure and Interpretation of Computer Programs
Gerald J. Sussman, Harold Abelson, Julie Sussman

> The lisp had to improved to be able to compile the program. The
> improved version can hardly manage an input of 100 and takes a
> noticable time, 200 and following fails.
>
> A more sane program fills in a table where each entry is derived
> from previous entries.

The scheme version you presented builds such a table --- it's called the
stack of execution. (Just another name for ``table''.)

zbigniew2011@gmail.com (LIT) writes:

>> Recursion is silly (if you can avoid it).
>
> Not really.
>
> Recursion is elegant — but actually isn't any
> more efficient than iteration, and of course
> it requires stack space.
>
> And yes, most of the time (or always?) there
> does exist iterative counterpart solution

What do you mean iterative? For instance, Gerald Sussman and Harold
Abelson classify as `iterative' the procedure

(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),

which is self-referential.

albert@cherry.(none) (albert) writes:
> This is a kind of reversed dynamic programming.

That is usually called memoization.

> What do you mean iterative?

An iterative function is one that loops
to repeat some part of the code, and
a recursive function is one that calls
itself again to repeat the code

P.S. NovaBBS seems to select the „proper group”
for me, not even asking any question; there's
a need to be more careful here, it seems
--
Z.

none wrote:

> Recursion is silly (if you can avoid it).

> I recently draw attention to a toy lisp in Forth.
> The example program was a scheme program that counts
> how many changes in coins are possible for e.g. 100 dollarcent.
> The lisp had to improved to be able to compile the program.
> The improved version can hardly manage an input of 100 and takes
> a noticable time, 200 and following fails.

IOW educated brute force can beat elegant recursion.

You are right in a brutish

Paul Rubin <no.email@nospam.invalid> writes:
>> This is a kind of reversed dynamic programming.
> That is usually called memoization.

Added: in Scheme, it can be idiomatic to implement memoization using
force and delay. So for the coin problem you'd have a lookup table
indexed by the amount to be changed, and the sizes of coins available,
giving the number of ways to change that amount with those coins.

Each slot in the table would say something like (delay (cc amount coins))
where cc is a recursive function that would return a delayed sum of
the different table lookups corresponding to different breakdowns of
the amount. Finally, you would force the table entries for the amounts
1,2...100 or whatever.

I haven't tried this so I may be missing something, but the above
follows a common pattern.

Paul Rubin <no.email@nospam.invalid> writes:
> I haven't tried this so I may be missing something, but the above
> follows a common pattern.

I still haven't worked out the details of the force/delay approach, but
here (at bottom) is a Scheme version that implements memoization using a
hash table by brute force. 100 cents and 200 cents take no perceptible
time.

I ran it with Guile 3.0 (compilation enabled) and got these results on a
small Hetzner VM (number of cents to be changed, result, cpu time in
seconds, and ram consumption in KB):

|---------+------------------------+-------+--------|
| amt | result | sec | KB |
|---------+------------------------+-------+--------|
| 100 | 293 | 0.01 | 9264 |
| 200 | 2728 | 0.01 | 9340 |
| 1000 | 2103596 | 0.01 | 10080 |
| 10000 | 139946140451 | 0.13 | 15176 |
| 100000 | 13398445413854501 | 1.25 | 67564 |
| 500000 | 41707305668679272501 | 5.76 | 293964 |
| 1000000 | 1333983445341383545001 | 15.24 | 580696 |
|---------+------------------------+-------+--------|

================================================================

(define (singleton? lst)
(and (not (null? lst))
(null? (cdr lst))))

(define allcoins '(1 5 10 25 50 100))

(define (cc amount coins)
(cond ((= amount 0) 1)
((< amount 0) 0)
((null? coins) 0)
((singleton? coins)
(if (= (remainder amount (car coins)) 0)
1
0))
(#t (+ (cc (- amount (car coins)) coins)
(cc amount (cdr coins))))))

(define (memoize f)
(define a (make-hash-table))
(define (g . args)
(let ((v (hash-ref a args)))
(if v v (hash-set! a args (apply f args)))))
g)

(set! cc (memoize cc))

(define amt (string->number (cadr (command-line))))

(display (cc amt allcoins))
(display "\n")

> 1000000 | 1333983445341383545001 | 15.24 | 580696

That is quite different from the result none showed.
| time coinsusa 1,000,000
| 666793341266850001
| real 0m0.353s

I guess you are computing something different?
The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

-marcel

mhx@iae.nl (mhx) writes:
> I guess you are computing something different?
> The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

Interesting, what values do you get for 100, 200, etc.? It could be
that my method is wrong. I just did it off the top of my head and may
have done something dumb.

On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
wrote:

>> Recursion is silly (if you can avoid it).
>
>Not really.
>
>Recursion is elegant — but actually isn't any
>more efficient than iteration, and of course
>it requires stack space.

Not necessarily. Scheme compilers actually are *required* to turn
self recursion into a loop (except in the case of a supported "debug"
mode).

I think some of the Lisps can do it also - at least with
(optimize (debug 0) (space 3))

>And yes, most of the time (or always?) there
>does exist iterative counterpart solution

Always. Given enough resources (which could be code or memory space),
any recursion can be turned into an equivalent loop, and vice versa.

mhx@iae.nl (mhx) writes:
> I guess you are computing something different?

Aha, one difference I notice is that Albert's code doesn't have a 100
cent coin. I included that because we have them in the US, though they
aren't used much except for in parking meters. They were introduced
partly for use in vending machines, but those now tend to have dollar
bill slots and sometimes also take credit cards.

Let me try again:

|---------+--------------------+-------+--------|
| 100 | 292 | 0.13 | 33644 |
| 200 | 2435 | 0.00 | 9412 |
| 1000 | 801451 | 0.01 | 9852 |
| 10000 | 6794128501 | 0.05 | 14316 |
| 100000 | 66793412685001 | 1.11 | 63904 |
| 500000 | 41682501983425001 | 6.07 | 240260 |
| 1000000 | 666793341266850001 | 10.67 | 475044 |
|---------+--------------------+-------+--------|

So we're getting the same results for 1000000 now, but my version is
still a lot slower. Maybe the memoization is not working right. Hmm.

On 2023-12-27, George Neuner <gneuner2@comcast.net> wrote:
> On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
> wrote:
>
>>> Recursion is silly (if you can avoid it).
>>
>>Not really.
>>
>>Recursion is elegant — but actually isn't any
>>more efficient than iteration, and of course
>>it requires stack space.
>
> Not necessarily. Scheme compilers actually are *required* to turn
> self recursion into a loop (except in the case of a supported "debug"
> mode).

Careful there: not all self-recursion is tail recursion!

For instance, the obvious way to write a recursive factorial fails
to be tail-recursive, but can be rewritten to tail from with
accumulator passing.

(I know you know all this, likely better than me, but `tis the
season to have your egg nogged.)

In article <2023Dec27.181846@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>albert@cherry.(none) (albert) writes:
>>A more sane program fills in a table where each entry is derived
>>from previous entries. A possibility to change for 100 cent is e.g.
>>adding 10 cent to the possibilities for 90 cent.
>>This is a kind of reversed dynamic programming.
>
>What is reversed about this?

This problem is not the clearest example for explaining this.
There are actually 5 levels of recursion in this problem,
resulting in 5 iterations of `add.
It is kind of reverse, for each (amount,coin level) there is a
memoization required. But these are normally requested from the upper
level, and there is a chance that particular pairs are not needed.
That at least is the hope for dynamic programming.
It all start with (100,5) .

Using iteration it is more clear what we are doing.
In the first place it is obvious that we need all amount's.
A lisper proposes a memoization table of amount * level entries,
that works probably.

My strategy is to build the table for all amounts for level
1. That is the first execution of `add. So the table is
filled in starting with amount 1 and only cents.
Compared to (100,5) starting from (0,1) this is reversed.
For the second and later execution of the iterations it is possible
to continue using the same table.
Compared to memoization we save the lookup of the keys also.

The table for change of 1,000,000 (10,000 dollar) is
8 megabyte, not too bad. In Europe we have 1 2 5 10 20 50 100 200
denomination. Multiplying the size of the table by 7
begins to become unfavourable, not to speak of the overhead that the
general lisp mechanism probably requires.

I will not ask for a calculation for more than 1000000
cents, so that the result fits in a single precision
64 bit number.
CHALLENGE
Can anyone reproduce the count 666793341266850001 for
1 million dollarcent in lisp ?

(Tools used: a simple forth and some 20 lines of Forth code.
It runs under a second. I wonder what iforth does. )

>
>- Anton

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

In article <pu8poi13a1m0lq1am4a2c4fpop5nro1emh@4ax.com>,
George Neuner <gneuner2@comcast.net> wrote:
>On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
>wrote:
>
>>> Recursion is silly (if you can avoid it).
>>
>>Not really.
>>
>>Recursion is elegant — but actually isn't any
>>more efficient than iteration, and of course
>>it requires stack space.
>
>Not necessarily. Scheme compilers actually are *required* to turn
>self recursion into a loop (except in the case of a supported "debug"
>mode).
>
>I think some of the Lisps can do it also - at least with
> (optimize (debug 0) (space 3))
>
>
>>And yes, most of the time (or always?) there
>>does exist iterative counterpart solution
>
>Always. Given enough resources (which could be code or memory space),
>any recursion can be turned into an equivalent loop, and vice versa.

In the Knuth TAOCP you cannot find recursive algorithms. They are
intended to run fast, and algorithms are specified with explicit
stacks. Of course the size of those stacks are specified.

Groetjes Albert
>
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

In article <8734vn9uit.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>Paul Rubin <no.email@nospam.invalid> writes:
>> I haven't tried this so I may be missing something, but the above
>> follows a common pattern.
>
>I still haven't worked out the details of the force/delay approach, but
>here (at bottom) is a Scheme version that implements memoization using a
>hash table by brute force. 100 cents and 200 cents take no perceptible
>time.
>
>I ran it with Guile 3.0 (compilation enabled) and got these results on a
>small Hetzner VM (number of cents to be changed, result, cpu time in
>seconds, and ram consumption in KB):
>
> |---------+------------------------+-------+--------|
> | amt | result | sec | KB |
> |---------+------------------------+-------+--------|
> | 100 | 293 | 0.01 | 9264 |
> | 200 | 2728 | 0.01 | 9340 |
> | 1000 | 2103596 | 0.01 | 10080 |
> | 10000 | 139946140451 | 0.13 | 15176 |
> | 100000 | 13398445413854501 | 1.25 | 67564 |
> | 500000 | 41707305668679272501 | 5.76 | 293964 |
> | 1000000 | 1333983445341383545001 | 15.24 | 580696 |
> |---------+------------------------+-------+--------|
>
>================================================================
>
<SNIP>

Impressed. My answer for 1000000 is actually wrong
because I didn't know that there are 1 dollar coins.

Improving my program:

~/euler: time coinsusa 100000
13398445413854501

real 0m0.095s
user 0m0.079s
sys 0m0.001s

Memory footprint estimated 900 Kbyte.

I see that you go beyond 64 bit numbers and I cannot
calculate the million dollarcent challenge.
The timing and foot print are slightly less as a reward
for more analysis.
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

In article <feea51c7336d6888f6d7b73e76cacebd@news.novabbs.com>,
mhx <mhx@iae.nl> wrote:
>> 1000000 | 1333983445341383545001 | 15.24 | 580696
>
>That is quite different from the result none showed.
>| time coinsusa 1,000,000
>| 666793341266850001
>| real 0m0.353s
>
>I guess you are computing something different?
>The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

Rubin is apparently knowledgeable about USA coins.
He corrected the coins table to contain 1 dollar coins. (What do I know.)
That spoils the benchmark effect.
Can you run the program again with 100 cent coins?
Maybe with 100,000 because now a million overflows 64 bit.

>
>-marcel
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

In article <87tto38djn.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>mhx@iae.nl (mhx) writes:
>> I guess you are computing something different?
>
>Aha, one difference I notice is that Albert's code doesn't have a 100
>cent coin. I included that because we have them in the US, though they
>aren't used much except for in parking meters. They were introduced
>partly for use in vending machines, but those now tend to have dollar
>bill slots and sometimes also take credit cards.
>
>Let me try again:
>
> |---------+--------------------+-------+--------|
> | 100 | 292 | 0.13 | 33644 |
> | 200 | 2435 | 0.00 | 9412 |
> | 1000 | 801451 | 0.01 | 9852 |
> | 10000 | 6794128501 | 0.05 | 14316 |
> | 100000 | 66793412685001 | 1.11 | 63904 |
> | 500000 | 41682501983425001 | 6.07 | 240260 |
> | 1000000 | 666793341266850001 | 10.67 | 475044 |
> |---------+--------------------+-------+--------|
>
>So we're getting the same results for 1000000 now, but my version is
>still a lot slower. Maybe the memoization is not working right. Hmm.

You must be kidding. The memoization using standard tools impressed me.
Compared to the result below it is only one order of magnitude.

In the meantime I have made a double precision version:

~/euler: time coinsusad 1000000
1333983445341383545001

real 0m1.209s
user 0m1.038s
sys 0m0.021s

A double precision version takes double the time,
900 ms for the original challenge.
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

On 28/12/2023 9:44 am, George Neuner wrote:
> On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
> wrote:
>
>>> Recursion is silly (if you can avoid it).
>>
>> Not really.
>>
>> Recursion is elegant — but actually isn't any
>> more efficient than iteration, and of course
>> it requires stack space.
>
> Not necessarily. Scheme compilers actually are *required* to turn
> self recursion into a loop (except in the case of a supported "debug"
> mode).
>
> I think some of the Lisps can do it also - at least with
> (optimize (debug 0) (space 3))

That's kind of offensive (to the programmer) which - not unlike ChatGPT -
puts humans in a diminished role. So the question becomes will humans have
any role at all? Much has been said about 'general purpose subroutines'.
ISTM the only logical reason to have them and (by implication) standards
is that they benefit automation.

albert@cherry.(none) (albert) writes:
> You must be kidding. The memoization using standard tools impressed me.
> Compared to the result below it is only one order of magnitude.

I see, so the algorithms are basically similar. I haven't examined your
code closely yet. But I see you are using a much more efficient memo
table than I am. Yours is indexed on the offset into the coin list,
while mine uses the entire list. I might try adapting mine, maybe to
use arrays instead of a hash table.

I noticed I got an 8x speedup and 5x memory reduction by simply
reversing the order of the coin list, i.e. using (100 50 25 10 5 1)
instead of (1 5 10 25 50 100).

In reality, 50 cent coins and dollar coins are rarely used in the US.
50 cent coins are large enough to be cumbersome, and dollar coins never
became popular because they are too easily confused with quarters (they
are just slightly larger).

Canada has all the coins that the US has, plus a 2 dollar coin, and they
actually use them. France before the Euro had even more, I believe.

In article <87plyq9419.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>albert@cherry.(none) (albert) writes:
>> You must be kidding. The memoization using standard tools impressed me.
>> Compared to the result below it is only one order of magnitude.
>
>I see, so the algorithms are basically similar. I haven't examined your
>code closely yet. But I see you are using a much more efficient memo
>table than I am. Yours is indexed on the offset into the coin list,
>while mine uses the entire list. I might try adapting mine, maybe to
>use arrays instead of a hash table.

It is similar in the sense that at the end intermediate results
are calculated in the same partial sums. There is a great difference
that it is reversed. Memoization asks for the intermediate results e.g. 100,5
to be calculated. I start from the bottom and just guess that all
intermediate results are needed.I start with calculating 1,1 2,1 3,1 ..
This depend on analysing the problem.
You will get nowhere by this method if you apply at eulerproject
problem 502 (counting castles).

>
>I noticed I got an 8x speedup and 5x memory reduction by simply
>reversing the order of the coin list, i.e. using (100 50 25 10 5 1)
>instead of (1 5 10 25 50 100).
>
>In reality, 50 cent coins and dollar coins are rarely used in the US.
>50 cent coins are large enough to be cumbersome, and dollar coins never
>became popular because they are too easily confused with quarters (they
>are just slightly larger).
>
>Canada has all the coins that the US has, plus a 2 dollar coin, and they
>actually use them. France before the Euro had even more, I believe.

France used denominations 10 centimes up till 10 Franc .
The 10 Franc piece and 2 euro piece and the Can 2 dollar piece
have comparable purchasing power. A the time the Netherlands
had a 2.5 guilder coins, also comparable.
Formally the Euro has a regular 1 2 5 10 20 50 100 200 series
but the 1 and 2 cent pieces are no more used in the Netherlands.
So 5 or 6 coins in actual use.

Groetjes Albert
>
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

From the FysForth days. It will run out of stack before it
encounters out of memory, but it clocks less than 1ms when doing
900000 count_change .

Don't ask me how it works :--)

-marcel

DOC
(* http://www.webcom.com/nazgul/change.html#gcc

For the curious, here are the results computed for various amounts, using coins in
denominations 1, 5, 10, 25 and 50. The ``answer'' column shows the number of ways
found to make change for the given amount, the ``leaves'' column shows the number
of leaf nodes in the tree recursion, and the ``calls'' column shows the total number
of times the recursive procedure was called.

(amount=)
n answer leaves calls
---------------------------------------------
50 50 786 1571
100 292 7750 15499
150 972 35888 71775
200 2435 114795 229589
250 5126 293666 587331
300 9590 646296 1292591
350 16472 1276080 2552159
400 26517 2321013 4642025
450 40570 3958690 7917379
500 59576 6411306 12822611
550 84580 9950656 19901311
600 116727 14903135 29806269
650 157262 21654738 43309475
700 207530 30656060 61312119
750 268976 42427296 84854591
800 343145 57563241 115126481
850 431682 76738290 153476579
900 536332 100711438 201422875
950 658940 130331280 260662559

All timings (argument = 200) are in seconds on a 75 MHz Pentium running Linux 1.2.13
with libc 5.0.9, except that CMUCL needed Linux 2.0.25 and libc 5.2.18, and MSW Logo
was run under Windows 95.

gcc Gnu C 0.05
p2c P2C Pascal Translator 0.05
a60 Algol 60 to C Translator 0.08
cmucl CMU Common Lisp 0.09
gcl Gnu Common Lisp 0.09
scheme MIT Scheme 0.15
swn MIT Scheme without Numerics 1.17
scheme48 Scheme 48 3.65
p4 P4 Pascal P-code Interpreter 7.31
postscript Ghostscript 8.52
emacs Emacs Lisp 12.27
awk Gnu Awk 15.34
orth Orthogonal 32.48
tex TeX 46.49
a60 Algol 60 Interpreter 69.69
intercal INTERCAL 75.60
ucblogo UCB Logo 214.00
mswlogo MSW Logo 221.00
logopascal Pascal in Logo 1049.00
walk Lisp in Awk 43000.00

*)
ENDDOC

ANEW -count_change

#1500000 =: MAXSIZE

CREATE _cc1 1 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc2 2 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc3 3 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc4 4 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE
CREATE _cc5 5 , HERE MAXSIZE CELLS ALLOT MAXSIZE CELLS ERASE

CREATE _ccx 0 , _cc1 , _cc2 , _cc3 , _cc4 , _cc5 ,

: 'cc _ccx []CELL @ []CELL ; ( amount kinds_of_coins -- addr )

CREATE KOC 0 , 1 , 5 , #10 , #25 , #50 ,

: first_denomination KOC []CELL @ ; ( kinds_of_coins -- n )

The order of recursive calls is important!
Stack overflow will follow if they are interchanged.
: cc ( amount kinds_of_coins -- n )
OVER 0= IF 2DROP 1 EXIT ENDIF
OVER 0< IF 2DROP 0 EXIT ENDIF
DUP 0= IF 2DROP 0 EXIT ENDIF
2DUP 'cc DUP @ ?DUP IF >R 3DROP R> EXIT ENDIF
>R
2DUP DUP >R first_denomination - R> RECURSE >R
1- RECURSE
R> +
DUP R> ! ;

: count_change ( amount -- u )
DUP MAXSIZE >= ABORT" out of range"
CR TIMER-RESET
5 cc . .ELAPSED ;

: count_changes ( -- )
#1550 #50 DO CR I 5 .R TIMER-RESET
I 5 cc 9 .R 2 SPACES .ELAPSED
#50 +LOOP ;

CR .( Try: count_changes)

DOC
(*
P54C-166 iForth 1.11e
FORTH> count_changes
50 50 0.000 seconds elapsed.
100 292 0.000 seconds elapsed.
150 972 0.001 seconds elapsed.
200 2435 0.000 seconds elapsed.
250 5126 0.000 seconds elapsed.
300 9590 0.001 seconds elapsed.
350 16472 0.000 seconds elapsed.
400 26517 0.000 seconds elapsed.
450 40570 0.001 seconds elapsed.
500 59576 0.000 seconds elapsed.
550 84580 0.000 seconds elapsed.
600 116727 0.001 seconds elapsed.
650 157262 0.000 seconds elapsed.
700 207530 0.000 seconds elapsed.
750 268976 0.001 seconds elapsed.
800 343145 0.001 seconds elapsed.
850 431682 0.000 seconds elapsed.
900 536332 0.001 seconds elapsed.
950 658940 0.000 seconds elapsed.
1000 801451 0.000 seconds elapsed.
1050 965910 0.001 seconds elapsed.
1100 1154462 0.001 seconds elapsed.
1150 1369352 0.000 seconds elapsed.
1200 1612925 0.001 seconds elapsed.
1250 1887626 0.001 seconds elapsed.
1300 2196000 0.000 seconds elapsed.
1350 2540692 0.000 seconds elapsed.
1400 2924447 0.001 seconds elapsed.
1450 3350110 0.001 seconds elapsed.
1500 3820626 0.000 seconds elapsed. ok
*)
ENDDOC

EOF

In article <8af29958c24b1596a65d3d7f927f6211@news.novabbs.com>,
mhx <mhx@iae.nl> wrote:
>From the FysForth days. It will run out of stack before it
>encounters out of memory, but it clocks less than 1ms when doing
>900000 count_change .
>
>Don't ask me how it works :--)

It is a straightforward transsciption of the scheme code.

>
>-marcel
>
>
>DOC

<SNIP>

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -