In article <2023Dec31.170120@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>albert@cherry.(none) (albert) writes:
>>In article <2023Dec30.084142@mips.complang.tuwien.ac.at>,
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>
>>>\ SORTM (best-performing)
>>>: sort2 ( al ah -- )
>>> begin
>>> over cell+ over u< while
>>> partition recurse
>>> repeat
>>> 2drop ;
>>
>>I hate it if one uses U< in comparing numbers that hapenns
>>to be positive.
>
>What makes you think that this code compares numbers with U<? It
>actually compares two addresses, and I certainly don't want my sorting
>programs to fail when the sorted array straddles the addresses
>2147483647 and 2147483648 on a 32-bit system. Note that an "a" prefix
>typically does not indicate a signed number.

Sorry, my bad. My qsort's all works with indices.
That remark is out of place.

>
>Followups set to comp.lang.forth
>
>- 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 <20231228140434.720@kylheku.com>,
Kaz Kylheku <433-929-6894@kylheku.com> wrote:
>On 2023-12-28, George Neuner <gneuner2@comcast.net> wrote:
>> On Wed, 27 Dec 2023 23:12:07 -0000 (UTC), Kaz Kylheku
>><433-929-6894@kylheku.com> wrote:
>>
>>>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!
>>
>> Oops, you're right. I should have said Scheme is required to turn
>> *tail-recursion* into a loop.
>>
>> However, it is true that any recursion can be turned into a loop, and
>
>Can it, by an algorithm? That's a theoretical question that's above my pay grade.
>
>(Or, well, below; if I were a CS academic, I'd make less.)
>
>It doesn't seem obvious to me. Consider a graph traversal (like garbage
>collection marking). When you visit N pointers of a graph node, only the
>last visit can be a tail call. The first N-1 have to return to that
>node.
>
>There is a mildly famous (in some circles) pointer-reversal trick that
>has been used to implement a stackless traversal for garbage collection.
>But it's not a simple code transformation; it mutates the nodes in order
>to, effectively, create a return stack within the graph itself.
>
>That could not possibly be a valid automatic compiler optimization.

Note that in the example that started this threat (the count change
program) there was a double recursion, that cannot be handled
readily with a tail recursion optimisation.
On the other hand the alternative algorithm was easier to understand
even to lispers who are thoroughly familiar with recursion.
It runs fast without the need for external optimisation like a
memoization.

And may I stress it:
This is my home brew compiler. It is a couple of thousand lines in
assembler. The compiler is built by a single call to the fasm
assembler, that takes less that 10 mS. No external library.
Two nested loops, that is all. As small as the original algorithm.

>
>--
>TXRg ProgramminLanguage: http://nongnu.org/txr
--
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 <87jzowirtb.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>albert@cherry.(none) (albert) writes:
>> Rubin's program also can be run with an older version of Guile (2.0.13).
>> My guess is that Rubin made a fresh start each time
>
>Yes, I re-ran the program for each value, to get the timing.
>
>> with the mysterious ?singleton call.
>
>singleton? just checks whether a list has exactly one element. It is
>used to detect the case where only one coin is available to make change
>with. In that case, there are either 0 ways or 1 way to make change,
>depending on whether the coin denomination divides the amount to be
>changed.

Next guess.
With
(set! cc (memoize cc))
you overwrite the `cc to henceforth to use the memoizer.

That means that the second calculation of the same results
is immediate and that larger results benefit from the
smaller results that are calculated before them.
True?

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 -

albert@cherry.(none) (albert) writes:
> you overwrite the `cc to henceforth to use the memoizer.
>
> That means that the second calculation of the same results
> is immediate and that larger results benefit from the
> smaller results that are calculated before them.
> True?

Yes, that is exactly right, sorry about the slow response. The Python
equivalent (untested) is:

def memoize(f):
def m(*args):
if args in memo: return memo[args]
memo[args] = f(*args)
return memo[args]
return m

@memoize
def cc(n, coins): ...

There is an aspect of the Scheme version that confuses me slightly but I
will ask some Scheme experts (I'm not one myself).

albert@cherry.(none) (albert) writes:
> On the other hand the alternative algorithm was easier to understand
> even to lispers who are thoroughly familiar with recursion.
> It runs fast without the need for external optimisation like a
> memoization.

I don't think I examined it, but is that the one that iteratively fills
the lookup table before doing the requested value?

I found in the memoizing Scheme version, after computing (cc 1000000),
the memo table held 670004 entries, which is much less than the 5
million that would be used by precomputing all the earlier entries.

When I removed the optimization (I originally hadn't thought of it as
one) of quickly checking divisibility when only one coin denomination
was available, the table size went up to 2470005 entries, still half
of what it would have been from precomputing everything.

In article <87ttnu54qa.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>albert@cherry.(none) (albert) writes:
>> On the other hand the alternative algorithm was easier to understand
>> even to lispers who are thoroughly familiar with recursion.
>> It runs fast without the need for external optimisation like a
>> memoization.
>
>I don't think I examined it, but is that the one that iteratively fills
>the lookup table before doing the requested value?
>
>I found in the memoizing Scheme version, after computing (cc 1000000),
>the memo table held 670004 entries, which is much less than the 5
>million that would be used by precomputing all the earlier entries.
>
>When I removed the optimization (I originally hadn't thought of it as
>one) of quickly checking divisibility when only one coin denomination
>was available, the table size went up to 2470005 entries, still half
>of what it would have been from precomputing everything.

Once you do memoization in Scheme, it is important that you mention
the order of nominations (increasing or decreasing).
The minimum should be N/50 + N/25 + N/10 + N/5 + N as far a I can see.
(In the order of increasion nominations)
I can't understand that there can be less that a million entries, unless ..
Can the memoization "see" that once cc(N-5,5) is known,
cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
in the iterative version),
and that cc(N,5) becomes cc(N,4)+cc(N-5,5) . That is chill.
(The iterative version also saves some 50% of the time going 50 -> 1)

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 -

> Can the memoization "see" that once cc(N-5,5) is known,
> cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
[..]

I never used naive memoization much because the table size becomes
impractical for real-world problems. If it is known how to compress
N-dim tables (in hopefully a simple way), I'd be very interested
to know how it is done (even when N=1).

-marcel

On 30/12/2023 15:54, Anton Ertl wrote:
> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> \ SORTI (slightly slower than SORTM, slightly faster than SORTI2)
>>>
>>> : sorti ( addr u -- )
>>> cells over + 0 -rot begin ( 0 al1 ah1 .. aln ahn )
>>> begin
>>> over cell+ over u>= while
>>> 2drop dup 0= if
>>> drop exit then
>>> repeat
>>> partition
>>> again ;
>>
>> Let's see if we can improve on this with the extended CASE (untested):
>>
>> : sorti3 ( addr u -- )
>> cells over + 0 -rot case ( 0 al1 ah1 .. aln ahn )
>> over cell+ over u< ?of partition contof
>> 2drop dup ?of contof
>> endcase
>> drop ;
>>
>> It looks neater and gets rid of the EXIT in the middle.
>
> But it suffers from me falling into Eaker's trap: ENDCASE already
> performs a DROP, so the DROP at the end is wrong:
>
> : sorti3 ( addr u -- )
> cells over + 0 -rot case ( 0 al1 ah1 .. aln ahn )
> over cell+ over u< ?of partition contof
> 2drop dup ?of contof
> endcase ;
>

Compare this with using the FOR-EACH construct discussed recently. THE
FOR-EACH definitions are:

: cs-drop-dest ( CS: dest -- ) postpone true postpone until ;

\ A workaround to get the MAP with locals working in GForth
[undefined] assume-live [if] : assume-live ; immediate [then]

: for-each
postpone ahead postpone assume-live postpone begin postpone 0<
postpone if postpone begin 3 cs-roll postpone then
; immediate

synonym do[ while [defined] [SwiftForth] [if] immediate [then]

: ]next
postpone repeat postpone then cs-drop-dest
; immediate

\ |> is the pipeline operator
: |> ( 0 -- ) \ or ( n -- n )
3 cs-pick postpone ?dup postpone 0= postpone until
; immediate

And SORTI3 using FOR-EACH could be:

: sorti3 ( ad u -- )
cells over + 0 -rot
for-each true
do[ over cell+ over u< dup >r if partition then r> |>
2drop dup 0= abs |>
]next drop
;

Untested on a real sort but tested with dummy data and dummy code for
the pipeline operations.

SORTi3 is written like that for comparison with your definition. I would
probably write it as:

: sort-partition \ There is probably a better name
over cell+ over u< dup >r if partition then r>
;

: ?done ( ad -- ad 0|1 ) dup 0= abs ;

: sorti3 ( ad u -- )
cells over + 0 -rot
for-each true
do[ sort-partition |> 2drop ?done |> ]next drop
;

The FOR-EACH TRUE is a bit awkward (i.e. no iterator needed) and
supports RUVIM's comment that the the iterator should just be first in
the pipeline. An alternative might be defining FOR[ that omits an
iterator and DO[. i.e. ... FOR[ ... |> ... etc ]NEXT

--
Gerry

On 2024-01-04, mhx <mhx@iae.nl> wrote:
>> Can the memoization "see" that once cc(N-5,5) is known,
>> cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
> [..]
>
> I never used naive memoization much because the table size becomes
> impractical for real-world problems. If it is known how to compress
> N-dim tables (in hopefully a simple way), I'd be very interested
> to know how it is done (even when N=1).

In some cases, eviction may be possible (i.e. caching).

If we consider memoized Fibonacci, once it has calculated fib(7),
it's not going to have to calculate fib(5) again. That value could
be evacuated from the table. In fact, I suspect that a LRU table
with only several entries would serve.

This is easily confirmed code-wise, using TXR Lisp:

$ txr -i fib.tl
Read-eval-disagree-downvote-insult treadmill initialized! Enter an expression:
1> (compile 'fib-rec)
#<vm fun: 2 param>
2> (pprof (fib 200))
malloc bytes: 74356
gc heap bytes: 66272
total: 140628
milliseconds: 2
453973694165307953197296969697410619233826
3> (trace fib-rec)
nil
4> (fib 8)
(fib-rec (8 #(nil nil nil))
(fib-rec (6 #(nil nil nil))
(fib-rec (4 #(nil nil nil))
(fib-rec (2 #(nil nil nil))
(fib-rec (0 #(nil nil nil))
1)
(fib-rec (1 #(nil nil nil))
1)
2)
(fib-rec (3 #((2 . 2) nil nil))
(fib-rec (1 #((2 . 2) nil nil))
1)
(fib-rec (2 #((2 . 2) nil nil))
2)
3)
5)
(fib-rec (5 #((4 . 5) (3 . 3) (2 . 2)))
(fib-rec (3 #((4 . 5) (3 . 3) (2 . 2)))
3)
(fib-rec (4 #((4 . 5) (3 . 3) (2 . 2)))
5)
8)
13)
(fib-rec (7 #((6 . 13) (5 . 8) (4 . 5)))
(fib-rec (5 #((6 . 13) (5 . 8) (4 . 5)))
8)
(fib-rec (6 #((6 . 13) (5 . 8) (4 . 5)))
13)
21)
34)
34

Calculating (fib 200) is instantaneous. The trace shows
that the caching with a three element table is sufficient;
E.g. once (fib-rec 5) is calculated, the second time
it is encountered, it no longer recurses to (fib-rec 3)
and (fib-rec 4); it just returns 8.

This is the code in fib.tl:

(defun fib-rec (n table)
(or (if (meq n 0 1) 1)
(cdr [find n table : car])
(flow (+ (fib-rec (ppred n) table)
(fib-rec (pred n) table))
(let f)
(cons n)
(set [(nrot table -1) 0])
(ret f))))

(defun fib (n)
(fib-rec n (vector 3)))

The auxiliary table parameter always holds the same 3 element
vector object throughout the recursion. The vector holds
cons pairs of the form (cons n (fib n)), thus mapping Fibonacci
indices to values.

Whenever there is a table miss, the nrot function is used to
rotate the table entries down, and the new value is placed
in the first element, [table 0].

In fact, a two element table is sufficient; if we change
the (vector 3) to (vector 2), the performance is not affected.

Moreover, it deosn't matter whether the recursive step is
(+ (fib-rec (ppred n) table) (fib-rec (pred n) table)) or
(+ (fib-rec (pred n) table) (fib-rec (ppred n) table));
a two-element cache is sufficient. (TXR Lisp is strictly
evaluated, left-to-right, like Common Lisp, so if we
vary the order of the arguments to +, we can control the
order in which the recursive calls take place.)

In conclusion, while memoized Fibonacci is great textbook
example for illustrating the power of memoization,
it woudl behoove the textbooks to also add the observation
that it still works with a two-slot LRU cache.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

mhx@iae.nl (mhx) writes:
> If it is known how to compress N-dim tables (in hopefully a simple
> way), I'd be very interested to know how it is done (even when N=1).

In the Scheme code I posted, the "coordinate list" is used as a hash key.

On 2024-01-04, Kaz Kylheku <433-929-6894@kylheku.com> wrote:
> In conclusion, while memoized Fibonacci is great textbook
> example for illustrating the power of memoization,
> it woudl behoove the textbooks to also add the observation
> that it still works with a two-slot LRU cache.

However, due to the function activation frames, memory
use is still O(n).

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

albert@cherry.(none) (albert) writes:
> Can the memoization "see" that once cc(N-5,5) is known,
> cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
> in the iterative version),

I'm not sure what you mean by that. The memoization scheme proceeds
recursively until it reaches a place where it knows how to get a
numerical answer. Then it computes and remembers that answer, so it can
use it the next time the calculation gets there.

> and that cc(N,5) becomes cc(N,4)+cc(N-5,5) . That is chill.

Yes that is right.

> (The iterative version also saves some 50% of the time going 50 -> 1)

I don't think I understand your iterative algorithm, but I think there
is one that actually doesn't have to remember the calculation results
all the way back to the beginning. It only has to remember the last 100
(or whatever the size of the largest coin is), and similarly for the
other coin sizes. I'll see if I can code that.

On Thursday, January 4, 2024 at 3:22:19 PM UTC-6, Paul Rubin wrote:
> albert@cherry.(none) (albert) writes:
> > Can the memoization "see" that once cc(N-5,5) is known,
> > cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
> > in the iterative version),
> I'm not sure what you mean by that. The memoization scheme proceeds
> recursively until it reaches a place where it knows how to get a
> numerical answer. Then it computes and remembers that answer, so it can
> use it the next time the calculation gets there.
> > and that cc(N,5) becomes cc(N,4)+cc(N-5,5) . That is chill.
> Yes that is right.
> > (The iterative version also saves some 50% of the time going 50 -> 1)
> I don't think I understand your iterative algorithm, but I think there
> is one that actually doesn't have to remember the calculation results
> all the way back to the beginning. It only has to remember the last 100
> (or whatever the size of the largest coin is), and similarly for the
> other coin sizes. I'll see if I can code that.

|>I think there is one that actually doesn't have to remember the calculation results
all the way back to the beginning.
To convert Fibonacci to a linear recursion one needs to keep two (usually the two previous) values
In Forth: swap, over, plus
On a register machine, one can do two iterations with two replace adds (a+b -> a, b+a -> b)
Also possible on a stack machine with the corresponding operators.

James Brakefield <jim.brakefield@ieee.org> writes:
> To convert Fibonacci to a linear recursion one needs to keep two
> (usually the two previous) values

This is about the coins problem, not Fibonacci.

In article <87le946bga.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>albert@cherry.(none) (albert) writes:
>> Can the memoization "see" that once cc(N-5,5) is known,
>> cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
>> in the iterative version),
>
>I'm not sure what you mean by that. The memoization scheme proceeds
>recursively until it reaches a place where it knows how to get a
>numerical answer. Then it computes and remembers that answer, so it can
>use it the next time the calculation gets there.
>
>> and that cc(N,5) becomes cc(N,4)+cc(N-5,5) . That is chill.
>
>Yes that is right.
>
>> (The iterative version also saves some 50% of the time going 50 -> 1)
>
>I don't think I understand your iterative algorithm, but I think there
>is one that actually doesn't have to remember the calculation results
>all the way back to the beginning. It only has to remember the last 100
>(or whatever the size of the largest coin is), and similarly for the
>other coin sizes. I'll see if I can code that.

I thought of that too, and it doesn't work. Something inherent of
two way recursion.

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 <20240104101004.858@kylheku.com>,
Kaz Kylheku <433-929-6894@kylheku.com> wrote:
>On 2024-01-04, mhx <mhx@iae.nl> wrote:
>>> Can the memoization "see" that once cc(N-5,5) is known,
>>> cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
>> [..]
>>
>> I never used naive memoization much because the table size becomes
>> impractical for real-world problems. If it is known how to compress
>> N-dim tables (in hopefully a simple way), I'd be very interested
>> to know how it is done (even when N=1).
>
>In some cases, eviction may be possible (i.e. caching).
>
>If we consider memoized Fibonacci, once it has calculated fib(7),
>it's not going to have to calculate fib(5) again. That value could
>be evacuated from the table. In fact, I suspect that a LRU table
>with only several entries would serve.
>
>This is easily confirmed code-wise, using TXR Lisp:
>
>$ txr -i fib.tl
>Read-eval-disagree-downvote-insult treadmill initialized! Enter an expression:
>1> (compile 'fib-rec)
>#<vm fun: 2 param>
>2> (pprof (fib 200))
>malloc bytes: 74356
>gc heap bytes: 66272
>total: 140628
>milliseconds: 2
>453973694165307953197296969697410619233826
>3> (trace fib-rec)
>nil
>4> (fib 8)
>(fib-rec (8 #(nil nil nil))
> (fib-rec (6 #(nil nil nil))
> (fib-rec (4 #(nil nil nil))
> (fib-rec (2 #(nil nil nil))
> (fib-rec (0 #(nil nil nil))
> 1)
> (fib-rec (1 #(nil nil nil))
> 1)
> 2)
> (fib-rec (3 #((2 . 2) nil nil))
> (fib-rec (1 #((2 . 2) nil nil))
> 1)
> (fib-rec (2 #((2 . 2) nil nil))
> 2)
> 3)
> 5)
> (fib-rec (5 #((4 . 5) (3 . 3) (2 . 2)))
> (fib-rec (3 #((4 . 5) (3 . 3) (2 . 2)))
> 3)
> (fib-rec (4 #((4 . 5) (3 . 3) (2 . 2)))
> 5)
> 8)
> 13)
> (fib-rec (7 #((6 . 13) (5 . 8) (4 . 5)))
> (fib-rec (5 #((6 . 13) (5 . 8) (4 . 5)))
> 8)
> (fib-rec (6 #((6 . 13) (5 . 8) (4 . 5)))
> 13)
> 21)
> 34)
>34
>
>Calculating (fib 200) is instantaneous. The trace shows
>that the caching with a three element table is sufficient;
>E.g. once (fib-rec 5) is calculated, the second time
>it is encountered, it no longer recurses to (fib-rec 3)
>and (fib-rec 4); it just returns 8.
>
>This is the code in fib.tl:
>
>(defun fib-rec (n table)
> (or (if (meq n 0 1) 1)
> (cdr [find n table : car])
> (flow (+ (fib-rec (ppred n) table)
> (fib-rec (pred n) table))
> (let f)
> (cons n)
> (set [(nrot table -1) 0])
> (ret f))))
>
>(defun fib (n)
> (fib-rec n (vector 3)))
>
>The auxiliary table parameter always holds the same 3 element
>vector object throughout the recursion. The vector holds
>cons pairs of the form (cons n (fib n)), thus mapping Fibonacci
>indices to values.
>
>Whenever there is a table miss, the nrot function is used to
>rotate the table entries down, and the new value is placed
>in the first element, [table 0].
>
>In fact, a two element table is sufficient; if we change
>the (vector 3) to (vector 2), the performance is not affected.
>
>Moreover, it deosn't matter whether the recursive step is
>(+ (fib-rec (ppred n) table) (fib-rec (pred n) table)) or
>(+ (fib-rec (pred n) table) (fib-rec (ppred n) table));
>a two-element cache is sufficient. (TXR Lisp is strictly
>evaluated, left-to-right, like Common Lisp, so if we
>vary the order of the arguments to +, we can control the
>order in which the recursive calls take place.)
>
>In conclusion, while memoized Fibonacci is great textbook
>example for illustrating the power of memoization,
>it woudl behoove the textbooks to also add the observation
>that it still works with a two-slot LRU cache.
+1

You have managed to arrive at this iterative version, that keeps
track of only two values.
: FIB
>R 0 1
R> 0 ?DO SWAP OVER + 1 +LOOP
DROP
;

(Interested to see this coded in lisp. )

>
>Mastodon: @Kazinator@mstdn.ca

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 <20240104114837.742@kylheku.com>,
Kaz Kylheku <433-929-6894@kylheku.com> wrote:
>On 2024-01-04, Kaz Kylheku <433-929-6894@kylheku.com> wrote:
>> In conclusion, while memoized Fibonacci is great textbook
>> example for illustrating the power of memoization,
>> it woudl behoove the textbooks to also add the observation
>> that it still works with a two-slot LRU cache.
>
>However, due to the function activation frames, memory
>use is still O(n).

In the coins example I did not use memoization per se, but
rather a reverse memoization. Please check that the memory
usage with the Forth example for FIB, is O(1), also with
reverse memoization.
[I had success with this technique in several of the 400 problems
of projecteuler.net that I solved.]
>
>--
>Mastodon: @Kazinator@mstdn.ca

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 -

On 2024-01-05, albert@cherry.(none) (albert) <albert@cherry> wrote:
> You have managed to arrive at this iterative version, that keeps
> track of only two values.

Well, yes; that is understood and where the intution comes from for why
Memoization implicitly reduces the exponential explosion in Fibonacci.
It must be effectively iterating on the recurrence in the
straightforward way, since it takes linear time.

The recurrence relation implies a two-element state; I guessed at
a cache size of three items as a fudge factor; when that
was debugged, I reduced to two.

Sometimes, the Fibonacci recurrence is expressed as a matrix
multiplication on a state vector [a b]

[1 1][a] => [a + b]
[1 0][b] [ a ]

a receives the sum of a + b, while b receives the prior value of a.

Raising this matrix to an arbitrary integer power is how we arrive
at the closed form solution.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Kaz Kylheku wrote:

> Sometimes, the Fibonacci recurrence is expressed as a matrix
> multiplication on a state vector [a b]

> [1 1][a] => [a + b]
> [1 0][b] [ a ]

> a receives the sum of a + b, while b receives the prior value of a.

> Raising this matrix to an arbitrary integer power is how we arrive
> at the closed form solution.

Really nice! I'll keep this general idea in a safe place.

-marcel

On 2024-01-05, mhx <mhx@iae.nl> wrote:
> Kaz Kylheku wrote:
>
>> Sometimes, the Fibonacci recurrence is expressed as a matrix
>> multiplication on a state vector [a b]
>
>> [1 1][a] => [a + b]
>> [1 0][b] [ a ]
>
>> a receives the sum of a + b, while b receives the prior value of a.
>
>> Raising this matrix to an arbitrary integer power is how we arrive
>> at the closed form solution.
>
> Really nice! I'll keep this general idea in a safe place.

You don't have to; it's found in textbooks.

Using linear algebra techniques found in introductory texts, you can do
this this:

n
[1 1]
[1 0]

The details escape me, much like a departing youthful appearance, but
basically we can factor it into a form

n
U X V

where U, X, V are all 2x2 matrices. The middle one X is special
in that it is diagonal (consisting of a diagonal trace of eigenvalues).
A diagonal matrix is easy to exponentiate.

Something like that.

That gives us that closed form formula for Fibonacci with those
square roots of five in it.

Closely relating to the Golden Ratio! Which is (/ (+ 1 (sqrt 5)) 2).
The ratio of successive values of the Fibonacci numbers approaches
the golden ratio.

1> (/ (fib 50) (fib 49))
1.61803398874989

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Kaz Kylheku wrote:

> On 2024-01-05, mhx <mhx@iae.nl> wrote:
>> Kaz Kylheku wrote:
>>
>>> Sometimes, the Fibonacci recurrence is expressed as a matrix
>>> multiplication on a state vector [a b]
>>
>>> [1 1][a] => [a + b]
>>> [1 0][b] [ a ]
>>
>>> a receives the sum of a + b, while b receives the prior value of a.
>>
>>> Raising this matrix to an arbitrary integer power is how we arrive
>>> at the closed form solution.
>>
>> Really nice! I'll keep this general idea in a safe place.

> You don't have to; it's found in textbooks.

It strongly connects to the control engineering approaches I use for
analyzing recurrences in switched electronic systems.

> Using linear algebra techniques found in introductory texts, you can do
> this this:

> n
> [1 1]
> [1 0]

> The details escape me, much like a departing youthful appearance, but
> basically we can factor it into a form

> n
> U X V

> where U, X, V are all 2x2 matrices. The middle one X is special
> in that it is diagonal (consisting of a diagonal trace of eigenvalues).
> A diagonal matrix is easy to exponentiate.

Tricky one to write from scratch :--) I implemented the Pade approximation
(the stablest one) for it when my appearance was still youthful.

> Something like that.

> That gives us that closed form formula for Fibonacci with those
> square roots of five in it.

> Closely relating to the Golden Ratio! Which is (/ (+ 1 (sqrt 5)) 2).
> The ratio of successive values of the Fibonacci numbers approaches
> the golden ratio.

Almost like a party trick. I love to find elegant techniques in
unrelated fields of research that solve (my) practical problems in
unexpected ways.

> 1> (/ (fib 50) (fib 49))
> 1.61803398874989

-marcel

mhx@iae.nl (mhx) writes:
>Kaz Kylheku wrote:
>> Closely relating to the Golden Ratio! Which is (/ (+ 1 (sqrt 5)) 2).
>> The ratio of successive values of the Fibonacci numbers approaches
>> the golden ratio.
>
>Almost like a party trick. I love to find elegant techniques in
>unrelated fields of research that solve (my) practical problems in
>unexpected ways.

Not sure if you wrote this about the golden ratio, but given the way
the golden ratio phi is defined, I find it unsurprising that

phi = lim(n->inf) fib(n+1)/fib(n)

The definition of the golden ratio is

(a+b)/a = a/b = phi (with a>b>0)

or, as described in <https://en.wikipedia.org/wiki/Golden_ratio>:

| a+b is to a as a is to b

Given that's exactly how Fibonacci numbers are formed, if the sequence
of ratios fib(n+1)/fib(n) converges, the result must be the golden
ratio.

It's equally unsurprising that for the Lucas numbers, which are formed
in the same way, but with different base values (2 and 1 instead of 0
and 1), the limit of L(n+1)/L(n) is also the golden ratio.

Conversely, you can compute the nth Fibonacci number using a closed
formula that involves phi.

- 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