Perhaps this (factor of large big int) is a good perf/test case for https://github.com/JuliaLang/julia/pull/10084
On Sunday, 15 March 2015 06:54:51 UTC-7, Tim Holy wrote: > > I don't know the algorithm, but my point is that > c = a*b > will, for a BigInt, allocate memory. Because Numbers are immutable and > BigInts > are Numbers, you can't write an algorithm mult!(c, a, b) that stores the > result in a pre-allocated "scratch space" c. Hence, you're doomed to > inefficiency compared to an implementation in C that uses such tricks. > Don't get > me wrong, in the context of the overall Julia ecosystem our current design > is > right one (immutability is a really awesome and important property), but > there > are downsides. > > But you don't have to live with the status quo. If you need efficient > BigInt > calculations, perhaps a MutableBigInts.jl package would be in order. You > could > define an OpaqueBigInt type (which would _not_ be a subtype of Number) and > implement mult!(c, a, b), add!(c, a, b), etc for that type. You could > basically copy the bigint implementation in base. gmp.jl is only 500 lines > of > code and the changes might be very minimal, so you may be able to knock > this > out in an afternoon :-). That is, unless making them not-numbers has too > many > negative consequences. (You may find yourself creating additional methods > of > other functions.) > > Best, > --Tim > > On Sunday, March 15, 2015 06:39:23 AM Hans W Borchers wrote: > > Tim, sorry, I do not understand what you mean here. > > Do you argue that it is not possible to write a relatively fast > > implementation of, e.g., Pollard's Rho algorithm in Julia. > > > > On Sunday, March 15, 2015 at 2:19:47 PM UTC+1, Tim Holy wrote: > > > 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 > >
