Here's the test class.
/// Test class for the prime-sequence primality checker types.
public final class PrimeSequnceTimingTests<Integer: PrimePrefixSampleProvider & FixedWidthInteger>: XCTestCase {
/// Returns the odd number the argument is the generator for.
///
/// (Technically, this can work for any `FixedWidthInteger`.)
static func oddNumber(for x: Integer) -> Integer? {
guard let one = Integer(exactly: 1), let two = Integer(exactly: 2) else { return nil }
let (product, multiplyfailed) = x.multipliedReportingOverflow(by: two)
guard !multiplyfailed else { return nil }
let (sum, addfailed) = product.addingReportingOverflow(one)
guard !addfailed else { return nil }
return sum
}
/// Determines if the argument is prime via repeated trial division.
///
/// (Technically, this can work for any `BinaryInteger`.)
static func isPrime(_ x: Integer) -> Bool {
guard x > 1 else { return false }
var n: Integer = 2
while n < x {
let (q, r) = x.quotientAndRemainder(dividingBy: n)
guard r != 0 else { return false } // Got composite
guard q > n else { break } // Reached square root of self
n += 1
}
return true
}
/// Test using wheel factorization by otherwise exhaustive trial division.
func test01aUncachedTrialDivsionTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: TrialDivisionPrimeChecker.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with exhaustive trial division.
func test01bUncachedTrialDivsionTests() {
let primes = LimitedArithmeticProgression<Integer>(from: 2, by: +1)!.filter(Self.isPrime)
measure {
XCTAssertTrue( primes.starts(with: Integer.primePrefix) )
}
}
/// Test using wheel factorization by trial division while caching the
/// post-wheel primes in an array.
func test02aArrayCachedTrialDivisonTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: ArrayCachingTrialDivisionPrimeChecker.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with trial divsion while caching discovered primes in an array.
func test02bArrayCachedTrialDivisonTests() {
let primes = LimitedPrimalityViaTrialDivisionSequence<Integer>().filter { $0.1 }.map { $0.0 }
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test using wheel factorization by trial division while caching the
/// post-wheel primes in a linked list.
func test03aListCachedTrialDivsionTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: ListCachingTrialDivisionPrimeChecker.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with trial division while caching discovered primes in a linked
/// list.
func test03bListCachedTrialDivsionTests() {
let primes = LimitedPrimalityViaTrialDivisionNodesSequence<Integer>().filter { $0.1 }.map { $0.0 }
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test using wheel factorization with the Sieve of Eratosthenes while
/// tracking prime multiples with an array-based priority queue.
func test04aPriorityQueueEratosthenesSieveTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: LimitedPriorityQueueEratosthenesSieve.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with the Sieve of Eratosthenes while tracking prime multiples with
/// an array-based priority queue.
func test04bPriorityQueueEratosthenesSieveTests() {
let primes = LimitedPrimalitySequence<Integer>().filter { $0.1 }.map { $0.0 }
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test using wheel factorization with the Sieve of Eratosthenes while
/// tracking values with a dicitionary from composites to a set of their
/// prime factors.
func test05aSetDictionaryEratosthenesSieveTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: LimitedSetDictionaryEratosthenesSieve.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with the Sieve of Eratosthenes while tracking values with a
/// dictionary from composites to a set of their prime factors.
func test05bSetDictionaryEratosthenesSieveTests() {
let primes = LimitedPrimalityViaSetsSequence<Integer>().filter { $0.1 }.map { $0.0 }
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test using wheel factorization with the Sieve of Eratosthenes while
/// tracking values with a dictionary from composites to a linked list of
/// their (minimally allocated) prime factors.
func test06aListDictionaryEratosthenesSieveTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: LimitedListDictionaryEratosthenesSieve.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with the Sieve of Eratosthenes while tracking values with a
/// dictionary from composites to a linked list of their (minimally
/// allocated) prime factors.
func test06bListDictionaryEratosthenesSieveTests() {
let primes = LimitedPrimalityViaNodesSequence<Integer>().filter { $0.1 }.map { $0.0 }
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
#if false
/// Test using wheel factorization with the Sieve of Sundaram while tracking
/// the progression of `(i, j)` pairs with a priority queue.
func test07aPriorityQueueSundaramSieveTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: LimitedPriorityQueueSundaramSieve.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with the Sieve of Sundaram while tracking the progression of
/// `(i, j)` pairs with a priority queue.
func test07bPriorityQueueSundaramSieveTests() {
let one = Integer(1), two = Integer(2)
let firstElement = CollectionOfOne(two)
let secondElementFirstSource = LimitedArithmeticProgression(from: one, by: +1)!
let secondElementSecondSource = LimitedOddCompositesHalvedFlooredSequence<Integer>()
let secondElementMergedSource = secondElementFirstSource.mergeSortedAsSets(with: secondElementSecondSource, keeping: .exclusivesFromFirst)
let secondElements = secondElementMergedSource.compactMap(Self.oddNumber(for:))
let primes = firstElement.cojoin(with: secondElements)
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
#endif
/// Test using wheel factorization with the Sieve of Sundaram while tracking
/// odd multiples directly with a priority queue.
func test07cPriorityQueueSundaramSieveTests() {
let primes = Integer.primeSequence(withPrimeBasisCount: 3, checkingWith: LimitedPriorityQueueSundaramSieveToo.self)!
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
/// Test with the Sieve of Sundaram while tracking odd multiples directly
/// with a priority queue.
func test07dPriorityQueueSundaramSieveTests() {
let two = CollectionOfOne<Integer>(2)
let odds = LimitedArithmeticProgression<Integer>(from: 3, by: +2)!
let oddComposites = LimitedOddCompositeSequence<Integer>()
let oddPrimes = odds.mergeSortedAsSets(with: oddComposites, keeping: .exclusivesFromFirst)
let primes = two.cojoin(with: oddPrimes)
measure {
XCTAssertTrue(primes.starts(with: Integer.primePrefix))
}
}
}
The PrimePrefixSampleProvider protocol lets me test against all the primes:
/// Vends the first few primes to test prime-generating sequences.
public protocol PrimePrefixSampleProvider: BinaryInteger {
/// Provides the first few primes.
static var primePrefix: [Self] { get }
}
I made complete lists for Int8, UInt8, Int16 and UInt16 (from downloading lists from the Internet). Since it's a prefix, we don't need an exhaustive list for 32 bits and above.
The "b" (and one "d") tests use custom sequences to generate prime numbers, either directly or after some sequence operations. Towards the end, I wondered if a specialized custom protocol and sequence would work better; those are run by the "a" (and one "c") tests.
/// A type that performs incremental primality tests.
///
/// If a conforming checker doesn't unconditionally succeed in its initializer,
/// it should document what values of a basis make it fail.
///
/// Due to the timing on how comformers to this type are supposed to interact
/// with `LimitedPrimeSequence`, conforming instances shouldn't be used except
/// through `LimitedPrimeSequence` and any user-created work-alikes.
public protocol WheeledPrimeChecker {
/// The type of integers tested by the checker.
associatedtype Integer: BinaryInteger
/// Creates a checker over the positive integers coprime to the integers
/// in the given sequence.
///
/// - Precondition: If not empty, `basis` stores the first few primes,
/// starting from 2, without gaps.
///
/// - Parameter basis: A list of the first few primes. May be empty.
/// - Postcondition: The checker may read the `basis` and cache it or any
/// other information from it that may help during calls to `isNextPrime`.
/// If `basis` has an unacceptable value, emit `nil`.
init?<S: Sequence>(basis: S) where S.Element == Integer
/// Returns whether the given value is prime, while allowing the check to
/// mutate internal state.
///
/// - Precondition:
/// - `coprime > 1`.
/// - Subsequent submitted values are strictly increasing.
/// - `coprime` is coprime to all the integers in the sequence submitted
/// to the initializer.
///
/// - Parameter coprime: The value to test for primality.
/// - Returns: `true` if `coprime` is prime; otherwise, `false`.
/// - Postcondition: This checker may adjust its internal state to record
/// `coprime` and/or facilitate future calls to this method.
mutating func isNextPrime(_ coprime: Integer) -> Bool
}
/// A sequence of the first few primes.
public struct LimitedPrimeSequence<Checker: WheeledPrimeChecker>: LazySequenceProtocol where Checker.Integer: FixedWidthInteger { /*...*/ }
extension FixedWidthInteger {
/// Returns a sequence of all the primes that fit into this type, aided by a
/// factorization wheel of the given length and a primality checker of the
/// given type.
///
/// If the method can determine if the computed factorization wheel basis is
/// long enough that all the coprimes are prime (determined when the largest
/// base is greater than the square root of `Self.max`), use of a primality
/// checker is skipped.
///
/// - Precondition:
/// - `count >= 0`.
/// - `count` isn't greater than the number of primes that fit within
/// the bounds of `Self.max`.
///
/// - Parameter count: The number of initial primes used in the basis.
/// - Parameter type: A metatype specifier for the predicate that tests if
/// given strictly-increasing values are prime.
/// - Returns: A sequence of all the prime supported by this type, starting
/// with those generated for the basis, then all of the integers coprime
/// to the basis's elements, after filtering out the composite values.
///
/// - Complexity: O(*n*!), where *n* is the last prime in the generated
/// basis (or 1 when said basis is empty). However, the calculations will
/// most likely finish early since factorials quickly surpass
/// `Self.max`.
public static func primeSequence<C: WheeledPrimeChecker>(withPrimeBasisCount count: Int, checkingWith type: C.Type) -> LimitedPrimeSequence<C>? where C.Integer == Self
}
Factorization wheels, which are used by the framework, are generated incrementally:
/// A sequence of factorization wheels for the first few primes.
public struct LimitedPrimeFactorizationWheelSequence<Integer: FixedWidthInteger>: LazySequenceProtocol { /*...*/ }
// The element type of the above is LimitedWheelFactorizedCoprimeSequence below.
Where a wheel is expressed as an arithmetic progression that filters out all the numbers that are multiples of at least one basis prime:
/// A sequence of the integers filtered through a prime factorization wheel.
public struct LimitedWheelFactorizedCoprimeSequence<Integer: FixedWidthInteger> { /*...*/ }
There are methods to return a wheel based on the desired length, or an optimized one.
extension FixedWidthInteger {
/// Returns a factorization wheel of the given length, along with that
/// length of initial primes used as the wheel's basis.
///
/// If the returned basis is not empty, and its last element is greater than
/// the square root of `Self.max`, then all of the returned wheel's elements
/// after the first are prime.
///
/// - Precondition:
/// - `length >= 0`.
/// - `length` isn't greater than the number of primes that fit within
/// the bounds of `Self.max`.
///
/// - Parameter length: The number of initial primes used in the basis. The
/// wheel's circumference will be the product of those primes, and its
/// (initial) spokes will be the integers less than the circumference that
/// are coprime to all of the primes in the basis.
/// - Returns: A tuple whose first member is an array of the first `length`
/// primes, and whose second member is a sequence the vends every positive
/// integer that is coprime to the values in the basis array. This method
/// will return `nil` instead if `length` is out-of-range.
public static func primeFactorizationWheel(ofLength length: Int) -> (basis: [Self], wheel: LimitedWheelFactorizedCoprimeSequence<Self>)?
/// Returns a factorization wheel sized for this integer type, along with
/// the basis for said wheel.
///
/// Due to diminishing returns, the 2/3/5/7 wheel is the highest one that
/// can be returned.
///
/// - Returns: A tuple whose first member is the first few primes, up to 7,
/// but not exceeding what `Self` can support. The second member is a
/// sequence that vends every positive integer that is coprime to the
/// values in the basis array.
public static func bestPrimeFactorizationWheel() -> (basis: [Self], wheel: LimitedWheelFactorizedCoprimeSequence<Self>)
}
The LimitedArithmeticProgression generic type is a lazy Sequence (and Collection) that takes the given FixedWidthInteger starting value and a Stride between each new value until .min or .max is reached (or would be surpassed).
The LimitedPrimalityViaTrialDivisionSequence and LimitedPrimalityViaTrialDivisionNodesSequence generic types are the custom sequences to test primality via trial division, but cache any discovered primes with an Array or custom linked list type, respectively.
The LimitedPrimalitySequence, LimitedPrimalityViaSetsSequence, and LimitedPrimalityViaNodesSequence generic types are custom sequences to test primality with a custom streaming variant of the Sieve of Eratosthenes. The first version uses a custom priority queue type, storing nodes containing a pair of a composite value and one of its prime factors. The queue is a minimum heap on the composite member. The other two sequences store a dictionary where the key is a composite integer and the value is a container of the composite's prime factors up to its square root. One design stores the primes in a Set, the other in a custom linked list type. An advantage of the linked list is that once a node for a prime integer is made, it's simply passed up to the next multiple; the Set design has to recreate nodes for each prime every time one of its multiples is processed.
The LimitedOddCompositesHalvedFlooredSequence generic type stores a priority queue on the i and j values for each combination of 1 <= i <= j. The queue is a minimum heap on the generator, which is i + j + 2 * i * j. The first node, with values i = 1, j = 1, and cached = 4 is preloaded. Every time a node's cached value is vended, we make new nodes for i -> i + 1 and j -> j + 1, so the total nodes stored goes up by 1 almost every time.
There are types to provide a set-subtraction (or other set combinations) or join two arbitrary sequences sharing an Element type.
The LimitedOddCompositeSequence generic type stores a priority queue to directly vend each odd composite integer in order. The nodes are arithmetic progressions for each odd number greater than 1, each inner sequence vending its target odd multiples starting with the target number times 3. Upon each vending, the currently smallest of all the first elements of each queued progression is returned, then that progression is updated to pop the just returned element.