1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Formula using rational numbers

  1. Feb 25, 2016 #1
    I want to convert a recursive real formula to rational number representation, but I get the wrong response.

    For the real formula:
    k = 1.9903694533443939
    u1 = -12.485780609032208
    u2 = -6.273096981091879

    u3 = k * u2 -u1

    /// 1st iteration
    u3 = -1.7763568394002505E-15 // approx. zero

    /// 2nd iteration
    u3 = 6.273096981091875

    /// 3rd iteration
    u3 = 12.485780609032204

    which are the correct values

    For the rationalized formula we have

    kn=39270881, kd=19730448
    u1n=-234750193, u1d = 18801403
    u2n=-181086902, u2d=28867225

    u3n = u1d * u2n * kn - u1n * u2d * kd;
    u3d = u1d * u2d * kd;

    /// 1st iteration
    u3n = -21418193, u3d = -4484756162545334248
    u3n/u3d = -3.552713678800501E-15 // approx. 0, ok

    /// 2nd iteration
    u3n = -417378632937067183, u3d = -909312338189447552
    u3n/u3d = 6.273096981101384 // ok

    /// 3rd iteration
    u3n = -366571621992223341, u3d = 216113855164233728
    u3n/u3d = 0.913588924930172 // wrong!

    Can anyone figure out what's wrong?

    Thank you in advance.
  2. jcsd
  3. Feb 25, 2016 #2


    User Avatar
    Science Advisor

    You need to describe what you are doing after the first iteration. What are the formulas for the second and third iterations?
  4. Feb 25, 2016 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    What software are you using?
    Are you encountering floating-point errors? Or exceeding the limits of your software variables?
  5. Feb 25, 2016 #4


    User Avatar
    Science Advisor


    You have a linear recurrence relation, ##u_{n}=ku_{n-1} - u_{n-2}## and are evaluating it iteratively, given starting values for ##k##, ##u_1## ##u_2##. You switch to rational arithmetic using 64 bit integers and run into overflow problems around ##u_5##.
  6. Feb 26, 2016 #5
    It's a loop of N iterations
    u3 = k * u2 -u1
    u1 = u2
    u2 = u3
  7. Feb 26, 2016 #6
    I'm using Java.
    What is the best way to deal with overflow in this case?
  8. Feb 26, 2016 #7
    Could you, please, recommend any book about rational numeric method?
  9. Feb 26, 2016 #8


    User Avatar
    Science Advisor

    It is not clear what your end goal is here. Second order homogeneous linear recurrence relations like this can be solved analytically, yielding solutions which normally take the form of a sum of exponentials, ##ae^{c_1n} + be^{c_2n}##. You would solve the characteristic polynomial ##x^2 - kx + 1 = 0## to find the values of ##c_1## and ##c_2## and then plug in the known values for ##u_1## and ##u_2## to determine the values of a and b.
  10. Feb 26, 2016 #9
    I think that is the wrong question. These are the questions that I would ask:
    • What is the application of this method, and why do you think that calculating the recurrence relation iteratively using precise rationals is the best solution?
    • What benefit do you think you get from using precise rationals and then converting to floating point - the fact that u3 is only approximately zero hints that you may not have better than floating point accuracy anyway?
    • Have you considered converting the recurrence relation to an explicit expression?
    But if you insist on implementing it this way, Java.math.BigNumber will give you arbitrary precision rationals.

    Note that you should use jbriggs' notation in post #4, that way the meaning of uk does not change between iterations.
  11. Feb 26, 2016 #10
    • It is an algorithm to calculate the sine function in a cellular automaton. The cell processors are not supposed to use floating point numbers. The module of the sine amplitude must match the automaton dimension, say N.
    • In the second case I showed the ratio just by comparison with the upper case.
    • The recurrence solution is what adapts naturally to a cellular automaton, I think, in which each cell is constrained to communicate with neighbor cells only.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook