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).
Toplevel
For an optimal experience with the ocaml interactive toplevel, the magic commands are:
#load "zarith.cma";;
#install_printer Z.pp_print;;
Alternatively, using the new Zarith_top toplevel module, simply:
#require "zarith.top";;
Types
Type of integers of arbitrary length.
Raised by conversion functions when the value cannot be represented in the destination type.
Construction
Converts from a base integer.
val of_int32 : int32 -> tConverts from a 32-bit integer.
val of_int64 : int64 -> tConverts from a 64-bit integer.
val of_string : string -> tConverts 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.) Raises an Invalid_argument exception if the string is not a syntactically correct representation of an integer.
val of_substring : string -> pos:int -> len:int -> tof_substring s ~pos ~len is the same as of_string (String.sub s
pos len)
val of_string_base : int -> string -> tParses a number represented as a string in the specified base, with optional - or + prefix. The base must be between 2 and 16.
val of_substring_base : int -> string -> pos:int -> len:int -> tof_substring_base base s ~pos ~len is the same as of_string_base
base (String.sub s pos len)
Basic arithmetic operations
Returns its argument plus one.
Returns its argument minus one.
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.
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.
val div_rem : t -> t -> t * tComputes 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.
Integer division with rounding towards +oo (ceiling). Can raise a Division_by_zero.
Integer division with rounding towards -oo (floor). Can raise a Division_by_zero.
val ediv_rem : t -> t -> t * tEuclidean 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.
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.
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.
val divexact : t -> t -> tdivexact 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.
val divisible : t -> t -> booldivisible a b returns true if a is exactly divisible by b. Unlike the other division functions, b = 0 is accepted (only 0 is considered divisible by 0).
val congruent : t -> t -> t -> boolcongruent a b c returns true if a is congruent to b modulo c. Unlike the other division functions, c = 0 is accepted (only equal numbers are considered equal congruent 0).
Bit-level operations
For all bit-level operations, negative numbers are considered in 2's complement representation, starting with a virtual infinite number of 1s.
Bitwise logical exclusive or.
Bitwise logical negation. The identity lognot a=-a-1 always hold.
val shift_left : t -> int -> tShifts to the left. Equivalent to a multiplication by a power of 2. The second argument must be nonnegative.
val shift_right : t -> int -> tShifts 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 nonnegative.
val shift_right_trunc : t -> int -> tShifts to the right, rounding towards 0. This is equivalent to a division by a power of 2, with truncation. The second argument must be nonnegative.
Returns the number of significant bits in the given number. If x is zero, numbits x returns 0. Otherwise, numbits x returns a positive integer n such that 2^{n-1} <= |x| < 2^n. Note that numbits is defined for negative arguments, and that numbits (-x) = numbits x.
val trailing_zeros : t -> intReturns the number of trailing 0 bits in the given number. If x is zero, trailing_zeros x returns max_int. Otherwise, trailing_zeros x returns a nonnegative integer n which is the largest n such that 2^n divides x evenly. Note that trailing_zeros is defined for negative arguments, and that trailing_zeros (-x) = trailing_zeros x.
val testbit : t -> int -> booltestbit x n return the value of bit number n in x: true if the bit is 1, false if the bit is 0. Bits are numbered from 0. Raise Invalid_argument if n is negative.
Counts the number of bits set. Raises Overflow for negative arguments, as those have an infinite number of bits set.
val hamdist : t -> t -> intCounts the number of different bits. Raises Overflow if the arguments have different signs (in which case the distance is infinite).
Conversions
Note that, when converting to an integer type that cannot represent the converted value, an Overflow exception is raised.
Converts to a base integer. May raise Overflow.
val to_int32 : t -> int32Converts to a 32-bit integer. May raise Overflow.
val to_int64 : t -> int64Converts to a 64-bit integer. May raise Overflow.
val to_string : t -> stringGives a human-readable, decimal string representation of the argument.
Gives a string representation of the argument in the specified printf-like format. The general specification has the following form:
% [flags] [width] type
Where the type actually indicates the base:
i, d, u: decimalb: binaryo: octalx: lowercase hexadecimalX: uppercase hexadecimal
Supported flags are:
+: prefix positive numbers with a + sign- space: prefix positive numbers with a space
-: left-justify (default is right justification)0: pad with zeroes (instead of spaces)#: alternate formatting (actually, simply output a literal-like prefix: 0x, 0b, 0o)
Unlike the classic printf, all numbers are signed (even hexadecimal ones), there is no precision field, and characters that are not part of the format are simply ignored (and not copied in the output).
Whether the argument fits in a regular int.
val fits_int32 : t -> boolWhether the argument fits in an int32.
val fits_int64 : t -> boolWhether the argument fits in an int64.
Printing
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.
Ordering
val compare : t -> t -> intComparison. compare x y returns 0 if x equals y, -1 if x is smaller than y, and 1 if x is greater than y.
Note that Pervasive.compare can be used to compare reliably two integers only on OCaml 3.12.1 and later versions.
val equal : t -> t -> boolLess than (and not equal).
Greater than (and not equal).
Returns -1, 0, or 1 when the argument is respectively negative, null, or positive.
Returns the minimum of its arguments.
Returns the maximum of its arguments.
Returns true if the argument is even (divisible by 2), false if odd.
Returns true if the argument is odd, false if even.
Powers
pow base exp raises base to the exp power. exp must be nonnegative. 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.
Returns the square root. The result is truncated (rounded down to an integer). Raises an Invalid_argument on negative arguments.
val sqrt_rem : t -> t * tReturns the square root truncated, and the remainder. Raises an Invalid_argument on negative arguments.
root x n computes the n-th root of x. n must be positive and, if n is even, then x must be nonnegative. Otherwise, an Invalid_argument is raised.
val rootrem : t -> int -> t * trootrem x n computes the n-th root of x and the remainder x-root**n. n must be positive and, if n is even, then x must be nonnegative. Otherwise, an Invalid_argument is raised.
val perfect_power : t -> boolTrue if the argument has the form a^b, with b>1
val perfect_square : t -> boolTrue if the argument has the form a^2.
Returns the base-2 logarithm of its argument, rounded down to an integer. If x is positive, log2 x returns the largest n such that 2^n <= x. If x is negative or zero, log2 x raise the Invalid_argument exception.
Returns the base-2 logarithm of its argument, rounded up to an integer. If x is positive, log2up x returns the smallest n such that x <= 2^n. If x is negative or zero, log2up x raise the Invalid_argument exception.
Representation
Returns the number of machine words used to represent the number.
extract a off len returns a nonnegative number corresponding to bits off to off+len-1 of b. Negative a are considered in infinite-length 2's complement representation.
signed_extract a off len extracts bits off to off+len-1 of b, as extract does, then sign-extends bit len-1 of the result (that is, bit off + len - 1 of a). The result is between - 2{^[len]-1} (included) and 2{^[len]-1} (excluded), and equal to extract a off len modulo 2{^len}.
val to_bits : t -> stringReturns 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.
val of_bits : string -> tConstructs 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.