primeFactorize: Vectorized Prime Factorization

In RcppAlgos: High Performance Tools for Combinatorics and Computational Mathematics

Vectorized Prime Factorization

Description

Implementation of Pollard's rho algorithm for generating the prime factorization. The algorithm is based on the "factorize.c" source file from the gmp library found here https://gmplib.org.

Usage

primeFactorize(v, namedList = FALSE, nThreads = NULL)

Arguments

v	Vector of integers or numeric values. Non-integral values will be cured to whole numbers.
namedList	Logical flag. If TRUE and the length(v) > 1, a named list is returned. The default is FALSE.
nThreads	Specific number of threads to be used. The default is NULL.

Details

As noted in the Description section above, this algorithm is based on the "factorize.c" source code from the gmp library. Much of the code in RcppAlgos::primeFactorize is a straightforward translation from multiple precision C data types to standard C++ data types. A crucial part of the algorithm's efficiency is based on quickly determining primality, which is easily computed with gmp. However, with standard C++, this is quite challenging. Much of the research for RcppAlgos::primeFactorize was focused on developing an algorithm that could accurately and efficiently compute primality.

For more details, see the documentation for isPrimeRcpp.

Value

• Returns an unnamed vector if length(v) == 1 regardless of the value of namedList. If v < 2^{31}, the class of the returned vector will be integer, otherwise the class will be numeric.

• If length(v) > 1, a named/unnamed list of vectors will be returned. If max(bound1, bound2) < 2^{31}, the class of each vector will be integer, otherwise the class will be numeric.

Note

The maximum value for each element in v is 2^{53} - 1.

Author(s)

Joseph Wood

References

• Pollard's rho algorithm

• Miller-Rabin primality test

• Accurate Modular Arithmetic with Double Precision

• 53-bit significand precision

See Also

primeFactorizeSieve, factorize

Examples

## Get the prime factorization of a single number
primeFactorize(10^8)

## Or get the prime factorization of many numbers
set.seed(29)
myVec <- sample(-1000000:1000000, 1000)
system.time(pFacs <- primeFactorize(myVec))

## Return named list
pFacsWithNames <- primeFactorize(myVec, namedList = TRUE)

## Using nThreads
system.time(primeFactorize(myVec, nThreads = 2))

RcppAlgos documentation built on May 29, 2024, noon