-
Enhancement
-
Resolution: Unresolved
-
Minor
-
None
-
None
-
Low
Add to package org.wildfly.common.math.
Requirements:
- Accept an int (and perhaps short, see below)
- Signed and unsigned variants
- Fast execution
- Low memory overhead, especially if never called
- Named to favor unsigned variants e.g. isPrime(int) vs isPrimeSigned(int)
Implementation ideas:
- Short-circuit for even numbers and 1
- Keep a table of short primes in the range 3 <= n <= 2^16; if the given value v is in this range then binary-search the table, else factor each prime up to sqrt(v) (could have an isPrime(short) variant to accomplish this, to which int values < 2^16 are delegated); if such a table is used, it should probably be binary-encoded (big-endian) in a resource file and read in to a short[] for spacial efficiency
- A fast sqrt(int) method could be useful, though it's unlikely to be faster than (int) Math.sqrt((float) value) on modern systems
- The signed variant eliminates Integer.MIN_VALUE (which is its own absolute value thanks to 2s complement, but is even thus not prime) and then does an unsigned test on abs(v) (because that's how it is)
Once this is done, add assert statements into HashMath to validate that the prime argument is indeed prime.