On Wed, Mar 11, 2009 at 12:21 AM, Tassilo Horn <tass...@member.fsf.org> wrote: > Investigated it a bit more (doing the algorithm step by step in the > repl) and now I know what's the culprit: The `expt' function from the > math contrib library is dead slow.
Dead slow? Compared to what? A naive expt function just multiplies the base over and over again, but the library certainly doesn't do that. The expt function in the contrib library does bit-shifting and bit-anding on the power number to figure out a minimal number of multiplications to do. Certainly you're going to be limited a bit by the fact that Java's BigInteger isn't the fastest implementation, and Clojure does a bit of dispatching to handle each multiplication, but the overall expt strategy is fast, so I just don't see how it could be categorized as "dead slow". > > For number theory you often need things like > > (mod (expt n exp) m) Yes, and to make things like this fast, the trick is to perform the mod at each multiplication step, rather than waiting until the end. That is why Java's BigInteger library includes modPow, which you can use directly from Clojure. If that's a better fit for your application, you should use that instead. Or, you could create your own modPow by copying the expt-int function from the contrib library, and wrapping mod around each multiplication. This might be faster than Java's version if the modulus is small because BigInteger math can then be avoided altogether. Incidentally, the BigInteger library includes an isProbablePrime function as well, which again, you can just use directly from Clojure. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
