Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
> Pancho <Pancho.Jones@proton.me> writes:
>
>> On 30/12/2023 23:19, BGB wrote:
>>
>>> Granted, There are plenty of other much more efficient ways of
>>> calculating Fibonacci numbers...
>>
>> Yes. In order of effort.
>>
>> 1) Memoize the recursive function.
>> 2) Return values for (n-1,n-2) as a tuple, and make it single (tail)
>> recursive. Which a smart compiler could theoretically convert to an
>> iterative loop.
>> 3) Write an iterative loop yourself.
>> 4) Remember college maths, and solve the recurrence relation to give a
>> very simple closed form solution.
>
> All of these approaches have drawbacks of one sort or another.
>
> For (1), we end up writing more code and using more memory.
> Some problems are a good fit to memoization, but computing
> Fibonacci numbers isn't one of the.
>
> For (2), compilers are not so good at dealing with tail
> recursion when the return value is a pair of results
> rather than a single result.
>
> For (3), iterative code takes more mental effort to see
> that it works than does a simple recursive version.

I don't think that

#include <stdio.h>

unsigned long int fib (int n)
{ unsigned long f1, f2, fn;

if (n < 2)
return 1;

f1 = 1;
f2 = 1;
while (n >= 2) {
fn = f2 + f1;
f1 = f2;
f2 = fn;
n--;
}
return fn;
}

is particularly intellecually challenging.

However, my favorite method is https://oeis.org/A331164 .
Not because it is particularly effective or easy to understand,
but because the sequence is nice to listen to.

Thomas Koenig wrote:

> #include <stdio.h>

> unsigned long int fib (int n)
> {
> unsigned long f1, f2, fn;

> if (n < 2)
> return 1;

> f1 = 1;
> f2 = 1;
> do { // we know n >=2 so at least 1 path through the loop is performed.
> fn = f2 + f1;
> f1 = f2;
> f2 = fn;
> n--;
> } while( n > 2 );
> return fn;
> }

Saves 1 cycle and and at least 1 instruction of code footprint.

MitchAlsup wrote:
> Daniel James wrote:
>
>> Unlike, say:
>
>>    double fib( int n )
>>    {
>>        return (pow( (1+sqrt(5.0))/2, n+1 )
>>                - pow( (1-sqrt(5.0))/2, n+1 ))
>>            / sqrt(5.0);
>>    }
>
> Looks fast to me::
>
> fib:
>     ADD    R2,R1,#1
>     POWN    R3,#(1+sqrt(5.0))/2,R2
>     POWN    R4,#(1-sqrt(5.0))/2,R2
>     FADD    R2,R3,R4
>     FDIV    R1,R2,#sqrt(5)
>     RET

The final FDIV should be a FMUL by (1.0/sqrt(5.0))

Probably followed by a round to nearest int.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Tim Rentsch wrote:
> Daniel James <daniel@me.invalid> writes:
>
>> However, the (signed) 64-bit integer result overflows for fib(n) where
>> n>45, which is more of a problem.
>
> fib( 92 ) is still less than 1UL << 63 (or fib(93) for a 64-bit
> unsigned type).
>
> And fib( 186 ) still fits in a 128-bit unsigned type.
>
If calculating fib(n) for n in the fixed 0..186 range is actually
important to you, then you would obviously allocate 16*187 (about 3KB)
bytes of table space and do a simple lookup instead.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> Thomas Koenig wrote:
>
>> #include <stdio.h>
>
>> unsigned long int fib (int n)
>> {
>>   unsigned long f1, f2, fn;
>
>>   if (n < 2)
>>     return 1;
>
>>   f1 = 1;
>>   f2 = 1;
>>   do { // we know n >=2 so at least 1 path through the loop is performed.
>>     fn = f2 + f1;
>>     f1 = f2;
>>     f2 = fn;
>>     n--;
>>   } while( n > 2 );
>>   return fn;
>> }
>
> Saves 1 cycle and and at least 1 instruction of code footprint.

I have written asm code for this, and noted that on x86 where reg MOVes
used to cost a cycle, it was better to unroll and get rid of the reg-reg
moves.

I think the following should work:

u64 fib(unsigned n)
{ if (n-- < 2) return 1;
a = 1; b = 1;

a += (n & 1); // Odd remaining n
n >>= 1;

while (n--) {
b += a;
a += b;
}
return a;
}

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Daniel James <daniel@me.invalid> writes:

> On 31/12/2023 09:12, Pancho wrote:
>
>> In fact, given that fib grows exponentially, so we only ever need to
>> calculate it for small values of n, the only ?bad? solution is the
>> naive double recursive one.
>
> Well, I might disagree.
>
> Given that we only ever need to calculate it for small values of n (as
> you say, and if that's true) its efficiency doesn't matter. If you
> need to compute it often enough that efficiency might become relevant
> just put the results in a table and use that. Given that fib goes over
> 10^12 after about 60 terms it needn't be a very big table.

When the size of the table is more than ten times the size of
the code, and the code is reasonably fast, using a table is a
poor choice. Fibonacci functions don't have to be slow.

> The naive doubly recursive solution has the huge merit of being
> human-readable.

But unacceptably slow.

> Unlike, say:
>
> double fib( int n )
> {
> return (pow( (1+sqrt(5.0))/2, n+1 )
> - pow( (1-sqrt(5.0))/2, n+1 ))
> / sqrt(5.0);
> }
>
> ... which is great for fibs of big values, but not fast for small ones.

Unacceptable for fibs of big values, because the values computed
are wrong.

Thomas Koenig <tkoenig@netcologne.de> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
>
>> Pancho <Pancho.Jones@proton.me> writes:
>>
>>> On 30/12/2023 23:19, BGB wrote:
>>>
>>>> Granted, There are plenty of other much more efficient ways of
>>>> calculating Fibonacci numbers...
>>>
>>> Yes. In order of effort.
>>>
>>> 1) Memoize the recursive function.
>>> 2) Return values for (n-1,n-2) as a tuple, and make it single (tail)
>>> recursive. Which a smart compiler could theoretically convert to an
>>> iterative loop.
>>> 3) Write an iterative loop yourself.
>>> 4) Remember college maths, and solve the recurrence relation to give a
>>> very simple closed form solution.
>>
>> All of these approaches have drawbacks of one sort or another.
>>
>> For (1), we end up writing more code and using more memory.
>> Some problems are a good fit to memoization, but computing
>> Fibonacci numbers isn't one of the.
>>
>> For (2), compilers are not so good at dealing with tail
>> recursion when the return value is a pair of results
>> rather than a single result.
>>
>> For (3), iterative code takes more mental effort to see
>> that it works than does a simple recursive version.
>
> I don't think that
>
> #include <stdio.h>
>
> unsigned long int fib (int n)
> {
> unsigned long f1, f2, fn;
>
> if (n < 2)
> return 1;
>
> f1 = 1;
> f2 = 1;
> while (n >= 2) {
> fn = f2 + f1;
> f1 = f2;
> f2 = fn;
> n--;
> }
> return fn;
> }
>
> is particularly intellecually challenging.

I'm sure there are other people who feel the same way.

Even so, when a short, functional, recursive version
is available, it is often easier to write, easier to
read, and simpler to show that it produces correct
results, in which case doing that is a better choice,
even if an imperative version is not particularly
intellecually challenging.

Incidentally your code produces wrong values, as
fib(0) is 0 and fib(1) is 1.

Tim Rentsch wrote:
> Daniel James <daniel@me.invalid> writes:
>
>> On 31/12/2023 09:12, Pancho wrote:
>>
>>> In fact, given that fib grows exponentially, so we only ever need to
>>> calculate it for small values of n, the only ?bad? solution is the
>>> naive double recursive one.
>>
>> Well, I might disagree.
>>
>> Given that we only ever need to calculate it for small values of n (as
>> you say, and if that's true) its efficiency doesn't matter. If you
>> need to compute it often enough that efficiency might become relevant
>> just put the results in a table and use that. Given that fib goes over
>> 10^12 after about 60 terms it needn't be a very big table.
>
> When the size of the table is more than ten times the size of
> the code, and the code is reasonably fast, using a table is a
> poor choice. Fibonacci functions don't have to be slow.
>
>> The naive doubly recursive solution has the huge merit of being
>> human-readable.
>
> But unacceptably slow.
>
>> Unlike, say:
>>
>> double fib( int n )
>> {
>> return (pow( (1+sqrt(5.0))/2, n+1 )
>> - pow( (1-sqrt(5.0))/2, n+1 ))
>> / sqrt(5.0);
>> }
>>
>> ... which is great for fibs of big values, but not fast for small ones.
>
> Unacceptable for fibs of big values, because the values computed
> are wrong.
>

So either you move to quad or arbitrary precision (which will of course
be somewhat slow, or you use a hybrid technique, with lookup tables for
smallish n, iterative loop for somewhat larger and your O(log(n))
approach only for very large n?

Working with 256-bit uints, each addition will take 4-8 clock cycles,
and it overflows well before n reaches 400, right? In that case a worst
case iterative solution is less than 3000 clock cycles or about a
microsecond away.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Tim Rentsch wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
>>
>>> Pancho <Pancho.Jones@proton.me> writes:
>>>
>>>> On 30/12/2023 23:19, BGB wrote:
>>>>
>>>>> Granted, There are plenty of other much more efficient ways of
>>>>> calculating Fibonacci numbers...
>>>>
>>>> Yes. In order of effort.
>>>>
>>>> 1) Memoize the recursive function.
>>>> 2) Return values for (n-1,n-2) as a tuple, and make it single (tail)
>>>> recursive. Which a smart compiler could theoretically convert to an
>>>> iterative loop.
>>>> 3) Write an iterative loop yourself.
>>>> 4) Remember college maths, and solve the recurrence relation to give a
>>>> very simple closed form solution.
>>>
>>> All of these approaches have drawbacks of one sort or another.
>>>
>>> For (1), we end up writing more code and using more memory.
>>> Some problems are a good fit to memoization, but computing
>>> Fibonacci numbers isn't one of the.
>>>
>>> For (2), compilers are not so good at dealing with tail
>>> recursion when the return value is a pair of results
>>> rather than a single result.
>>>
>>> For (3), iterative code takes more mental effort to see
>>> that it works than does a simple recursive version.
>>
>> I don't think that
>>
>> #include <stdio.h>
>>
>> unsigned long int fib (int n)
>> {
>> unsigned long f1, f2, fn;
>>
>> if (n < 2)
>> return 1;
>>
>> f1 = 1;
>> f2 = 1;
>> while (n >= 2) {
>> fn = f2 + f1;
>> f1 = f2;
>> f2 = fn;
>> n--;
>> }
>> return fn;
>> }
>>
>> is particularly intellecually challenging.
>
> I'm sure there are other people who feel the same way.
>
> Even so, when a short, functional, recursive version
> is available, it is often easier to write, easier to
> read, and simpler to show that it produces correct
> results, in which case doing that is a better choice,
> even if an imperative version is not particularly
> intellecually challenging.
>
> Incidentally your code produces wrong values, as
> fib(0) is 0 and fib(1) is 1.
>

So return n for (n<2)?

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

MitchAlsup <mitchalsup@aol.com> schrieb:
> Thomas Koenig wrote:
>
>> #include <stdio.h>
>
>> unsigned long int fib (int n)
>> {
>> unsigned long f1, f2, fn;
>
>> if (n < 2)
>> return 1;
>
>> f1 = 1;
>> f2 = 1;
>> do { // we know n >=2 so at least 1 path through the loop is performed.
>> fn = f2 + f1;
>> f1 = f2;
>> f2 = fn;
>> n--;
>> } while( n > 2 );

(This should be n >= 2)
>> return fn;
>> }
>
> Saves 1 cycle and and at least 1 instruction of code footprint.

Fortunately, this is one of the transformations which compilers
do automatically these days. For both versions, the code for
fib generated by a recent gcc on x86_64 with -O3 is

fib:
..LFB11:
.cfi_startproc
movl $1, %edx
cmpl $1, %edi
jle .L1
movl $1, %eax
movl $1, %ecx
jmp .L3
.p2align 4,,10
.p2align 3
..L5:
movq %rdx, %rax
..L3:
subl $1, %edi
leaq (%rcx,%rax), %rdx
movq %rax, %rcx
cmpl $1, %edi
jne .L5
..L1:
movq %rdx, %rax
ret

which looks pretty good.

On 01/01/2024 15:00, Daniel James wrote:
> On 31/12/2023 16:40, Pancho wrote:
>>> The naive doubly recursive solution has the huge merit of being
>>> human-readable.
>>
>> Yes, but you'd be surprised how quickly double recursion goes bad. I
>> haven't tested recently, but off the top of my head, the maximum
>> function call depth would be something like 300, so fib(10) would be
>> a stack overflow. fib(60) would need a stack function call depth ~
>> 1e18.
>
> On 64-bit gcc here on Debian (so, 64-bit ints) I can call fib(50)
> without blowing the stack, but it takes minutes (on a Ryzen 7).
>
> However, the (signed) 64-bit integer result overflows for fib(n) where
> n>45, which is more of a problem.
>

Yes, I explained that was a brain fart on my part. I remembered the
recursive stack limit was low and confused the number of recursive calls
with stack depth.

The real place I've had recursive stuff break, is tree/graph handling,
where a tree may adopt linear characteristics. There are much better
algorithms than a naive recursive one.

>>> Unlike, say:
>>>
>>>    double fib( int n )
>>>    {
>>>        return (pow( (1+sqrt(5.0))/2, n+1 )
>>>                - pow( (1-sqrt(5.0))/2, n+1 ))
>>>            / sqrt(5.0);
>>>    }
>>>
>>> ... which is great for fibs of big values, but not fast for small
>>> ones.
>>>
>>
>> Why isn't it fast for small fibs?
>
> Gut feeling. I haven't timed it, and it may be.
>

Yes, what I'm saying is it normally isn't valid. Floating point
functions are fast, and it is rarely something you need to optimise.

> I mean ... obviously it will be as fast for small ones as for large, but
> for small ones it won't beat an iterative calculation and for very small
> ones I doubt it will beat the naive recursive method.
>

It generally doesn't matter if something very, very fast is slightly
faster than something just very fast. Especially when you also have
very, very slow behaviour elsewhere.

> My point, though, was that clear code is often more important than fast
> execution, and while the naive recursive method for fibs gets horribly
> slow for large values even it is acceptable for small ones.
>

From a mathematical viewpoint, the closed form solution gives clearer
behaviour. It really depends on what you want, giving it a standard name
is probably the most important thing.

>> I seem to recall, if statements are more costly than floating point
>> function calls, like exponential.
>
> if statements are costly if they invalidate instruction prefetch and/or
> jump to code that isn't in the cache ... but optimizers and CPUs are
> pretty good at branch prediction and cacheing.
>

I was remembering software doing real life financial calcs, but I'm old,
so it was a long time ago. Pipelines are longer now, but maybe branch
prediction is better?, So I don't know if it is more of a problem or
less of a problem nowadays.

Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
>>
>>> Pancho <Pancho.Jones@proton.me> writes:
>>>
>>>> On 30/12/2023 23:19, BGB wrote:
>>>>
>>>>> Granted, There are plenty of other much more efficient ways of
>>>>> calculating Fibonacci numbers...
>>>>
>>>> Yes. In order of effort.
>>>>
>>>> 1) Memoize the recursive function.
>>>> 2) Return values for (n-1,n-2) as a tuple, and make it single (tail)
>>>> recursive. Which a smart compiler could theoretically convert to an
>>>> iterative loop.
>>>> 3) Write an iterative loop yourself.
>>>> 4) Remember college maths, and solve the recurrence relation to give a
>>>> very simple closed form solution.
>>>
>>> All of these approaches have drawbacks of one sort or another.
>>>
>>> For (1), we end up writing more code and using more memory.
>>> Some problems are a good fit to memoization, but computing
>>> Fibonacci numbers isn't one of the.
>>>
>>> For (2), compilers are not so good at dealing with tail
>>> recursion when the return value is a pair of results
>>> rather than a single result.
>>>
>>> For (3), iterative code takes more mental effort to see
>>> that it works than does a simple recursive version.
>>
>> I don't think that
>>
>> #include <stdio.h>
>>
>> unsigned long int fib (int n)
>> {
>> unsigned long f1, f2, fn;
>>
>> if (n < 2)
>> return 1;
>>
>> f1 = 1;
>> f2 = 1;
>> while (n >= 2) {
>> fn = f2 + f1;
>> f1 = f2;
>> f2 = fn;
>> n--;
>> }
>> return fn;
>> }
>>
>> is particularly intellecually challenging.
>
> I'm sure there are other people who feel the same way.
>
> Even so, when a short, functional, recursive version
> is available, it is often easier to write, easier to
> read, and simpler to show that it produces correct
> results, in which case doing that is a better choice,
> even if an imperative version is not particularly
> intellecually challenging.

Unless, of course, it runs in exponential time, as the
primitive version with the recurrence does.

Compilers often do not do a good job of replacing recursion
with iteration (is there a verb for that? Maybe it can be called
iterationizing?), so it is something to consider if an algorithm
is at all time critical or stack space is problematic.

Thomas Koenig <tkoenig@netcologne.de> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
>
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
>>>
>>>> Pancho <Pancho.Jones@proton.me> writes:
>>>>
>>>>> On 30/12/2023 23:19, BGB wrote:
>>>>>
>>>>>> Granted, There are plenty of other much more efficient ways of
>>>>>> calculating Fibonacci numbers...
>>>>>
>>>>> Yes. In order of effort.
>>>>>
>>>>> 1) Memoize the recursive function.
>>>>> 2) Return values for (n-1,n-2) as a tuple, and make it single (tail)
>>>>> recursive. Which a smart compiler could theoretically convert to an
>>>>> iterative loop.
>>>>> 3) Write an iterative loop yourself.
>>>>> 4) Remember college maths, and solve the recurrence relation to give a
>>>>> very simple closed form solution.
>>>>
>>>> All of these approaches have drawbacks of one sort or another.
>>>>
>>>> For (1), we end up writing more code and using more memory.
>>>> Some problems are a good fit to memoization, but computing
>>>> Fibonacci numbers isn't one of the.
>>>>
>>>> For (2), compilers are not so good at dealing with tail
>>>> recursion when the return value is a pair of results
>>>> rather than a single result.
>>>>
>>>> For (3), iterative code takes more mental effort to see
>>>> that it works than does a simple recursive version.
>>>
>>> I don't think that
>>>
>>> #include <stdio.h>
>>>
>>> unsigned long int fib (int n)
>>> {
>>> unsigned long f1, f2, fn;
>>>
>>> if (n < 2)
>>> return 1;
>>>
>>> f1 = 1;
>>> f2 = 1;
>>> while (n >= 2) {
>>> fn = f2 + f1;
>>> f1 = f2;
>>> f2 = fn;
>>> n--;
>>> }
>>> return fn;
>>> }
>>>
>>> is particularly intellecually challenging.
>>
>> I'm sure there are other people who feel the same way.
>>
>> Even so, when a short, functional, recursive version
>> is available, it is often easier to write, easier to
>> read, and simpler to show that it produces correct
>> results, in which case doing that is a better choice,
>> even if an imperative version is not particularly
>> intellecually challenging.
>
> Unless, of course, it runs in exponential time, as the
> primitive version with the recurrence does.

Sure. Implicit in my comment is that the alternatives being
considered are algorithmically comparable. Otherwise it's
comparing apples and oranges.

> Compilers often do not do a good job of replacing recursion
> with iteration (is there a verb for that? Maybe it can be called
> iterationizing?), so it is something to consider if an algorithm
> is at all time critical or stack space is problematic.

Of course. I take it as given that recursive functions that use
an actual recursive call are unacceptable, except perhaps in
special cases, as for example quicksort. I tend to use functional
recursion and mutual recursion a fair amount, but not in cases
where an actual call is done in the recursive cycle.

By the way a term that may satisfy your question is "tail call
optimization".

Terje Mathisen <terje.mathisen@tmsw.no> writes:

> Tim Rentsch wrote:
>
>> Thomas Koenig <tkoenig@netcologne.de> writes:
[...]

>>> unsigned long int fib (int n)
>>> {
>>> unsigned long f1, f2, fn;
>>>
>>> if (n < 2)
>>> return 1;
>>>
>>> f1 = 1;
>>> f2 = 1;
>>> while (n >= 2) {
>>> fn = f2 + f1;
>>> f1 = f2;
>>> f2 = fn;
>>> n--;
>>> }
>>> return fn;
>>> }

[...]

>> Incidentally your code produces wrong values, as
>> fib(0) is 0 and fib(1) is 1.
>
> So return n for (n<2)?

In situations like this one, usually I would favor something
more like this:

if( n < 8 ) return 0xd8532110u >> n*4 & 15;

Terje Mathisen wrote:

> Tim Rentsch wrote:
>> Daniel James <daniel@me.invalid> writes:
>>
>>> On 31/12/2023 09:12, Pancho wrote:
>>>
>>>> In fact, given that fib grows exponentially, so we only ever need to
>>>> calculate it for small values of n, the only ?bad? solution is the
>>>> naive double recursive one.
>>>
>>> Well, I might disagree.
>>>
>>> Given that we only ever need to calculate it for small values of n (as
>>> you say, and if that's true) its efficiency doesn't matter. If you
>>> need to compute it often enough that efficiency might become relevant
>>> just put the results in a table and use that. Given that fib goes over
>>> 10^12 after about 60 terms it needn't be a very big table.
>>
>> When the size of the table is more than ten times the size of
>> the code, and the code is reasonably fast, using a table is a
>> poor choice. Fibonacci functions don't have to be slow.
>>
>>> The naive doubly recursive solution has the huge merit of being
>>> human-readable.
>>
>> But unacceptably slow.
>>
>>> Unlike, say:
>>>
>>> double fib( int n )
>>> {
>>> return (pow( (1+sqrt(5.0))/2, n+1 )
>>> - pow( (1-sqrt(5.0))/2, n+1 ))
>>> / sqrt(5.0);
>>> }
>>>
>>> ... which is great for fibs of big values, but not fast for small ones.
>>
>> Unacceptable for fibs of big values, because the values computed
>> are wrong.
>>

> So either you move to quad or arbitrary precision (which will of course
> be somewhat slow, or you use a hybrid technique, with lookup tables for
> smallish n, iterative loop for somewhat larger and your O(log(n))
> approach only for very large n?

> Working with 256-bit uints, each addition will take 4-8 clock cycles,
> and it overflows well before n reaches 400, right? In that case a worst
> case iterative solution is less than 3000 clock cycles or about a
> microsecond away.

Whereas table lookup is never more than 100ns away (in DRAM).

> Terje

Thomas Koenig wrote:

> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:
>>
>>> #include <stdio.h>
>>
>>> unsigned long int fib (int n)
>>> {
>>> unsigned long f1, f2, fn;
>>
>>> if (n < 2)
>>> return 1;
>>
>>> f1 = 1;
>>> f2 = 1;
>>> do { // we know n >=2 so at least 1 path through the loop is performed.
>>> fn = f2 + f1;
>>> f1 = f2;
>>> f2 = fn;
>>> n--;
>>> } while( n > 2 );

> (This should be n >= 2)

OK

Thomas Koenig wrote:

> Compilers often do not do a good job of replacing recursion
> with iteration (is there a verb for that? Maybe it can be called
> iterationizing?), so it is something to consider if an algorithm
> is at all time critical or stack space is problematic.

Tail recursion elimination.

Terje Mathisen <terje.mathisen@tmsw.no> writes:

> MitchAlsup wrote:
>
>> Thomas Koenig wrote:
>>
>>> #include <stdio.h>
>>>
>>> unsigned long int fib (int n)
>>> {
>>> unsigned long f1, f2, fn;
>>>
>>> if (n < 2)
>>> return 1;
>>>
>>> f1 = 1;
>>> f2 = 1;
>>> do { // we know n >=2 so at least 1 path through the loop is performed.
>>> fn = f2 + f1;
>>> f1 = f2;
>>> f2 = fn;
>>> n--;
>>> } while( n > 2 );
>>> return fn;
>>> }
>>
>> Saves 1 cycle and and at least 1 instruction of code footprint.
>
> I have written asm code for this, and noted that on x86 where reg
> MOVes used to cost a cycle, it was better to unroll and get rid of the
> reg-reg moves.
>
> I think the following should work:
>
> u64 fib(unsigned n)
> {
> if (n-- < 2) return 1;
> a = 1; b = 1;
>
> a += (n & 1); // Odd remaining n
> n >>= 1;
>
> while (n--) {
> b += a;
> a += b;
> }
> return a;
> }

This code still has the off-by-one error w.r.t. the
value of n.

We can fix that and simultaneously simplify the code:

u64
fib( unsigned n ){
u64 b = n&1, a = b^1;

n >>= 1;
while( n-- ) a += b, b += a;

return b;
}

Pancho <Pancho.Jones@proton.me> writes:

> On 01/01/2024 15:00, Daniel James wrote:

>>>> double fib( int n )
>>>> {
>>>> return (pow( (1+sqrt(5.0))/2, n+1 )
>>>> - pow( (1-sqrt(5.0))/2, n+1 ))
>>>> / sqrt(5.0);
>>>> }
>>>>
>>>> ... which is great for fibs of big values, but not fast for small
>>>> ones.

> From a mathematical viewpoint, the closed form solution gives clearer
> behaviour.

The problem with using this mathematically exact formula is
that the code gives wrong answers. Using floating point is
a poor choice for computing Fibonacci values.

Terje Mathisen <terje.mathisen@tmsw.no> writes:

> Tim Rentsch wrote:
>
>> Daniel James <daniel@me.invalid> writes:
>>
>>> However, the (signed) 64-bit integer result overflows for fib(n) where
>>> n>45, which is more of a problem.
>>
>> fib( 92 ) is still less than 1UL << 63 (or fib(93) for a 64-bit
>> unsigned type).
>>
>> And fib( 186 ) still fits in a 128-bit unsigned type.
>
> If calculating fib(n) for n in the fixed 0..186 range is actually
> important to you, then you would obviously allocate 16*187 (about 3KB)
> bytes of table space and do a simple lookup instead.

I have no doubt that some people would, but I wouldn't. It isn't
hard to write code that has very good performance, and that doesn't
have the associated costs in terms of memory use, cache behavior,
and potential page faults and TLB misses.

(To be clear, I am talking specifically about computing fibonacci
values.)

Terje Mathisen <terje.mathisen@tmsw.no> writes:

> Tim Rentsch wrote:
>
>> Daniel James <daniel@me.invalid> writes:
>>
>>> On 31/12/2023 09:12, Pancho wrote:
>>>
>>>> In fact, given that fib grows exponentially, so we only ever need to
>>>> calculate it for small values of n, the only ?bad? solution is the
>>>> naive double recursive one.
>>>
>>> Well, I might disagree.
>>>
>>> Given that we only ever need to calculate it for small values of n (as
>>> you say, and if that's true) its efficiency doesn't matter. If you
>>> need to compute it often enough that efficiency might become relevant
>>> just put the results in a table and use that. Given that fib goes over
>>> 10^12 after about 60 terms it needn't be a very big table.
>>
>> When the size of the table is more than ten times the size of
>> the code, and the code is reasonably fast, using a table is a
>> poor choice. Fibonacci functions don't have to be slow.
>>
>>> The naive doubly recursive solution has the huge merit of being
>>> human-readable.
>>
>> But unacceptably slow.
>>
>>> Unlike, say:
>>>
>>> double fib( int n )
>>> {
>>> return (pow( (1+sqrt(5.0))/2, n+1 )
>>> - pow( (1-sqrt(5.0))/2, n+1 ))
>>> / sqrt(5.0);
>>> }
>>>
>>> ... which is great for fibs of big values, but not fast for small ones.
>>
>> Unacceptable for fibs of big values, because the values computed
>> are wrong.
>
> So either you move to quad or arbitrary precision (which will of
> course be somewhat slow,

To me, what makes floating point unattractive in this case is
great care must be taken to ensure correct values are produced.
Add to that the increased time cost, and using floating point
just looks like a lot more downside than upside.

> or you use a hybrid technique, with lookup
> tables for smallish n, iterative loop for somewhat larger and your
> O(log(n)) approach only for very large n?

Oh, you remembered I wrote an O(log(n)) fibonacci function. That
is nice. :)

Based on what I know now, my inclination is to use the constant-shift
technique (as seen in another post) for n < 8, the O(log(n)) method
for results that will be more than 64 bits, and a small-constant-linear
method in between those two regions. (Incidentally, the intermediate
method is something I had already written, and might be seen as a
generalization of your two-fold speedup code. You might want to take
a look at enhancing the two-fold speedup idea so it does at most one of
those, and then after that gets a four-fold speedup. The best
performing code I have for 64 bits goes two steps farther, so all the
iterations after the "startup transient" are 16-fold speedup.)

> Working with 256-bit uints, each addition will take 4-8 clock cycles,
> and it overflows well before n reaches 400, right? In that case a
> worst case iterative solution is less than 3000 clock cycles or about
> a microsecond away.

By test, my O(log(n)) code runs in 25-30 nanoseconds for 128-bit
results. At a guess, 256-bit results would run about 5 to 10
times slower than that.

By the way, your two-fold speedup code runs about 1.6 times as
fast as using simple iteration.

Tim Rentsch wrote:

> Terje Mathisen <terje.mathisen@tmsw.no> writes:

>>

>>> Incidentally your code produces wrong values, as
>>> fib(0) is 0 and fib(1) is 1.
>>
>> So return n for (n<2)?

> In situations like this one, usually I would favor something
> more like this:

> if( n < 8 ) return 0xd8532110u >> n*4 & 15;

Which is::

CMP R2,R1,#8
PLT R2,TTT
LEA R2,[IP,R1<<2,0xF00000000-.]
SLL R1,0xd853110,R2
RET

.....

Thomas Koenig wrote:
> MitchAlsup <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:
>>
>>> #include <stdio.h>
>>
>>> unsigned long int fib (int n)
>>> {
>>> unsigned long f1, f2, fn;
>>
>>> if (n < 2)
>>> return 1;
>>
>>> f1 = 1;
>>> f2 = 1;
>>> do { // we know n >=2 so at least 1 path through the loop is performed.
>>> fn = f2 + f1;
>>> f1 = f2;
>>> f2 = fn;
>>> n--;
>>> } while( n > 2 );
>
> (This should be n >= 2)
>>> return fn;
>>> }
>>
>> Saves 1 cycle and and at least 1 instruction of code footprint.
>
> Fortunately, this is one of the transformations which compilers
> do automatically these days. For both versions, the code for
> fib generated by a recent gcc on x86_64 with -O3 is
>
> fib:
> .LFB11:
> .cfi_startproc
> movl $1, %edx
> cmpl $1, %edi
> jle .L1
> movl $1, %eax
> movl $1, %ecx
> jmp .L3
> .p2align 4,,10
> .p2align 3
> .L5:
> movq %rdx, %rax
> .L3:
> subl $1, %edi
> leaq (%rcx,%rax), %rdx
> movq %rax, %rcx
> cmpl $1, %edi
> jne .L5
> .L1:
> movq %rdx, %rax
> ret
>
> which looks pretty good.

OK at best:

The decrement of EDI should be paired with the JNE, saving a CMP, and
the two reg-reg moves could be avoided with a single level of unrolling.

OTOH, with 3-way superscalar processing and zero-cycle MOV, it should
still run at about two cycles/iteration, and a single cycle is a hard
limit due to the latency of the ADD (or in this case, LEA).

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Tim Rentsch wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
>>
>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> schrieb:
>>>>
>>>>> Pancho <Pancho.Jones@proton.me> writes:
>>>>>
>>>>>> On 30/12/2023 23:19, BGB wrote:
>>>>>>
>>>>>>> Granted, There are plenty of other much more efficient ways of
>>>>>>> calculating Fibonacci numbers...
>>>>>>
>>>>>> Yes. In order of effort.
>>>>>>
>>>>>> 1) Memoize the recursive function.
>>>>>> 2) Return values for (n-1,n-2) as a tuple, and make it single (tail)
>>>>>> recursive. Which a smart compiler could theoretically convert to an
>>>>>> iterative loop.
>>>>>> 3) Write an iterative loop yourself.
>>>>>> 4) Remember college maths, and solve the recurrence relation to give a
>>>>>> very simple closed form solution.
>>>>>
>>>>> All of these approaches have drawbacks of one sort or another.
>>>>>
>>>>> For (1), we end up writing more code and using more memory.
>>>>> Some problems are a good fit to memoization, but computing
>>>>> Fibonacci numbers isn't one of the.
>>>>>
>>>>> For (2), compilers are not so good at dealing with tail
>>>>> recursion when the return value is a pair of results
>>>>> rather than a single result.
>>>>>
>>>>> For (3), iterative code takes more mental effort to see
>>>>> that it works than does a simple recursive version.
>>>>
>>>> I don't think that
>>>>
>>>> #include <stdio.h>
>>>>
>>>> unsigned long int fib (int n)
>>>> {
>>>> unsigned long f1, f2, fn;
>>>>
>>>> if (n < 2)
>>>> return 1;
>>>>
>>>> f1 = 1;
>>>> f2 = 1;
>>>> while (n >= 2) {
>>>> fn = f2 + f1;
>>>> f1 = f2;
>>>> f2 = fn;
>>>> n--;
>>>> }
>>>> return fn;
>>>> }
>>>>
>>>> is particularly intellecually challenging.
>>>
>>> I'm sure there are other people who feel the same way.
>>>
>>> Even so, when a short, functional, recursive version
>>> is available, it is often easier to write, easier to
>>> read, and simpler to show that it produces correct
>>> results, in which case doing that is a better choice,
>>> even if an imperative version is not particularly
>>> intellecually challenging.
>>
>> Unless, of course, it runs in exponential time, as the
>> primitive version with the recurrence does.
>
> Sure. Implicit in my comment is that the alternatives being
> considered are algorithmically comparable. Otherwise it's
> comparing apples and oranges.
>
>> Compilers often do not do a good job of replacing recursion
>> with iteration (is there a verb for that? Maybe it can be called
>> iterationizing?), so it is something to consider if an algorithm
>> is at all time critical or stack space is problematic.
>
> Of course. I take it as given that recursive functions that use
> an actual recursive call are unacceptable, except perhaps in
> special cases, as for example quicksort. I tend to use functional

In my own quicksort implementation (from 3-4 decades ago) I used
recursion for the smaller partition and looping for the other/larger
half. That way stack usage/recursion depth was guaranteed to never
exceed log2(n/5). The /5 divisor was because I used a different sort
algorithm on partition sizes <= 5.

> recursion and mutual recursion a fair amount, but not in cases
> where an actual call is done in the recursive cycle.
>
> By the way a term that may satisfy your question is "tail call
> optimization".

As noted, that is always a good idea even when having two (or more!)
recursive calls in the source code.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Tim Rentsch wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>
>> Tim Rentsch wrote:
>>
>>> Thomas Koenig <tkoenig@netcologne.de> writes:
> [...]
>
>>>> unsigned long int fib (int n)
>>>> {
>>>> unsigned long f1, f2, fn;
>>>>
>>>> if (n < 2)
>>>> return 1;
>>>>
>>>> f1 = 1;
>>>> f2 = 1;
>>>> while (n >= 2) {
>>>> fn = f2 + f1;
>>>> f1 = f2;
>>>> f2 = fn;
>>>> n--;
>>>> }
>>>> return fn;
>>>> }
>
> [...]
>
>>> Incidentally your code produces wrong values, as
>>> fib(0) is 0 and fib(1) is 1.
>>
>> So return n for (n<2)?
>
> In situations like this one, usually I would favor something
> more like this:
>
> if( n < 8 ) return 0xd8532110u >> n*4 & 15;

Nice!

Could be extended a little bit more with a lookup table, or to 16 values
with a SIMD in-register lookup operation. Using a 64-bit constant allows
11 values to fit inside 6-bit sub-containers, as long as they are stored
in reverse order so that the bottom value (0) can survive without the
top two bits.

Something like

if (n < 11) return ((0<<60)+(1<<54)+(1<<48)+(2<<42)...(21<<6)+34)>>
(60-n*6) & 63;

Anyway, this is code golfing and not a realistic scenario where you
would definitely use a direct lookup table for all the possible values.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"