View Single Post
Old 2009-02-25, 12:05   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Raman View Post
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.
R.D. Silverman is offline   Reply With Quote