RcppAlgos - High Performance Tools for Combinatorics and Computational Mathematics

Provides optimized functions and flexible combinatorial iterators implemented in C++ for solving problems in combinatorics and computational mathematics. Utilizes the RMatrix class from 'RcppParallel' for thread safety. There are combination/permutation functions with constraint parameters that allow for generation of all results of a vector meeting specific criteria (e.g. generating integer partitions/compositions or finding all combinations such that the sum is between two bounds). Capable of generating specific combinations/permutations (e.g. retrieve only the nth lexicographical result) which sets up nicely for parallelization as well as random sampling. Gmp support permits exploration where the total number of results is large (e.g. comboSample(10000, 500, n = 4)). Additionally, there are several high performance number theoretic functions that are useful for problems common in computational mathematics. Some of these functions make use of the fast integer division library 'libdivide'. The primeSieve function is based on the segmented sieve of Eratosthenes implementation by Kim Walisch. It is also efficient for large numbers by using the cache friendly improvements originally developed by Tomás Oliveira. Finally, there is a prime counting function that implements Legendre's formula based on the work of Kim Walisch.

Last updated 1 months ago

combinationscombinatoricsfactorizationnumber-theoryparallelpermutationprime-factorizationsprimesieve

9.85 score 45 stars 12 packages 146 scripts 1.5k downloads

RcppBigIntAlgos - Factor Big Integers with the Parallel Quadratic Sieve

Features the multiple polynomial quadratic sieve (MPQS) algorithm for factoring large integers and a vectorized factoring function that returns the complete factorization of an integer. The MPQS is based off of the seminal work of Carl Pomerance (1984) <doi:10.1007/3-540-39757-4_17> along with the modification of multiple polynomials introduced by Peter Montgomery and J. Davis as outlined by Robert D. Silverman (1987) <doi:10.1090/S0025-5718-1987-0866119-8>. Utilizes the C library GMP (GNU Multiple Precision Arithmetic). For smaller integers, a simple Elliptic Curve algorithm is attempted followed by a constrained version of Pollard's rho algorithm. The Pollard's rho algorithm is the same algorithm used by the factorize function in the 'gmp' package.

Last updated 6 months ago

algorithmgmpinteger-factorizationmpqsprime-factorizationsprimesquadratic-sievequadratic-sieve-algorithm

3.81 score 13 stars 8 scripts 257 downloads