basis/math/polynomials/polynomials-docs.factor

   1 USING: help.markup help.syntax kernel math sequences ;
   2 IN: math.polynomials
   3
   4 ARTICLE: "polynomials" "Polynomials"
   5 "A polynomial is a vector with the highest powers on the right:"
   6 { $code "{ 1 1 0 1 } -> 1 + x + x^3" "{ } -> 0" }
   7 "Numerous words are defined to help with polynomial arithmetic:"
   8 { $subsections
   9     p=
  10     p+
  11     p-
  12     p*
  13     p-sq
  14     p^
  15     powers
  16     n*p
  17     p/mod
  18     pgcd
  19     polyval
  20     pdiff
  21     pextend-conv
  22     ptrim
  23     2ptrim
  24 } ;
  25
  26 ABOUT: "polynomials"
  27
  28 HELP: powers
  29 { $values { "n" integer } { "x" number } { "seq" sequence } }
  30 { $description "Output a sequence having " { $snippet "n" } " elements in the format: " { $snippet "{ 1 x x^2 x^3 ... }" } "." }
  31 { $examples { $example "USING: math.polynomials prettyprint ;" "4 2 powers ." "{ 1 2 4 8 }" } } ;
  32
  33 HELP: p=
  34 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "?" boolean } }
  35 { $description "Tests if two polynomials are equal." }
  36 { $examples { $example "USING: math.polynomials prettyprint ;" "{ 0 1 } { 0 1 0 } p= ." "t" } } ;
  37
  38 HELP: ptrim
  39 { $values { "p" "a polynomial" } { "q" "a polynomial" } }
  40 { $description "Trims excess zeros from a polynomial." }
  41 { $examples { $example "USING: math.polynomials prettyprint ;" "{ 0 1 0 0 } ptrim ." "{ 0 1 }" } } ;
  42
  43 HELP: 2ptrim
  44 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "p'" "a polynomial" } { "q'" "a polynomial" } }
  45 { $description "Trims excess zeros from two polynomials." }
  46 { $examples { $example "USING: kernel math.polynomials prettyprint ;" "{ 0 1 0 0 } { 1 0 0 } 2ptrim [ . ] bi@" "{ 0 1 }\n{ 1 }" } } ;
  47
  48 HELP: p+
  49 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "r" "a polynomial" } }
  50 { $description "Adds " { $snippet "p" } " and " { $snippet "q" } " component-wise." }
  51 { $examples { $example "USING: math.polynomials prettyprint ;" "{ 1 0 1 } { 0 1 } p+ ." "{ 1 1 1 }" } } ;
  52
  53 HELP: p-
  54 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "r" "a polynomial" } }
  55 { $description "Subtracts " { $snippet "q" } " from " { $snippet "p" } " component-wise." }
  56 { $examples { $example "USING: math.polynomials prettyprint ;" "{ 1 1 1 } { 0 1 } p- ." "{ 1 0 1 }" } } ;
  57
  58 HELP: n*p
  59 { $values { "n" number } { "v" "a polynomial" } { "w" "a polynomial" } }
  60 { $description "Multiplies each element of " { $snippet "p" } " by " { $snippet "n" } "." }
  61 { $examples { $example "USING: math.polynomials prettyprint ;" "4 { 3 0 1 } n*p ." "{ 12 0 4 }" } } ;
  62
  63 HELP: pextend-conv
  64 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "p'" "a polynomial" } { "q'" "a polynomial" } }
  65 { $description "Convolution, extending to " { $snippet "p_m + q_n - 1" } "." }
  66 { $examples { $example "USING: kernel math.polynomials prettyprint ;" "{ 1 0 1 } { 0 1 } pextend-conv [ . ] bi@" "{ 1 0 1 0 }\n{ 0 1 0 0 }" } } ;
  67
  68 HELP: p*
  69 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "r" "a polynomial" } }
  70 { $description "Multiplies two polynomials." }
  71 { $examples { $example "USING: math.polynomials prettyprint ;" "{ 1 2 3 0 0 0 } { 1 2 0 0 } p* ." "{ 1 4 7 6 0 0 0 0 0 }" } } ;
  72
  73 HELP: p-sq
  74 { $values { "p" "a polynomial" } { "p^2" "a polynomial" } }
  75 { $description "Squares a polynomial." }
  76 { $examples { $example "USING: math.polynomials prettyprint ;" "{ 1 2 0 } p-sq ." "{ 1 4 4 0 0 }" } } ;
  77
  78 HELP: p^
  79 { $values { "p" "a polynomial" } { "n" number } { "p^n" "a polynomial" } }
  80 { $description "Computes " { $snippet "p" } " to the power of " { $snippet "n" } "." }
  81 { $examples { $example "USING: math.polynomials prettyprint ;" "{ 1 2 0 } 3 p^ ." "{ 1 6 12 8 0 0 0 }" } } ;
  82
  83 HELP: p/mod
  84 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "z" "a polynomial" } { "w" "a polynomial" } }
  85 { $description "Computes to quotient " { $snippet "z" } " and remainder " { $snippet "w" } " of dividing " { $snippet "p" } " by " { $snippet "q" } "." }
  86 { $examples { $example "USING: kernel math.polynomials prettyprint ;" "{ 1 1 1 1 } { 3 1 } p/mod [ . ] bi@" "V{ 7 -2 1 }\nV{ -20 0 0 }" } } ;
  87
  88 HELP: pgcd
  89 { $values { "p" "a polynomial" } { "q" "a polynomial" } { "a" "a polynomial" } { "d" "a polynomial" } }
  90 { $description "Computes the greatest common divisor " { $snippet "d" } " of " { $snippet "p" } " and " { $snippet "q" } ", and another value " { $snippet "a" } " satisfying:" { $code "a*q = d mod p" } }
  91 { $notes "GCD in the case of polynomials is a monic polynomial of the highest possible degree that divides into both " { $snippet "p" } " and " { $snippet "q" } "." }
  92 { $examples
  93     { $example "USING: kernel math.polynomials prettyprint ;"
  94                "{ 1 1 1 1 } { 1 1 } pgcd [ . ] bi@"
  95                "{ 0 0 }\n{ 1 1 }"
  96     }
  97 } ;
  98
  99 HELP: pdiff
 100 { $values { "p" "a polynomial" } { "p'" "a polynomial" } }
 101 { $description "Finds the derivative of " { $snippet "p" } "." } ;
 102
 103 HELP: polyval
 104 { $values { "x" number } { "p" "a polynomial" } { "p[x]" number } }
 105 { $description "Evaluate " { $snippet "p" } " with the input " { $snippet "x" } "." }
 106 { $examples { $example "USING: math.polynomials prettyprint ;" "2 { 1 0 1 } polyval ." "5" } } ;
 107
 108 HELP: polyval*
 109 { $values { "p" "a literal polynomial" } }
 110 { $description "Macro version of " { $link polyval } ". Evaluates the literal polynomial " { $snippet "p" } " at the value off the top of the stack." }
 111 { $examples { $example "USING: math.polynomials prettyprint ;" "2 { 1 0 1 } polyval* ." "5" } } ;
 112
 113 { polyval polyval* } related-words