Thread: Continued Fraction Algorithm View Single Post
2009-02-25, 12:05   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Raman I am not understanding any algorithm. In the beginning, people in the forum used up so to write: Now, I see that people are reluctant to help. I assume that people are getting irritated due to repeated demands. I think that it is better for me to behave in a way that I think is good, let whatever happen, I am not going to care. Take the continued fraction expansion of $\sqrt {kN}$ $\LARGE \sqrt {kN} = q_0 + \frac{1}{q_1 + \frac{1}{q_2 + \frac{1}{q_3 + \frac{1}{\ddots\,}}}}$ In my method, to calculate the value of qi's that I used up so $A_{-2}=0$ $A_{-1}=1$ $A_0=\lfloor{\sqrt{kN}}\rfloor$ $B_{-2}=1$ $B_{-1}=0$ $B_0=1$ $A_i=q_iA_{i-1}+A_{i-2}$ $B_i=q_iB_{i-1}+B_{i-2}$ The ith convergents are given up so by $\frac{A_i}{B_i}$ The even convergents are in deficit, and the odd convergents are in excess. So, thus, to calculate the values of qi's in my trial program, I used up so If i is even, qi is the least value such that $\frac{q_iA_{i-1}+A_{i-2}}{q_iB_{i-1}+B_{i-2}} \le \lfloor{\sqrt{kN}}\rfloor$ If i is odd, qi is the least value such that $\frac{q_iA_{i-1}+A_{i-2}}{q_iB_{i-1}+B_{i-2}} > \lfloor{\sqrt{kN}}\rfloor$ This is the algorithm that I used up so for my trial program. If it is admissible to use floating point arithmetic, qi can be directly calculated as follows: $\LARGE \pi = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + \frac{1}{\ddots\,}}}}}$ $C_0 = \lfloor \pi \rfloor = 3$ $C_1 = \lfloor \frac{1}{\pi - 3} \rfloor = 7$ $C_2 = \lfloor \frac{1}{\frac{1}{\pi - 3} - 7} \rfloor = 15$ and so on... But, in the paper by Morrison and Brillhart, A method of factoring and the factorization of F7 It is rather given some new formulas, where $g=\lfloor{\sqrt{kN}}\rfloor$ $g+P_n=q_nQ_n+r_n$, $0 \le r_n < Q_n$ $g+P_{n+1}=2g-r_n$ $Q_{n+1}=Q_{n-1}+q_n(r_n-r_{n-1})$ I don't understand how these formulas are arrived at g is reduced to an integer, so how the bottom three formulas will produce an indefinite continued fraction expansion? Just for theory, not the implementations at all, by now itself. Of course, for the time being.. How come $q_n = \lfloor \frac{\sqrt{kN}+P_n}{Q_n} \rfloor$ What is Pn? The term Qn is indeed OK for me, up so thus. $A_{n-1}^2 - kNB_{n-1}^2 = (-1)^nQ_n$. How come $0 \le P_n < \sqrt{kN}$ and then $0 < Q_n < 2 \sqrt{kN}$ thus?

See either Riesel's book, or Knuth Vol 2.