Thread: Fibonacci sequence

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    9

    Fibonacci sequence

    Hi. Can somebody tell me where the solution is wrong?
    The task: http://img338.imageshack.us/img338/8097/task.png
    My solution: Ideone.com | Online C++ Compiler & Debugging Tool

    PS. I use Fibonacci sequence to designate the number of combinations (2,3,5,8,13,21,34...)

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    This code is only 42 lines long, so you sould just post it here. Don't make us chase it.
    I don't understand why you've involved a matrix or power function. It looks to me like all you have to do is to calculate the square of the Nth fibonacci number modulo 1000000007.
    You aren't using your default arguments to the constructor so what's the point in having them?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    9
    I don't understand why you've involved a matrix or power function.
    1. It calculates fib(n) mod 1000000007.
    2. Calculates square and do the mod 1000000007.
    3. Now my calculations look like this: ((fib(n) mod 1000000007)*(fib(n) mod 1000000007)) mod 1000000007

    ((fib(n) mod 1000000007)*(fib(n) mod 1000000007)) mod 1000000007 = (fib(n)*fib(n)) mod 1000000007

    It looks to me like all you have to do is to calculate the square of the Nth fibonacci number modulo 1000000007
    Exactly, you're right, but how I can implement it in the code?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by paut View Post
    ((fib(n) mod 1000000007)*(fib(n) mod 1000000007)) mod 1000000007 = (fib(n)*fib(n)) mod 1000000007
    Whilst that expansion is correct, the left hand side suffers less from arithmetic overflow than the right. It may be that you actually need to go the other direction, i.e. move the mod 1000000007 into the fib function, in order to prevent overflow.

    It's hard to know what's wrong with your solution if you're using an online marking system that just gives correct/incorrect output.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fibonacci sequence in c++
    By anytime in forum C++ Programming
    Replies: 50
    Last Post: 02-06-2011, 11:40 PM
  2. fibonacci sequence
    By cph in forum C Programming
    Replies: 57
    Last Post: 04-30-2009, 07:17 AM
  3. Fibonacci Sequence
    By Dogmasur in forum C Programming
    Replies: 15
    Last Post: 08-10-2008, 07:55 AM
  4. Fibonacci sequence
    By girliegti in forum C++ Programming
    Replies: 8
    Last Post: 09-30-2003, 10:40 PM
  5. Fibonacci Sequence
    By Unregistered in forum C++ Programming
    Replies: 6
    Last Post: 09-08-2001, 11:29 AM