Thread: Continued Fraction Algorithm View Single Post
2009-02-25, 11:38   #1
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

100111010012 Posts
Continued Fraction Algorithm

I am not understanding any algorithm.

In the beginning, people in the forum used up so to write:
Quote:
 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.
Quote:
 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$
$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?

Last fiddled with by Raman on 2009-02-25 at 11:42