The Museum of HP Calculators


Quadratic Hypersurfaces for the HP-41

This program is Copyright © 2006 by Jean-Marc Baillard and is used here by permission.

This program is supplied without representation or warranty of any kind. Jean-Marc Baillard and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.


Overview
 

-The following program reduces the cartesian equation of a quadratic hypersurface (QHS) in a n-dimensional space  ( n > 1 )

-Given    (QHS):  a11 x12 + a22 x22 + .............. + ann xn2 + Sum i < j  ai j xi xj  +  b1 x1 + b2 x2 + ............. + bn xn =  c

    the elements  ai j ( i < j ) are gradually zeroed by the Jacobi's iterative method.

-When all these elements are smaller than 10 -8 ( line 27 ) , the quadratic form is diagonalized.
 ( the n eigenvalues are in registers R01 thru Rnn at this step )
-Then ( lines 211 to 265 ) several translations and/or rotations are performed to reduce the equation further.
 

Data Registers:             R00 = n                        ( All these registers are to be initialized before executing "QUAD"  )

           I                R01 = a11    Rn+1 = a1,2   R2n    = a2,3   ..................................  R(n2+n)/2 = an-1,n       R(n2+n)/2+1 = b1        R(n2+3n)/2+1 = c
          N               R02 = a22    Rn+2 = a1,3   R2n+1 = a2,4     ...................                                                    R(n2+n)/2+2 = b2
          P                ...............         .................      ...................                                                                               ........................
          U               ...............         .................    R3n-2 = a2,n
          T               ................      R2n-1 = a1,n
          S                Rnn = ann                                                                                                                              R(n2+3n)/2 = bn

 -----------------------------------------------------------------------------------------------------------------------------------------------------------------

                  When the program stops:

                                       R00 = n
          O
          U              R01 = a'11      Rn+1 =  b'1       R2n+1 = c'
          T               R02 = a'22      Rn+2 =  b'2
          P              ...............         .................
          U
          T
          S               Rnn = a'nn      R2n =   b'n

-So, the reduced equation is:    (QHS):  a'11 X12 + a'22 X22 + .............. + a'nn Xn2  + b'1 X1 + b'2 X2 + ............. + b'n Xn =  c'

 where   b'i  = 0  if  a'ii # 0  and  c' = 0 or 1

Flags: /
Subroutines: /
 

Program Listing
 

-The synthetic registers  M , N , O , P  may be replaced by  any unused standard registers,
  for instance,  R92  R93  R94  R95  , provided  n < 13
 

  01  LBL "QUAD"
  02  LBL 01
  03  RCL 00
  04  ENTER^
  05  X^2
  06  +
  07  2
  08  /
  09  RCL 00
  10   E3
  11  /
  12  +
  13  ENTER^
  14  ENTER^
  15  CLX
  16  LBL 02
  17  RCL IND Z
  18  ABS
  19  X>Y?
  20  STO Z
  21  X>Y?
  22  +
  23  RDN
  24  DSE Z
  25  GTO 02
  26  VIEW X
  27   E-8                            ( or another "small" number )
  28  X>Y?
  29  GTO 11                      ( a three-byte GTO )
  30  CLX
  31  ENTER^
  32  R^
  33  INT
  34  STO M
  35  RCL 00
  36  -
  37  X<>Y
  38  LBL 03
  39  ISG Z
  40  CLX
  41  RCL 00
  42  +
  43  R^
  44  -
  45  X<Y?
  46  GTO 03
  47  -
  48  RCL 00
  49  +
  50  RCL IND X
  51  RCL IND Z
  52  -
  53  RCL IND M
  54  X<>Y
  55  R-P
  56  CLX
  57  2
  58  /
  59  1
  60  P-R
  61  STO N
  62  RDN
  63  STO O
  64  X^2
  65  RCL IND Z
  66  *
  67  STO P                   ( synthetic )
  68  CLX
  69  RCL IND Y
  70  RCL N
  71  X^2
  72  *
  73  ST+ P
  74  CLX
  75  X<> IND M
  76  RCL N
  77  *
  78  RCL O
  79  *
  80  ENTER^
  81  X<> P
  82  +
  83  X<> IND Y
  84  RCL O
  85  X^2
  86  *
  87  RCL P
  88  -
  89  X<> IND Z
  90  RCL N
  91  X^2
  92  *
  93  ST+ IND Z
  94  CLX
  95  RCL 00
  96  ENTER^
  97  X^2
  98  +
  99  2
100  /
101  STO P                   ( synthetic )
102  ST+ Z
103  +
104  XEQ 07
105  RCL 00
106  DSE X
107  X<> P
108  ST- Z
109  -
110  LBL 04
111  RCL P
112  ST+ Z
113  +
114  RCL M
115  X=Y?
116  GTO 00
117  RDN
118  XEQ 07
119  DSE P
120  GTO 04
121  LBL 00
122  RDN
123  LBL 05
124  RCL P
125  ENTER^
126  SIGN
127  ST+ T
128  -
129  +
130  X<>Y
131  RCL M
132  X=Y?
133  GTO 00
134  X<> Z
135  XEQ 07
136  DSE P
137  GTO 05
138  LBL 00
139  X<> Z
140  LBL 06
141  DSE P
142  X=0?
143  GTO 01                      ( a three-byte GTO )
144  ISG X
145  CLX
146  ISG Y
147  CLX
148  XEQ 07
149  GTO 06
150  LBL 07
151  RCL IND X
152  RCL O
153  *
154  SIGN
155  CLX
156  RCL IND Z
157  RCL N
158  ST* Y
159  X<> L
160  -
161  X<> IND Z
162  RCL O
163  *
164  X<> IND Y
165  RCL N
166  *
167  ST+ IND Y
168  RDN
169  RTN
170  LBL 08                           Lines 170 to 185 replace by zero all the coefficients smaller than  10 -7 in magnitude ( line 173 )
171  RCL 00
172  ST+ X
173   E-7
174  ISG Y
175  LBL 09
176  RCL IND Y
177  ABS
178  X<Y?
179  CLX
180  X=0?
181  STO IND Z
182  RDN
183  DSE Y
184  GTO 09
185  RTN
186  LBL 10
187  ST/ IND M
188  DSE M
189  GTO 10
190  RTN
191  LBL 11                               Lines 192 to 208 move the coefficients bi & c
192  RCL 00                              from registers   R(n2+n)/2+1  thru  R(n2+3n)/2+1    to registers   Rn+1  thru  R2n+1
193  ENTER^
194  X^2
195  +
196  2
197  /
198  RCL 00
199  1
200  ST+ Z
201  +
202   E3
203  /
204  ST+ Y
205  LASTX
206  /
207  +
208  REGMOVE
209  CLD
210  XEQ 08
211  RCL 00
212  ENTER^
213  ST+ X
214  STO M
215  ISG M
216  LBL 12
217  RCL IND Y
218  X=0?
219  GTO 12
220  4
221  *
222  RCL IND Y
223  X^2
224  X<>Y
225  /
226  ST+ IND M
227  CLX
228  STO IND Y
229  LBL 12
230  RDN
231  DSE X
232  DSE Y
233  GTO 12
234  XEQ 08
235  RCL IND M
236  X#0?
237  XEQ 10
238  RCL 00
239  STO N
240  ST+ X
241  STO M
242  ENTER^
243  ENTER^
244  CLX
245  ISG Z
246  LBL 13
247  RCL IND Y
248  X=0?
249  GTO 13
250  R-P
251  STO IND Z
252  X<>Y
253  CLX
254  STO IND T
255  ENTER^
256  +
257  LBL 13
258  RDN
259  DSE Y
260  DSE N
261  GTO 13
262  X#0?
263  XEQ 10
264  CLA
265  END

( 397 bytes / SIZE ( n2+3n+4 )/2 )
 
 
      STACK        INPUTS      OUTPUTS
           X             /             /

Example:    (QHS):  3 x2 + 4 y2 + 7 z2 + 6 t2 + 9 x.y + 3 x.z + 7 x.t + 4 y.z + 8 y.t + 2 z.t + 9 x + 2 y + 5 z + 4 t = 10  in a 4-dimensional space.

       SIZE 016  or greater

   4  STO 00  and we store these ( n2+3n+2 )/2 = 15 coefficients as shown below:

           3     9     4      2       9       10                          R01     R05     R08     R10      R11       R15
           4     3     8               2                     into          R02     R06     R09                  R12                     respectively
           7     7                      5                                    R03     R07                              R13
           6                             4                                    R04                                         R14
 

 XEQ "QUAD"  the HP-41 displays the successive greatest  | ai j |  ( which tend to zero )  and when the program stops, the results are in registers R01 thru R2n+1

         R01 =  -0.209131158     R05 = 0      R09 = 1                       Execution time = 2mn28s
         R02 =   0.297006169     R06 = 0
         R03 =   1.235467092     R07 = 0
         R04 =   2.716166061     R08 = 0

  So, the reduced equation is   -0.209131158 X2 +  0.297006169 Y2 + 1.235467092 Z2 + 2.716166061 T2 = 1    a "hyper-hyperboloid"?
 

Notes:     The 4 eigenvalues of the initial quadratic form are     -1.035428817  ,   1.470506591  ,  6.116918408  ,  13.44800383
                These 4 numbers are in registers R01 thru R04  when the program reaches line 191 or line 209

-If you want to save these values, for instance in registers R2n+2 to R3n+1,

      add  RCL 00   RCL 00   .1   %   +   +   2   +   E3   /    1   +   REGMOVE   after line 209 or 210

-In the above example, n = 4 and the eigenvalues will be eventually in registers  R10 R11 R12 R13

-If you want to compute the n eigenvalues only,

   store  n into R00 , the coefficients ai i & ai j  into R01 thru  R(n2+n)/2  and
   replace lines 170 to 265  by  LBL 11   CLA  CLD  END
   replace lines 95 to 109 by  RCL 00   DSE X   STO P  ( synthetic )  RDN           >>  They will be in R01 thru Rnn at the end.

-Actually, these eigenvalues are the n eigenvalues of the symmetric matrix  M = [ mi j ]  defined by   mi i = ai i  and  mi j = mj i = (1/2) ai j  for i # j

-The results are quite similar to those given by "QUADRIC"  in a 3-dimensional space ( cf "Quadrics for the HP-41" )
  but here, the names of the hypersurfaces have been omitted for 2 reasons:

    1°) This would require many extra bytes.
    2°) I don't know the exact terminology!

-For n = 7 , the execution time is of the order of  18 minutes.
-If this program is executed from extended memory, n could reach 23.
 

Exercise:    (QHS):   2 x2 + 3 y2 + 4 z2 + 2 t2 + 2 x.y + 6 x.z + 4 x.t + 12 y.z + 2 y.t + 6 z.t + 2 x + 3 y + 4 z + 5 t = 10  in a 4-dimensional space.

Answer:    The reduced equation is:     Y = 1.461929785 X2 -  1.113606716 Z2 -  5.533772793 T2    a kind of hyperbolic hyperparaboloid?

  and the 4 eigenvalues of the original quadratic form are:    -3.101221397 ,  0  ,  2.362316584  ,  11.73890481
 

Go back to the HP-41 software library
Go back to the general software library
Go back to the main exhibit hall