Also, I've not looked at any of the math code in clojure contrib, but expressed as such, I wouldn't expect the idiom "(mod (expt n exp) m)" to be at all fast for reasons largely independent of the numeric implementation underneath.
Computing the entire power and then reducing it modulo m is going to be gruesome at the number sizes you'll expect in cryptographic or computational number theory applications. Even if BigInteger were faster, you're going to be giving that code much less of a workout using "repeated squaring" or the "binary algorithm." There seems to be a decent wikipedia writeup on it at http://en.wikipedia.org/wiki/Modular_exponentiation and if you want more details and options, Shallit and Bach's "Algorithmic Number Theory" (http://www.amazon.com/Algorithmic-Number- Theory-Vol-Foundations/dp/0262024055) is a good place to look. I had thought a while back about digging into building some math code for clojure contrib for applications like algebra and number theory, since Clojure's Lispyness makes it well suited for that, but wasn't sure anybody else was especially interested. I was also thinking about throwing together an interval arithmetic package that would have been useful to me on a now concluded project, but never got around to it. Are there Clojurers out there doing math-intensive stuff with regularity? Jerry On Mar 11, 5:41 am, Jeffrey Straszheim <straszheimjeff...@gmail.com> wrote: > Probably. The Java BigInteger classes are not particularly fast, and do not > seem to be a priority to Sun. Therefore Clojure is not competitive on large > integer algorithms. > > On Wed, Mar 11, 2009 at 2:21 AM, Tassilo Horn <tass...@member.fsf.org>wrote: > > > > > Phil Hagelberg <p...@hagelb.org> writes: > > > Hi Phil, > > > >> If not, is there better way than inserting gazillions of printlns to > > >> check why and where a function doesn't do the right thing? > > > > Most definitely! Break your functions up into smaller pieces, then > > > write tests for them using test-is. If your functions are hard to > > > test, it's probably because they need to be broken out differently. > > > Yeah, might be. To get started with clojure I tried to translate the > > Miller-Rabin pseudo prime algorithm from wikipedia. Basically it seems > > to work correctly, but the preformance is really bad for numbers above a > > certain limit. > > > 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. > > > For number theory you often need things like > > > (mod (expt n exp) m) > > > where the exponent may be very huge. Is that something which cannot be > > done faster in Clojure because of the Java Integer/BigInteger stuff? > > That would be a shame! I just fell in love with clojure cause the code > > looks that concise and right! > > > Bye, > > 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 -~----------~----~----~----~------~----~------~--~---
