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

Details

    • Enhancement
    • Resolution: Unresolved
    • Minor
    • None
    • None
    • Low

    Description

      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.

      Attachments

        Activity

          People

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

            Dates

              Created:
              Updated: