# Formula using rational numbers

1. Feb 25, 2016

### intervoxel

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?

2. Feb 25, 2016

### mathman

You need to describe what you are doing after the first iteration. What are the formulas for the second and third iterations?

3. Feb 25, 2016

### robphy

What software are you using?
Are you encountering floating-point errors? Or exceeding the limits of your software variables?

4. Feb 25, 2016

### jbriggs444

Guessing...

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$.

5. Feb 26, 2016

### intervoxel

It's a loop of N iterations
u3 = k * u2 -u1
u1 = u2
u2 = u3

6. Feb 26, 2016

### intervoxel

I'm using Java.
What is the best way to deal with overflow in this case?

7. Feb 26, 2016

### intervoxel

8. Feb 26, 2016

### jbriggs444

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.

9. Feb 26, 2016

### MrAnchovy

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.

10. Feb 26, 2016

### intervoxel

• 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.