bisection

# Bisecting Hyperplanes for the HP-41

Overview

1°)  Bisecting Lines

a)  Program#1
b)  Program#2

2°)  Bisecting Hyperplanes

a)  Program#1
b)  Program#2

-Given 2 hyperplanes,

(H) : a1 x1 + ........ + an xn + b = 0
(H') : a'1 x1 + ........ + a'n xn + b' = 0 ,

we seek the set of points that are equidistant from (H) & (H')

-If   a12 + ..... + an2 = a'12 + ..... + a'n2 = 1 ,  ( otherwise, we simply have to normalize the coefficients )

the answer is given by  a1 x1 + ........ + an xn + b = +/- ( a'1 x1 + ........ + a'n xn + b' )  which are in general the equations of 2 hyperplanes (H") & (H''')

-We assume that the basis are orthonormal.

1°)  Bisecting Lines

a) Program#1

-Though the programs listed in paragraph 2°) could be applied in this case, simpler routines may be written.
-Here, we suppose that the equations of the straight-lines are expressed in the slope-intercept form:

(D1) : y = m1 x + p1  ,  (D2) : y = m1 x + p1

Data Registers:   R00 to R04: temp
Flag:  F01
Subroutines: /

 01  LBL "BISL"  02  CF 01  03  STO 03  04  RDN  05  STO 02         06  RDN  07  STO 01  08  X<>Y  09  STO 00  10  X^2 11  1  12  +  13  SQRT  14  ST/ 00  15  ST/ 01  16  1/X  17  STO 04         18  RCL 02  19  X^2  20  1 21  +  22  SQRT  23  ST/ 02  24  ST/ 03  25  1/X  26  RCL 01         27  RCL 03  28  ST+ 01  29  -  30  RCL 00 31  RCL 02  32  ST+ 00  33  -  34  RCL 04         35  R^  36  ST+ 04  37  -  38  X=0?  39  SF 01  40  X#0? 41  ST/ Z  42  X#0?  43  /  44  RCL 01         45  RCL 04  46  ST/ 00  47  /  48  RCL 00  49  END

( 69 bytes / SIZE 005 )

 STACK INPUTS OUTPUTS T m1 p' Z p1 m' Y m2 p X p2 m

If  F01 is set at the end, do not take into account  m' and p'

Example:    (D1) : y = 3 x + 4  ,  (D2) : y = -2 x + 1

3   ENTER^
4   ENTER^
-2   ENTER^
1   XEQ "BISL"  >>>>   0.071067812
RDN    2.242640687
RDN  -14.07106780
RDN    -6.242640680

-F01 is clear, so we get 2 lines:   (D) : y = 0.071067812 x + 2.242640687
and   (D') : y = -14.07106780 x - 6.242640680

Notes:

-If flag F01 is set, i-e if  | m1 | = | m2 | , then "forget" m' & p'

b) Program#2

-Now, the equations of the straight-lines are expressed in the general form:

(D1) : a1 x + b1 y + c1 = 0  ,  (D2) : a2 x + b2 y + c2 = 0   with  ( a1 , b1 ) # ( 0 , 0 )  and  ( a2 , b2 ) # ( 0 , 0 )

-The equations of the bisecting lines (D) & (D') replace the original coefficients in R01 thru R06.

Data Registers:               R00  is unused                                ( Registers R01 thru R06 are to be initialized before executing "BISL" )

•  R01 = a1           •  R04 = a2                                                              R01 = a              R04 = a'
•  R02 = b1           •  R05 = b2           and when the program stops:       R02 = b             R05 = b'
•  R03 = c1           •  R06 = c2                                                              R03 = c              R06 = c'
Flags: /
Subroutines: /

 01  LBL "BISL"  02  RCL 01  03  RCL 02         04  R-P  05  RCL 04  06  RCL 05 07  R-P  08  RCL Z          09  /  10  ST* 01  11  ST* 02  12  ST* 03 13  RCL 01  14  RCL 04         15  ST+ 01  16  -  17  STO 04  18  RCL 02 19  RCL 05  20  ST+ 02  21  -  22  STO 05         23  RCL 03  24  RCL 06 25  ST+ 03  26  -  27  STO 06         28  END

( 44 bytes / SIZE 007 )

 STACK INPUT OUTPUT X / /

Example:   (D1) : 2 x + 9 y + 1 = 0  ,  (D2) : 6 x + 7 y + 4 = 0

2  STO 01    6  STO 04
9  STO 02    7  STO 05
1  STO 03    4  STO 06   XEQ "BISL"   gives in 2 seconds:

R01 =  8      R04 = -4
R02 = 16     R05 =  2            whence    (D) : 8 x + 16 y + 5 = 0  and   (D') :  -4 x + 2 y - 3 = 0
R03 =  5      R06 = -3

2°)  Bisecting Hyperplanes

a) Program#1

-For planes and hyperplanes, we use the same method.

-First, the equations are supposed to be written in the form:

(H) :  xn = a1 x1+ ........ + an-1 xn-1 + b  ,   (H') :  xn = a'1 x1 + ........ + a'n-1 xn-1 + b'

-At the end, the equations of the bisecting hyperplanes (H") & (H''')  replace the original coefficients in registers R01 to R2n

Data Registers:           •  R00 = n                    ( Registers R00 thru R2n are to be initialized before executing "BISHP" )

•  R01 = a1                    •  Rn+1 = a'1
•  R02 = a2                    •  Rn+2 = a'2
..............                        ................

•  Rn-1 = an-1                •  R2n-1 = a'n-1
•  Rnn  =  b                    •  R2n   =   b'
Flag:  F01
Subroutines: /

 01  LBL "BISHP"  02  CF 01  03  RCL 00          04  ENTER^  05  ST+ Y  06   E3  07  /  08  +  09  ENTER^  10  ENTER^  11  SIGN  12  ST- Y  13  LBL 01  14  RCL IND Y  15  X^2 16  +  17  DSE Y  18  GTO 01  19  SQRT  20  LBL 02  21  ST/ IND Z  22  DSE Z  23  GTO 02  24  1/X  25  STO M  26  STO N  27  RCL 00          28  RCL 00  29  1  30  ST- Y 31  LBL 03  32  RCL IND Y  33  X^2  34  +  35  DSE Y  36  GTO 03  37  SQRT  38  LBL 04          39  ST/ IND Z  40  DSE Z  41  GTO 04  42  1/X  43  ST+ M  44  ST- N  45  RCL 00 46  ENTER^  47  ST+ Y  48  LBL 05  49  RCL IND Y  50  RCL IND Y  51  ST- IND T  52  +  53  STO IND Y  54  RDN  55  DSE Y  56  DSE X  57  GTO 05  58  RCL 00          59  ENTER^  60  ST+ Y 61  RCL N  62  X=0?  63  SF 01  64  RCL M  65  LBL 06          66  X<>Y  67  X#0?  68  ST/ IND T  69  X<>Y  70  ST/ IND Z  71  DSE T  72  DSE Z  73  GTO 06  74  CLA  75  END

( 123 bytes / SIZE 2n+1 )

 STACK INPUT OUTPUT X / /

Example:   (P) :  z = 3 x + y + 25  ,  (P') : z = x/7 - y + 13/7   ( 2 planes in a 3-Dimensional space )

-We are in a 3-Dimensional space so   3  STO 00

3   STO 01              7   1/X   STO 04
1   STO 02              1  CHS  STO 05
25  STO 03         13 ENTER 7 /  STO 06

XEQ "BISHP"  returns in 5 seconds

R01 =    1             R04 = -2
R02 = -0.4           R05 = -2.5                  thus,  (P") :  z = x - 0.4 y + 8.8  &  (P''') :  z = -2 x -2.5 y - 15.5
R03 =  8.8           R06 = -15.5

Notes:

-If F01 is set, the coefficients in R01 to Rnn give the equation of one hyperplane.
-It may happen if the second hyperplane is parallel to (Oxn) or if (H) // (H')

b) Program#2

-Now, the equations are written in the general form:

(H) :  a1 x1 + ........ + an xn + b = 0  ,   (H') :   a'1 x1 + ........ + a'n xn + b' = 0

with  ( a1 , ..... , an ) # ( 0 , ........ , 0 )  and  ( a'1 , ..... , a'n ) # ( 0 , ........ , 0 )

-At the end, the equations of the bisecting hyperplanes (H") & (H''')  replace the original coefficients in registers R01 to R2n+2

Data Registers:           •  R00 = n                     ( Registers R00 thru R2n+2 are to be initialized before executing "BISHP" )

•  R01 = a1                    •  Rn+2 = a'1
•  R02 = a2                    •  Rn+3 = a'2
..............                        ................

•  Rnn  = an                   •  R2n+1 = a'n
•  Rn+1 =  b                  •  R2n+2 =   b'
Flags:  /
Subroutines:  /

 01  LBL "BISHP"  02  RCL 00  03  0  04  LBL 01  05  RCL IND Y  06  X^2  07  +  08  DSE Y  09  GTO 01          10  STO M  11  RCL 00 12  ENTER^  13  ST+ Y  14  1  15  ST+ Z  16  +  17   E3  18  /  19  +  20  0  21  LBL 02          22  RCL IND Y 23  X^2  24  +  25  DSE Y  26  GTO 02          27  0  28  X<> M  29  /  30  SQRT  31  X<>Y  32  INT  33  X<>Y 34  LBL 03  35  ST* IND Y  36  DSE Y  37  GTO 03  38  RCL 00          39  1  40  +  41  ENTER^  42  ST+ X  43  LBL 04  44  RCL IND Y 45  RCL IND Y  46  ST+ IND T  47  -  48  STO IND Y  49  RDN  50  DSE X  51  DSE Y  52  GTO 04          53  END

( 85 bytes / SIZE 2n+3 )

 STACK INPUT OUTPUT X / n+1

Example:      (H) :  x + y + 2 z + 5 t + 3 = 0  ,  (H') :  x + 5 y + 7 z + 7 t + 2 = 0    ( in a 4-dimensional space )

4   STO 00    ( 4-dimensional space )

1   STO 01               1   STO 06
1   STO 02               5   STO 07
2   STO 03               7   STO 08
5   STO 04               7   STO 09
3   STO 05               2   STO 10

XEQ "BISHP"   yields in 5 seconds:

R01 =  3              R06 =  1
R02 =  7              R07 = -3
R03 = 11             R08 = -3          whence   (H") : 3 x + 7 y + 11 z + 17 t + 8 = 0  ,  (H''') :  x - 3 y - 3 z + 3 t + 4 = 0
R04 = 17             R09 =  3
R05 =  8              R10 =  4

Notes:

-In this example, all the coefficients are integers, but in most cases, the exact results are irrational numbers.
-With n = 50 , execution time = 51 seconds.