hp41programs

Pell Equation

Pell's Equation for the HP-41


Overview
 

 1°)  x2 - d y2 = m
 2°)  x2 - d y2 = 1
 

-Here, x , y , d , m are integers: Pell's equation is a Diophantine equation.
-In paragraph 1, the positive integers y are tested until x is an integer.
-In paragraph 2, continued fractions are used and a solution is return much faster.
 

1°)    x2 - d y2 = m
 
 

Data Registers: /
Flag:  F29
Subroutines: /

-The append character is denoted  ~
 
 

01  LBL "PELL"
02  STO T
03  CLX
04  STO Z
05  LBL 01
06  SIGN
07  ST+ Z
08  CLX
09  RCL Z       
10  X^2
11  X<>Y
12  ST* Y
13  X<>Y
14  R^
15  ST+ Y
16  RDN
17  SQRT        
18  FRC
19  X#0?
20  GTO 01
21  FIX 0
22  CF 29
23  CLA
24  ARCL L     
25  "~^2-" 
26  ARCL Y
27  "~*"
28  ARCL Z
29  "~^2="
30  ARCL T
31  FIX 4
32  SF 29
33  PROMPT   
34  GTO 01
35  END

 
  ( 70 bytes / SIZE 000 )
 
 

      STACK        INPUTS      OUTPUTS
           T             /            m
           Z             /             y
           Y             d             d
           X             m             0
           L              /             x

Example:                  x2 - 7 y2 = 2

  7  ENTER^
  2  XEQ "PELL"  >>>>   "3^2-7*1^2=2"
                              R/S     "45^2-7*17^2=2"
                              R/S     "717^2-7*271^2=2"
                              R/S     ..............................

Note:

-Do not disturb the stack before pressing R/S again.
-Execution time is often prohibitive and the following approach is better.
 

2°)    x2 - d y2 = 1
 

-Here, d must not be a perfect square.
-The following routine uses the continued fraction of sqrt(d).

-"PELL1" takes d in X-register and returns the smallest solution x , y in registers X , Y.
 

Data Registers:    R00 = d     R01 thru R10: temp
Flags: /
Subroutines: /
 
 

01  LBL "PELL1"
02  STO 00
03  ENTER^
04  SQRT
05  INT
06  STO 01
07  STO 04
08  STO 10
09  X^2
10  -
11  STO 02
12  STO 05
13  CLX
14  STO 06
15  STO 08
16  SIGN
17  STO 07
18  STO 09       
19  LBL 01
20  RCL 00
21  SQRT
22  RCL 01
23  +
24  RCL 02
25  /
26  INT
27  STO 03
28  RCL 02
29  *
30  RCL 01
31  -
32  STO 01
33  X^2
34  CHS
35  RCL 00       
36  +
37  RCL 02
38  /
39  STO 02
40  RCL 06
41  RCL 07
42  STO 06
43  RCL 03
44  *
45  +
46  STO 07
47  RCL 09
48  RCL 10
49  STO 09       
50  RCL 03
51  *
52  +
53  STO 10
54  SIGN
55  ST+ 08
56  RCL 02
57  RCL 05
58  X#Y?
59  GTO 01
60  RCL 01
61  RCL 04
62  X#Y?
63  GTO 01       
64  RCL 08
65  2
66  MOD
67  X#0?
68  GTO 01
69  RCL 06
70  RCL 09
71  END
 

 
   ( 85 bytes / SIZE 011 )
 
 

      STACK        INPUTS      OUTPUTS
           Y             /             y
           X             d             x

Examples:

   41  XEQ "PELL1"   >>>>   x = 2049         ---Execution time = 8s---
                                  X<>Y   y = 320

   61       R/S       >>>>   x = 1766319049         ---Execution time = 26s---
                          X<>Y   y =  226153980
 

-Obviously, the first program could not have found this solution!
 

Reference:

[1]   http://mathworld.wolfram.com/PellEquation.html