fibonacci sequence

This is a discussion on fibonacci sequence within the C Programming forums, part of the General Programming Boards category; You know what laserlight, I had an unfortunate IO error (That would be "Idiot Operator" not "Input/Output"). Yeah it works ...

  1. #46
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    You know what laserlight, I had an unfortunate IO error (That would be "Idiot Operator" not "Input/Output"). Yeah it works fine.. I am just a boob sometimes.

    And yeah I tried the non-trigonometric version when I was looking at the derivation which is why I wasn't following how come my results weren't working. But it works fine.

  2. #47
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Quote Originally Posted by MK27 View Post
    Oh malarky

    Code:
    #include <stdio.h>
    
    int main () {
    	int a=0, b=1, n=a+b,i,ii;
    	puts("Number of iterations");
    	scanf("&#37;d",&ii);
    	printf("%d %d ",a,b);
    	for (i=0;i<ii;i++) {
    		n=a+b;
    		printf("%d ",n);
    		a=b;b=n;
    	}
    }
    I don't know much math, so I'd be really interested to read how you could make this computation "more efficient".

    [edit] i guess this is actually iterative, and not recursive
    That was a challenge! Here is my contest entry:
    Code:
    int fib(int n) {
    int a[2] = { 0, 1 }, i;
    for (i = n + 1 >> 1 ; i; i--)
        a[0] += a[1] += a[0];
    return a[n & 1]; }
    This takes about 1/2 the time yours does. But caution: highest legit value is 64. Gives 1,640,636,603 which is the largest integer that fits into 32 bit. I could go 64-bit but for timing purposes I just threw the two functions into another loop - executing factorial(64) 10,000,000 times.

    Yours took about 12-13 seconds.
    Mine is around 6-7 seconds.
    (Mac laptop 1.33 GHz PowerPC G4)

  3. #48
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    a[0] += a[1] += a[0];
    isn't that UB?

    Code:
    i = (n + 1) >> 1
    ??

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #49
    cph
    cph is offline
    Registered User cph's Avatar
    Join Date
    Sep 2008
    Location
    Indonesia
    Posts
    82
    um, excuse me, may I rephrase my question?
    Code:
    /* http://goldennumber.net/five(5).htm */
    #define PHI pow(M_E, asinh(0.5))
    
    /* http://goldennumber.net/five(5).htm */
    double fib (unsigned int n)
    {
        return((pow(PHI, (double)n)) / sqrt(5.0));
    }
    I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).

  5. #50
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quote Originally Posted by cph
    I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).
    64-bit numbers?
    GMP?

    You are asking how to reach above and beyond a hardware limitation. You are asking how to make your computer do something that is beyond the implementation of your algorithm. Right? I mean you see how I arrive at that conclusion, right?

  6. #51
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Quote Originally Posted by matsp View Post
    Code:
    a[0] += a[1] += a[0];
    isn't that UB?

    Code:
    i = (n + 1) >> 1
    ??

    --
    Mats
    += associativity is right-to-left just as any assignment, so I assume it is executed in that order.

    (n + 1) >> 1 - true, but I abhor extra parenthesis when they're not needed. Operator precedence is such that addition is done before the shift.

  7. #52
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by nonoob View Post
    I abhor extra parenthesis when they're not needed.
    They do add to clarity though, and your post was a good example of that.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  8. #53
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Quote Originally Posted by nonoob
    += associativity is right-to-left just as any assignment, so I assume it is executed in that order.
    Order of evaluation and associativity are not the same thing. However, I think that matsp is wrong - there is no undefined behaviour as far as I can tell. I recall a thread some time ago where the conclusion was that the XOR swap of a and b written as a ^= b ^= a ^= b; resulted in undefined behaviour, but I believe that is because a is modified twice within consecutive sequence points. In your code, however, both a[0] and a[1] are modified exactly once within consecutive sequence points.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #54
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Thanks for that explanation, laserlight. i was starting to get worried that I am misunderstanding associativity in any standard precedence chart. What is it then if "right-to-left" is not related to execution order? The right argument is evaluated first, I thought.

  10. #55
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Quote Originally Posted by nonoob
    What is it then if "right-to-left" is not related to execution order? The right argument is evaluated first, I thought.
    The order of evaluation of operands is unspecified. In this case, it does not matter, but consider this contrived example:
    Code:
    #include <stdio.h>
    
    int *foo(int *x, int y)
    {
        printf("&#37;d\n", y);
        return x;
    }
    
    int main(void)
    {
        int a = 1;
        int b = 2;
        *foo(&a, 1) += *foo(&b, 2) += *foo(&a, 3);
        return 0;
    }
    It is possible that on one implementation the output is "1\n2\n3\n" while on another it is "3\n2\n1\n".
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #56
    Registered User
    Join Date
    Apr 2009
    Posts
    8
    Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.

    First of all, the problem with this method posted above:
    Code:
    pow(PHI, n) / sqrt(5.0)
    is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.

    The correct way would be:
    Code:
    int Fib( int n )
    {
      static const double s = sqrt(5.0);
      return int( (pow(1+s,n)-pow(1-s,n))/(pow(2.0,n)*s) );
    }
    (use long long instead of int for large n, as the result will obviously not fit in 32 bit integers).

    There is, however, an even much faster way. After quite some experimenting with several approaches and lotsa optimizing, this is imho the ultimate solution: (besides using a direct lookup or caching table of course)
    Code:
    unsigned int Fib( unsigned int n )
    {
      n--;
      unsigned int a=1,b=0,c=1,p=1,t;
      while (p<=n) p += p;
      do
      {
        p >>= 1;
        t = b*b;
        b *= a+c;
        a = a*a + t;
        c = c*c + t;    
        if (n&p)
        {
          c = b;
          b = a;
          a += c;
        }
      }
      while (p>1);
      return a;
    }
    This performs about 3 times as fast as the pow / √5 method. Of course, again, use long long for large n.

  12. #57
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Quote Originally Posted by Phuzzillogic
    Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.
    That is okay; I maintain that it is fine to post in an ancient thread when you have something worthwhile to contribute, especially if it is an important correction.

    Quote Originally Posted by Phuzzillogic
    is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.
    It is not incorrect in its idea since the idea is that the other half can be ignored as it has negligible contribution in the approximation. I demonstrated a correct way to perform this approximation in post #45.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #58
    Registered User
    Join Date
    Apr 2009
    Posts
    8
    Quote Originally Posted by laserlight View Post
    It is not incorrect in its idea since the idea is that the other half can be ignored as it has negligible contribution in the approximation. I demonstrated a correct way to perform this approximation in post #45.
    Ah I see, you're right, the correction you applied indeed makes up for the missing term.

    Nonetheless, when I compare this "single pow" method to my integer version, the latter is still almost 15% faster.

Page 4 of 4 FirstFirst 1234
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fibonacci Sequence
    By Dogmasur in forum C Programming
    Replies: 15
    Last Post: 08-10-2008, 08:55 AM
  2. Fibonacci sequence
    By MuffanMan123 in forum C++ Programming
    Replies: 6
    Last Post: 02-26-2008, 09:15 AM
  3. Immediate programming help! Please!
    By xMEGANx in forum C++ Programming
    Replies: 6
    Last Post: 02-20-2008, 12:52 PM
  4. Fibonacci sequence output statement
    By chocha7 in forum C++ Programming
    Replies: 10
    Last Post: 11-18-2004, 11:04 PM
  5. Fibonacci sequence
    By girliegti in forum C++ Programming
    Replies: 8
    Last Post: 09-30-2003, 11:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21