package euler

  1. Overview
  2. Docs

Arithmetic on overflowing integers.

All operations defined here act on overflowing integers. An overflowing integer is any native integer (type int) except Stdlib.min_int. Otherwise said, they are the integers whose absolute value is at most max_int = 2int_size−1 − 1. This makes the range of overflowing integers symmetrical, so that computing the opposite ( ~- ) or the absolute value abs never overflows (the presence of an additional value 2int_size−1 being arbitrarily interpreted as a negative value fits the modulo semantics of integers, but is alien to an overflowing semantics). This allows to use Stdlib.min_int as a special value, for example to signal that an overflow occurred. Here, we rather raise an exception for that purpose. All functions in this library may fail when given Stdlib.min_int where an overflowing integer was expected.

All operations defined here either are free of overflows, or raise Overflow when their result would exceed the range of overflowing integers (and only in that case). Functions which can overflow are signaled explicitly in this documentation.

Functions in this library may raise Assert_failure, instead of the more traditional Invalid_argument, when some precondition is not met. This is not necessarily signaled in this documentation, but all preconditions are stated in the English description of functions. However, we still treat division‐by‐zero differently than other preconditions; for that we raise Division_by_zero, and signal it in this documentation.

As much as possible, time and space complexities are indicated. If absent, constant time or constant space is implied.

val max_int : int

The largest representable integer. This is Stdlib.max_int.

val min_int : int

The smallest representable integer. This is the opposite of max_int, and differs from Stdlib.min_int.

exception Overflow

Raised when the integer result of an operation is not representable.

exception Division_not_exact

Raised when an operation was expected to perform an exact division but the dividend was not a multiple of the divisor.

Base operations

val sign : int -> int

sign a is +1 if a is positive, 0 if it is null, and −1 if it is negative.

val mul_sign : int -> int -> int

mul_sign s n is n if s is non-negative and −n otherwise.

val mul_sign0 : int -> int -> int

mul_sign0 s n is n if s is positive, 0 if it is null, and −n if it is negative. In other words, it is equivalent to mul (sign s) a, but much faster.

val abs : int -> int

Absolute value. By contrast with Stdlib.abs, it cannot overflow.

val min : int -> int -> int

Minimum of two integers.

val max : int -> int -> int

Maximum of two integers.

val compare : int -> int -> int

compare a b returns 0 when a is equal to b, a negative integer when a is smaller than b, and a positive integer when a is greater than b. It is the same as Stdlib.compare but much faster.

val equal : int -> int -> bool

equal a b returns true when a is equal to b, false otherwise.

val pred : int -> int

pred n is n−1.

  • raises Overflow

    when the result overflows.

val succ : int -> int

succ n is n+1.

  • raises Overflow

    when the result overflows.

val opp : int -> int

Integer opposite. By contrast with Stdlib.(~-), it cannot overflow.

val add : int -> int -> int

Overflowing integer addition.

  • raises Overflow

    when the result overflows.

val sub : int -> int -> int

Overflowing integer subtraction.

  • raises Overflow

    when the result overflows.

val sum_seq : int Seq.t -> int

Overflowing integer summation. Unlike a naive iteration of add, this succeeds as long as the result is representable, even when partial sums overflow. Beware that the input sequence is read twice. If that is undesirable, use Seq.memoize (OCaml 4.14). Complexity: time 𝒪(n), space 𝒪(1) where n is the length of the sequence.

  • raises Overflow

    when the result overflows.

val sum : int list -> int

Same as sum_seq but where the input sequence is a list.

  • raises Overflow

    when the result overflows.

val mul : int -> int -> int

Overflowing integer multiplication.

  • raises Overflow

    when the result overflows.

val mul2 : int -> int

mul2 a is equivalent to mul 2 a but much faster.

  • raises Overflow

    when the result overflows.

val mul_pow2 : int -> int -> int

mul_pow2 k a is equivalent to mul (pow2 k) a but much faster.

  • raises Overflow

    when the result overflows.

val prod_seq : int Seq.t -> int

Overflowing n-ary multiplication. Unlike a naive iteration of mul, this succeeds as long as the result is representable even when partial products overflow (this situation only happens when one of the operands is zero). Every operand is read at most once; when an operand is zero, following operands are not read. Complexity: time 𝒪(n), space 𝒪(1) where n is the length of the sequence.

  • raises Overflow

    when the result overflows.

val prod : int list -> int

Same as prod_seq but where the input sequence is a list.

  • raises Overflow

    when the result overflows.

val div_exact : int -> int -> int

Exact integer division. By contrast with Stdlib.(/), it cannot overflow.

val ediv : int -> int -> int * int

ediv a b is the Euclidean division of a by b; it returns (q, r) such that a = b×q + r and 0 ≤ r < b. By contrast with division from the standard library, the remainder is never negative.

val equo : int -> int -> int

equo a b is the quotient of the Euclidean division of a by b.

val erem : int -> int -> int

erem a b is the remainder of the Euclidean division of a by b.

Faster alternatives when the divisor is 2.

val ediv2 : int -> int * int
val equo2 : int -> int
val erem2 : int -> int

Faster alternatives when the divisor is a power of 2. ediv_pow2 a k is equivalent to ediv a (pow2 k).

  • raises Overflow

    when the remainder overflows (happens only when a < 0 and pow2 k overflows).

val ediv_pow2 : int -> int -> int * int
val equo_pow2 : int -> int -> int
val erem_pow2 : int -> int -> int
val mul_div_exact : int -> int -> int -> int

mul_div_exact a b d computes a×bd when d does divide a×b.

  • raises Overflow

    when the result overflows.

val mul_quo : int -> int -> int -> int

mul_quo a b d tries to compute a×b÷d. It can overflow even if the final result fits in the range of overflowing integers. This case is guaranteed not to happen as long the denominator of the reduced fraction is less than √max_int (in particular, when d is less than √max_int). FIXME: This must be fixed, but I don’t know how.

val pow : int -> int -> int

Overflowing integer exponentiation. pow a n is a to the power n, provided that n is non‐negative. Of course, 00 = 1. Complexity: 𝒪(log(n)) integer multiplications.

  • raises Overflow

    when the result overflows.

val pow2 : int -> int

pow2 n is equivalent to pow 2 n, but much faster. Complexity: 𝒪(1).

  • raises Overflow

    when the result overflows.

val powm1 : int -> int

powm1 n is equivalent to pow (-1) (abs n), but much faster. n may be negative. Complexity: 𝒪(1).

val log : ?base:int -> int -> int

log ~base n is the logarithm of n in base base rounded towards zero, provided that base is at least 2 and that n is non‐negative. In other words, it returns ⌊ln(n)∕ln(base)⌋, This is the unique integer k such that basekn < basek+1. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.

  • returns

    −1 when n = 0.

val log2 : int -> int

log2 n is equivalent to log ~base:2 n but faster.

  • returns

    −1 when n = 0.

val logsup : ?base:int -> int -> int

logsup ~base n is the number of digits of n in base base, provided that base is at least 2 and that n is non‐negative. It is equal to ⌈ln(n+1)∕ln(base)⌉ and also (when n is not null) to ⌊ln(n)∕ln(base)⌋ + 1. This is the unique integer k such that basek−1n < basek. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.

  • returns

    0 when n = 0.

val log2sup : int -> int

log2sup n is equivalent to logsup ~base:2 n but faster.

  • returns

    0 when n = 0.

val isqrt : int -> int

isqrt n is the integer square root of n, provided that n is non‐negative. In other words, it is the greatest integer r such that r² ≤ n, that is, ⌊√n⌋.

val icbrt : int -> int

icbrt n is the integer cube root of n, rounded towards zero. In other words, it is sign n × r where r is the greatest integer such that r³ ≤ |n|.

Divisors and multiples

val is_multiple : of_:int -> int -> bool

is_multiple ~of_:a b is true iff b is a multiple of a. This function never raise Division_by_zero, but returns true when a = 0 and b = 0.

val is_even : int -> bool

is_even a is equivalent to is_multiple ~of_:2 a.

val is_odd : int -> bool

is_odd a is equivalent to not (is_multiple ~of_:2 a).

val gcd : int -> int -> int

gcd a b is the positive greatest common divisor of a and b. Complexity: 𝒪(log(min(|a|,|b|))) integer divisions.

  • returns

    0 only when a = b = 0.

val gcdext : int -> int -> int * int * int

gcdext a b is the extended Euclidean algorithm; it returns (d, u, v) where d is the positive greatest common divisor of a and b, and u and v are Bézout’s coefficients, such that u×a + v×b = d. Bézout’s coefficients (u, v) are defined modulo (b/d, −a/d). Furthermore, if a, b ≠ 0, there exists a pair of coefficients such that:

  • 0 < u ≤ |b/d|
  • −|a/d| < v ≤ 0

In particular, when a and b are representable, there always exists a representable pair of coefficients.

Complexity: 𝒪(log(min(|a|,|b|))) integer divisions.

  • returns

    d = 0 only when a = b = 0.

  • raises Overflow

    when the computation of Bézout’s coefficients provokes an overflow, even though there exists a representable pair of coefficients. FIXME: This must be fixed, but I don’t know how.

val lcm : int -> int -> int

lcm a b is the lesser common multiple of a and b. Its sign is that of a×b. Complexity: 𝒪(log(min(|a|,|b|))) integer divisions.

val valuation : factor:int -> int -> int * int

valuation ~factor:d n returns (k, m) such that n = dk×m and m is not divisible by d. This assumes that n is not null and that d is not ±1. Complexity: 𝒪(k) = 𝒪(log(n)) integer divisions.

val valuation_of_2 : int -> int * int

valuation_of_2 is equivalent to valuation ~factor:2, but much faster.

val is_square : ?root:int -> int -> bool

is_square ~root n is true if and only if n is the square of root. When root is omitted, is_square n says whether n is a perfect square.

val jacobi : int -> int -> int

jacobi a n is the Jacobi symbol (a|n), provided that n is odd and positive. Complexity: 𝒪(log(min(|a|,n))) integer divisions.

Binomial coefficients

val binoms : int -> int array

binoms n returns the nth row of Pascal’s triangle, provided that n is a non-negative integer. Complexity: time 𝒪(n), space 𝒪(n).

  • raises Overflow

    when the greatest value of the result overflows. For 64‐bit OCaml, this happens for n ≥ 66.

val binom : int -> int -> int

binom n p is the pth element of the nth row of Pascal’s triangle, provided that 0 ≤ pn. Complexity: time 𝒪(min(p,np)) = 𝒪(n), space 𝒪(1).

  • raises Overflow

    when the result overflows.

val central_binom : int -> int

central_binom p is the pth element of the 2×pth row of Pascal’s triangle, provided that 0 ≤ p. Complexity: time 𝒪(p), space 𝒪(1).

  • raises Overflow

    when the result overflows. For 64‐bit OCaml, this happens for p ≥ 33.

Bit manipulation

Most standard bitwise functions are omitted, because it is not clear what to do with overflowing integers. One common usage, dividing or multiplying by powers of 2, is covered by other, specialized functions.

Missing functions from the standard library: (land) / Int.logand, (lor) / Int.logor, (lxor) / Int.logxor, lnot / Int.lognot, (lsl) / Int.shift_left, (lsr) / Int.shift_right_logical, (asr) / Int.shift_right.

val number_of_bits_set : int -> int

number_of_bits_set n is the number of non-zero bits in the binary writing of the integer n (assuming two’s complement for negative numbers). Complexity: 𝒪(result).

Randomness

val rand : ?min:int -> ?max:int -> unit -> int

rand ~min ~max () draws a random integer with the uniform distribution between min and max (inclusive). max must be greater than or equal to min. min defaults to 0, max defaults to max_int.

val rand_signed : ?max:int -> unit -> int

rand_signed ~max () draws a random integer with the uniform distribution, with an absolute value at most max. max must be non-negative.

Sequences

val range' : ?step:int -> ?from:int -> ?til:int -> unit -> int Seq.t

range' ~step ~from ~til () returns the sequence of integers between from (inclusive) and til (exclusive), by increments of step. step must be non-zero, but it can be negative, in which case the sequence is decreasing. step defaults to 1, from defaults to 0; when til is not given, the default is to build the sequence of all representable integers starting from from with increment step. The sequence is persistent (the unit argument is meaningless, it just erases optional arguments). Complexity: 𝒪(1) time and space.

val range : from:int -> til:int -> int Seq.t

range_down ~from ~til are the integers from from down to til+1. In other words it is range' ~step:~-1 ~from ~til ().

val range0 : int -> int Seq.t

range0 n are the n integers from 0 up to n−1. In other words, it is range ~from:0 ~til:n.

val range1 : int -> int Seq.t

range0 n are the n integers from 1 up to n. In other words, it is range ~from:1 ~til:(n+1) (except that n is allowed to be max_int).

Operators

We deliberately override the standard operators. This is to make sure we don’t write unsafe arithmetic by accident.

val (~-) : int -> int

Prefix notation for opp.

val (+) : int -> int -> int

Infix notation for add.

val (-) : int -> int -> int

Infix notation for sub.

val (*) : int -> int -> int

Infix notation for mul.

val (/) : int -> int -> int

Infix notation for div_exact. Note that this is more restrictive than the usual division from the standard library; this forces us to realize when we are doing a non-exact division, for which we must write //.

val (//) : int -> int -> int

Infix notation for equo. Note that this is not the same as Stdlib.(/) when the dividend is negative.

val (/%) : int -> int -> int

Infix notation for erem. Same remark as for (//). We don’t use (%) because we likely want that symbol to be available for other things (e.g. for function composition).

val (mod) : int -> int -> int

Same.

module Unsafe : sig ... end

Module Unsafe gives access to the old operations for when we know what we are doing (i.e. we know that a given operation cannot overflow) and we absolutely don’t want to pay for the overhead of the safe functions. Operators in that module are suffixed with a ! so as to distinguish them clearly.

OCaml

Innovation. Community. Security.