commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bill Barker" <wbar...@wilshire.com>
Subject Re: [math] Prime Numbers Library.
Date Mon, 13 Mar 2006 00:58:04 GMT

"Sharon Lourduraj" <sharon.lourduraj@gmail.com> wrote in message 
news:4414B5DA.5090101@gmail.com...
> 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].

> 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.

> 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 ;-).

>
> 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
>
> I will updated a full-fledged plan as time allows.
>
> Thanks,
> -Sharon
>
> P.S:
> Source 1: http://en.wikipedia.org/wiki/Primality_test
> Source 2: http://primes.utm.edu/prove/index.html 




---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message