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

 Page 1 of 1 [ 1 post ]

Relevant Pages