On 3/12/06, Bill Barker <[EMAIL PROTECTED]> wrote: > > "Sharon Lourduraj" <[EMAIL PROTECTED]> wrote in message > news:[EMAIL PROTECTED] > > Hello, > > > > Thank you for the positive input on implementing Prime Number functions. I > > have created a 'wish' on the Math Wish List page. I would like to lay out > > an initial plan before everyone starts to jump into coding the algorithms. > > > > Here is the base "off-my-head" plan, in the order that might prove the > > implementation to be of positive value, also the order of difficulty: > > > > 1. Implement naive primality (quick tests, but are slow for large numbers) > > testing algorithms. These algorithms are not very fast and are mainly > > intended for small numbers. Some involve trial and error methods. Some > > involve generating a sieve, as aligned, to test the given number and > > derive result from the contents of the sieve. > > > > +1 IMHO, this really should be a part of [math].
+1 for API, +0 for naive implementation. I am OK with starting with naive implementations to get the API right, which is a strategy that we have used before, but need to make sure the design will support robust impls. > > > 2. Implement probabilistic testing (classical tests) algorithms. These > > algorithms include tests that identify a number as a probable-prime, of > > course using logical deduction (Fermat, Miller-Rabin, etc.) theorized by > > mathematicians. These algorithms are relatively fast for large numbers, > > but are sophisticated. They do contain a calculated error margin. > > > > Currently, [math] doesn't support integer calculations bigger than 'int'. > It could do 'long', but it's really not much of an improvement in this area. > It's really is going to need a BigInteger class simply to handle the 2048+ > bit integers that are of interest to crypto providers. Of course, the > number theorests will want much larger :). > > And, yes, I'm volunteering. What about the jdk-supplied class? I don't know anything about the implementation, but this class also supports a probablePrime method that takes a Random and bit length as arguments. We could provide one of our own (Random's) there and leverage the primitives in this class. Assm you mean using or extending this, or accomodating BigIntegers in the API. Or is the jdk impl not usable? > > > 3. Implement General purpose testing algorithms. These algorithms are > > extremely advanced. They are significantly faster than any other > > algorithms. Some of these algorithms have been widely accepted to work, > > but are based on conjectures that have still not been proved true (but > > are widely assumed to be). These algorithms will significantly test our > > brains and the scope of [math]. > > > > Bring it on ;-). +1 and of course the Riemann hypothesis is true ;-P > > > > > Alright, all that thoughts are off my head now. Feel free to make any > > corrections, I do not have much knowledge of advanced algorithms just a > > keen interest. Also, feel free to make suggestions. > > > > I have created a wiki entry :-) > > http://wiki.apache.org/jakarta-commons/PrimeNumbers Thanks!! Phil --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
