From: Ros@invalid.invalid
On Wed, 22 Oct 2025 23:36:47 -0000 (UTC), Kaz Kylheku wrote:
>On 2025-10-22, Rosario19 wrote:
>> On Tue, 30 Sep 2025 16:12:14 -0000 (UTC), Kaz Kylheku wrote:
>>
>>>On 2025-09-30, Janis Papanagnou wrote:
>>>> In another newsgroup the question came up to what degree the
>>>> GNU "C" compilers can handle optimization of recursions like
>>>> fib() or ack(), i.e. cascading ones. Somebody here may know?
>>>
>>>What exactly are you talking about? The ability to unroll one or more
>>>levels of recursion by inlining cases of a function into itself
>>>to create a larger functon that makes fewer calls?
>>>
>>>The common way fib is written recursively doesn't lend to
>>>tail call optimization; it has to be refactored for that.
>>>
>>>The usual way Ackermann is written, it has some tail calls
>>>and a non-tail call, since one of its cases returns
>>>a call to ack, which has an argument computed by calling ack.
>>>
>>>> Can we expect that (with the higher optimization levels) the
>>>> exponential complexity from cascaded recursion gets linearized?
>>>
>>>I'm reasonably sure that GCC is not going to recognize and linearize
>>>"return fib(n - 1) + fib(n - 2)" recursion. You have to do it yourself
>>>with explicit memoization or iterative rewrite.
>>
>> iterative fibonacci it seems many time faster than the recursive one.
>> I don't know if the compiler can optimize until that point...
>
>iterative fibonacci can be expressed by tail recursion, which
>the compiler can optimize to iteration.
>
>You have to refactor fib for tail recursion; it may be easier
>to start with the iterative version and turn the loop into
>a tail call.
>
>Iterative fib(n) starts with the vector v = <0, 1> and then
>performs the step n times, returning the second element of
>the vector.
>
>The step is to multiply the vector by the matrix
>
> [ 0 1 ]
> v_next = [ 1 1 ] v
>
>In other words
>
> v_next[0] = v[1]
> v_next[1] = v[0] + v[1]
>
>Thus a tail-recursive fib can look like this. The
>recursive helper function:
>
> static int fib_tail(int v0, int v1, int n)
> {
> if (n == 0)
> return v0 + 1;
> else
> return fib_tail(v1, v0 + v1, n - 1);
> }
>
>plus the entry point that conforms to the expected fib API:
>
> int fib(int n)
> {
> return fib_tail(0, 1, n);
> }
>
>When I compile that with GCC11 for X86-64, using -O3 -S,
>I get this [edited for brevity by omitting various environment-related
>cruft]:
>
>fib:
> movl $1, %eax
> xorl %edx, %edx
> testl %edi, %edi
> jne .L2
> jmp .L8
>.L5:
> movl %ecx, %eax
>.L2:
> leal (%rdx,%rax), %ecx
> movl %eax, %edx
> subl $1, %edi
> jne .L5
> addl $1, %eax
> ret
>.L8:
> ret
yes this seems the iterative one
>The static helper function fib_tail has disappeared, inlined into fib, and
>turned from recursion to iteration.
>
>GCC is not going to turn this:
>
> int fib(int n)
> {
> if (n < 2)
> return 1;
> else
> return fib(n - 1) + fib(n - 2);
> }
>into the above pair of functions, or anything similar.
>
>That's not ordinary optimization of the type which improves the code generated
>for the user's algorithm; that's recognizing and redesigning the algorithm.
>
>The line between those is blurred, but not /that/ blurred.
int fib1(int n){return fib_tail(0, 1, n);}
is different from
int fib(int n){if(n<2) return 1;return fib(n - 1) + fib(n - 2);
both these function calculate from the 0 1 the number result, but
fib() start to calculate from n goes dowwn until n=0, than goes up
until n=input, instead fib1() go only down for n. It seen the calls
(fib has 2 call each call... instead fib_tail() just 1), I think fib()
is O(n^2) instead fib1 is O(n).
--------------------------------
#include
unsigned fib(unsigned n){if(n<2)return n; return fib(n-1)+fib(n-2);}
unsigned fibr(unsigned i, unsigned j, unsigned n)
{if(n==0) return i;
return fibr(j,i+j,n-1);
}
unsigned fib1(unsigned n){return fibr(0,1,n);}
unsigned f(unsigned n)
{unsigned r,i,j;
if(n==0) return 0;
n-=1;
for(r=j=i=1;n;--n)
{r=j;j+=i;i=r;}
return r;
}
main(void)
{unsigned i, r;
for(i=0;i<40;++i)
{r=fib1(i);
printf("fibonacciRic(%u)=%u\n", i, r);
}
for(i=0;i<40;++i)
{r=f(i);
printf("fibonacciIter(%u)=%u\n", i, r);
}
return 0;
}
result:
C:\>fibonacci
fibonacciRic(0)=0
fibonacciRic(1)=1
fibonacciRic(2)=1
fibonacciRic(3)=2
fibonacciRic(4)=3
fibonacciRic(5)=5
fibonacciRic(6)=8
fibonacciRic(7)=13
fibonacciRic(8)=21
fibonacciRic(9)=34
fibonacciRic(10)=55
fibonacciRic(11)=89
fibonacciRic(12)=144
fibonacciRic(13)=233
fibonacciRic(14)=377
fibonacciRic(15)=610
fibonacciRic(16)=987
fibonacciRic(17)=1597
fibonacciRic(18)=2584
fibonacciRic(19)=4181
fibonacciRic(20)=6765
fibonacciRic(21)=10946
fibonacciRic(22)=17711
fibonacciRic(23)=28657
fibonacciRic(24)=46368
fibonacciRic(25)=75025
fibonacciRic(26)=121393
fibonacciRic(27)=196418
fibonacciRic(28)=317811
fibonacciRic(29)=514229
fibonacciRic(30)=832040
fibonacciRic(31)=1346269
fibonacciRic(32)=2178309
fibonacciRic(33)=3524578
fibonacciRic(34)=5702887
fibonacciRic(35)=9227465
fibonacciRic(36)=14930352
fibonacciRic(37)=24157817
fibonacciRic(38)=39088169
fibonacciRic(39)=63245986
fibonacciIter(0)=0
fibonacciIter(1)=1
fibonacciIter(2)=1
fibonacciIter(3)=2
fibonacciIter(4)=3
fibonacciIter(5)=5
fibonacciIter(6)=8
fibonacciIter(7)=13
fibonacciIter(8)=21
fibonacciIter(9)=34
fibonacciIter(10)=55
fibonacciIter(11)=89
fibonacciIter(12)=144
fibonacciIter(13)=233
fibonacciIter(14)=377
fibonacciIter(15)=610
fibonacciIter(16)=987
fibonacciIter(17)=1597
fibonacciIter(18)=2584
fibonacciIter(19)=4181
fibonacciIter(20)=6765
fibonacciIter(21)=10946
fibonacciIter(22)=17711
fibonacciIter(23)=28657
fibonacciIter(24)=46368
fibonacciIter(25)=75025
fibonacciIter(26)=121393
fibonacciIter(27)=196418
fibonacciIter(28)=317811
fibonacciIter(29)=514229
fibonacciIter(30)=832040
fibonacciIter(31)=1346269
fibonacciIter(32)=2178309
fibonacciIter(33)=3524578
fibonacciIter(34)=5702887
fibonacciIter(35)=9227465
fibonacciIter(36)=14930352
fibonacciIter(37)=24157817
fibonacciIter(38)=39088169
fibonacciIter(39)=63245986
fib1 and f here seems ugual fast
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
