"Fossies" - the Fresh Open Source Software Archive

Member "pari-2.13.1/src/functions/operators/HEADER" (14 Jan 2021, 14144 Bytes) of package /linux/misc/pari-2.13.1.tar.gz:


As a special service "Fossies" has tried to format the requested text file into HTML format (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "HEADER": 2.13.0_vs_2.13.1.

    1 Function: _header_operators
    2 Class: header
    3 Section: operators
    4 Doc:
    5  \section{Standard monadic or dyadic operators}
    6 
    7  \subsec{Boolean operators}\sidx{Boolean operators}
    8 
    9  Any nonzero value is interpreted as \var{true} and any zero as \var{false}
   10  (this includes empty vectors or matrices). The standard boolean operators
   11  \kbd{||} (\idx{inclusive or}), \kbd{\&\&} (\idx{and})\sidx{or} and \kbd{!}
   12  in prefix notation (\idx{not}) are available.
   13  Their value is $1$ (true) or $0$ (false):
   14  \bprog
   15  ? a && b  \\ 1 iff a and b are nonzero
   16  ? a || b  \\ 1 iff a or b is nonzero
   17  ? !a      \\ 1 iff a is zero
   18  @eprog
   19 
   20  \subsec{Comparison}
   21  The standard real \idx{comparison operators} \kbd{<=}, \kbd{<}, \kbd{>=},
   22  \kbd{>}, are available in GP. The result is 1 if the comparison is true, 0
   23  if it is false. These operators allow to compare integers (\typ{INT}),
   24  rational (\typ{FRAC}) or real (\typ{REAL}) numbers,
   25  real quadratic numbers (\typ{QUAD} of positive discriminant) and infinity
   26  (\kbd{oo}, \typ{INFINITY}).
   27 
   28  By extension, two character strings (\typ{STR}) are compared using
   29  the standard lexicographic order. Comparing a string to an object of a
   30  different type raises an exception. See also the \tet{cmp} universal
   31  comparison function.
   32 
   33  \subsec{Equality}
   34  Two operators allow to test for equality: \kbd{==} (equality up to type
   35  coercion) and \kbd{===} (identity). The result is $1$ if equality is decided,
   36  else $0$.
   37 
   38  The operator \kbd{===} is strict: objects of different type or length are
   39  never identical, polynomials in different variables are never identical,
   40  even if constant. On the contrary, \kbd{==} is very liberal: $a~\kbd{==}~b$
   41  decides whether there is a natural map sending $a$ to the domain of $b$
   42  or sending $b$ to the domain of $a$, such that the comparison makes sense
   43  and equality holds. For instance
   44  \bprog
   45  ? 4 == Mod(1,3) \\ equal
   46  %1 = 1
   47  ? 4 === Mod(1,3) \\ but not identical
   48  %2 = 0
   49 
   50  ? 'x == 'y   \\ not equal (nonconstant and different variables)
   51  %3 = 0
   52  ? Pol(0,'x) == Pol(0,'y)  \\ equal (constant: ignore variable)
   53  %4 = 1
   54  ? Pol(0,'x) == Pol(0,'y)  \\ not identical
   55  %5 = 0
   56 
   57  ? 0 == Pol(0) \\ equal
   58  %6 = 1
   59  ? [0] == 0     \\ equal
   60  %7 = 1
   61  ? [0, 0] == 0  \\ equal
   62  %8 = 1
   63  ? [0] == [0,0] \\ not equal
   64  %9 = 1
   65  @eprog\noindent In particular \kbd{==} is not transitive in general; it is
   66  transitive when used to compare objects known to have the same type. The
   67  operator \kbd{===} is transitive. The \kbd{==} operator allows two
   68  equivalent negated forms: \kbd{!=} or \kbd{<>}; there is no negated form for
   69  \kbd{===}.
   70 
   71  Do not mistake \kbd{=} for \kbd{==}: it is the assignment statement.
   72 
   73  \subseckbd{+$/$-} The expressions \kbd{+}$x$ and \kbd{-}$x$ refer
   74  to monadic operators: the first does nothing, the second negates $x$.
   75 
   76  The library syntax is \fun{GEN}{gneg}{GEN x} for \kbd{-}$x$.
   77 
   78  \subseckbd{+} The expression $x$ \kbd{+} $y$ is the \idx{sum} of $x$ and $y$.
   79  Addition between a scalar type $x$ and a \typ{COL} or \typ{MAT} $y$ returns
   80  respectively $[y[1] + x, y[2],\dots]$ and $y + x \text{Id}$. Other additions
   81  between a scalar type and a vector or a matrix, or between vector/matrices of
   82  incompatible sizes are forbidden.
   83 
   84  The library syntax is \fun{GEN}{gadd}{GEN x, GEN y}.
   85 
   86  \subseckbd{-} The expression $x$ \kbd{-} $y$ is the \idx{difference} of $x$
   87  and $y$. Subtraction between a scalar type $x$ and a \typ{COL} or \typ{MAT}
   88  $y$ returns respectively $[y[1] - x, y[2],\dots]$ and $y - x \text{Id}$.
   89  Other subtractions between a scalar type and a vector or a matrix, or
   90  between vector/matrices of incompatible sizes are forbidden.
   91 
   92  The library syntax is \fun{GEN}{gsub}{GEN x, GEN y} for $x$ \kbd{-} $y$.
   93 
   94  \subseckbd{*} The expression $x$ \kbd{*} $y$ is the \idx{product} of $x$
   95  and $y$. Among the prominent impossibilities are multiplication between
   96  vector/matrices of incompatible sizes, between a \typ{INTMOD} or \typ{PADIC}
   97  Restricted to scalars, \kbd{*} is commutative; because of vector and matrix
   98  operations, it is not commutative in general.
   99 
  100  Multiplication between two \typ{VEC}s or two \typ{COL}s is not
  101  allowed; to take the \idx{scalar product} of two vectors of the same length,
  102  transpose one of the vectors (using the operator \kbd{\til} or the function
  103  \kbd{mattranspose}, see \secref{se:linear_algebra}) and multiply a line vector
  104  by a column vector:
  105  \bprog
  106  ? a = [1,2,3];
  107  ? a * a
  108    ***   at top-level: a*a
  109    ***                  ^--
  110    *** _*_: forbidden multiplication t_VEC * t_VEC.
  111  ? a * a~
  112  %2 = 14
  113  @eprog
  114 
  115  If $x,y$ are binary quadratic forms, compose them; see also
  116  \kbd{qfbnucomp} and \kbd{qfbnupow}. If $x,y$ are \typ{VECSMALL} of the same
  117  length, understand them as permutations and compose them.
  118 
  119  The library syntax is \fun{GEN}{gmul}{GEN x, GEN y} for $x$ \kbd{*} $y$.
  120  Also available is \fun{GEN}{gsqr}{GEN x} for $x$ \kbd{*} $x$.
  121 
  122  \subseckbd{/} The expression $x$ \kbd{/} $y$ is the \idx{quotient} of $x$
  123  and $y$. In addition to the impossibilities for multiplication, note that if
  124  the divisor is a matrix, it must be an invertible square matrix, and in that
  125  case the result is $x*y^{-1}$. Furthermore note that the result is as exact
  126  as possible: in particular, division of two integers always gives a rational
  127  number (which may be an integer if the quotient is exact) and \emph{not} the
  128  Euclidean quotient (see $x$ \kbd{\bs} $y$ for that), and similarly the
  129  quotient of two polynomials is a rational function in general. To obtain the
  130  approximate real value of the quotient of two integers, add \kbd{0.} to the
  131  result; to obtain the approximate $p$-adic value of the quotient of two
  132  integers, add \kbd{O(p\pow k)} to the result; finally, to obtain the
  133  \idx{Taylor series} expansion of the quotient of two polynomials, add
  134  \kbd{O(X\pow k)} to the result or use the \kbd{taylor} function
  135  (see \secref{se:taylor}). \label{se:gdiv}
  136 
  137  The library syntax is \fun{GEN}{gdiv}{GEN x, GEN y} for $x$ \kbd{/} $y$.
  138 
  139  \subseckbd{\bs} The expression \kbd{$x$ \bs\ $y$} is the
  140  \idx{Euclidean quotient} of $x$ and $y$. If $y$ is a real scalar, this is
  141  defined as \kbd{floor($x$/$y$)} if $y > 0$, and \kbd{ceil($x$/$y$)} if
  142  $y < 0$ and the division is not exact. Hence the remainder
  143  \kbd{$x$ - ($x$\bs$y$)*$y$} is in $[0, |y|[$.
  144 
  145  Note that when $y$ is an integer and $x$ a polynomial, $y$ is first promoted
  146  to a polynomial of degree $0$. When $x$ is a vector or matrix, the operator
  147  is applied componentwise.
  148 
  149  The library syntax is \fun{GEN}{gdivent}{GEN x, GEN y}
  150  for $x$ \kbd{\bs} $y$.
  151 
  152  \subseckbd{\bs/} The expression $x$ \b{/} $y$ evaluates to the rounded
  153  \idx{Euclidean quotient} of $x$ and $y$. This is the same as \kbd{$x$ \bs\ $y$}
  154  except for scalar division: the quotient is such that the corresponding
  155  remainder is smallest in absolute value and in case of a tie the quotient
  156  closest to $+\infty$ is chosen (hence the remainder would belong to
  157  $[{-}|y|/2, |y|/2[$).
  158 
  159  When $x$ is a vector or matrix, the operator is applied componentwise.
  160 
  161  The library syntax is \fun{GEN}{gdivround}{GEN x, GEN y}
  162  for $x$ \b{/} $y$.
  163 
  164  \subseckbd{\%} The expression \kbd{$x$ \% $y$} evaluates to the modular
  165  \idx{Euclidean remainder} of $x$ and $y$, which we now define. When $x$ or $y$
  166  is a nonintegral real number, \kbd{$x$\%$y$} is defined as
  167  \kbd{$x$ - ($x$\bs$y$)*$y$}. Otherwise, if $y$ is an integer, this is
  168  the smallest
  169  nonnegative integer congruent to $x$ modulo $y$. (This actually coincides
  170  with the previous definition if and only if $x$ is an integer.) If $y$ is a
  171  polynomial, this is the polynomial of smallest degree congruent to
  172  $x$ modulo $y$. For instance:
  173  \bprog
  174  ? (1/2) % 3
  175  %1 = 2
  176  ? 0.5 % 3
  177  %2 = 0.5000000000000000000000000000
  178  ? (1/2) % 3.0
  179  %3 = 1/2
  180  @eprog
  181  Note that when $y$ is an integer and $x$ a polynomial, $y$ is first promoted
  182  to a polynomial of degree $0$. When $x$ is a vector or matrix, the operator
  183  is applied componentwise.
  184 
  185  The library syntax is \fun{GEN}{gmod}{GEN x, GEN y}
  186  for $x$ \kbd{\%} $y$.
  187 
  188  \subseckbd{\var{op}=} When \var{op} is a binary arithmetic operator among
  189  \kbd{+}, \kbd{-}, \kbd{\%}, \kbd{/}, \kbd{\bs} or \kbd{\bs/}, the construct
  190  $x \var{op}= y$ is a shortcut for $x = x \var{op} y$.
  191  \bprog
  192  ? v[1] += 10  \\ increment v[1] by 10
  193  ? a /= 2 \\ divide a by 2
  194  @eprog
  195 
  196  \subseckbd{++} \kbd{$x$++} is a shortcut for \kbd{$x$ = $x$ + 1}.
  197 
  198  \subseckbd{--} \kbd{$x$--} is a shortcut for \kbd{$x$ = $x$ - 1}.
  199 
  200  \subseckbd{\pow} The expression $x\hbox{\kbd{\pow}}n$ is \idx{powering}.
  201 
  202  \item If the exponent $n$ is an integer, then exact operations are performed
  203  using binary (left-shift) powering techniques. By definition, $x^0$ is
  204  (an empty product interpreted as) an exact $1$ in the underlying prime
  205  ring:
  206  \bprog
  207  ? 0.0 ^ 0
  208  %1 = 1
  209  ? (1 + O(2^3)) ^ 0
  210  %2 = 1
  211  ? (1 + O(x)) ^ 0
  212  %3 = 1
  213  ? Mod(2,4)^0
  214  %4 = Mod(1,4)
  215  ? Mod(x,x^2)^0
  216  %5 = Mod(1, x^2)
  217  @eprog\noindent
  218  If $x$ is a $p$-adic number, its precision will increase if $v_p(n) > 0$ and
  219  $n \neq 0$. Powering a binary quadratic form (types \typ{QFI} and
  220  \typ{QFR}) returns a representative of the class, which is reduced if the
  221  input was. (In particular, \kbd{x \pow 1} returns $x$ itself, whether it is
  222  reduced or not.)
  223 
  224  PARI rewrites the multiplication $x * x$ of two \emph{identical}
  225  objects as $x^2$. Here, identical means the operands are reference the same
  226  chunk of memory; no equality test is performed. This is no longer true when
  227  more than two arguments are involved.
  228  \bprog
  229  ? a = 1 + O(2); b = a;
  230  ? a * a  \\ = a^2, precision increases
  231  %2 = 1 + O(2^3)
  232  ? a * b \\ not rewritten as a^2
  233  %3 = 1 + O(2)
  234  ? a*a*a \\ not rewritten as a^3
  235  %4 = 1 + O(2)
  236  @eprog
  237 
  238  \item If the exponent is a rational number $p/q$ the behaviour depends
  239  on~$x$. If $x$ is a complex number, return $\exp(n \log x)$ (principal
  240  branch), in an exact form if possible:
  241  \bprog
  242  ? 4^(1/2)  \\ 4 being a square, this is exact
  243  %1 = 2
  244  ? 2^(1/2)  \\ now inexact
  245  %2 = 1.4142135623730950488016887242096980786
  246  ? (-1/4)^(1/2) \\ exact again
  247  %3 = 1/2*I
  248  ? (-1)^(1/3)
  249  %4 = 0.500...+ 0.866...*I
  250  @eprog\noindent Note that even though $-1$ is an exact cube root of $-1$,
  251  it is not $\exp(\log(-1)/3)$; the latter is returned.
  252 
  253  Otherwise return a solution $y$ of $y^q = x^p$ if it exists; beware that
  254  this is defined up to $q$-th roots of 1 in the base field. Intmods modulo
  255  composite numbers are not supported.
  256  \bprog
  257  ? Mod(7,19)^(1/2)
  258  %1 = Mod(11, 19) \\ is any square root
  259  ? sqrt(Mod(7,19))
  260  %2 = Mod(8, 19)  \\ is the smallest square root
  261  ? Mod(1,4)^(1/2)
  262   ***   at top-level: Mod(1,4)^(1/2)
  263   ***                         ^------
  264   *** _^_: not a prime number in gpow: 4.
  265  @eprog
  266 
  267  \item If the exponent is a negative integer or rational number,
  268  an \idx{inverse} must be computed. For noninvertible \typ{INTMOD} $x$, this
  269  will fail and (for $n$ an integer) implicitly exhibit a factor of the modulus:
  270  \bprog
  271  ? Mod(4,6)^(-1)
  272    ***   at top-level: Mod(4,6)^(-1)
  273    ***                         ^-----
  274    *** _^_: impossible inverse modulo: Mod(2, 6).
  275  @eprog\noindent
  276  Here, a factor 2 is obtained directly. In general, take the gcd of the
  277  representative and the modulus. This is most useful when performing
  278  complicated operations modulo an integer $N$ whose factorization is
  279  unknown. Either the computation succeeds and all is well, or a factor $d$
  280  is discovered and the computation may be restarted modulo $d$ or $N/d$.
  281 
  282  For noninvertible \typ{POLMOD} $x$, the behavior is the same:
  283  \bprog
  284  ? Mod(x^2, x^3-x)^(-1)
  285    ***   at top-level: Mod(x^2,x^3-x)^(-1)
  286    ***                               ^-----
  287    *** _^_: impossible inverse in RgXQ_inv: Mod(x^2, x^3 - x).
  288  @eprog\noindent Note that the underlying algorihm (subresultant) assumes
  289  that the base ring is a domain:
  290  \bprog
  291  ? a = Mod(3*y^3+1, 4); b = y^6+y^5+y^4+y^3+y^2+y+1; c = Mod(a,b);
  292  ? c^(-1)
  293    ***   at top-level: Mod(a,b)^(-1)
  294    ***                         ^-----
  295    *** _^_: impossible inverse modulo: Mod(2, 4).
  296  @eprog\noindent
  297  In fact $c$ is invertible, but $\Z/4\Z$ is not a domain and the algorithm
  298  fails. It is possible for the algorithm to succeed in such situations
  299  and any returned result will be correct, but chances are that an error
  300  will occur first. In this specific case, one should work with $2$-adics.
  301  In general, one can also try the following approach
  302  \bprog
  303  ? inversemod(a, b) =
  304  { my(m, v = variable(b));
  305    m = polsylvestermatrix(polrecip(a), polrecip(b));
  306    m = matinverseimage(m, matid(#m)[,1]);
  307    Polrev(m[1..poldegree(b)], v);
  308  }
  309  ? inversemod(a,b)
  310  %2 = Mod(2,4)*y^5 + Mod(3,4)*y^3 + Mod(1,4)*y^2 + Mod(3,4)*y + Mod(2,4)
  311  @eprog\noindent
  312  This is not guaranteed to work either since \kbd{matinverseimage} must also
  313  invert pivots. See \secref{se:linear_algebra}.
  314 
  315  For a \typ{MAT} $x$, the matrix is expected to be square and invertible, except
  316  in the special case \kbd{x\pow(-1)} which returns a left inverse if one exists
  317  (rectangular $x$ with full column rank).
  318  \bprog
  319  ? x = Mat([1;2])
  320  %1 =
  321  [1]
  322 
  323  [2]
  324 
  325  ? x^(-1)
  326  %2 =
  327  [1 0]
  328  @eprog
  329 
  330  \item Finally, if the exponent $n$ is not an rational number, powering is
  331  treated as the transcendental function $\exp(n\log x)$, although it will be
  332  more precise than the latter when $n$ and $x$ are exact:
  333  \bprog
  334  ? s = 1/2 + 10^14 * I
  335  ? localprec(200); z = 2^s  \\ for reference
  336  ? exponent(2^s - z)
  337  %3 = -127  \\ perfect
  338  ? exponent(exp(s * log(2)) - z)
  339  %4 = -84 \\ not so good
  340  @eprog\noindent The second computation is less precise because $\log(2)$ is
  341  first computed to $38$ decimal digits, then multiplied by $s$, which has a
  342  huge imaginary part amplifying the error.
  343 
  344  In this case, $x \mapsto x^n$ is treated as a transcendental function and
  345  and in particular acts
  346  componentwise on vector or matrices, even square matrices ! (See
  347  \secref{se:trans}.) If $x$ is $0$ and $n$ is an inexact $0$, this will raise
  348  an exception:
  349  \bprog
  350  ? 4 ^ 1.0
  351  %1 = 4.0000000000000000000000000000000000000
  352  ? 0^ 0.0
  353   ***   at top-level: 0^0.0
  354   ***                  ^----
  355   *** _^_: domain error in gpow(0,n): n <= 0
  356  @eprog
  357 
  358  The library syntax is \fun{GEN}{gpow}{GEN x, GEN n, long prec}
  359  for $x\hbox{\kbd{\pow}}n$.