Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

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

Alternatively, using the new `Zarith_top`

toplevel module, simply:

`#require "zarith.top";;`

Raised by conversion functions when the value cannot be represented in the destination type.

`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 (signed) integer.

`val of_int64 : int64 -> t`

Converts from a 64-bit (signed) integer.

`val of_nativeint : nativeint -> t`

Converts from a native (signed) integer.

`val of_int32_unsigned : int32 -> t`

Converts from a 32-bit integer, interpreted as an unsigned integer.

`val of_int64_unsigned : int64 -> t`

Converts from a 64-bit integer, interpreted as an unsigned integer.

`val of_nativeint_unsigned : nativeint -> t`

Converts from a native integer, interpreted as an unsigned 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)
```

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`

.

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`

.

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`

.

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`

.

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`

.

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

.

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

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

For all bit-level operations, negative numbers are considered in 2's complement representation, starting with a virtual infinite number of 1s.

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

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.

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.

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.

`val to_int : t -> int`

Converts to a signed OCaml `int`

. Raises an `Overflow`

if the value does not fit in a signed OCaml `int`

.

`val to_int32 : t -> int32`

Converts to a signed 32-bit integer `int32`

. Raises an `Overflow`

if the value does not fit in a signed `int32`

.

`val to_int64 : t -> int64`

Converts to a signed 64-bit integer `int64`

. Raises an `Overflow`

if the value does not fit in a signed `int64`

.

`val to_nativeint : t -> nativeint`

Converts to a native signed integer `nativeint`

. Raises an `Overflow`

if the value does not fit in a signed `nativeint`

.

`val to_int32_unsigned : t -> int32`

Converts to an unsigned 32-bit integer. The result is stored into an OCaml `int32`

. Beware that most `Int32`

operations consider `int32`

to a signed type, not unsigned. Raises an `Overflow`

if the value is negative or does not fit in an unsigned 32-bit integer.

`val to_int64_unsigned : t -> int64`

Converts to an unsigned 64-bit integer. The result is stored into an OCaml `int64`

. Beware that most `Int64`

operations consider `int64`

to a signed type, not unsigned. Raises an `Overflow`

if the value is negative or does not fit in an unsigned 64-bit integer.

`val to_nativeint_unsigned : t -> nativeint`

Converts to a native unsigned integer. The result is stored into an OCaml `nativeint`

. Beware that most `Nativeint`

operations consider `nativeint`

to a signed type, not unsigned. Raises an `Overflow`

if the value is negative or does not fit in an unsigned native integer.

`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 an OCaml signed `int`

.

`val fits_int32 : t -> bool`

Whether the argument fits in a signed `int32`

.

`val fits_int64 : t -> bool`

Whether the argument fits in a signed `int64`

.

`val fits_nativeint : t -> bool`

Whether the argument fits in a signed `nativeint`

.

`val fits_int32_unsigned : t -> bool`

Whether the argument is non-negative and fits in an unsigned `int32`

.

`val fits_int64_unsigned : t -> bool`

Whether the argument is non-negative and fits in an unsigned `int64`

.

`val fits_nativeint_unsigned : t -> bool`

Whether the argument is non-negative fits in an unsigned `nativeint`

.

`val print : t -> unit`

Prints the argument on the standard output.

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

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.

`val hash : t -> int`

Hashes a number, producing a small integer. The result is consistent with equality: if `a`

= `b`

, then `hash a`

= `hash b`

. OCaml's generic hash function, `Hashtbl.hash`

, works correctly with numbers, but `Z.hash`

is slightly faster.

Greatest common divisor. The result is always nonnegative. We have `gcd(a,0) = gcd(0,a) = abs(a)`

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

.

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

Least common multiple. The result is always nonnegative. We have `lcm(a,0) = lcm(0,a) = 0`

.

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

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

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

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

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

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

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

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

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

`val size : t -> int`

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

. Negative `a`

are considered in infinite-length 2's complement representation. Raises an `Invalid_argument`

if `off`

is strictly negative, or if `len`

is negative or null.

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

. Raises an `Invalid_argument`

if `off`

is strictly negative, or if `len`

is negative or null.

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

`val random_int : ?rng:Random.State.t -> t -> t`

`random_int bound`

returns a random integer between 0 (inclusive) and `bound`

(exclusive). `bound`

must be greater than 0.

The source of randomness is the `Random`

module from the OCaml standard library. The optional `rng`

argument specifies which random state to use. If omitted, the default random state for the `Random`

module is used.

Random numbers produced by this function are not cryptographically strong and must not be used in cryptographic or high-security contexts. See `Z.random_int_gen`

for an alternative.

`val random_bits : ?rng:Random.State.t -> int -> t`

`random_bits nbits`

returns a random integer between 0 (inclusive) and `2{^nbits}`

(exclusive). `nbits`

must be nonnegative. This is a more efficient special case of `Z.random_int`

when the bound is a power of two.

The source of randomness and the `rng`

optional argument are as described in `Z.random_int`

.

Random numbers produced by this function are not cryptographically strong and must not be used in cryptographic or high-security contexts. See `Z.random_bits_gen`

for an alternative.

`random_int_gen ~fill bound`

returns a random integer between 0 (inclusive) and `bound`

(exclusive). `bound`

must be greater than 0.

The `fill`

parameter is the source of randomness. It is called as `fill buf pos len`

, and is responsible for drawing `len`

random bytes and writing them to offsets `pos`

to `pos + len - 1`

of the byte array `buf`

.

Example of use where `/dev/random`

provides the random bytes: << In_channel.with_open_bin "/dev/random" (fun ic -> Z.random_int_gen ~fill:(really_input ic) bound) >> Example of use where the Cryptokit library provides the random bytes: << Z.random_int_gen ~fill:Cryptokit.Random.secure_rng#bytes bound >>

`val random_bits_gen : fill:(bytes -> int -> int -> unit) -> int -> t`

`random_bits_gen ~fill nbits`

returns a random integer between 0 (inclusive) and `2{^nbits}`

(exclusive). `nbits`

must be nonnegative. This is a more efficient special case of `Z.random_int_gen`

when the bound is a power of two. The `fill`

parameter is as described in `Z.random_int_gen`

.

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

.

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

Conversion from `int`

`of_int`

.

`module Compare : sig ... end`

On This Page