home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / news / 4569 / goodies8 / math / polylib.doc < prev    next >
Text File  |  1993-02-18  |  13KB  |  424 lines
  1. (Comp.sources.hp48)
  2. Item: 113 by mheiskan@hut.fi
  3. Author: [Mika Heiskanen]
  4.   Subj: POLY and ARIT libs v2.0
  5.   Date: Mon Jun 01 1992
  6.  
  7. [Oooh!  These are libraries that most students would KILL for!  -jkh-]
  8.  
  9. I have received several requests about the new version of my POLY routines
  10. (which I promised to publish). I have done lots of bug fixing and new
  11. routines, but the libs are still not ready. Since I'm not likely to finish
  12. it for some time to come, I'll publish this new version.
  13.  
  14. ARIT library is finished (unless I get some new ideas :)
  15. POLY library doesn't have the unfinished routines, but it is still a lot
  16. better than the previous version. 
  17.  
  18. All routines are written in system rpl for speed.  ARIT is independent of
  19. POLY but you need ARIT if you use POLY.
  20.  
  21. ARIT contains programs for arithmetic manipulations :
  22.  
  23. SCOLCT : symbolic colct, does lists too (To simplify polynomials ofcourse!)
  24. MCOLCT : above multiple times
  25. SEXPAN : still the usual expan, but does lists too
  26. EXCO   : multiple SEXPAN and SCOLCT 
  27. GCD    : greatest common denominator
  28. LCM    : least common multiple
  29. FACTOR : obvious
  30. FACS   : gives each factor only once
  31. RVAL   : simplifies expression which will be rational
  32. RADD   : adds rational numbers
  33. RSUB   : substracts ...
  34. RMUL   : multiplies ...
  35. RDIV   : divides ...
  36. RPOT   : rational number to ...
  37. RINV   : inverse of ...
  38. RABS   : absolute of ...
  39. SSQRT  : symbolic square root
  40. ...
  41.  
  42.  
  43. POLY contains programs for polymonial calculations :
  44.  
  45. PADD   : adds polynomials
  46. PMUL   : multiplies ...
  47. PDIV   : divides ...
  48. POWP   : polynomial to integer power
  49. PDER   : derivative of poly.
  50. PRIM   : primitive ...
  51. SROOTS : symbolic roots of polynomial
  52. ROOTS  : numerical ones
  53. SDG2   : symb. roots of 2nd (1st) degree polynomial
  54. DEG2   : roots of ...
  55. PVAL   : value of polynomial at a point (Horner method)
  56. P->A   : similar to above, use with symbolic arguments
  57. A->P   : algebraic to polynomial
  58. A->F   : algebraic to rational polynomial
  59. F->A   : can you guess? :)
  60. DOAL   : operates on each coef.
  61. SMPF   : simplifies a rat. poly.
  62. FADD   : adds ...
  63. FSUB   : something unthinkable...
  64. FMUL   : multiply and fill the earth...
  65. FDER   : derivative of ...
  66. FVAL   : value of ... at a point
  67. PGCD   : greatest common ... of 2 polynomials
  68. PLCM   : least ...      
  69. TOG5   : toggles flag 5
  70. + subroutines
  71.  
  72. New ones:
  73. PF     : Partial fractions
  74. IRT    : Given roots gives the polynomial
  75.  
  76. And now with more details:
  77.  
  78. The routines recognize rational numbers of the form +-(A/B) where A and B
  79. are real (complex) integers.
  80. Polynonials are expressed in the usual form, as lists with the highest
  81. order coefficient first.
  82. POLY uses the routines in ARIT directory to enable calculations with
  83. rational coefficients. However POLY has 2 modes, if you don't want to
  84. use rational numbers (faster). Flag 5 is used to indicate corresponding 
  85. modes with flag set meaning rational mode. You will see a little 5 in 
  86. the status area to indicate this. TOG5 is supplied to help toggling modes.
  87.  
  88. And now to each program:
  89.  
  90. n1,n2... real integer
  91. r1,r2... rational numbers (Note: can be n1,n2 too!)
  92.  
  93.                               ARIT directory:
  94.                               ~~~~~~~~~~~~~~~
  95.  
  96. GCD:
  97.   Finds GCD of 2 real integers
  98.   Stack: 
  99.         2: n2           -> 
  100.         1: n1                           1: n3
  101.   Examples:                                      
  102.         2: 9            ->              
  103.         1: 6                            1: 3
  104.  
  105. LCM:
  106.   Finds LCM of 2 real integers
  107.   Operation similar to above GCD
  108.  
  109. FACTOR:
  110.   Programmed by Klaus Kalb.
  111.   Slightly modified to consider 2^20-1 to be always the highest possible
  112.   factor, also tagged with the number to be factored.
  113.   Stack:
  114.         1: n1           ->              1: n1:{ factors }
  115.   Examples:
  116.         1: 1456         ->              1: 1456: {2 2 2 2 7 13}
  117.  
  118.         1: 1            ->              1: 1: {}
  119.  
  120.         1: n1<1         ->              error
  121.  
  122. FACS:
  123.   Gives each factor once, tagging removed.
  124.   Examples :
  125.         1: 1456         ->              1: {2 7 13} 
  126.         
  127.         1: 0 or 1       ->              1: {}
  128.  
  129. RVAL: 
  130.   Evaluates algebraic expression, simplifies rational numbers as they appear.
  131.   Uses programs RADD, RMUL ... SSQRT. Doesn't simplify algebraics.
  132.   Stack:
  133.         1: Symbolic     ->              1: Simplified
  134.         1: Other        ->              1: Unchanged
  135.   Examples:
  136.         1: '(5/6-2*INV(5/4/3))^3-3'  -> 1: '-1766159/27000'
  137.         1: '2*4/5-A/B'               -> 1: '(B*8-A*5)/(5*B)'
  138.         1: '(2,4)/6'                 -> 1: '(1,2)/3'
  139.         1: '2-4*SQRT(24)'            -> 1: '2-2*SQRT(6)*4'
  140.            (Since 4*SQRT(6) is considered symbolic)
  141.  
  142. SCOLCT: Similar to above but does the usual COLCT too. Use this!
  143.         Accepts lists of algebraics too.
  144.         Compare RVAL and SCOLCT with the last example above and you'll see
  145.         the difference.
  146.  
  147. SIMP:
  148.   Simplifies a rational number
  149.   Stack:
  150.         1: r1                        -> 1: r2
  151.   Examples:
  152.         1: '-4/2'               ->      1: -2
  153.         1: 'A*6/3'              ->      1: 'A*6/3' (Try SCOLCT instead)
  154.         1: '(25,24)/(2,3)'      ->      1: '(122,-27)/13'
  155.         1: 4                    ->      1: 4
  156.  
  157. RADD:
  158.   Adds rational numbers.
  159.   Stack:
  160.         2: r2
  161.         1: r1                   ->      1: r3
  162.   Examples:
  163.         2: 4
  164.         1: '1/3'                ->      1: '13/3'
  165.  
  166.         2: '3/2'
  167.         1: '(12,14)/4'          ->      1: '(9,7)/2'
  168.  
  169. RSUB:
  170.   Does NEG, then above.
  171.  
  172. RMUL:
  173.   Multiplies rational numbers
  174.   Stack:
  175.         2: r2
  176.         1: r1                   ->      1: r3
  177.   Examples:
  178.         2: 3
  179.         1: '3/4'                ->      1: '9/4'
  180.  
  181. RDIV
  182.   Divides rational numbers. 
  183.   Stack: 
  184.     This is getting quite obvious, isn't it? 
  185.     
  186. RPOT
  187.   Rational to integer power
  188.   Stack:
  189.         2: r1
  190.         1: n1                   ->      1: r2
  191.   Examples:
  192.         2: '5/6'
  193.         1: -2                   ->      1: '36/25'
  194.  
  195. RINV
  196.   Inverse of rational
  197.  
  198. RABS
  199.   Absolute of rational
  200.   Examples:
  201.         1: '-(5/4)'             ->      1: '5/4'
  202.         1: '1/-6'               ->      1: '1/6'
  203.  
  204. SRE
  205.   Real part of symbolic, number etc
  206.  
  207. SIM 
  208.   Imaginary part of ...
  209.  
  210. SSQRT:
  211.   Calculates square root symbolically.
  212.   Examples:
  213.         1: 1456                 ->      1: '4*SQRT(91)'
  214.         1: (6,8)                ->      1: '(2,1)*SQRT(2)'
  215.         1: 'A+B'                ->      1: 'SQRT(A+B)'
  216.  
  217.  
  218.                               POLY directory:
  219.                               ~~~~~~~~~~~~~~~
  220.  
  221. 5 in front of stack level means rational mode is on.
  222.  
  223. { 1 2 3 }                              = normal form      = x^2+2x+3
  224.  
  225. {{ 1 2 3 }}                            = root form        = (x-1)(x-2)(x-3)
  226.  
  227. { { 1 2 3 } { 1 2 } {{ A B }} } = factored form = (x^2+2x+3)(x+2)(x-A)(x-B)
  228.  
  229. All progs use normal form unless mentioned otherwise.
  230.  
  231.  
  232. PADD:
  233.   Adds polynomials
  234.   Examples:
  235.         2: { 1 2 3 4 }          ->      1: { 1 2 4 6 }
  236.         1:     { 1 2 }
  237.         2: { '1/3' '4/7' }      ->    5 1: { '2/3' '4/3' '25/7' }
  238.         1: { '2/3' 1 3 }                1: { '2/3' 1.333... 3.5714 ...}       
  239.  
  240.  
  241. PMUL:
  242.   Examples:
  243.         2: { 1 2 3 4 }          ->      1: { 1 4 7 10 8 }
  244.         1:     { 1 2 }
  245.         2: { 4 3 2 '2/3' }            5 1: { 6 '25/2' 13 8 '10/3' '2/3' }
  246.         1: { '3/2' 2 1 }                1: { 6  12.5 13 ... }
  247.  
  248. PDIV:
  249.   Examples:
  250.         2: { 4 3 2 '2/3'}       ->    5 2: { '8/3' '-14/9' }
  251.         1: { '3/2' 2 1 }                1: { '22/9' '20/9' }
  252.         meaning
  253.         4x^3+3x^2+2x+2/3                22/9*x+20/9
  254.         ---------------- = 8/3*x-14/9 + -----------
  255.           3/2x^2+2x+1                  3/2x^2+2x+1
  256.  
  257. PMUL, PADD and PDIV accept reals etc too. Example:
  258.  
  259. 2: { 2 3 }       PMUL ->   1: { 6 9 }
  260. 1: 3             PADD ->   1: { 2 6 }
  261.  
  262.  
  263.  
  264. POWP:
  265.   Examples:
  266.         2: { 1 2 '1/2' }        ->    5 1: { 1 6 '27/2' 14 '27/4' '3/2' '1/8 }
  267.         1: 3
  268.         meaning
  269.         ( x^2+2x+1/2 )^3 = x^6+6x^5....
  270.  
  271.  
  272. PDER:
  273.   Derivative of a polynomial
  274.   Examples:
  275.         1: { '3/2' 4 5 }        ->    5 1: { 3 4 } 
  276.  
  277. PRIM:
  278.   Primitive of a polynomial
  279.   Examples:
  280.         1: { '3/2' 4 5 }        ->    5 1: { '1/2' 2 4 0 }
  281.                                         1: { .5 2 4 0 }
  282.  
  283. SROOTS:
  284.   Finds roots of a polynomial
  285.   Rational roots and roots of the form
  286.      A+SQRT(B)
  287.      ---------
  288.          C
  289.   are recognized. Sets flag 5 temporarily.
  290.   Don't use symbolics except rationals with any root finding programs.
  291.   Examples:
  292.         1: { 5 4 }              ->      1: '-4/5'
  293.         1: { 3 (4,5) (1,1) }    ->      2: '(-4,-5)/6+(1,2)/6*SQRT(7)'
  294.                                         1: '.........-...............'
  295.         1: { '4/3' '19/3' '47/2' 51 '250/3' '199/2' '200/3' '109/3' 10 } 
  296.         -> 8: '-1/2'
  297.            7: '-1+(0,1)*SQRT(5)'
  298.            6: '-1-.............'
  299.            5: (-0.23702...,-1.79456...)
  300.            4: -1.52595...
  301.            3: '-1/8+(0,1)/8*SQRT(31)'
  302.            2: '....-................'
  303.            1: (-0.23702...,1.79456...)
  304.  
  305. ROOTS:
  306.   Uses Laguerres method to find the numerical roots of a polynomial.
  307.   ROOTS does ->NUM in the beginning. 
  308.   Examples:
  309.         Look above, the results are just numbers.
  310.  
  311. SDG2:
  312.   Finds symbolic roots of a 2nd (1st) degree polynomial
  313.   Usage is quite obvious.
  314.  
  315. DEG2:
  316.   Look above. Results numbers.
  317.  
  318. New features:
  319.   SROOTS and ROOTS also accept factored forms. Root forms will stay the
  320.   same (I wonder why? :)
  321.  
  322.   Roots will be given in root form. (Funny, eh?)
  323.   IRT makes no difference between root and normal forms (for convenience)
  324.  
  325. PF:
  326.   Partial fraction expansion. Doesn't support 2nd degree form yet.
  327.   2: Normal form
  328.   1: Normal, root or factored form
  329.  
  330.   Result will be in two parts. For multiple roots highest coef comes first.
  331.   Level 2 has the coefs. 
  332.   Level 1 has the roots. 
  333.   
  334.   Try this:
  335.   2: { 1 }            PF ->  2: { '1/(-A+B)' '1/(A-B)' }
  336.   1: {{ A B }}               1: {{ B A }}
  337.  
  338. Meaning:       
  339.                 1       1
  340.               ----     ---
  341.      1        -A+B     A-B
  342. ---------- = ------ + -----
  343. (X-A)(X-B)    X-B      X-A
  344.    
  345. That is: B and A are different numbers!!
  346. This is because all algebraics are compared as strings.
  347.  
  348. PVAL:
  349.   Evaluates a polynomial at a point using Horner's method. NOT suitable
  350.   when using symbolics.
  351.   Examples:
  352.         2: { '1/2' '2/3' '3/4' }        ->    5 1: '481/300'
  353.         1: '4/5'                                1: 1.603333...
  354.  
  355. P->A:
  356.   Similar to above. Use with symbolics. Flag 5 has no effect.
  357.   Examples:
  358.         2: { A B C }                    ->      1: 'AX^2+BX+C'
  359.         1: 'X'
  360.  
  361. DOAL:
  362.   Operates on each coeff. If level 1 isn't a program, poly. is multiplied
  363.   with it. Flag 5 has effect only in that case.
  364.   Examples:
  365.         2: { 1 2 3 }                    ->      1: { 1 .5 .333...}
  366.         1: << INV >> 
  367.         2: { 1 2 3 }                    ->      1: { 1 '1/2' '1/3' }
  368.         1: << RINV >> 
  369.         2: { 1 2 3 }                    ->    5 1: { '1/2' 1 '3/2' }
  370.         1: '1/2'                        ->      1: { .5 1 1.5 }
  371.  
  372. A->P: 
  373.   Transforms an algebraic to a polynomial. Uses A->F (next)
  374.   Examples:
  375.         2: '((x^2+2*x+1)/(x+1) - x^3)^2' ->     1: {1 0 -2 -2 1 2 1 }
  376.         1: 'x'
  377.  
  378. A->F:
  379.   Similar to above. Result is a rational polynomial and is simplified.
  380.   Examples:
  381.         2: '1/x-x'                      ->      2: { -1 0 1 }
  382.         1: 'x'                                  1: { 1 0}
  383.  
  384. Rational polynomial routines have the obvious normal form + denominator can
  385. be in the root form too.
  386.  
  387. SMPF:
  388.   Simplifies a rat. pol.
  389.   Examples:
  390.         2: { 1 2 1 }                    ->      2: { 1 1 }
  391.         1 : { 1 1}                              1: { 1 }
  392.  
  393. FADD:
  394.   Adds ...
  395.  
  396. FMUL
  397.   Multiplies ...
  398.  
  399. FDER:
  400.   Derivative of ...
  401.  
  402. FVAL:
  403.   See PVAL.
  404.  
  405. PGCD:
  406.   Grestest common denominator of 2 polynomials. Used by SMPF.
  407.   Examples:
  408.         2: { 1 2 1 }                    ->      1: { 1 1 }
  409.         1: { 1 1 }
  410.  
  411. PGCD doesn't normalize coefs at any point. This can lead to wrong results
  412. in SMPF if big integer coefs are used.  I will fix this later.
  413.  
  414. STRIP:
  415.   Strips leading zeros
  416.   Examples:
  417.         1: { 0 0 (0,0) 0 1 }            -> 1: { 1 }
  418.         1: { 0 0 }                      -> 1: { 0 } 
  419.  
  420. And last but not least...
  421.  
  422. TOG5:
  423.   Toggles flag 5
  424.