Hans, it would be interesting to see how your Pollard Rho example compares on the pooling bigint branch https://github.com/JuliaLang/julia/pull/10084. It ought to allocate far less memory...
On 20 March 2015 at 00:01, Hans W Borchers <[email protected]> wrote: > As Bill noted, it is known that Pollard Rho does not "perform comparably > for > all numbers of the same size." Still I got interested in trying it out > myself. > I wrote a simple implementation and got this result: > > julia> n = big(3)^100 + 2 > julia> @time factorize(n) > elapsed time: 74.539066901 seconds (5360852768 bytes allocated, 23.12% > gc time) > Dict{BigInt,Int64} with 3 entries: > 246451584544723 => 1 > 31721 => 1 > 65924521656039679831393… => 1 > > So I, as Bill would say, "was lucky." Of course, this is not of real use, > but > I learned some things, and I learned that Julia with BigInt may not yet be > ready for number theory applications. > > > > On Thursday, March 19, 2015 at 11:26:10 PM UTC+1, [email protected] > wrote: >> >> Tim is correct in a sense. I translated some big int code a while ago, I >> think it was the pollard rho method (don't quite remember the details) and >> the inability to reuse storage for a bigint caused a big performance hit. >> (I thought about some workaround, but unfortunately I don't remember what >> it was or if I even tried it) >> >> Stefan wrote a simple stop-gap factor() routine and noted in a comment >> that it needs to be improved. But Bill Hart is correct: It can't do 3^100 + >> 2 no matter how efficient bigint arithmetic is. >> >> The Maxima routines and the perl module by Dana Jacobsen are good, but >> they would require translating and asking the authors to liberalize the >> license. >> >> I wrapped the msieve c library. >> >> https://github.com/jlapeyre/PrimeSieve.jl >> >> It does 3^100 + 2 in less than a second on my machine >> >> On Friday, March 13, 2015 at 6:20:16 PM UTC+1, Hans W Borchers wrote: >>> >>> I got interested in factorizing some larger integers such as N = 3^100 + >>> 2 . >>> In all tries, factor(N) did not return and had to be interrupted: >>> >>> julia> N = big(3)^100 + 2 >>> julia> factor(N) >>> ^CERROR: interrupt >>> in finalizer at ./base.jl:126 >>> in + at gmp.jl:243 >>> in factor at primes.jl:111 >>> >>> It is calling GMP, but the GMP software cannot be the reason as this >>> works >>> with the GMP package in R and returns the factorization within seconds: >>> >>> R> library(gmp) >>> R> N <- bigz(3)^100 >>> R> factorize(N) >>> Big Integer ('bigz') object of length 3: >>> [1] 31721 246451584544723 65924521656039679831393482841 >>> R> system.time(factorize(N)) >>> user system elapsed >>> 3.738 0.000 3.730 >>> >>> Is this a bug? Did I do something wrong? >>> The first factor, 31721, is not even large. Mathematical software such >>> as >>> GAP or PARI/GP will factorize this in much less than a second. >>> >>> PS: Versioninfo >>> Julia Version 0.3.6; System: Linux (x86_64-linux-gnu) >>> CPU: Intel(R) Core(TM) i3-3217U CPU @ 1.80GHz; WORD_SIZE: 64 >>> BLAS: libblas.so.3; LAPACK: liblapack.so.3 >>> LIBM: libopenlibm; LLVM: libLLVM-3.3 >>> >>
