Pell Equation (was: Continued Fractions.) 
Author Message
 Pell Equation (was: Continued Fractions.)

Quote:
> In general (for larger N), because of the limited
> precision of floating point numbers, you have
> to modify f to work in Z[%:N] .  Such modification
> is left as an exercise for the reader :-)

Integer solutions of 1=(x^2)-N*(y^2), N not a perfect square.

Let r be %:N .  Write the residual term as (p+r)%q where p and q
are integers.  The verb g below computes in Z[%:N] to produce
the continued fraction expansion of %:N .

g=: 3 : 0
 N=. y.
 p=. 0x
 q=. 1x
 r=. %:N
 assert. r~:<.r
 m0=. <.q%~p+r
 z=. $0
 while. 1 do.
  m=. <.q%~p+r
  t=. (m*q)-p
  q=. q%~N-(p-m*q)^2
  p=. t
  if. m=2*m0 do. x: z return. end.
  z=. z, m
 end.
)

   ] N=: ?. 2e3    NB. a random integer
263
   ] v=: g N
16 4 1 1 1 1 15 1 1 1 1 4
   'x y'=: 2 x: (+%)/ v
   x
139128
   y
8579
   x^2
19356600384
   N*y^2
19356600383
   (x^2) - N*(y^2)
1

Now a bigger example:

   ] N=: ?.1e8     NB. a random integer
13153778
   ] v=: g N
3626 1 4 2 1 2 2 3 18 2 517 1 1 1 2 3 ...
   $ v
1066
   'x y'=: 2 x: (+%)/ v
   $ ": x
546

That is, x is a 546-digit number.


   fmt x
14284020174585239297767485378249531009467113848922
57777366986473004810368901903783607819017614430359
82622052262807806238846280996028730137902830328665
13249240267302167594754743180893140587056492990534
77314675386816346885502112261087694122760751525785
09946609934789821653313215686869349227735011298846
43439600233619246593765779421517498994498238759993
08350962311828862804706971113967879428951794446441
65160744106741207697639053066079066383999120638447
93925032605875536571097023872273733535556334470232
6429484022597062161766627333627078584761639937
   fmt y
39384487726174944454150630955144661284673691047950
71754105736546145287621919842703868970751035980658
93858759191248353883560328854948405365360157191271
49138691949673047012263630720644931927245509295746
78260516241084985421566401957956611902284505632580
23753245730272268685833194579405706745863016891434
31398076812746091863971794944943394903800603743230
29578310717272124424913232825415503743798486332263
30769921698935522003859577402612806800896565264682
93415835651301208262399756236438566472530073183884
003719429644448790439913309908462606089184
   (x^2) - N*(y^2)
1



Sun, 07 Nov 2004 06:26:18 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Continued Fractions.

2. Continued fractions, help needed.

3. continued fractions

4. Looking for references: Gosper, Continued Fraction Arithmetic

5. Finite Continued Fractions in SICP

6. iterative vs recursive processes WAS Finite Continued Fractions

7. continued fraction software MERRCZ

8. continued fraction

9. Reverse Engineering Continued (Am I on the right track)

10. I am not deaf, but am I mute?

11. fractions

12. LinkJ fractions hack

 

 
Powered by phpBB® Forum Software