Formula using rational numbers

[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?

Thank you in advance.

 

[mathman]

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

 

[robphy]

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

 

[jbriggs444]

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

u3 = k * u2 -u1

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

 

[intervoxel]

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

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

 

[intervoxel]

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

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

 

[intervoxel]

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

Could you, please, recommend any book about rational numeric method?

 

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

 

[pbuk]

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

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 u₃ 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 u_k does not change between iterations.

 

[intervoxel]

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 u₃ 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 u_k does not change between iterations.

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