Integers.
This modules provides arbitrary-precision integers.
Small integers internally use a regular OCaml int
.
When numbers grow too large, we switch transparently to GMP numbers
(mpn
numbers fully allocated on the OCaml heap).
This interface is rather similar to that of Int32
and Int64
,
with some additional functions provided natively by GMP
(GCD, square root, pop-count, etc.).
This file is part of the Zarith library
http://forge.ocamlcore.org/projects/zarith .
It is distributed under LGPL 2 licensing, with static linking exception.
See the LICENSE file included in the distribution.
Copyright (c) 2010-2011 Antoine Miné, Abstraction project.
Abstraction is part of the LIENS (Laboratoire d'Informatique de l'ENS),
a joint laboratory by:
CNRS (Centre national de la recherche scientifique, France),
ENS (École normale supérieure, Paris, France),
INRIA Rocquencourt (Institut national de recherche en informatique, France).
For an optimal experience with the ocaml
interactive toplevel,
the magic commands are:
#load "zarith.cma";;
#install_printer Z.pp_print;;
#
type t
Type of integers of arbitrary length.
#
exception Overflow
Raised by conversion functions when the value cannot be represented in
the destination type.
#
external of_int : int
-> t
= "ml_z_of_int"
Converts from a base integer.
#
external of_int32 : int32
-> t
= "ml_z_of_int32"
Converts from a 32-bit integer.
#
external of_int64 : int64
-> t
= "ml_z_of_int64"
Converts from a 64-bit integer.
#
external of_nativeint : nativeint
-> t
= "ml_z_of_nativeint"
Converts from a native integer.
#
external of_float : float
-> t
= "ml_z_of_float"
Converts from a floating-point value.
The value is truncated.
Raises Overflow
on infinity and NaN arguments.
#
val of_string : string
-> t
Converts a string to an integer.
An optional -
prefix indicates a negative number, while a +
prefix is ignored.
An optional prefix 0x
, 0o
, or 0b
(following the optional -
or +
prefix) indicates that the number is,
represented, in hexadecimal, octal, or binary, respectively.
Otherwise, base 10 is assumed.
(Unlike C, a lone 0
prefix does not denote octal.)
#
external of_string_base : int
-> string
-> t
= "ml_z_of_string_base"
Parses a number represented as a string in the specified base,
with optional -
or +
prefix.
The base must be between 2 and 16.
Basic arithmetic operations
#
external succ :
t -> t
= "ml_z_succ" "ml_as_z_succ"
Returns its argument plus one.
#
external pred :
t -> t
= "ml_z_pred" "ml_as_z_pred"
Returns its argument minus one.
#
external abs :
t -> t
= "ml_z_abs" "ml_as_z_abs"
#
external neg :
t -> t
= "ml_z_neg" "ml_as_z_neg"
#
external add :
t -> t -> t
= "ml_z_add" "ml_as_z_add"
#
external sub :
t -> t -> t
= "ml_z_sub" "ml_as_z_sub"
#
external mul :
t -> t -> t
= "ml_z_mul" "ml_as_z_mul"
#
external div :
t -> t -> t
= "ml_z_div" "ml_as_z_div"
Integer division. The result is truncated towards zero
and obeys the rule of signs.
Raises Division_by_zero
if the divisor (second argument) is 0.
#
external rem :
t -> t -> t
= "ml_z_rem" "ml_as_z_rem"
Integer remainder. Can raise a Division_by_zero
.
The result of rem a b
has the sign of a
, and its absolute value is
strictly smaller than the absolute value of b
.
The result satisfies the equality a = b * div a b + rem a b
.
#
external div_rem :
t -> t -> t *
t
= "ml_z_div_rem"
Computes both the integer quotient and the remainder.
div_rem a b
is equal to (div a b, rem a b)
.
Raises Division_by_zero
if b = 0
.
#
external cdiv :
t -> t -> t
= "ml_z_cdiv"
Integer division with rounding towards +oo (ceiling).
Can raise a Division_by_zero
.
#
external fdiv :
t -> t -> t
= "ml_z_fdiv"
Integer division with rounding towards -oo (floor).
Can raise a Division_by_zero
.
#
val ediv_rem :
t -> t -> t *
t
Euclidean division and remainder. ediv_rem a b
returns a pair (q, r)
such that a = b * q + r
and 0 <= r < |b|
.
Raises Division_by_zero
if b = 0
.
#
val ediv :
t -> t -> t
Euclidean division. ediv a b
is equal to fst (ediv_rem a b)
.
The result satisfies 0 <= a - b * ediv a b < |b|
.
Raises Division_by_zero
if b = 0
.
#
val erem :
t -> t -> t
Euclidean remainder. erem a b
is equal to snd (ediv_rem a b)
.
The result satisfies 0 <= erem a b < |b|
and
a = b * ediv a b + erem a b
. Raises Division_by_zero
if b = 0
.
#
external divexact :
t -> t -> t
= "ml_z_divexact"
divexact a b
divides a
by b
, only producing correct result when the
division is exact, i.e., when b
evenly divides a
.
It should be faster than general division.
Can raise a Division_by_zero
.
For all bit-level operations, negative numbers are considered in 2's
complement representation, starting with a virtual infinite number of
1s.
#
external logand :
t -> t -> t
= "ml_z_logand" "ml_as_z_logand"
#
external logor :
t -> t -> t
= "ml_z_logor" "ml_as_z_logor"
#
external logxor :
t -> t -> t
= "ml_z_logxor" "ml_as_z_logxor"
Bitwise logical exclusive or.
#
external lognot :
t -> t
= "ml_z_lognot" "ml_as_z_lognot"
Bitwise logical negation.
The identity lognot a
=-a-1
always hold.
#
external shift_left :
t -> int
-> t
= "ml_z_shift_left" "ml_as_z_shift_left"
Shifts to the left.
Equivalent to a multiplication by a power of 2.
The second argument must be non-negative.
#
external shift_right :
t -> int
-> t
= "ml_z_shift_right" "ml_as_z_shift_right"
Shifts to the right.
This is an arithmetic shift,
equivalent to a division by a power of 2 with rounding towards -oo.
The second argument must be non-negative.
#
external shift_right_trunc :
t -> int
-> t
= "ml_z_shift_right_trunc"
Shifts to the right, rounding towards 0.
This is equivalent to a division by a power of 2, with truncation.
The second argument must be non-negative.
#
external popcount :
t -> int
= "ml_z_popcount"
Counts the number of bits set.
Raises Overflow
for negative arguments, as those have an infinite
number of bits set.
#
external hamdist :
t -> t -> int
= "ml_z_hamdist"
Counts the number of different bits.
Raises Overflow
if the arguments have different signs
(in which case the distance is infinite).
Note that, when converting to an integer type that cannot represent the
converted value, an Overflow
exception is raised.
#
external to_int :
t -> int
= "ml_z_to_int"
Converts to a base integer. May raise an Overflow
.
#
external to_int32 :
t -> int32
= "ml_z_to_int32"
Converts to a 32-bit integer. May raise an Overflow
.
#
external to_int64 :
t -> int64
= "ml_z_to_int64"
Converts to a 64-bit integer. May raise Overflow
.
#
external to_nativeint :
t -> nativeint
= "ml_z_to_nativeint"
Converts to a native integer. May raise an Overflow
.
#
external to_float :
t -> float
= "ml_z_to_float"
Converts to a floating-point value.
This function is designed explicitly for the case where the FPU
rounds towards +oo, in which case the resulting float always
over-approximates the argument.
It is not guaranteed to be the least over-approximation though.
In the (default) case where the FPU does not round towards +oo, it is
only guaranteed that the result approximates the argument (but it may
not be the nearest float).
#
val to_string :
t -> string
Gives a human-readable, decimal string representation of the argument.
#
external fits_int :
t -> bool
= "ml_z_fits_int" "noalloc"
Whether the argument fits in a regular int
.
#
external fits_int32 :
t -> bool
= "ml_z_fits_int32" "noalloc"
Whether the argument fits in an int32
.
#
external fits_int64 :
t -> bool
= "ml_z_fits_int64" "noalloc"
Whether the argument fits in an int64
.
#
external fits_nativeint :
t -> bool
= "ml_z_fits_nativeint" "noalloc"
Whether the argument fits in a nativeint
.
#
val print :
t -> unit
Prints the argument on the standard output.
#
val output :
Pervasives.
out_channel -> t -> unit
Prints the argument on the specified channel.
Also intended to be used as %a
format printer in Printf.printf
.
#
val sprint : unit
-> t -> string
To be used as %a
format printer in Printf.sprintf
.
#
val bprint :
Buffer.
t -> t -> unit
To be used as %a
format printer in Printf.bprintf
.
#
val pp_print :
Format.
formatter -> t -> unit
Prints the argument on the specified formatter.
Can be used as %a
format printer in Format.printf
and as
argument to #install_printer
in the top-level.
#
external compare :
t -> t -> int
= "ml_z_compare" "noalloc"
#
external equal :
t -> t -> bool
= "ml_z_equal" "noalloc"
#
val lt :
t -> t -> bool
Less than (and not equal).
#
val gt :
t -> t -> bool
Greater than (and not equal).
#
external sign :
t -> int
= "ml_z_sign" "noalloc"
Returns -1, 0, or 1 when the argument is respectively negative, null, or
positive.
#
val min :
t -> t -> t
Returns the minimum of its arguments.
#
val max :
t -> t -> t
Returns the maximum of its arguments.
#
val hash :
t -> int
Hashes a number.
This functions gives the same result as OCaml's polymorphic hashing
function.
The result is consistent with equality: if a
= b
, then hash a
=
hash b
.
#
external gcd :
t -> t -> t
= "ml_z_gcd"
Greatest common divisor.
The result is always positive.
Raises a Division_by_zero
is either argument is null.
#
val gcdext :
t -> t -> t *
t *
t
gcd_ext u v
returns (g,s,t)
where g
is the greatest common divisor
and g=us+vt
.
g
is always positive.
Raises a Division_by_zero
is either argument is null.
#
val lcm :
t -> t -> t
Least common multiple.
The result is always positive.
Raises a Division_by_zero
is either argument is null.
#
external powm :
t -> t -> t -> t
= "ml_z_powm"
powm base exp mod
computes base
^exp
modulo mod
.
Negative exp
are supported, in which case (base
^-1)^(-exp
) modulo
mod
is computed.
However, if exp
is negative but base
has no inverse modulo mod
, then
a Division_by_zero
is raised.
#
external invert :
t -> t -> t
= "ml_z_invert"
invert base mod
returns the inverse of base
modulo mod
.
Raises a Division_by_zero
if base
is not invertible modulo mod
.
#
external probab_prime :
t -> int
-> int
= "ml_z_probab_prime"
probab_prime x r
returns 0 if x
is definitely composite,
1 if x
is probably prime, and 2 if x
is definitely prime.
The r
argument controls how many Miller-Rabin probabilistic
primality tests are performed (5 to 10 is a reasonable value).
#
external nextprime :
t -> t
= "ml_z_nextprime"
Returns the next prime greater than the argument.
The result is only prime with very high probability.
#
external pow :
t -> int
-> t
= "ml_z_pow"
pow base exp
raises base
to the exp
power.
exp
must be non-negative.
Note that only exponents fitting in a machine integer are supported, as
larger exponents would surely make the result's size overflow the
address space.
#
external sqrt :
t -> t
= "ml_z_sqrt"
Returns the square root. The result is truncated.
Raises an Invalid_argument
on negative arguments.
#
external sqrt_rem :
t -> t *
t
= "ml_z_sqrt_rem"
Returns the square root truncated, and the remainder.
Raises an Invalid_argument
on negative arguments.
#
external root :
t -> int
-> t
= "ml_z_root"
root base n
computes the n
-th root of exp
.
n
must be non-negative.
#
external perfect_power :
t -> bool
= "ml_z_perfect_power"
True if the argument has the form a^b
, with b>1
#
external perfect_square :
t -> bool
= "ml_z_perfect_square"
True if the argument has the form a^2
.
#
external size :
t -> int
= "ml_z_size" "noalloc"
Returns the number of machine words used to represent the number.
#
external to_bits :
t -> string
= "ml_z_to_bits"
Returns a binary representation of the argument.
The string result should be interpreted as a sequence of bytes,
corresponding to the binary representation of the absolute value of
the argument in little endian ordering.
The sign is not stored in the string.
#
external of_bits : string
-> t
= "ml_z_of_bits"
Constructs a number from a binary string representation.
The string is interpreted as a sequence of bytes in little endian order,
and the result is always positive.
We have the identity: of_bits (to_bits x) = abs x
.
However, we can have to_bits (of_bits s) <> s
due to the presence of
trailing zeros in s.
Prefix and infix operators
Classic (and less classic) prefix and infix int
operators are
redefined on t
.
This makes it easy to typeset expressions.
Using OCaml 3.12's local open, you can simply write
Z.(~$2 + ~$5 * ~$10)
.
#
external (~-) :
t -> t
= "ml_z_neg" "ml_as_z_neg"
#
external (+) :
t -> t -> t
= "ml_z_add" "ml_as_z_add"
#
external (-) :
t -> t -> t
= "ml_z_sub" "ml_as_z_sub"
#
external (*) :
t -> t -> t
= "ml_z_mul" "ml_as_z_mul"
#
external (/) :
t -> t -> t
= "ml_z_div" "ml_as_z_div"
#
external (/>) :
t -> t -> t
= "ml_z_cdiv"
#
external (/<) :
t -> t -> t
= "ml_z_fdiv"
#
external (/|) :
t -> t -> t
= "ml_z_divexact"
Exact division div_exact
.
#
external mod :
t -> t -> t
= "ml_z_rem" "ml_as_z_rem"
#
external land :
t -> t -> t
= "ml_z_logand" "ml_as_z_logand"
Bit-wise logical and logand
.
#
external lor :
t -> t -> t
= "ml_z_logor" "ml_as_z_logor"
Bit-wise logical inclusive or logor
.
#
external lxor :
t -> t -> t
= "ml_z_logxor" "ml_as_z_logxor"
Bit-wise logical exclusive or logxor
.
#
external (~!) :
t -> t
= "ml_z_lognot" "ml_as_z_lognot"
Bit-wise logical negation lognot
.
#
external lsl :
t -> int
-> t
= "ml_z_shift_left" "ml_as_z_shift_left"
Bit-wise shift to the left shift_left
.
#
external asr :
t -> int
-> t
= "ml_z_shift_right" "ml_as_z_shift_right"
Bit-wise shift to the right shift_right
.
#
external (~$) : int
-> t
= "ml_z_of_int"
Conversion from int
of_int
.
#
external (**) :
t -> int
-> t
= "ml_z_pow"
#
val version : string
Library version (this file refers to version "1.3"
).