Function reikna::factor::quick_factorize_wsp

pub fn quick_factorize_wsp(val: u64, sprimes: &[u64]) -> Vec<u64>

Return a Vec<u64> of value's prime factorization, using sprimes as a list of small primes;

sprimes should be a sorted list of the prime numbers in [1, MAX_SMALL_NUM], or else this function will not behave properly. A suitable list can be generated using prime::prime_sieve(MAX_SMALL_NUM).

Alternatively, if only a few values are being factored, quick_factorize() can be used in lieu of this function and an explicit list of primes.

This function will factor "small" values, i.e., those less than MAX_SMALL_NUM, using prime::factorize_wp(), which in turn factors by trial division over a list of primes. This is the fastest way of factoring relatively small values.

Large values are factored using Brent's modification of Pollard's Rho Algorithm, implemented in the function rho().

Note this function can take a long time if the value being factored is a large prime or a value with one very large factor. The correct factorization will be returned for these values, but it is best to filter them out of any data set being factored before hand.

The factor list this function returns is sorted.

Examples

use reikna::factor::*;
use reikna::prime;
let sprimes = prime::prime_sieve(MAX_SMALL_NUM);
assert_eq!(quick_factorize_wsp(65_536, &sprimes), vec![2; 16]);
assert_eq!(quick_factorize_wsp(9_223_372_036_854_775_807, &sprimes), 
           vec![7, 7, 73, 127, 337, 92737, 649657]);