hypertex/pages/INT.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\IntegerXmpTitle}{Integer}
\newcommand{\IntegerXmpNumber}{9.38}
%
% =====================================================================
\begin{page}{IntegerXmpPage}{9.38 Integer}
% =====================================================================
\beginscroll

%
%
%
%
%


%% int.htex
%%
%% Integer examples
%%

\Language{} provides many operations for manipulating arbitrary
precision integers.
In this section we will show some of those that come from \spadtype{Integer}
itself plus some that are implemented in other packages.
More examples of using integers are in the following sections:
\downlink{``\ugIntroNumbersTitle''}{ugIntroNumbersPage} in section \ugIntroNumbersNumber
\downlink{`IntegerNumberTheoryFunctions'}{IntegerNumberTheoryFunctionsXmpPage}\ignore{IntegerNumberTheoryFunctions},
\downlink{`DecimalExpansion'}{DecimalExpansionXmpPage}\ignore{DecimalExpansion},
\downlink{`BinaryExpansion'}{BinaryExpansionXmpPage}\ignore{BinaryExpansion},
\downlink{`HexadecimalExpansion'}{HexadecimalExpansionXmpPage}\ignore{HexadecimalExpansion}, and
\downlink{`RadixExpansion'}{RadixExpansionXmpPage}\ignore{RadixExpansion}.

\beginmenu
    \menudownlink{{9.38.1. Basic Functions}}{ugxIntegerBasicPage}
    \menudownlink{{9.38.2. Primes and Factorization}}{ugxIntegerPrimesPage}
    \menudownlink{{9.38.3. Some Number Theoretic Functions}}{ugxIntegerNTPage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxIntegerBasicTitle}{Basic Functions}
\newcommand{\ugxIntegerBasicNumber}{9.38.1.}
%
% =====================================================================
\begin{page}{ugxIntegerBasicPage}{9.38.1. Basic Functions}
% =====================================================================
\beginscroll

\xtc{
The size of an integer in \Language{} is only limited by the amount of
computer storage you have available.
The usual arithmetic operations are available.
}{
\spadpaste{2^(5678 - 4856 + 2 * 17)}
}

\xtc{
There are a number of ways of working with the sign of an integer.
Let's use this \spad{x} as an example.
}{
\spadpaste{x := -101 \bound{x}}
}
\xtc{
First of all, there is the absolute value function.
}{
\spadpaste{abs(x) \free{x}}
}
\xtc{
The \spadfunFrom{sign}{Integer} operation returns \spad{-1} if its argument
is negative, \spad{0} if zero and \spad{1} if positive.
}{
\spadpaste{sign(x) \free{x}}
}
%
\xtc{
You can determine if an integer is negative in several other ways.
}{
\spadpaste{x < 0 \free{x}}
}
\xtc{
}{
\spadpaste{x <= -1 \free{x}}
}
\xtc{
}{
\spadpaste{negative?(x) \free{x}}
}
%
\xtc{
Similarly, you can find out if it is positive.
}{
\spadpaste{x > 0 \free{x}}
}
\xtc{
}{
\spadpaste{x >= 1 \free{x}}
}
\xtc{
}{
\spadpaste{positive?(x) \free{x}}
}
\xtc{
This is the recommended way of determining whether an integer is zero.
}{
\spadpaste{zero?(x) \free{x}}
}
%

\beginImportant
Use the \spadfunFrom{zero?}{Integer} operation whenever you are testing any
mathematical object for equality with zero.
This is usually more efficient that using \spadop{=} (think of matrices:
it is easier to tell if a matrix is zero by just checking term by term
than constructing another ``zero'' matrix and comparing the two
matrices term by term) and also avoids the problem that \spadop{=} is
usually used for creating equations.
\endImportant

\xtc{
This is the recommended way of determining
whether an integer is equal to one.
}{
\spadpaste{one?(x) \free{x}}
}

\xtc{
This syntax is used to test equality using \spadopFrom{=}{Integer}.
It says that you want a \spadtype{Boolean} (\spad{true} or
\spad{false}) answer rather than an equation.
}{
\spadpaste{(x = -101)@Boolean \free{x}}
}

\xtc{
The operations \spadfunFrom{odd?}{Integer} and
\spadfunFrom{even?}{Integer} determine whether an integer is odd or even,
respectively.
They each return a \spadtype{Boolean} object.
}{
\spadpaste{odd?(x) \free{x}}
}
\xtc{
}{
\spadpaste{even?(x) \free{x}}
}
\xtc{
The operation \spadfunFrom{gcd}{Integer} computes the greatest common divisor of
two integers.
}{
\spadpaste{gcd(56788,43688)}
}
\xtc{
The operation
\spadfunFrom{lcm}{Integer} computes their least common multiple.
}{
\spadpaste{lcm(56788,43688)}
}
\xtc{
To determine the maximum of two integers, use \spadfunFrom{max}{Integer}.
}{
\spadpaste{max(678,567)}
}
\xtc{
To determine the minimum, use \spadfunFrom{min}{Integer}.
}{
\spadpaste{min(678,567)}
}

\xtc{
The \spadfun{reduce} operation is used to extend
binary operations to more than two arguments.
For example, you can use \spadfun{reduce} to find the maximum integer in
a list or compute the least common multiple of all integers in the list.
}{
\spadpaste{reduce(max,[2,45,-89,78,100,-45])}
}
\xtc{
}{
\spadpaste{reduce(min,[2,45,-89,78,100,-45])}
}
\xtc{
}{
\spadpaste{reduce(gcd,[2,45,-89,78,100,-45])}
}
\xtc{
}{
\spadpaste{reduce(lcm,[2,45,-89,78,100,-45])}
}

\xtc{
The infix operator ``/'' is {\it not} used to compute the quotient
of integers.
Rather, it is used to create rational numbers as described in
\downlink{`Fraction'}{FractionXmpPage}\ignore{Fraction}.
}{
\spadpaste{13 / 4}
}
\xtc{
The infix operation \spadfunFrom{quo}{Integer} computes the integer
quotient.
}{
\spadpaste{13 quo 4}
}
\xtc{
The infix operation \spadfunFrom{rem}{Integer} computes the integer
remainder.
}{
\spadpaste{13 rem 4}
}
\xtc{
One integer is evenly divisible by another if the remainder is zero.
The operation \spadfunFrom{exquo}{Integer} can also be used.
See \downlink{``\ugTypesUnionsTitle''}{ugTypesUnionsPage} in Section \ugTypesUnionsNumber\ignore{ugTypesUnions} for an example.
}{
\spadpaste{zero?(167604736446952 rem 2003644)}
}

\xtc{
The operation \spadfunFrom{divide}{Integer} returns a record of the
quotient and remainder and thus is more efficient when both are needed.
}{
\spadpaste{d := divide(13,4) \bound{d}}
}
\xtc{
}{
\spadpaste{d.quotient \free{d}}
}
\xtc{
Records are discussed in detail in \downlink{``\ugTypesRecordsTitle''}{ugTypesRecordsPage} in Section \ugTypesRecordsNumber\ignore{ugTypesRecords}.
}{
\spadpaste{d.remainder \free{d}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxIntegerPrimesTitle}{Primes and Factorization}
\newcommand{\ugxIntegerPrimesNumber}{9.38.2.}
%
% =====================================================================
\begin{page}{ugxIntegerPrimesPage}{9.38.2. Primes and Factorization}
% =====================================================================
\beginscroll

\xtc{
Use the operation \spadfunFrom{factor}{Integer} to factor integers.
It returns an object of type \spadtype{Factored Integer}.
%-% \HDindex{factorization}{ugxIntegerPrimesPage}{9.38.2.}{Primes and Factorization}
See \downlink{`Factored'}{FactoredXmpPage}\ignore{Factored} for a discussion of the
manipulation of factored objects.
}{
\spadpaste{factor 102400}
}

\xtc{
The operation \spadfunFrom{prime?}{Integer} returns \spad{true} or \spad{false} depending
on whether its argument is a prime.
%-% \HDindex{prime}{ugxIntegerPrimesPage}{9.38.2.}{Primes and Factorization}
}{
\spadpaste{prime? 7}
}
\xtc{
}{
\spadpaste{prime? 8}
}
\xtc{
The operation \spadfunFrom{nextPrime}{IntegerPrimesPackage} returns the
least prime number greater than its argument.
}{
\spadpaste{nextPrime 100}
}
\xtc{
The operation
\spadfunFrom{prevPrime}{IntegerPrimesPackage} returns the greatest prime
number less than its argument.
}{
\spadpaste{prevPrime 100}
}
\xtc{
To compute all primes between two integers (inclusively), use the
operation \spadfunFrom{primes}{IntegerPrimesPackage}.
}{
\spadpaste{primes(100,175)}
}
\xtc{
You might sometimes want to see the factorization of an integer
when it is considered a {\it Gaussian integer}.
%-% \HDindex{Gaussian integer}{ugxIntegerPrimesPage}{9.38.2.}{Primes and Factorization}
See \downlink{`Complex'}{ComplexXmpPage}\ignore{Complex} for more details.
}{
\spadpaste{factor(2 :: Complex Integer)}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxIntegerNTTitle}{Some Number Theoretic Functions}
\newcommand{\ugxIntegerNTNumber}{9.38.3.}
%
% =====================================================================
\begin{page}{ugxIntegerNTPage}{9.38.3. Some Number Theoretic Functions}
% =====================================================================
\beginscroll

\Language{} provides several number theoretic operations for integers.
More examples are in \downlink{`IntegerNumberTheoryFunctions'}{IntegerNumberTheoryFunctionsXmpPage}\ignore{IntegerNumberTheoryFunctions}.

\xtc{
The operation \spadfunFrom{fibonacci}{IntegerNumberTheoryFunctions}
computes the Fibonacci numbers.
%-% \HDindex{Fibonacci numbers}{ugxIntegerNTPage}{9.38.3.}{Some Number Theoretic Functions}
The algorithm has running time
O(\spad{log(n)^3}) for argument \spad{n}.
}{
\spadpaste{[fibonacci(k) for k in 0..]}
}
\xtc{
The operation \spadfunFrom{legendre}{IntegerNumberTheoryFunctions}
computes the Legendre symbol for its two integer arguments where the
second one is prime.
If you know the second argument to be prime, use
\spadfunFrom{jacobi}{IntegerNumberTheoryFunctions} instead where no check
is made.
}{
\spadpaste{[legendre(i,11) for i in 0..10]}
}
\xtc{
The operation \spadfunFrom{jacobi}{IntegerNumberTheoryFunctions} computes
the Jacobi symbol for its two integer arguments.
%-% \HDindex{Jacobi symbol}{ugxIntegerNTPage}{9.38.3.}{Some Number Theoretic Functions}
By convention, \spad{0} is returned if the greatest common divisor of the
numerator and denominator is not \spad{1}.
}{
\spadpaste{[jacobi(i,15) for i in 0..9]}
}
\xtc{
The operation \spadfunFrom{eulerPhi}{IntegerNumberTheoryFunctions} computes
%-% \HDindex{Euler!phi function@{$\varphi$ function}}{ugxIntegerNTPage}{9.38.3.}{Some Number Theoretic Functions}
the values of Euler's phi-function where
\spad{phi(n)}
equals the number of positive integers
less than or equal to \spad{n} that are relatively prime to
the positive integer \spad{n}.
%-% \HDindex{phi@{$\varphi$}}{ugxIntegerNTPage}{9.38.3.}{Some Number Theoretic Functions}
}{
\spadpaste{[eulerPhi i for i in 1..]}
}
\xtc{
The operation \spadfunFrom{moebiusMu}{IntegerNumberTheoryFunctions}
%-% \HDindex{mu@{$\mu$}}{ugxIntegerNTPage}{9.38.3.}{Some Number Theoretic Functions}
computes the Moebius mu function.
%-% \HDindex{Moebius@{M\"{o}bius}!mu function@{$\mu$ function}}{ugxIntegerNTPage}{9.38.3.}{Some Number Theoretic Functions}
}{
\spadpaste{[moebiusMu i for i in 1..]}
}

\xtc{
Although they have somewhat limited utility, \Language{} provides
%-% \HDindex{Roman numerals}{ugxIntegerNTPage}{9.38.3.}{Some Number Theoretic Functions}
Roman numerals.
}{
\spadpaste{a := roman(78) \bound{a}}
}
\xtc{
}{
\spadpaste{b := roman(87) \bound{b}}
}
\xtc{
}{
\spadpaste{a + b \free{a}\free{b}}
}
\xtc{
}{
\spadpaste{a * b \free{a}\free{b}}
}
\xtc{
}{
\spadpaste{b rem a \free{a}\free{b}}
}
\endscroll
\autobuttons
\end{page}
%