package euler

The largest representable integer. This is Stdlib.max_int.

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

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

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

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

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

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.

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

Minimum of two integers.

Maximum of two integers.

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.

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

pred n is n−1.

• raises Overflow

  when the result overflows.

succ n is n+1.

• raises Overflow

  when the result overflows.

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

Overflowing integer addition.

• raises Overflow

  when the result overflows.

Overflowing integer subtraction.

• raises Overflow

  when the result overflows.

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.

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

• raises Overflow

  when the result overflows.

Overflowing integer multiplication.

• raises Overflow

  when the result overflows.

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

• raises Overflow

  when the result overflows.

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

• raises Overflow

  when the result overflows.

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.

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

• raises Overflow

  when the result overflows.

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

• raises Division_by_zero

  when the divisor is null.

• raises Division_not_exact

  when the dividend is not a multiple of the divisor.

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.

• raises Division_by_zero

  when b is null.

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.

• raises Division_by_zero

  when b is null.

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

• raises Division_by_zero

  when b is null.

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

• raises Division_by_zero

  when b is null.

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

• raises Division_by_zero

  when c is null.

• raises Division_not_exact

  when c does not divide a×b.

• raises Overflow

  when the result overflows.

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

• raises Division_by_zero

  when c is null.

• raises Overflow

  when the quotient overflows.

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

• raises Division_by_zero

  when c is null.

• raises Overflow

  when the result overflows.

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.

• raises Division_by_zero

  when c is null.

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

• raises Overflow

  when the result overflows.

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

• raises Overflow

  when the result overflows.

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

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 basek ≤ n < base^k+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.

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

• returns

  −1 when n = 0.

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 base^{k−1} ≤ n < 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.

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

• returns

  0 when n = 0.

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.

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

kth_root ~k n is the integer k^th 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.

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.

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.

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.

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 k^th power. When root is provided, it is equivalent to is_pow ~base:root ~exp:k n.

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.

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.

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

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

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.

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.

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.

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 a₁, …, a_n, and the u_i are coefficients such that a₁×u₁ + … + a_n×u_n = 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.

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.

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.

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.

• raises Division_by_zero

  when d is null.

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

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.

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

binoms n returns the n^th 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.

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

• raises Overflow

  when the result overflows.

central_binom p is the p^th 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.

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

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.

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

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.

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

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

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

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

Prefix notation for opp.

Infix notation for add.

Infix notation for sub.

Infix notation for mul.

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

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

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

Same.

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 (**.).

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

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.