Euler.ArithArithmetic 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.
The smallest representable integer. This is the opposite of max_int, and differs from Stdlib.min_int.
Raised when an operation was expected to perform an exact division but the dividend was not a multiple of the divisor.
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.
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.
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.
Same as sum_seq but where the input sequence is a list.
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.
Same as prod_seq but where the input sequence is a list.
Exact integer division. By contrast with Stdlib.(/), it cannot overflow.
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.
Faster alternatives when the divisor is 2.
Faster alternatives when the divisor is a power of 2. ediv_pow2 a k is equivalent to ediv a (pow2 k).
mul_div_exact a b d computes a×b∕d when d does divide a×b.
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.
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.
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 < basek+1. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.
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−1 ≤ n < basek. The default base is 10. Complexity: 𝒪(log(log(n))) integer multiplications.
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.
gcd a b is the positive greatest common divisor of a and b. Complexity: 𝒪(log(min(|a|,|b|))) integer divisions.
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:
u ≤ |b/d|a/d| < v ≤ 0In particular, when a and b are representable, there always exists a representable pair of coefficients.
Complexity: 𝒪(log(min(|a|,|b|))) integer divisions.
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.
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.
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 nth row of Pascal’s triangle, provided that n is a non-negative integer. Complexity: time 𝒪(n), space 𝒪(n).
binom n p is the pth element of the nth row of Pascal’s triangle, provided that 0 ≤ p ≤ n. Complexity: time 𝒪(min(p,n−p)) = 𝒪(n), space 𝒪(1).
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).
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.
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).
We deliberately override the standard operators. This is to make sure we don’t write unsafe arithmetic by accident.
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.
module Unsafe : sig ... endModule 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.