It's more than a question of which algorithm to use: the immutability of numbers means that every single bignum addition or multiplication requires allocation. So currently, julia is going to have a hard time competing with a hand-rolled method that allocates a cache of numbers to (re)use as scratch space for calculations. You can do this if you're willing to manage all these temporaries manually.
The best solution would be to make julia smart enough to do that "behind the scenes." This is a very interesting but nontrivial problem (with potential costs if it's "close but not smart enough"). --Tim On Friday, March 13, 2015 01:38:18 PM Hans W Borchers wrote: > That's right; I looked into the source of the 'gmp' package, > the C code in there is the same as the demo code you are linking to. > It uses Pollard's Rho and Miller Rabin for primality testing. > That code is under GPL license. > > As Miller Rabin is used for Julia's isprime() function, it would be nice > implement Pollard Rho in pure Julia and demo how fast it can be. > > But consider that there will be improvements and newer versions > of this algorithm that should be taken into account. > > On Friday, March 13, 2015 at 8:54:37 PM UTC+1, Simon Byrne wrote: > > The R gmp docs say that they use the Pollard Rho algorithm, and there is > > an implementation of it in the GMP demos directory: > > https://gmplib.org/repo/gmp/file/2d027c920892/demos/factorize.c > > > > So presumably they're using that code? > > > > simon > > > > On Friday, 13 March 2015 18:46:21 UTC, Steven G. Johnson wrote: > >> On Friday, March 13, 2015 at 1:25:14 PM UTC-4, Jake Bolewski wrote: > >>> This is falling back to factor() for generic integers, so the GMP method > >>> does not looked to be wrapped. The generic version will be terribly > >>> slow > >>> for bigints. Would be easy to add if you would like to submit a Pull > >>> Request. > >> > >> At first glance, I'm not seeing a built-in factorization method in GMP. > >> > >> Googling "factorization gmp" turns up a bunch of algorithms that people > >> > >> have built on top of GMP, but nothing in GMP itself. (We should see > >> what > >> algorithm/code R is using.)
