Vectorized Prime Factorization
primeFactorize.RdImplementation 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.
Arguments
- v
Vector of integers or numeric values. Non-integral values will be cured to whole numbers.
- namedList
Logical flag. If
TRUEand thelength(v) > 1, a named list is returned. The default isFALSE.- nThreads
Requested number of threads. The default is
NULLfor serial execution. Requests are capped by the available hardware and the useful work in the calculation. Small or simple cases may use fewer threads.
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) == 1regardless of the value ofnamedList. 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. Ifmax(bound1, bound2)\(< 2^{31}\), the class of each vector will be integer, otherwise the class will be numeric.
Examples
## Get the prime factorization of a single number
primeFactorize(10^8)
#> [1] 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5
## Or get the prime factorization of many numbers
set.seed(29)
myVec <- sample(-1000000:1000000, 1000)
system.time(pFacs <- primeFactorize(myVec))
#> user system elapsed
#> 0.001 0.000 0.000
## Return named list
pFacsWithNames <- primeFactorize(myVec, namedList = TRUE)
## Using nThreads
system.time(primeFactorize(myVec, nThreads = 2))
#> user system elapsed
#> 0.001 0.000 0.001