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

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.

• 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 d computes a×b∕d when d does divide a×b.

• raises Division_by_zero

  when d is null.

• raises Division_not_exact

  when d does not divide a×b.

• raises Overflow

  when the result overflows.

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.

• raises Division_by_zero

  when d is null.

• raises Overflow

  as described.

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

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 basek ≤ n < base^k+1. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.

• returns

  −1 when n = 0.

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

• returns

  −1 when n = 0.

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 base^{k−1} ≤ n < basek. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.

• returns

  0 when n = 0.

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

• returns

  0 when n = 0.

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

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

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.

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

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

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.

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.

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

  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.

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.

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

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.