|
Magma includes both the Karatsuba algorithm and the Schönhage-Strassen
FFT-based algorithm for the multiplication of integers
([AHU74, Chap. 7], [vzGG99, Sec. 8.3]).
The crossover
point (where the FFT method beats the Karatsuba method) is currently
215 bits (approx. 10000 decimal digits) on Sun SPARC workstations
and 217 bits (approx. 40000 decimal digits) on Digital Alpha
workstations. Assembler macros are used for critical operations and
64-bit operations are used on DEC-Alpha machines.
Magma also contains an asymptotically-fast integer (and polynomial)
division algorithm which reduces division to multiplication with a
constant scale factor that is in the practical range. Thus division of
integers and polynomials are based on the Karatsuba and
Schönhage-Strassen (FFT) methods when applicable. The crossover point
for integer division (when the new method outperforms the classical
method) is currently at the point of dividing a 212 bit
(approx. 1200 decimal digit) integer by a 211 (approx. 600 decimal
digit) integer on Sun SPARC workstations.
+ n : RngIntElt -> RngIntElt
- n : RngIntElt -> RngIntElt
m + n : RngIntElt, RngIntElt -> RngIntElt
m - n : RngIntElt, RngIntElt -> RngIntElt
m * n : RngIntElt, RngIntElt -> RngIntElt
n ^ k : RngIntElt, RngIntElt -> RngIntElt
m / n : RngIntElt, RngIntElt -> RngIntElt
m +:= n : RngIntElt, RngIntElt -> RngIntElt
m -:= n : RngIntElt, RngIntElt -> RngIntElt
m *:= n : RngIntElt, RngIntElt -> RngIntElt
m /:= n : RngIntElt, RngIntElt -> RngIntElt
m ^:= k : RngIntElt, RngIntElt -> RngIntElt
n div:= m : RngIntElt, RngIntElt -> RngIntElt
n mod:= m : RngIntElt, RngIntElt -> RngIntElt
The quotient q of the division with remainder n=qm + r, where 0≤r<m
or m<r≤0 (depending on the sign of m), for integers n and m != 0.
The remainder r of the division with remainder n=qm + r, where 0≤r<m
or m<r≤0 (depending on the sign of m), for integers n and m != 0.
Assuming that the integer n is exactly divisible by the integer d,
return the exact quotient of n by d (as an integer). An error
results if d does not divide n exactly.
The following functions use bit operations on the internal representation,
so are in general quicker than using the usual arithmetic operators.
Given integers n and b, with b≥0, return n x 2b.
Given integers n and b, with b≥0, return n div 2b.
Given integers n and b, with b≥0, return n mod 2b (so the
result is always non-negative).
The following functions apply logical operators to integers by
interpreting them as sequences of bits. Note that the (implicitly
infinite) 2-adic expansion of these integers is used, which enables
consistent handling of negative integers. In particular, the
BitwiseNot of a non-negative integer will be negative, and
vice versa.
The integer whose 2-adic representation is the bitwise `not' of the
2-adic representation of x.
The integer whose 2-adic representation is the bitwise `and' of the
2-adic representations of x and y.
The integer whose 2-adic representation is the bitwise `or' of the
2-adic representations of x and y.
The integer whose 2-adic representation is the bitwise `xor' of the
2-adic representations of x and y.
m eq n : RngIntElt, RngIntElt -> BoolElt
m ne n : RngIntElt, RngIntElt -> BoolElt
n in R : RngIntElt, Rng -> BoolElt
n notin R : RngIntElt, Rng -> BoolElt
Parent(n) : RngIntElt -> RngInt
Category(n) : RngIntElt -> Cat
IsZero(n) : RngIntElt -> BoolElt
IsOne(n) : RngIntElt -> BoolElt
IsMinusOne(n) : RngIntElt -> BoolElt
IsNilpotent(n) : RngIntElt -> BoolElt
IsIdempotent(n) : RngIntElt -> BoolElt
IsUnit(n) : RngIntElt -> BoolElt
IsZeroDivisor(n) : RngIntElt -> BoolElt
IsRegular(n) : RngInt -> BoolElt
IsIrreducible(n) : RngIntElt -> BoolElt
IsPrime(n) : RngIntElt -> BoolElt
Returns true if the integer n is even, otherwise false.
Returns true if the integer n is odd, otherwise false.
Returns true if and only if the integer n is divisible by the integer d;
if true, the quotient of n by d is also returned.
Returns true if the non-negative integer n is the square of an integer,
false otherwise. If n is a square, its positive square root is
also returned.
Returns true if the non-zero integer n is not divisible by the square of any
prime, false otherwise.
If the integer n>1 is a power n=bk of an integer b, with k>1,
this function returns true, the minimal positive b and its associated k;
if it is not such integer power the function returns false.
If the integer n>1 is k-th power, with k>1, of some integer
b, so that n=bk, this function returns true, and b;
if it is not a k-th integer power the function returns false.
Proof: BoolElt Default: true
Returns true if and only if the integer n is a prime.
A rigorous primality test
which returns a proven result will be used unless the parameter Proof
is false. The reader is referred to Section Primes and Primality Testing
for a complete description of this function.
In this example we find some 10-digit primes that are congruent to 3 modulo 4
such that (p - 1)/2 is also prime.
> { p : p in [10^10+3..10^10+1000 by 4] |
> IsPrime(p) and IsPrime((p-1) div 2) };
{ 10000000259, 10000000643 }
Returns true if and only if a is integral, which is of course
true for every integer n.
Returns true if n fits in a single word in the internal representation
of integers in Magma, that is, if |n|<230, false otherwise.
m gt n : RngIntElt, RngIntElt -> BoolElt
m ge n : RngIntElt, RngIntElt -> BoolElt
m lt n : RngIntElt, RngIntElt -> BoolElt
m le n : RngIntElt, RngIntElt -> BoolElt
Maximum(m, n) : RngIntElt, RngIntElt -> RngIntElt
Maximum(Q) : [RngIntElt] -> RngIntElt
Minimum(m, n) : RngIntElt, RngIntElt -> RngIntElt
Minimum(Q) : [RngIntElt] -> RngIntElt
The complex conjugate of n, which will be the integer n itself.
The conjugate of n, which will be the integer n itself.
The norm in Q of n, which will be the integer n itself.
The Euclidean norm (length) of n, which will equal the absolute
value of n.
The trace (in Q) of n, which will be the integer n itself.
Returns the minimal polynomial of the integer n, which
is the monic linear polynomial with constant coefficient n in a
univariate polynomial ring R over the integers.
Abs(n) : RngIntElt -> RngIntElt
Absolute value of the integer n.
The integral part of the logarithm to the base two of the positive integer n.
The integral part of the logarithm to the base b of the positive integer n
i.e., the largest integer k such that bk ≤n. The integer b must be
greater than or equal to two.
Returns both the quotient q and remainder r obtained upon dividing the
integer m by the integer n, that is,
m = q.n + r, where 0 ≤r < n if n>0 and n<r≤0 if n<0.
The valuation of the integer x at the prime p. This is the largest
integer v for which pv divides x. If x = 0 then v = ∞.
The optional second return value is the integer u such that x = pv u.
Given a positive integer a, return the integer b=
⌊root n of a⌋, i.e. the integral part of the
n-th root of a. To obtain the actual root (as a real number),
a must e coerced into a real field and the function Root
applied.
Returns -1, 0 or 1 depending upon whether the integer n is
negative, zero or positive, respectively.
The ceiling of the integer n, that is, n itself.
The floor of the integer n, that is, n itself.
This function rounds the integer n to itself.
This function returns the integer truncation of the integer n, that
is, n itself.
Given a non-negative integer n, return a squarefree integer x
as well as a positive integer y, such that n=xy2.
Given a positive integer n, return the integer
⌊√n⌋, i.e., the integral part of the
square root of the integer n.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|