Lawrence D'Oliveiro <ldo@nz.invalid> writes:

> On Fri, 29 Dec 2023 23:22:53 -0300, Julieta Shem wrote:
>
>> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>>
>>> Arbitrary gotos:
>>> -- useful/desirable? Not so.
>>
>> Very useful, very desirable.
>
> Come on ... you don’t mean you code that way, do you?

I do and, of course, I'm not the only one.

Knuth, Donald E. ``Structured programming with /go-to/ statements.''
ACM Computing Surveys (CSUR) 6.4 (1974): 261-301.

On Sat, 30 Dec 2023 17:17:07 -0300, Julieta Shem wrote:

> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>
>> On Fri, 29 Dec 2023 23:22:53 -0300, Julieta Shem wrote:
>>
>>> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>>>
>>>> Arbitrary gotos:
>>>> -- useful/desirable? Not so.
>>>
>>> Very useful, very desirable.
>>
>> Come on ... you don’t mean you code that way, do you?
>
> I do and, of course, I'm not the only one.
>
> Knuth, Donald E. ``Structured programming with /go-to/ statements.''
> ACM Computing Surveys (CSUR) 6.4 (1974): 261-301.

Frankly, I don’t know how realistic his examples were: all I can say is,
dynamic memory allocation was a lot less common in his day.

Here’s my exposition on goto-free programming, and why it’s such a good
idea: <https://gitlab.com/ldo/a_structured_discipline_of_programming/>.

On 2023-12-30, Lawrence D'Oliveiro <ldo@nz.invalid> wrote:
> On Sat, 30 Dec 2023 17:17:07 -0300, Julieta Shem wrote:
>
>> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>>
>>> On Fri, 29 Dec 2023 23:22:53 -0300, Julieta Shem wrote:
>>>
>>>> Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>>>>
>>>>> Arbitrary gotos:
>>>>> -- useful/desirable? Not so.
>>>>
>>>> Very useful, very desirable.
>>>
>>> Come on ... you don’t mean you code that way, do you?
>>
>> I do and, of course, I'm not the only one.
>>
>> Knuth, Donald E. ``Structured programming with /go-to/ statements.''
>> ACM Computing Surveys (CSUR) 6.4 (1974): 261-301.
>
> Frankly, I don’t know how realistic his examples were: all I can say is,
> dynamic memory allocation was a lot less common in his day.
>
> Here’s my exposition on goto-free programming, and why it’s such a good
> idea: <https://gitlab.com/ldo/a_structured_discipline_of_programming/>.

There is a fundamental difference between goto and using control
structures. Control structures nest, and so they avoid producing
program control flow graphs that have certain undesirable properties,
which is not guaranteed with goto.

For instance control structures will not produce a graph that is
analogous to what we get from this:

if (condition_a) {
// ...
label:
statement;
// ...
}

if (condition_b) {
// ...
goto label;
}

The feature here is that we have a backwards branch, but it's not
exactly an ordinary backwards branch. A backwards branch normally goes
back to a node which was necessarily visited on the way to the branch.

The branch above goes to a node which is not necessarily reached
on the way to the goto. In fact, statement may be executing for
the first time when the "goto label" branch is taken.

If you banish gotos, you can guarantee to your compiler back-end
that you don't have these kinds of branches in the program graph.
All the backwards branches to to program nodes that dominate
the branch points. (Meaning that the branch points are not reachable in
the forward direction without traversing those backwards target points.)

The Red Dragon Book discusses this (1988 edition).

I think these kinds of odd backward gotos will also tend to
make the logic harder to follow.

--
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.

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.
Are you really expecting the index straddles the boundary e.g
9223372036854775807 and 9223372036854775809

<SNIP>
>- anton
--
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:
>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.

Followups set to comp.lang.forth

- 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

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 <87a5pveeit.fsf@yaxenu.org>, Julieta Shem <jshem@yaxenu.org> wrote:
>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.

That is pretty insane. It is however the prerogative of a math book,
that you are allowed to define whatever terms as soon as you include
the definitions. The reader should be aware that the term may
not be in universal 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 -

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).

On Wed, 03 Jan 2024 10:17:43 -0800, Paul Rubin wrote:

> The Python equivalent (untested) is:

Fixed missing definition of “memo” variable:

def memoize(f) :

memo = {}

def m(*args) :
if args not in memo :
memo[args] = f(*args)
#end if
return memo[args]
#end m

#begin memoize
return m
#end memoize

Of course this still doesn’t work with keyword args ...

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 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.

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.

On Fri, 5 Jan 2024 21:24:00 -0000 (UTC), Kaz Kylheku wrote:

> The ratio of successive values of the Fibonacci numbers approaches the
> golden ratio.

The golden ratio is also obtained by just about the simplest of all
continued fractions:

1
1 + -------------
1
1 + ---------
1
1 + -----
...

On 2024-01-05, Lawrence D'Oliveiro <ldo@nz.invalid> wrote:
> On Fri, 5 Jan 2024 21:24:00 -0000 (UTC), Kaz Kylheku wrote:
>
>> The ratio of successive values of the Fibonacci numbers approaches the
>> golden ratio.
>
> The golden ratio is also obtained by just about the simplest of all
> continued fractions:
>
> 1
> 1 + -------------
> 1
> 1 + ---------
> 1
> 1 + -----
> ...

That's recursive, like a Droste image, and so we can rewrite it
self-referentially:

R = 1 + 1/R

R^2 = R + 1

R^2 - R - 1 = 0

Then solve for R using the quadratic formula:

1 +/- sqrt(5)
R = -------------
2

One of the solutions is negative, which we can reject. A continued
fraction with only positive constants and addition cannot have
a limit that is negatively valued.

---

Puzzle:

Could we use this information somehow to neatly build an amplifier whose
closed-loop gain is the Golden Ratio, using only resistors that have
integer-valued resistances in Ohms?

I might post this to the Electronics Stack Exchange.

--
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.