Re: multiplying large numbers very quickly
- If you're interested in seeing how fast an implementation works on the
problem's dataset but you are exceeding the 2 second time limit, try this
Problem 439 is a copy of the fast multiplication challenge, but the
time limit is increased to 30 seconds. This is where I discovered that
the num library finishes in 4.5 seconds while the O(n^2) method
implemented with arrays takes >30 seconds.
4.5 seconds is pretty good imo, but considering that some people's c
and c++ entries complete in <1 second, I would think that there is
some room for improvement. Heck if java can do it, I sure hope ocaml
can. Curiously, the best non-c/c++ entry was haskell at 1.37 seconds.
I'm trying to code up a karatsuba implementation, but something tells
me that anything with arrays is going to kill ocaml. The only
alternative data structure I can think of so far is skipping the
string to int array conversion, and doing the math directly in the string.
Any algorithm more sophisticated than karatsuba is not going to be
possible for my level of education, unfortunately. Karatsuba is hard
- --- "William D. Neumann" <wneumann@...> wrote:
> If that's the case, unless you can call out to anotherSurely you mean fun, not painful.
> library, like gmp or numerix (I might try that after lunch),
> you're going to need to code it up yourself (which would
> likekly be painful).
Do you Yahoo!?
Everyone is raving about the all-new Yahoo! Mail beta.
- Radu Grigore wrote:
> --- "William D. Neumann" <wneumann@...> wrote:If this exercise was an end in itself, then yes it would be fun, but...
>> If that's the case, unless you can call out to another
>> library, like gmp or numerix (I might try that after lunch),
>> you're going to need to code it up yourself (which would
>> likekly be painful).
> Surely you mean fun, not painful.
if its is simply a means to an end then it most certainly will be a pain.
> Do you Yahoo!?
> Everyone is raving about the all-new Yahoo! Mail beta.
> Archives up to November 11, 2006 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.
> Yahoo! Groups Links