Implementation of recursion in different languages: what happens inthe background ?

Discussion in 'C Programming' started by Sébastien de Mapias, Feb 12, 2008.

  1. Hello,
    Hopefully I'm asking my question on the proper forum, but it's some
    kind of low-level computer language issue and I guess here, many
    people are likely to give me fine enlightenments (and I suppose -?-
    that the interpreters I talk about below are coded in C)... I've found
    on the page
    http://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-python-away/
    a discussion about the performance differences between several
    languages (Ruby, Perl, Python...) to execute the same operation,
    using recursive function calls.

    Could someone explain me how such differences can be explained ?
    Where does it come from ?

    Thanks a lot...
    Regards,
    Seb
     
    Sébastien de Mapias, Feb 12, 2008
    #1
    1. Advertising

  2. Sébastien de Mapias

    jbroquefere Guest

    Re: Implementation of recursion in different languages: what happensin the background ?

    Hello,
    To my mind, it depends more about the compiler than the language.
    But, because im new here, and a young student, my intepretation might
    be wrong.



    On 12 fév, 12:13, "Sébastien de Mapias" <> wrote:
    > Hello,
    > Hopefully I'm asking my question on the proper forum, but it's some
    > kind of low-level computer language issue and I guess here, many
    > people are likely to give me fine enlightenments (and I suppose -?-
    > that the interpreters I talk about below are coded in C)... I've found
    > on the pagehttp://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-pyth...
    > a discussion about the performance differences between several
    > languages (Ruby, Perl, Python...) to execute the same operation,
    > using recursive function calls.
    >
    > Could someone explain me how such differences can be explained ?
    > Where does it come from ?
    >
    > Thanks a lot...
    > Regards,
    > Seb
     
    jbroquefere, Feb 12, 2008
    #2
    1. Advertising

  3. Sébastien de Mapias

    jacob navia Guest

    Re: Implementation of recursion in different languages: what happensin the background ?

    Sébastien de Mapias wrote:
    > Hello,
    > Hopefully I'm asking my question on the proper forum, but it's some
    > kind of low-level computer language issue and I guess here, many
    > people are likely to give me fine enlightenments (and I suppose -?-
    > that the interpreters I talk about below are coded in C)... I've found
    > on the page
    > http://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-python-away/
    > a discussion about the performance differences between several
    > languages (Ruby, Perl, Python...) to execute the same operation,
    > using recursive function calls.
    >
    > Could someone explain me how such differences can be explained ?
    > Where does it come from ?
    >
    > Thanks a lot...
    > Regards,
    > Seb


    Python 2.5.1: 31.507s
    Ruby 1.9.0: 11.934s

    I just added "C"

    not even 1 second...

    :)
    #include <stdio.h>
    int fib(int n)
    {
    if (n < 2)
    return n;
    else
    return fib(n-1)+fib(n-2);
    }

    int main(void)
    {
    for(int i = 1; i<36;i++) {
    printf("fib(%d)=%d\n",i,fib(i));
    }
    }
    fib(1)=1
    fib(2)=1
    fib(3)=2
    fib(4)=3
    fib(5)=5
    fib(6)=8
    fib(7)=13
    fib(8)=21
    fib(9)=34
    fib(10)=55
    fib(11)=89
    fib(12)=144
    fib(13)=233
    fib(14)=377
    fib(15)=610
    fib(16)=987
    fib(17)=1597
    fib(18)=2584
    fib(19)=4181
    fib(20)=6765
    fib(21)=10946
    fib(22)=17711
    fib(23)=28657
    fib(24)=46368
    fib(25)=75025
    fib(26)=121393
    fib(27)=196418
    fib(28)=317811
    fib(29)=514229
    fib(30)=832040
    fib(31)=1346269
    fib(32)=2178309
    fib(33)=3524578
    fib(34)=5702887
    fib(35)=9227465


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Feb 12, 2008
    #3
  4. Sébastien de Mapias

    Chris Dollin Guest

    Re: Implementation of recursion in different languages: what happens in the background ?

    jacob navia wrote:

    > Python 2.5.1: 31.507s
    > Ruby 1.9.0: 11.934s
    >
    > I just added "C"
    >
    > not even 1 second...


    Since one expects a factor of between 10 and 100 for interpretive
    implementations, that's hardly surprising. How does your implementation
    perform for fib(100)?

    --
    "Well begun is half done." - Proverb

    Hewlett-Packard Limited Cain Road, Bracknell, registered no:
    registered office: Berks RG12 1HN 690597 England
     
    Chris Dollin, Feb 12, 2008
    #4
  5. Sébastien de Mapias

    jacob navia Guest

    Re: Implementation of recursion in different languages: what happensin the background ?

    Chris Dollin wrote:
    > jacob navia wrote:
    >
    >> Python 2.5.1: 31.507s
    >> Ruby 1.9.0: 11.934s
    >>
    >> I just added "C"
    >>
    >> not even 1 second...

    >
    > Since one expects a factor of between 10 and 100 for interpretive
    > implementations, that's hardly surprising. How does your implementation
    > perform for fib(100)?
    >


    Using long long instead of int and the 64 bit lcc-win compiler
    instead of the 32 bit lcc-win32 I obtain:
    fib(1)=1
    fib(2)=1
    fib(3)=2
    fib(4)=3
    fib(5)=5
    fib(6)=8
    fib(7)=13
    fib(8)=21
    fib(9)=34
    fib(10)=55
    fib(11)=89
    fib(12)=144
    fib(13)=233
    fib(14)=377
    fib(15)=610
    fib(16)=987
    fib(17)=1597
    fib(18)=2584
    fib(19)=4181
    fib(20)=6765
    fib(21)=10946
    fib(22)=17711
    fib(23)=28657
    fib(24)=46368
    fib(25)=75025
    fib(26)=121393
    fib(27)=196418
    fib(28)=317811
    fib(29)=514229
    fib(30)=832040
    fib(31)=1346269
    fib(32)=2178309
    fib(33)=3524578
    fib(34)=5702887
    fib(35)=9227465
    fib(36)=14930352
    fib(37)=24157817
    fib(38)=39088169
    fib(39)=63245986
    fib(40)=102334155
    fib(41)=165580141
    fib(42)=267914296
    fib(43)=433494437
    fib(44)=701408733
    fib(45)=1134903170
    fib(46)=1836311903
    fib(47)=2971215073

    TimeThis : Command Line : tfib
    TimeThis : Start Time : Tue Feb 12 13:14:25 2008
    TimeThis : End Time : Tue Feb 12 13:16:51 2008
    TimeThis : Elapsed Time : 00:02:25.941

    I think no C compiler will go (using exactly the same program as given
    of course) beyond fib(50) in a reasonable amount of time.

    fib(100) would take more than the age of the Universe...


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Feb 12, 2008
    #5
  6. Re: Implementation of recursion in different languages: what happensin the background ?

    Could you please tell me how you 'timed' your
    execution ? Thanks.
     
    Sébastien de Mapias, Feb 12, 2008
    #6
  7. Sébastien de Mapias

    Chris Dollin Guest

    Re: Implementation of recursion in different languages: what happens in the background ?

    jacob navia wrote:

    > Chris Dollin wrote:
    >> jacob navia wrote:
    >>
    >>> Python 2.5.1: 31.507s
    >>> Ruby 1.9.0: 11.934s
    >>>
    >>> I just added "C"
    >>>
    >>> not even 1 second...

    >>
    >> Since one expects a factor of between 10 and 100 for interpretive
    >> implementations, that's hardly surprising. How does your implementation
    >> perform for fib(100)?
    >>

    >
    > Using long long instead of int and the 64 bit lcc-win compiler
    > instead of the 32 bit lcc-win32 I obtain:


    Sorry, Jacob, I was confusing `fib` and `fact` and thinking of the
    size of the numbers rather than the time taken. The fix for the
    recursion time is easy.

    I'd say that you were comparing apples and oranges, except that's
    easy.

    --
    "Ashes are burning the way." - Renaissance, /Ashes Are Burning/

    Hewlett-Packard Limited registered no:
    registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England
     
    Chris Dollin, Feb 12, 2008
    #7
  8. Re: Implementation of recursion in different languages: what happensin the background ?

    On Feb 12, 11:13 am, "Sébastien de Mapias" <>
    wrote:
    > Hello,
    > Hopefully I'm asking my question on the proper forum, but it's some
    > kind of low-level computer language issue and I guess here, many
    > people are likely to give me fine enlightenments (and I suppose -?-
    > that the interpreters I talk about below are coded in C)... I've found
    > on the pagehttp://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-pyth...
    > a discussion about the performance differences between several
    > languages (Ruby, Perl, Python...) to execute the same operation,
    > using recursive function calls.
    >
    > Could someone explain me how such differences can be explained ?
    > Where does it come from ?


    I doubt that there is a simple answer to your
    question. One would have to dig deep in the
    internals of the interpreters/compilers of the
    languages under question to see how they
    implement function calls, arithmetic, etc.
    and how that might affect performance. So a
    group or mailing list for the developers of
    interpreters/compilers of the languages would
    be a better place.

    The only general comment I can make is that
    some languages optimize tail recursive calls
    by turning them into loops. Scheme for example
    is required to do that by its standard. I
    don't know what the situation is with Ruby and
    Python and it's not relevant to the Fibonacci
    benchmark since the recursive call there is
    not tail recursive.

    Crossposting and setting follow-ups for
    comp.programming where I think this is more
    on topic.
     
    Spiros Bousbouras, Feb 12, 2008
    #8
  9. Sébastien de Mapias

    Kaz Kylheku Guest

    Re: Implementation of recursion in different languages: what happensin the background ?

    On Feb 12, 4:19 am, jacob navia <> wrote:
    > I think no C compiler will go (using exactly the same program as given
    > of course) beyond fib(50) in a reasonable amount of time.
    >
    > fib(100) would take more than the age of the Universe...


    fib(100) cannot be done using that program because the answer is the
    69 bit integer 354224848179261915075.

    In a high level language, you can memoize your function with some
    trivial spelling change.

    In Python, simple memoization can be done with a custom function
    decorator, which turns into a trivial blurb that you add in front of
    the function definition.

    In CLISP, with my own memoization macro:

    [1]> (define-memoized-function fib (n) (if (< n 2) n (+ (fib (1- n))
    (fib (- n 2)))))
    [2]> (compile 'fib)
    FIB ;
    NIL ;
    NIL
    [3]> (time (fib 100))
    Real time: 1.0E-6 sec.
    Run time: 0.0 sec.
    Space: 9944 Bytes
    354224848179261915075

    You can do memoization and wider integers in C, but the program will
    be so ugly that the Fibonacci part of it won't even be recognizeable
    any longer, except for the name.
     
    Kaz Kylheku, Feb 12, 2008
    #9
  10. Sébastien de Mapias

    jacob navia Guest

    Re: Implementation of recursion in different languages: what happensin the background ?

    Kaz Kylheku wrote:
    > On Feb 12, 4:19 am, jacob navia <> wrote:
    >> I think no C compiler will go (using exactly the same program as given
    >> of course) beyond fib(50) in a reasonable amount of time.
    >>
    >> fib(100) would take more than the age of the Universe...

    >
    > fib(100) cannot be done using that program because the answer is the
    > 69 bit integer 354224848179261915075.
    >
    > In a high level language, you can memoize your function with some
    > trivial spelling change.
    >
    > In Python, simple memoization can be done with a custom function
    > decorator, which turns into a trivial blurb that you add in front of
    > the function definition.
    >
    > In CLISP, with my own memoization macro:
    >
    > [1]> (define-memoized-function fib (n) (if (< n 2) n (+ (fib (1- n))
    > (fib (- n 2)))))
    > [2]> (compile 'fib)
    > FIB ;
    > NIL ;
    > NIL
    > [3]> (time (fib 100))
    > Real time: 1.0E-6 sec.
    > Run time: 0.0 sec.
    > Space: 9944 Bytes
    > 354224848179261915075
    >
    > You can do memoization and wider integers in C, but the program will
    > be so ugly that the Fibonacci part of it won't even be recognizeable
    > any longer, except for the name.
    >
    >


    In ONLY 0.05 seconds you can do it in lcc-win:

    fib( 0)= 0
    fib( 1)= 1
    fib( 2)= 1
    fib( 3)= 2
    fib( 4)= 3
    fib( 5)= 5
    fib( 6)= 8
    fib( 7)= 13
    fib( 8)= 21
    fib( 9)= 34
    fib( 10)= 55
    fib( 11)= 89
    fib( 12)= 144
    fib( 13)= 233
    fib( 14)= 377
    fib( 15)= 610
    fib( 16)= 987
    fib( 17)= 1597
    fib( 18)= 2584
    fib( 19)= 4181
    fib( 20)= 6765
    fib( 21)= 10946
    fib( 22)= 17711
    fib( 23)= 28657
    fib( 24)= 46368
    fib( 25)= 75025
    fib( 26)= 121393
    fib( 27)= 196418
    fib( 28)= 317811
    fib( 29)= 514229
    fib( 30)= 832040
    fib( 31)= 1346269
    fib( 32)= 2178309
    fib( 33)= 3524578
    fib( 34)= 5702887
    fib( 35)= 9227465
    fib( 36)= 14930352
    fib( 37)= 24157817
    fib( 38)= 39088169
    fib( 39)= 63245986
    fib( 40)= 102334155
    fib( 41)= 165580141
    fib( 42)= 267914296
    fib( 43)= 433494437
    fib( 44)= 701408733
    fib( 45)= 1134903170
    fib( 46)= 1836311903
    fib( 47)= 2971215073
    fib( 48)= 4807526976
    fib( 49)= 7778742049
    fib( 50)= 12586269025
    fib( 51)= 20365011074
    fib( 52)= 32951280099
    fib( 53)= 53316291173
    fib( 54)= 86267571272
    fib( 55)= 139583862445
    fib( 56)= 225851433717
    fib( 57)= 365435296162
    fib( 58)= 591286729879
    fib( 59)= 956722026041
    fib( 60)= 1548008755920
    fib( 61)= 2504730781961
    fib( 62)= 4052739537881
    fib( 63)= 6557470319842
    fib( 64)= 10610209857723
    fib( 65)= 17167680177565
    fib( 66)= 27777890035288
    fib( 67)= 44945570212853
    fib( 68)= 72723460248141
    fib( 69)= 117669030460994
    fib( 70)= 190392490709135
    fib( 71)= 308061521170129
    fib( 72)= 498454011879264
    fib( 73)= 806515533049393
    fib( 74)= 1304969544928657
    fib( 75)= 2111485077978050
    fib( 76)= 3416454622906707
    fib( 77)= 5527939700884757
    fib( 78)= 8944394323791464
    fib( 79)= 14472334024676221
    fib( 80)= 23416728348467685
    fib( 81)= 37889062373143906
    fib( 82)= 61305790721611591
    fib( 83)= 99194853094755497
    fib( 84)= 160500643816367088
    fib( 85)= 259695496911122585
    fib( 86)= 420196140727489673
    fib( 87)= 679891637638612258
    fib( 88)= 1100087778366101931
    fib( 89)= 1779979416004714189
    fib( 90)= 2880067194370816120
    fib( 91)= 4660046610375530309
    fib( 92)= 7540113804746346429
    fib( 93)= 12200160415121876738
    fib( 94)= 19740274219868223167
    fib( 95)= 31940434634990099905
    fib( 96)= 51680708854858323072
    fib( 97)= 83621143489848422977
    fib( 98)= 135301852344706746049
    fib( 99)= 218922995834555169026
    fib(100)= 354224848179261915075
    TimeThis : Command Line : tfib-bigq
    TimeThis : Start Time : Tue Feb 12 22:14:56 2008


    TimeThis : Command Line : tfib-bigq
    TimeThis : Start Time : Tue Feb 12 22:14:56 2008
    TimeThis : End Time : Tue Feb 12 22:14:56 2008
    TimeThis : Elapsed Time : 00:00:00.054

    Note that we arrive to the same result for fib(100).
    That is somehow reassuring :)

    Program:

    #include <math.h>
    #include <stdio.h>
    #include <qfloat.h>
    int main(void)
    {
    qfloat GoldenRatio = (1+sqrt(5.0Q))/2.0q;

    for (int i=0; i<=100;i++) {
    qfloat phiN = pow(GoldenRatio,(qfloat)i);
    qfloat s = pow((1-GoldenRatio),(qfloat)i);
    qfloat fib = (phiN-s)/sqrt(5.0q);

    printf("fib(%3d)=%29.25qg\n",i,fib);
    }
    }



    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Feb 12, 2008
    #10
  11. Sébastien de Mapias

    Bartc Guest

    Re: Implementation of recursion in different languages: what happens in the background ?

    "jacob navia" <> wrote in message
    news:forvf7$6jn$...
    > Sébastien de Mapias wrote:
    >> Hello,
    >> Hopefully I'm asking my question on the proper forum, but it's some
    >> kind of low-level computer language issue and I guess here, many
    >> people are likely to give me fine enlightenments (and I suppose -?-
    >> that the interpreters I talk about below are coded in C)... I've found
    >> on the page
    >> http://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-python-away/
    >> a discussion about the performance differences between several
    >> languages (Ruby, Perl, Python...) to execute the same operation,
    >> using recursive function calls.
    >>
    >> Could someone explain me how such differences can be explained ?
    >> Where does it come from ?
    >>
    >> Thanks a lot...
    >> Regards,
    >> Seb

    >
    > Python 2.5.1: 31.507s
    > Ruby 1.9.0: 11.934s
    >
    > I just added "C"
    >
    > not even 1 second...
    >
    > :)
    > #include <stdio.h>
    > int fib(int n)
    > {
    > if (n < 2)
    > return n;
    > else
    > return fib(n-1)+fib(n-2);
    > }
    >
    > int main(void)
    > {
    > for(int i = 1; i<36;i++) {
    > printf("fib(%d)=%d\n",i,fib(i));
    > }
    > }


    That's not quite the same code as Ruby/Python, it should be more like:

    #include <stdio.h>
    int fib(int n)
    {
    if (n==0 || n==1) /* test this way */
    return n;
    else
    return fib(n-1)+fib(n-2);
    }

    int main(void)
    {
    for(int i = 0; i<36;i++) { /* start from 0 */
    printf("fib(%d)=%d\n",i,fib(i));
    }
    }

    Your changes gave you an advantage of some 10% :)

    For the record, my own timings were: Ruby(1.8.6) 90 secs, Python(2.5.1) 30
    secs, C(lccwin) 0.52 seconds.

    (And one of my own compiled C-like languages, 0.5 seconds, one of my own
    interpreted languages, 10 secs. If new Ruby is really that fast then I may
    have a bit of work to do to stay ahead)

    --
    Bart
     
    Bartc, Feb 12, 2008
    #11
  12. Sébastien de Mapias

    Army1987 Guest

    Re: Implementation of recursion in different languages: whathappens in the background ?

    jacob navia wrote:

    > I think no C compiler will go (using exactly the same program as given
    > of course) beyond fib(50) in a reasonable amount of time.

    army1987@army1987-laptop:~$ cat fib.c
    #include <stdio.h>
    long long fib(long long n)
    {
    if (n < 2)
    return n;
    else
    return fib(n-1)+fib(n-2);
    }

    int main(void)
    {
    for(long long i = 1; i<52;i++) {
    printf("fib(%lld)=%lld\n",i,fib(i));
    }
    }
    army1987@army1987-laptop:~$ gcc -std=c99 -O3 fib.c -o fib
    army1987@army1987-laptop:~$ time ./fib
    fib(1)=1
    fib(2)=1
    [...]
    fib(50)=12586269025
    fib(51)=20365011074

    real 19m4.878s
    user 18m50.311s
    sys 0m3.824s

    (No, it's not reasonable...)
    (BTW, what does it do when n < 0?)
    --
    Army1987 (Replace "NOSPAM" with "email")
     
    Army1987, Feb 13, 2008
    #12
  13. Sébastien de Mapias

    Army1987 Guest

    Re: Implementation of recursion in different languages: whathappensin the background ?

    Kaz Kylheku wrote:

    > You can do memoization and wider integers in C, but the program will
    > be so ugly that the Fibonacci part of it won't even be recognizeable
    > any longer, except for the name.

    As for wider integers, maybe, but as for memoization, what's so ugly with:
    #include <stdio.h>
    #include <errno.h>
    #include <limits.h>
    #define MAX 47 /* assuming 32-bit long */

    long int fib(int n)
    {
    static long int values[MAX] = { 0, 1 };
    static int i = 1;
    if (n < 0)
    return (n % 2 ? -1 : 1) * fib(-n);
    if (n >= MAX) {
    errno = ERANGE;
    return LONG_MAX;
    }
    while (i < n) {
    i++;
    values = values[i - 1] + values[i - 2];
    }
    return values[n];
    }

    int main(void)
    {
    int i = 0;
    while (1) {
    long r = fib(i);
    if (errno == ERANGE)
    break;
    printf("%2d %10ld\n", i, r);
    i++;
    }
    return 0;
    }

    (And you can use a floating type instead of long int to have a wider
    range, if you don't care about results becoming inexact for large n...)

    --
    Army1987 (Replace "NOSPAM" with "email")
     
    Army1987, Feb 14, 2008
    #13
  14. Sébastien de Mapias

    jacob navia Guest

    Re: Implementation of recursion in different languages: what happensin the background ?

    Army1987 wrote:
    > jacob navia wrote:
    >
    >> I think no C compiler will go (using exactly the same program as given
    >> of course) beyond fib(50) in a reasonable amount of time.

    > army1987@army1987-laptop:~$ cat fib.c


    [snip]

    > fib(51)=20365011074
    >
    > real 19m4.878s
    > user 18m50.311s
    > sys 0m3.824s
    >
    > (No, it's not reasonable...)
    > (BTW, what does it do when n < 0?)


    Off by one bug?

    :)

    Try fib(55) when your computer has nothing else to do.

    In any case, the non recursive function will do this
    in MUCH less than a second.

    When it is less than zero it returns its argument
    unchanged...

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Feb 14, 2008
    #14
  15. Sébastien de Mapias

    Spoon Guest

    Re: Implementation of recursion in different languages: what happensin the background ?

    Army1987 wrote:

    > (And you can use a floating type instead of long int to have a wider
    > range, if you don't care about results becoming inexact for large n...)


    I offer another fast (and not quite correct) implementation.

    #include <stdint.h>
    uint64_t fib(int n)
    {
    uint64_t temp, u = 0, v = 1;
    while (--n) { temp = u + v; u = v; v = temp; }
    return v;
    }
     
    Spoon, Feb 14, 2008
    #15
  16. Sébastien de Mapias

    Army1987 Guest

    Re: Implementation of recursion in different languages: whathappens in the background ?

    jacob navia wrote:

    > Army1987 wrote:

    [fibonacci function]
    >> (BTW, what does it do when n < 0?)

    >
    > Off by one bug?

    No. If you use a signed parameter for fib(), you ought to look up how
    fibonacci(-n) is defined. Another possibility is to use an unsigned
    parameter.
    > :)
    >
    > Try fib(55) when your computer has nothing else to do.
    >
    > In any case, the non recursive function will do this in MUCH less than a
    > second.

    Indeed.

    <OT>
    army1987@army1987-laptop:~$ cat fib.py
    #!/usr/bin/python
    def fib(n):
    a, b = 0, 1
    for i in xrange(n):
    a, b = b, a + b
    return a

    if __name__ == "__main__":
    for i in xrange(101):
    print i, fib(i)

    army1987@army1987-laptop:~$ time ./fib.py
    0 0
    1 1
    [...]
    99 218922995834555169026
    100 354224848179261915075

    real 0m0.016s
    user 0m0.016s
    sys 0m0.000s
    </OT>
    I know there is an implementation which gives exact results without using
    floating point with O(log n) time.
    http://it.wikipedia.org/wiki/Successione_di_Fibonacci#Versione_a_complessit.C3.A0_logaritmica
    --
    Army1987 (Replace "NOSPAM" with "email")
     
    Army1987, Feb 14, 2008
    #16
  17. Sébastien de Mapias

    Army1987 Guest

    Re: Implementation of recursion in different languages: whathappens in the background ?

    Spoon wrote:

    > Army1987 wrote:


    > I offer another fast (and not quite correct) implementation.
    >
    > #include <stdint.h>
    > uint64_t fib(int n)
    > {
    > uint64_t temp, u = 0, v = 1;
    > while (--n) { temp = u + v; u = v; v = temp; }
    > return v;
    > }

    It's not correct only when n <= 0.
    (When fibonacci(n) is greater than the number of grains of wheat on that
    chessboard, the result is not correct in Z, but it *is* correct in Z_{2^64}.)


    --
    Army1987 (Replace "NOSPAM" with "email")
     
    Army1987, Feb 14, 2008
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. NM
    Replies:
    6
    Views:
    491
    Default User
    Sep 20, 2006
  2. Jethrie-JDuprez in the news
    Replies:
    4
    Views:
    1,420
    Mayeul
    Apr 26, 2009
  3. Hidekazu IWAKI
    Replies:
    0
    Views:
    539
    Hidekazu IWAKI
    Dec 15, 2009
  4. Zeynel
    Replies:
    1
    Views:
    580
    alex23
    Dec 6, 2010
  5. Thomas Jollans
    Replies:
    15
    Views:
    428
    Steven D'Aprano
    Jul 16, 2011
Loading...

Share This Page