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
