package euler

  1. Overview
  2. Docs

Module Euler.ArithSource

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, it is an integer whose absolute value is at most max_int = 2int_size−1 − 1, implying that the minimum value is min_int = −max_int = −2int_size−1 + 1 = Stdlib.min_int+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).

Incidentally, this allows to use Stdlib.min_int as a special value, for example to signal that an overflow occurred. However in this library 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 (time complexities are termed as a count of machine-arithmetic operations). If absent, constant time or constant space is implied.

By opening it, this module can mostly be used as a drop-in replacement for Stdlib arithmetic operations. This allows lightweight notations and avoids accidental uses of overflow-unsafe Stdlib operations. Beware of the following changes:

  • min_int has a different value (as explained);
  • min, max and compare are monomorphic functions for type int, instead of polymorphic functions;
  • (**) is redefined as the integer exponentation (the floating-point exponentiation is available as (**.));
  • (/) is restricted to an exact division (a possibly-rounded division is available as (//), which differs from Stdlib.(/) in that it does an Euclidean division);
  • (mod) is redefined as the Euclidean remainder.
Sourceval max_int : int

The largest representable integer. This is Stdlib.max_int.

Sourceval min_int : int

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

Sourceexception Overflow

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

Sourceexception 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

Sourceval sign : int -> int

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

Sourceval mul_sign : int -> int -> int

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

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

Sourceval abs : int -> int

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

Sourceval min : int -> int -> int

Minimum of two integers.

Sourceval max : int -> int -> int

Maximum of two integers.

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

Sourceval equal : int -> int -> bool

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

Sourceval pred : int -> int

pred n is n−1.

  • raises Overflow

    when the result overflows.

Sourceval succ : int -> int

succ n is n+1.

  • raises Overflow

    when the result overflows.

Sourceval opp : int -> int

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

Sourceval add : int -> int -> int

Overflowing integer addition.

  • raises Overflow

    when the result overflows.

Sourceval sub : int -> int -> int

Overflowing integer subtraction.

  • raises Overflow

    when the result overflows.

Sourceval sum_of_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.

Sourceval sum : int list -> int

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

  • raises Overflow

    when the result overflows.

Sourceval mul : int -> int -> int

Overflowing integer multiplication.

  • raises Overflow

    when the result overflows.

Sourceval mul2 : int -> int

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

  • raises Overflow

    when the result overflows.

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

Sourceval prod_of_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.

Sourceval prod : int list -> int

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

  • raises Overflow

    when the result overflows.

Sourceval div_exact : int -> int -> int

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

Sourceval sdiv : int -> int -> int * int

sdiv a b is the “signed” division of a by b; it returns (q, r) such that a = b×q + r and |r| < |a| and r is of the same sign as a.

This is the standard library’s division. However, using sdiv is better than computing both Stdlib.(a / b) and Stdlib.(a mod b) separately, because sdiv spares one machine division, which is much more costly than a multiplication.

sdiv is slightly faster than ediv, so it is also useful when we don’t need the remainder to be positive or when we know that a ≥ 0.

Sourceval 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 sdiv, the remainder is never negative.

Sourceval equo : int -> int -> int

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

Sourceval erem : int -> int -> int

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

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

Faster alternatives when the divisor is 2.

Sourceval ediv_pow2 : int -> int -> int * int
Sourceval equo_pow2 : int -> int -> int
Sourceval erem_pow2 : int -> 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; equo_pow2 is not affected).

Sourceval mul_div_exact : int -> int -> int -> int

mul_div_exact a b c computes a×bc when c does divide a×b.

  • raises Overflow

    when the result overflows.

Sourceval mul_ediv : int -> int -> int -> int * int

mul_ediv a b c computes the Euclidean division of a×b by c, even when the intermediate product would overflow.

  • raises Overflow

    when the quotient overflows.

Sourceval mul_equo : int -> int -> int -> int

mul_equo a b c is the quotient of the Euclidean division of a×b by c.

  • raises Overflow

    when the result overflows.

Sourceval mul_erem : int -> int -> int -> int

mul_erem a b c is the remainder of the Euclidean division of a×b by c. It cannot overflow.

If you are interested in modular arithmetic, see also Modular.mul.

Exponentiation and logarithms

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

Sourceval pow2 : int -> int

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

  • raises Overflow

    when the result overflows.

Sourceval powm1 : int -> int

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

Sourceval ilog : ?base:int -> int -> int

ilog ~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. This is a relatively slow operation in general, but it is specially optimized for bases 2, 16, 64, 10 and 60. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.

  • returns

    −1 when n = 0.

Sourceval ilog2 : int -> int

ilog2 n is equivalent to ilog ~base:2 n but faster.

  • returns

    −1 when n = 0.

Sourceval ilogsup : ?base:int -> int -> int

ilogsup ~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. As for ilog, this is relatively slow but it is fast for bases 2, 16, 64, 10 and 60. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.

  • returns

    0 when n = 0.

Sourceval ilog2sup : int -> int

ilog2sup n is equivalent to ilogsup ~base:2 n but faster.

  • returns

    0 when n = 0.

Sourceval is_pow : ?base:int -> ?exp:int -> int -> bool

is_pow ~base ~exp n is true if and only if n = baseexp. When exp is omitted, is_kth_pow ~base n says whether n is some power of base. When exp is provided, it is equivalent to is_kth_pow ~k:exp ~root:base n. The default base is 10.

Sourceval is_pow2 : int -> bool

is_pow2 n is equivalent to is_pow ~base:2 n, but much faster.

Roots

Sourceval kth_root : k:int -> int -> int

kth_root ~k n is the integer kth root of n, rounded towards zero. In other words, it is sign n × r where r is the greatest integer such that rk ≤ |n|. k must be positive. If k is even, n must be non-negative.

Sourceval 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⌋. It is equivalent to kth_root ~k:2 n but should be faster.

Sourceval isqrt_if_square : int -> int option

isqrt_if_square n is the integer square root of n if n is a perfect square, or None otherwise. When n is not square, this is faster than combining isqrt with is_square.

Sourceval 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|. It is equivalent to kth_root ~k:3 n but may be faster.

Sourceval is_kth_pow : k:int -> ?root:int -> int -> bool

is_kth_pow ~k ~root n is true if and only if n = rootk. When root is omitted, is_kth_pow n says whether n is a kth power. When root is provided, it is equivalent to is_pow ~base:root ~exp:k n.

Sourceval 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. It is equivalent to is_kth_pow ~k:2 ~root n but faster.

Divisors and multiples

Sourceval is_multiple : of_:int -> int -> bool

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

Sourceval is_even : int -> bool

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

Sourceval is_odd : int -> bool

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

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

Sourceval gcd_of_seq : int Seq.t -> int

The positive greatest common divisor of a sequence of numbers. Complexity: 𝒪(n × log(m)) integer divisions where n is the length of the sequence and m is its maximum element.

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

If a ≠ 0, b ≠ 0 and |a| ≠ |b|, then this function returns the unique pair of coefficients whose magnitude is minimal; this pair is in the following range (in particular, the function never overflows):

  • |u| ≤ ½|b/d|
  • |v| ≤ ½|a/d|

In the edge cases (a = 0 or b = 0 or |a| = |b|), it returns (u, v) = (0, 0) or (±1, 0) or (0, ±1).

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

  • returns

    d = 0 only when a = b = 0.

Sourceval gcdext_of_seq : int Seq.t -> int * int list

The positive greatest common divisor of a sequence of numbers, with Bézout coefficients. gcdext_of_seq @@ List.to_seq [ a1 ; … ; an ] returns a pair (d, [ u1 ; … ; un ]) such that d is the positive greatest common divisor of a1, …, an, and the ui are coefficients such that a1×u1 + … + an×un = d.

Complexity: 𝒪(n × log(m)) integer divisions where n is the length of the sequence and m is its maximum element.

  • raises Overflow

    when the computation of Bézout’s coefficients provokes an overflow, which may happen even if there exists a representable vector of coefficients.

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

  • raises Overflow

    when the result overflows.

Sourceval lcm_of_seq : int Seq.t -> int

The lesser common multiple of a sequence of numbers. Complexity: 𝒪(n × log(m)) integer divisions where n is the length of the sequence and m is its maximum element.

  • raises Overflow

    when the result overflows.

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

Sourceval valuation_of_2 : int -> int * int

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

Sourceval smallest_root : int -> int * int

smallest_root n returns (r, k) such that n = rk and |r| is minimal (which also implies that k is maximal). n must be non-zero.

  • returns

    (1, 0) for n = 1, and (-1, 1) for n = -1.

Sourceval 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

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

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

Sourceval central_binom : int -> int

central_binom p is the pth element of the (2×p)th 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.

Sourceval 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

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

Sourceval 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

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

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

range ~from ~til are the integers from from up to til−1. In other words it is range' ~step:1 ~from ~til ().

Sourceval range_down : 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 ().

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

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

Sourceval (~-) : int -> int

Prefix notation for opp.

Sourceval (+) : int -> int -> int

Infix notation for add.

Sourceval (-) : int -> int -> int

Infix notation for sub.

Sourceval (*) : int -> int -> int

Infix notation for mul.

Sourceval (/) : 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 (//).

Sourceval (//) : int -> int -> int

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

Sourceval (/%) : 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).

Sourceval (mod) : int -> int -> int

Same.

Sourceval (**) : int -> int -> int

Infix notation for pow. Note that this overrides the standard library’s notation for floating-point exponentiation. Thus we re-expose the latter with the notation (**.).

Sourceval (**.) : float -> float -> float

New infix notation for Stdlib.( ** ), the floating-point exponentiation.

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