Miscellaneous Number Functions

This module offers various functions to manipulate numbers that are not otherwise offered by R7RS, Gambit, :std/srfi/141, :srfi/144, or :srfi/151.

To use the bindings from this module:

(import :std/misc/number)

Extended Real Number Line

The (affine) extended real number line, where real numbers are enriched with positive and negative infinity, compactifying their order. Positive infinity is represented by IEEE number +inf.0 while negative infinity is represented by IEEE number -inf.0, so that common operations like < <= + *, etc., already work. However, a few operations are provided in a library so that max and min functions work better with infinities. Notably:

  • (xmin) will return +inf.0 where (min) throws an error, and similarly (xmax) will return -inf.0 where (max) throws an error.
  • (xmax -inf.0 (+ 1 (expt 2 54))) will return the exact integer 18014398509481985, where (max -inf.0 (+ 1 (expt 2 54))) returns the rounded 1.8014398509481984e16. More generally, xmin and xmax preserve the type of the argument they return.

real->sign

(real->sign x) -> -1, 0 or 1

Given an extended real number x, return an integer, -1 if the number is negative, 0 if it is zero, and 1 if it is positive.

Examples:

> (real->sign 2.7)
1
> (real->sign 1e-100)
1
> (real->sign -42)
-1
> (real->sign -inf.0)
-1
> (real->sign 0.0)
0
> (real->sign 0)
0

xmin

(xmin <x1> ... <xn>) -> real

xmin returns the lower bound of the set of its extended real arguments. In particular, it returns +inf.0 (the positive infinity) if provided zero arguments, and is the identity function when given a single argument.

xmin/list

(xmin/list <l>) -> real

xmin/list returns the lower bound of the list of extended real arguments passed as its arguments. In particular, it returns +inf.0 (the positive infinity) if provided an empty list.

xmin!

(xmin! <var> <x> ...) -> void

xmin! side-effects a variable to change it to the xmin of the previous value and the provided arguments.

xmin/map

(xmin/map <f> <l> [<base>]) -> real

Given a list <l> or any thing you can iterate on, and a function <f>, xmin/map returns the lower bound of the images by <f> of the items in <l>, and of a <base> real, by default +inf.0 (the positive infinity). The function is short-circuiting and will not evaluate further values and their side-effects after the bottom value -inf.0 is reached.

xmax

(xmax <x1> ... <xn>) -> real

xmax returns the upper bound of the set of its extended real arguments. In particular, it returns -inf.0 (the negative infinity) if provided zero arguments, and is the identity function when given a single argument.

xmax/list

(xmax/list <l>) -> real

xmax/list returns the lower bound of the list of extended real arguments passed as its arguments. In particular, it returns -inf.0 (the negative infinity) if provided an empty list.

xmax!

(xmax! <var> <x> ...) -> void

xmax! side-effects a variable to change it to the xmax of the previous value and the provided arguments.

xmax/map

(xmax/map <f> <l> [<base>]) -> real

Given a list <l> or any thing you can iterate on, and a function <f>, xmax/map returns the upper bound of the images by <f> of the items in <l>, and of a <base> xreal, by default -inf.0 (the negative infinity). The function is short-circuiting and will not evaluate further values and their side-effects after the top value +inf.0 is reached.

Counters

increment!, pre-increment!, post-increment!, decrement!, pre-decrement!, post-decrement!

(increment! place) -> (void)
(increment! place increment ...) -> (void)
(pre-increment! place) -> number
(pre-increment! place increment ...) -> number
(post-increment! place) -> number
(post-increment! place increment ...) -> number
(decrement! place) -> (void)
(decrement! place decrement ...) -> (void)
(pre-decrement! place) -> number
(pre-decrement! place decrement ...) -> number
(post-decrement! place) -> number
(post-decrement! place decrement ...) -> number

These macro will modify a variable or other place containing a number to increment (respectively, decrement) its value, adding to it (respectively, subtracting from it) one (if no further argument is specified) or the provided arguments (if specified). increment! and decrement! return #!void, pre-increment! and pre-decrement! return the value after addition (respectively, subtraction), and post-increment! and post-decrement! return the value before addition (respectively, subtraction).

make-counter

(make-counter) -> counter
(make-counter n) -> counter

This function creates a new counter, a function that takes zero or more arguments, adds the sum of these arguments to the counter (or 1, not 0, if no argument was provided), and returns the original value of the counter before the addition (post-increment). You can thus reserve how many entries you are counting before the next call. Note that this function provides no guarantee of atomicity in case of multithreaded use.

Euclidian Division

integer-part

(integer-part x) -> integer

Given a real number x, integer-part will return the integer part as an exact integer, i.e. the number with largest absolute value whose absolute value is no greater than that of x.

fractional-part

(fractional-part x) -> integer

floor-align, ceiling-align

(floor-align n alignment) -> integer
(ceiling-align n alignment) -> integer

Given an integer n, and a non-zero integer alignment, if alignment is positive, floor-align returns the largest multiple of alignment non-greater than n, and ceiling-align returns the smallest multiple of alignment non-lesser than n; if alignment is negative, the roles of floor-align and ceiling-align are swapped.

Examples:

> (floor-align 20 10)
20
> (floor-align 25 10)
20
> (floor-align 25 -10)
30
> (ceiling-align 20 10)
20
> (ceiling-align 25 10)
30
> (ceiling-align 25 -10)
20

Natural Numbers

uint?

(uint? x) -> Bool

Given any object x, return true if it is an non-negative exact integer.

sint?

(sint? x) -> Bool

Given any object x, return true if it is an exact integer.

positive-integer?

(positive-integer? x) -> Bool

Given any object x, return true if it is an positive exact integer.

n-bits->n-u8

(n-bits->n-u8 n) -> integer

Given a number of bits, return the number of bytes necessary to store those bits.

uint-length-in-u8

(uint-length-in-u8 n) -> integer

Given a non-negative exact integer n, return the number of 8-bit bytes necessary to encode all the bits of n.

sint-length-in-u8

(sint-length-in-u8 n) -> integer

Given an exact integer n (that may be positive, negative or zero), return the number of 8-bit bytes necessary to encode all the bits of n including the sign bit.

check-argument-uint

(check-argument-uint n) -> unspecified

Check that argument n is a non-negative exact integer, or raise an error.

check-argument-sint

(check-argument-sint n) -> unspecified

Check that argument n is an exact integer, or raise an error.

check-argument-exact-integer

(check-argument-exact-integer n) -> unspecified

Check that argument n is an exact integer, or raise an error.

check-argument-positive-integer

(check-argument-positive-integer n) -> unspecified

Check that argument n is a positive exact integer, or raise an error.

normalize-uint

(normalize-uint x length-in-bits) => uint

Given an exact integer x and a length-in-bits, return a non-negative exact integer of given length that has the same length-in-bits lower order bits as x.

normalize-sint

(normalize-sint x length-in-bits) => sint

Given an exact integer x and a length-in-bits, return a (signed) exact integer of given length that has the same length-in-bits lower order bits as x, including the sign bit as the (length-in-bits minus 1)th.

uint-below?

(uint-below? x end) -> Bool

Given any object x, return true if it is an non-negative exact integer less than end (not included).

uint-of-length?

(uint-of-length? x length-in-bits) -> Bool

Given any object x, return true if it is an non-negative exact integer that can be stored in length-in-bits bits, as witnessed by its integer-length being no greater than length-in-bits (included).

sint-of-length?

(sint-of-length? x length-in-bits) -> Bool

Given any object x, return true if it is a (negative, zero or positive) exact integer that can be stored in length-in-bits bits (including sign bit), as witnessed by its integer-length being strictly less than length-in-bits (not included).

Iteration

for-each-integer

(for-each-integer fun from below)

Given fun a function of one argument, call fun with each successive increasing integer starting with from up to and not including below.

Binary Search (a.k.a. Dichotomy)

half

(half n)

Given an integer n, return half of n if it is even, or half of n-1 if it is odd.

least-integer?

(least-integer pred? start end) -> integer

Do a binary search in interval [start, end) to find the least integer for which pred? holds, assuming pred? is “increasing”, i.e. if true for some integer in the interval, it is true for all greater integers in the interval. If no integer in the interval satisfies pred?, return end. If all do, return start. If pred? isn't actually increasing, return some integer in the interval.

Modular Arithmetics

divides?

(divides f n) -> bool

Given two integers f and n, return true if f is a dividing factor of n, i.e. there exists a g such that n=f*g.

Examples:

> (divides? 2 256)
#t
> (divides? 2 255)
#f

bezout

(bezout a b) -> (values integer integer integer)

Given two integers a and b, return three values x y and d, such that d is the (non-negative) gcd of a and b, and a*x+b+y=d, thus forming a Bezout relationship.

Note: the current implementation doesn't use constant-time computations and shouldn't be used for production-grade cryptography.

mult-mod a b n

(mult-mod a b n) -> integer

Given two integers a, b and a positive integer n, return the product m of a and b modulo n.

Note: the current implementation doesn't use constant-time computations and shouldn't be used for production-grade cryptography. Its performance is only moderate.

invert-mod

(invert-mod a n) -> integer

Given an integer a and a positive integer n, return the inverse of a modulo n, or raise an error if a is not invertible modulo n.

Note: the current implementation doesn't use constant-time computations and shouldn't be used for production-grade cryptography. Its performance is only moderate.

invert-mod

(invert-mod a n) -> integer

Given integers a and b and a positive integer n, divide a by b modulo n, i.e. return an integer m such that a = b*m [n], if such an integer exists, or raise an error if no such integer exists.

Note: the current implementation doesn't use constant-time computations and shouldn't be used for production-grade cryptography. Its performance is only moderate.

mult-expt-mod

(mult-expt-mod a x e n) -> integer

Given integers a, x, e and n, multiply a by x to the power e modulo n. If e is negative then x must be invertible modulo n.

Note: the current implementation doesn't use constant-time computations and shouldn't be used for production-grade cryptography. Its performance is only moderate.

expt-mod

(expt-mod x e n) -> integer

Given integers x, e and n, compute x to the power e modulo n. If e is negative then x must be invertible modulo n.

Note: the current implementation doesn't use constant-time computations and shouldn't be used for production-grade cryptography. Its performance is only moderate.

Logarithms

integer-log

(integer-log a b) -> integer

Given two integers a and b, return the largest natural integer n such that b**n <= a.

factor-out-powers-of-2

(factor-out-powers-of-2 n) -> integer

Given an integer n, return two values: the smallest integer m such that n = m*2**k for some integer k, and the integer k.

factor-out-powers

(factor-out-powers a b) -> integer

Given integers a and b, return two values: the smallest integer m such that a = m*b**k for some integer k, and the integer k.