Loading ...
Sorry, an error occurred while loading the content.

Re: multiplying large numbers very quickly

Expand Messages
  • jshaw10
    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
    Message 1 of 8 , Dec 5, 2006
    • 0 Attachment
      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

      http://www.spoj.pl/problems/TMUL/

      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
      enough. :(
    • Radu Grigore
      ... Surely you mean fun, not painful. ____________________________________________________________________________________ Do you Yahoo!? Everyone is raving
      Message 2 of 8 , Dec 5, 2006
      • 0 Attachment
        --- "William D. Neumann" <wneumann@...> wrote:
        > 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.




        ____________________________________________________________________________________
        Do you Yahoo!?
        Everyone is raving about the all-new Yahoo! Mail beta.
        http://new.mail.yahoo.com
      • Hugo Ferreira
        ... If this exercise was an end in itself, then yes it would be fun, but... if its is simply a means to an end then it most certainly will be a pain.
        Message 3 of 8 , Dec 6, 2006
        • 0 Attachment
          Radu Grigore wrote:
          > --- "William D. Neumann" <wneumann@...> wrote:
          >> 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 this exercise was an end in itself, then yes it would be fun, but...
          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.
          > http://new.mail.yahoo.com
          >
          >
          > 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
          >
          >
          >
          >
        Your message has been successfully submitted and would be delivered to recipients shortly.