Uploaded image for project: 'WildFly Common'
  1. WildFly Common
  2. WFCOM-8

Fast method to determine if a number is prime (great student project!)

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: Minor 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.

              Unassigned Unassigned
              dlloyd@redhat.com David Lloyd
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

                Created:
                Updated: