Pell's Equation for the HP-41

Overview
 

 1°)  x² - d y² = m
 2°)  x² - d y² = 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°)    x² - d y² = 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:                  x² - 7 y² = 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°)    x² - d y² = 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