View Single Post
Old 2009-02-25, 11:38   #1
Raman's Avatar
"Mr. Tuch"
Dec 2007
Chennai, India

100111010012 Posts
Default Continued Fraction Algorithm

I am not understanding any algorithm.

In the beginning, people in the forum used up so to write:
If you want help in understanding an algorithm, I will be more than happy to answer any questions.
Now, I see that people are reluctant to help. I assume that people are getting irritated due to repeated demands.
Enough clues??????
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
The ith convergents are given up so by
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+P_n=q_nQ_n+r_n, 0 \le r_n < Q_n
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}

Last fiddled with by Raman on 2009-02-25 at 11:42
Raman is offline   Reply With Quote