# Module `Z`

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

## Types

## Construction

`val zero : t`

The number 0.

`val one : t`

The number 1.

`val minus_one : t`

The number -1.

`val of_int : int -> t`

Converts from a base integer.

`val of_int32 : int32 -> t`

Converts from a 32-bit integer.

`val of_int64 : int64 -> t`

Converts from a 64-bit integer.

`val of_nativeint : nativeint -> t`

Converts from a native integer.

`val of_float : float -> t`

Converts from a floating-point value. The value is truncated (rounded towards zero). 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.) 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 -> t`

`of_substring s ~pos ~len`

is the same as`of_string (String.sub s pos len)`

`val of_string_base : int -> string -> t`

Parses 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 -> t`

`of_substring_base base s ~pos ~len`

is the same as`of_string_base base (String.sub s pos len)`

## Basic arithmetic operations

`val div : t -> t -> t`

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.

`val rem : t -> t -> t`

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 * t`

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`

.

`val cdiv : t -> t -> t`

Integer division with rounding towards +oo (ceiling). Can raise a

`Division_by_zero`

.

`val fdiv : t -> t -> t`

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`

.

`val divexact : t -> t -> t`

`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`

.

## Bit-level operations

`val shift_left : t -> int -> t`

Shifts to the left. Equivalent to a multiplication by a power of 2. The second argument must be nonnegative.

`val shift_right : t -> int -> t`

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 nonnegative.

`val shift_right_trunc : t -> int -> t`

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 nonnegative.

`val numbits : t -> int`

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 -> int`

Returns 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 -> bool`

`testbit 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.

`val popcount : t -> int`

Counts the number of bits set. Raises

`Overflow`

for negative arguments, as those have an infinite number of bits set.

## Conversions

`val to_int : t -> int`

Converts to a base integer. May raise

`Overflow`

.

`val to_int32 : t -> int32`

Converts to a 32-bit integer. May raise

`Overflow`

.

`val to_int64 : t -> int64`

Converts to a 64-bit integer. May raise

`Overflow`

.

`val to_nativeint : t -> nativeint`

Converts to a native integer. May raise

`Overflow`

.

`val to_float : t -> float`

Converts to a floating-point value. This function rounds the given integer according to the current rounding mode of the processor. In default mode, it returns the floating-point number nearest to the given integer, breaking ties by rounding to even.

`val to_string : t -> string`

Gives a human-readable, decimal string representation of the argument.

`val format : string -> t -> string`

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`

: decimal`b`

: binary`o`

: octal`x`

: lowercase hexadecimal`X`

: 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).

`val fits_int : t -> bool`

Whether the argument fits in a regular

`int`

.

`val fits_int32 : t -> bool`

Whether the argument fits in an

`int32`

.

`val fits_int64 : t -> bool`

Whether the argument fits in an

`int64`

.

`val fits_nativeint : t -> bool`

Whether the argument fits in a

`nativeint`

.

## Printing

`val print : t -> unit`

Prints the argument on the standard output.

`val output : Stdlib.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 : Stdlib.Buffer.t -> t -> unit`

To be used as

`%a`

format printer in`Printf.bprintf`

.

`val pp_print : Stdlib.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.

## Ordering

`val compare : t -> t -> int`

Comparison.

`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 sign : t -> int`

Returns -1, 0, or 1 when the argument is respectively negative, null, or positive.

`val is_even : t -> bool`

Returns true if the argument is even (divisible by 2), false if odd.

`val is_odd : t -> bool`

Returns true if the argument is odd, false if even.

## Elementary number theory

`val gcd : t -> t -> t`

Greatest common divisor. The result is always nonnegative. We have

`gcd(a,0) = gcd(0,a) = abs(a)`

, including`gcd(0,0) = 0`

.

`val gcdext : t -> t -> t * t * t`

`gcdext u v`

returns`(g,s,t)`

where`g`

is the greatest common divisor and`g=us+vt`

.`g`

is always nonnegative.Note: the function is based on the GMP

`mpn_gcdext`

function. The exact choice of`s`

and`t`

such that`g=us+vt`

is not specified, as it may vary from a version of GMP to another (it has changed notably in GMP 4.3.0 and 4.3.1).

`val lcm : t -> t -> t`

Least common multiple. The result is always nonnegative. We have

`lcm(a,0) = lcm(0,a) = 0`

.

`val powm : t -> t -> t -> t`

`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.

`val powm_sec : t -> t -> t -> t`

`powm_sec base exp mod`

computes`base`

^`exp`

modulo`mod`

. Unlike`Z.powm`

, this function is designed to take the same time and have the same cache access patterns for any two same-size arguments. Used in cryptographic applications, it provides better resistance to side-channel attacks than`Z.powm`

. The exponent`exp`

must be positive, and the modulus`mod`

must be odd. Otherwise,`Invalid_arg`

is raised.

`val invert : t -> t -> t`

`invert base mod`

returns the inverse of`base`

modulo`mod`

. Raises a`Division_by_zero`

if`base`

is not invertible modulo`mod`

.

`val probab_prime : t -> int -> int`

`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).

`val nextprime : t -> t`

Returns the next prime greater than the argument. The result is only prime with very high probability.

`val remove : t -> t -> t * int`

`remove a b`

returns`a`

after removing all the occurences of the factor`b`

. Also returns how many occurrences were removed.

`val fac : int -> t`

`fac n`

returns the factorial of`n`

(`n!`

). Raises an`Invaid_argument`

if`n`

is non-positive.

`val fac2 : int -> t`

`fac2 n`

returns the double factorial of`n`

(`n!!`

). Raises an`Invaid_argument`

if`n`

is non-positive.

`val facM : int -> int -> t`

`facM n m`

returns the`m`

-th factorial of`n`

. Raises an`Invaid_argument`

if`n`

or`m`

is non-positive.

`val primorial : int -> t`

`primorial n`

returns the product of all positive prime numbers less than or equal to`n`

. Raises an`Invaid_argument`

if`n`

is non-positive.

`val bin : t -> int -> t`

`bin n k`

returns the binomial coefficient`n`

over`k`

. Raises an`Invaid_argument`

if`k`

is non-positive.

`val fib : int -> t`

`fib n`

returns the`n`

-th Fibonacci number. Raises an`Invaid_argument`

if`n`

is non-positive.

`val lucnum : int -> t`

`lucnum n`

returns the`n`

-th Lucas number. Raises an`Invaid_argument`

if`n`

is non-positive.

## Powers

`val pow : t -> int -> t`

`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.

`val sqrt : t -> t`

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 * t`

Returns the square root truncated, and the remainder. Raises an

`Invalid_argument`

on negative arguments.

`val root : t -> int -> t`

`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 * t`

`rootrem 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 -> bool`

True if the argument has the form

`a^b`

, with`b>1`

`val perfect_square : t -> bool`

True if the argument has the form

`a^2`

.

`val log2 : t -> int`

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.

`val log2up : t -> int`

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

`val size : t -> int`

Returns the number of machine words used to represent the number.

`val extract : t -> int -> int -> t`

`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.

`val signed_extract : t -> int -> int -> t`

`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 -> string`

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.

`val of_bits : string -> t`

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

`val (~$) : int -> t`

Conversion from

`int`

`of_int`

.

`module Compare : sig ... end`