Thread: Fibonacci Formula, How to round in C++?

  1. #1
    #junkie
    Join Date
    Oct 2004
    Posts
    240

    Question Fibonacci Formula, How to round in C++?

    Ok, my question is simple, how do you round in c++? im sure there is some prebuilt function to do this, least i hope.

    What im trying to do is build a test for figuring out a simple Fibonacci formula, (n-1+n-2)=x type thing. Basically you can do it perfectly through Recursion, but as all you know far better than me (assuming i got this right), with big numbers you end up having thousands of instances of the function to complete your Fabonacci formula.

    What i wanna do is figure the percentage of a number and round it to zero, i wanna see where (61%of n+40% of n)=x starts going wrong. Cuz rounded to zero, in small numbers that works just as good as recursion, im just curious as to what number it will go off on. Thus i need to know how to round in C++.

    Thanks
    (if you dont know what Fabonacci is dont worry bout it, all i need to know is how to round in c++ lol).

    Also, sidenote, here is an example of a Fab Formula.
    1,1,2,3,5,8,13,21,34,55,89,144,223..
    01110111011000010110110001100100011011110010000001 11000101110101011010010111010000100000011011000110 10010110011001100101001000000111100101101111011101 0100100000011011100111010101100010

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    There is a formula for calculating fibonacci numbers without recursion or loops.
    The n:th number equals
    1/s * ( ((1+s)/2)^n - ((1-s)/2)^n )
    where
    s = sqrt(5)

    The proof involves setting up an equation with matrices and calculating A^n for a 2x2 matrix.

    EDIT: even though it contains a number of sqrt(5), the result is always an integer.
    Last edited by Sang-drax; 10-14-2004 at 04:29 PM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    #junkie
    Join Date
    Oct 2004
    Posts
    240
    ok, thanks lol.
    What about round though? still curious
    01110111011000010110110001100100011011110010000001 11000101110101011010010111010000100000011011000110 10010110011001100101001000000111100101101111011101 0100100000011011100111010101100010

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    one way is to use int variables and add 0.5 to the number you want to round. ints ignore any decimal places (truncates, whatever). Therefore if the given value is less than 0.5 it will round down to the current value and if 0.5 or above it will round up to the next int value.

  5. #5
    #junkie
    Join Date
    Oct 2004
    Posts
    240
    oh duh, forgot about int trunacating decimals. So 1547.2445213 it would round to 1547 right?
    01110111011000010110110001100100011011110010000001 11000101110101011010010111010000100000011011000110 10010110011001100101001000000111100101101111011101 0100100000011011100111010101100010

  6. #6
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    Yes.

    1547.2445213 -> 1547
    1547.4999999 -> 1547
    1547.5000000 -> 1548
    1547.9999999 -> 1548

  7. #7
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    In <cmath>, you can also use floor() and ceil() to preserve the floating point data type (which is a good thing with really large numbers).

    Sang drax, the proof I've seen of that formula does not make use of matrices (I can't remember it right off, but I could probably figure it out after a while). I'd be interested in seeing that one if you have a link handy.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  8. #8
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    1547.9999999 -> 1548
    WRONG!
    Casting a double to an int (either explict or just through assignment) TRUNCATES!

    Code:
    double x = 1547.999999;
    int y = x;
    int z = int(x);
    Both y and z with be 1547 not 1548

  9. #9
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    jlou was just trying to say that
    1547.9999999 should be rounded up to 1548,
    I believe.
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  10. #10
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,090
    Quote Originally Posted by Zeusbwr
    So 1547.2445213 it would round to 1547 right?
    Quote Originally Posted by jlou
    Yes.

    1547.2445213 -> 1547
    1547.4999999 -> 1547
    1547.5000000 -> 1548
    1547.9999999 -> 1548
    Quote Originally Posted by Thantos
    WRONG!
    Casting a double to an int (either explict or just through assignment) TRUNCATES!

    Code:
    double x = 1547.999999;
    int y = x;
    int z = int(x);
    Both y and z with be 1547 not 1548
    Quote Originally Posted by alphaoide
    jlou was just trying to say that
    1547.9999999 should be rounded up to 1548,
    I believe.
    Yes. I was answering Zeusbwr's question, and providing extra examples.

  11. #11
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by Zach L.
    Sang drax, the proof I've seen of that formula does not make use of matrices (I can't remember it right off, but I could probably figure it out after a while). I'd be interested in seeing that one if you have a link handy.
    I don't have a link to it on the Internet, but I can try to show you here on the internet:
    The idea is do calculate a power of a 2x2 matrix by diagonalizing it.
    Code:
    F[k] is the k:th Fibonacci number
    
    X[k] is a 2x1 matrix:
    (F[k]    )
    (F[k-1] )  = X[k]
    
    A is a matrix such that
    X[k] = A*X[k-1]
    
    A then equals
    ( 1 1 )
    ( 1 0 )
    
    The n:th Fibonacci number can then be written
    X[n+1] = A^n * X[1]
    We know that X[1] equals 
    ( 1 )
    ( 0 )
    so all we have to do is calculating A^n and multiplying it with X[1].
    
    This is done by calculating the two eigenvalues of A which are:
    (1 + sqrt(5))/2
    (1 - sqrt(5))/2
    using the eigenvalues and eigenvectors we can diagonalize A by writing A as S*D*S^-1
    where S is a matrix with the eigenvectors and D is a diagonal matris.
    A^n  = S * D^n * S^-1
    
    This equals, after the three matrix multiplications, the formula I posted above.
    This will make no sense if you haven't studied linear algebra.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fibonacci prime
    By dbzx in forum C Programming
    Replies: 5
    Last Post: 04-17-2009, 11:13 AM
  2. About aes
    By gumit in forum C Programming
    Replies: 13
    Last Post: 10-24-2006, 03:42 PM
  3. I need some quick help with code.
    By stehigs321 in forum C Programming
    Replies: 35
    Last Post: 10-30-2003, 10:07 PM
  4. Someone help me with this game??
    By stehigs321 in forum Game Programming
    Replies: 15
    Last Post: 10-30-2003, 09:42 PM
  5. Please help with some coding..
    By stehigs321 in forum C Programming
    Replies: 2
    Last Post: 10-27-2003, 06:44 PM