kahan_pairs

Generate pairs of integers.

This crate implements an algorithm described by Prof. W. Kahan to enumerate pairs of positive integers.

lib.rs:

Generate pairs of integers.

This crate implements an algorithm described by Prof. W. Kahan to enumerate pairs of positive integers.

Correctness

The results returned by this crate are correct for all values of n up to 2^52. Results for values of n greater than that may be incorrect, due to floating point imprecision.

no-std support

This crate has two features: std and libm. These features are mutually exclusive, and will cause a compile error if both are enabled simultaneously, or if neither are enabled.

The std feature is enabled by default, and allows the crate to use the f64 sqrt and trunc intrinsics, which are necessary for certain steps of the algorithm. If running in a no-std environment is desired, the std feature can be disabled, and the libm feature enabled, which will replace the use of the aforementioned intrinsics with the equivalent functions from libm.

Usage

use kahan_pairs::pairs;

let mut pairs = pairs();

assert_eq!(pairs.next(), Some((1, 1)));
assert_eq!(pairs.next(), Some((1, 2)));
assert_eq!(pairs.next(), Some((2, 1)));
assert_eq!(pairs.next(), Some((1, 3)));
assert_eq!(pairs.next(), Some((2, 2)));

Starting from 0 instead of 1:

use kahan_pairs::pairs_0;

let mut pairs = pairs_0();

assert_eq!(pairs.next(), Some((0, 0)));
assert_eq!(pairs.next(), Some((0, 1)));
assert_eq!(pairs.next(), Some((1, 0)));
assert_eq!(pairs.next(), Some((0, 2)));
assert_eq!(pairs.next(), Some((1, 1)));

Calculate for any n:

use kahan_pairs::nth_pair;

assert_eq!(nth_pair(100), (9, 6));
assert_eq!(nth_pair(99_999), (318, 130));

use kahan_pairs::nth_pair_0;

assert_eq!(nth_pair_0(105), (13, 0));
assert_eq!(nth_pair_0(99_999), (317, 129));