Mark Engelberg <mark.engelb...@gmail.com> writes: Hi Mark,
> 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? Sorry, I didn't want to be offensive, and indeed I also was false. ;-) I've written the same code with Common Lisp and Rupy and thought that it was much faster at least in the former. But that's not really true. Even in CL it takes ages for big exponents. > 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". Yes, you're right. >> 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. Cool, thanks for the tip. > 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. Even better. > Incidentally, the BigInteger library includes an isProbablePrime > function as well, which again, you can just use directly from Clojure. Yeah, but my motivation was only to get going with clojure. So I'll integrate the "mod each pow step" tip and be happy. Maybe I'll poste the code to get some feedback on where I could benefit from some clojure idioms. Bye and thanks a lot for the tips, Tassilo --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
