Crate kahan_pairs

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

Structs

• Pairs
  An iterator over every unique pair of positive integers, excluding 0
• Pairs0
  An iterator over every unique pair of positive integers, including 0

Functions

• get_nth_pair
  Infallibly return the nth pair of positive integers, according to the crate’s namesake algorithm
• get_nth_pair_0
  Infallibly return the nth pair of positive integers, according to a version of the crate’s namesake algorithm that includes 0 in the output
• nth_pair
  Return the nth pair of positive integers, according to the crate’s namesake algorithm
• nth_pair_0
  Return the nth pair of positive integers, according to a version of the crate’s namesake algorithm that includes 0 in the output
• pairs
  Return an iterator that enumerates every unique pair of positive integers, excluding 0
• pairs_0
  Return an iterator that enumerates every unique pair of positive integers, including 0
• try_nth_pair
  Return the nth pair of positive integers, according to the crate’s namesake algorithm, or None if n == 0
• try_nth_pair_0
  Return the nth pair of positive integers, according to a version of the crate’s namesake algorithm that includes 0 in the output, or None if n == 0