Technical Tips

Return-Path: Received: from pacific-carrier-annex.mit.edu by po10.mit.edu (8.9.2/4.7) id SAA10072; Tue, 6 Aug 2002 18:24:37 -0400 (EDT) Received: from hermes.sun.com (hermes.sun.com [64.124.140.169]) by pacific-carrier-annex.mit.edu (8.9.2/8.9.2) with SMTP id SAA00803 for ; Tue, 6 Aug 2002 18:24:36 -0400 (EDT) Date: 6 Aug 2002 12:24:33 -0800 From: "JDC Tech Tips" To: alexp@mit.edu Message-Id: <197041071928150221@hermes.sun.com> Subject: Core Java Technologies Tech Tips, August 6, 2002 (Prime Numbers, Overloading) Mime-Version: 1.0 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: SunMail 1.0 Technical Tips

View this issue as simple text August 6, 2002

Generating Prime Numbers
When Not to Overload Methods

These tips were developed using Java^TM 2 SDK, Standard Edition, v 1.4.

This issue of the Core Java Technologies Tech Tips is written by Glen McCluskey.

Generating Prime Numbers

A prime number is an integer greater than 1, with only itself and 1 as divisors. The first few primes are 2, 3, 5, 7, 11, and 13.

This tip examines two ways of generating primes. The first approach works for relatively small (32-bit) prime numbers. The second uses the BigInteger class to generate large primes (typically hundreds or thousands of digits).

Here's an example of where prime numbers are used. Suppose that you're working on a custom hash table scheme. You know that there will be about 1000 entries in the table, and you want the table to be no more than two thirds full, relative to the number of slots available. This implies a table size of 1500. A common hash table algorithm uses a table size that's prime, in order to reduce the number of collisions. So you need to find a prime number with a value near 1500. How can you do this? Here's one way:

    public class PrimeDemo1 {
    
        // check whether a number is prime
    
        static boolean isPrime(int n) {
    
            // 2 is the smallest prime
    
            if (n <= 2) {
                return n == 2;
            }
    
            // even numbers other than 2 are not prime
    
            if (n % 2 == 0) {
                return false;
            }
    
            // check odd divisors from 3
            // to the square root of n
    
            for (int i = 3, end = (int)Math.sqrt(n);
            i <= end; i += 2) {
                if (n % i == 0) {
                    return false;
                }
            }
    
            return true;
        }
    
        // find the smallest prime >= n
    
        static int getPrime(int n) {
            while (!isPrime(n)) {
                n++;
            }
            return n;
        }
    
        public static void main(String args[]) {
            System.out.println(getPrime(1500));
        }
    }

The PrimeDemo1 program defines an isPrime method. The method handles the special case of 2 (which is prime). It then screens out other positive even numbers (which are not prime, because they have 2 as a divisor). The isPrime method then tries odd divisors starting at 3 and going up to the square root of the number.

The output of the program is:

that is, 1511 is the smallest prime of value 1500 or above.

This approach does the job, and is reasonably fast. But it has a couple of shortcomings. One problem is that you can't use the program to generate prime numbers above 32 bits (about 10 decimal digits). (To convert a number of bits to an approximate number of decimal digits, multiply by log10(2), or 0.301).

Some applications require very long primes, such as 2048 bits (approximately 615 digits). An example is encryption, which relies on the idea that the product of two large primes cannot readily be factored into those primes -- except by a brute-force attack using very large amounts of computer time.

Even if the PrimeDemo1 program could somehow represent very long numbers, there is another problem. Trying all odd divisors up to the square root is a hopelessly inefficient technique for generating prime numbers, when the numbers are really big. Here, another approach is required.

There is indeed a very fast way to generate large primes, but with a catch. The generated numbers are probably prime, but there is a slight chance that they might not be. The standard set by ANSI X9.80 specifies a certainty for use in private-key encryption: the probability that a generated prime is actually prime is greater than 1 minus 1/2 to the 100th power. So there's less than a 1 in 2 to the 100th power chance that a generated number is not prime. 1 in 2 to the 100th power is about 1 in 1.27 times 10 to the 30th power, which is indeed a very low probability.

Given this background, how do you actually generate a big prime? Here's a simple example:

    import java.math.BigInteger;
    import java.util.Random;
    
    public class PrimeDemo2 {
        public static void main(String args[]) {
            Random rnd = new Random(0);
    
            // obtain a 100-bit probable prime, 
            // with the probability that the number 
            // is composite at less than 
            // 1 in 2 to the 100th power
    
            BigInteger prime = 
                    BigInteger.probablePrime(100, rnd);
    
            System.out.println(prime);
        }
    }

This program generates a 100-bit prime, using the passed-in Random object as a source of random values. The output of the program is:

    689572171629632424814677540353

The probablePrime method generates a 100-bit number, and then subjects that number to certain tests of primality, called the Miller-Rabin and Lucas-Lehmer tests.

How fast does probablePrime run? Let's look at a final example to help answer this question:

    import java.math.BigInteger;
    import java.util.Random;

    public class PrimeDemo3 {
        public static void main(String args[]) {
            for (int numBits = 100; 
                numBits <= 300; numBits += 100) {
                generatePrimes(100, numBits);
            }
        }

        static Random rnd = new Random();

        // Generate numPrimes probable primes 
        // of numBits length.
        
        static void generatePrimes(
                         int numPrimes, int numBits) {
            long start = System.currentTimeMillis();
            for (int i = 1; i <= numPrimes; i++) {
                BigInteger.probablePrime(numBits, rnd);
            }
            long elapsed = 
                    System.currentTimeMillis() - start;
            System.out.println(
                   "ms to generate " + numBits 
                    + " bit prime  = "
                    + (elapsed / numPrimes));
        }
    }

When you run the program, you should get results like this (your results might differ depending on your operating environment):

    ms to generate 100 bit prime  = 31
    ms to generate 200 bit prime  = 111
    ms to generate 300 bit prime  = 235

These results show that it took 31 milliseconds to generate a 100-bit prime, 111 milliseconds to generate a 200-bit prime, and 235 milliseconds to generate a 300-bit prime. Clearly, the time it takes to generate primes is not linear in relation to the number of bits.

There are a number of other prime-related features in BigInteger. For example, there's a method named isProbablePrime that you can use to test an existing BigInteger value for primality.

For more information about generating prime numbers, see section 4.5.4, "Factoring Into Primes", and section 6.4, "Hashing" in "The Art of Computer Programming" by Donald Knuth. Also, see "Enhancements to java.math".

When Not to Overload Methods

Suppose that you are writing a Java application, and you have some code like this that uses overloading for methodA and methodB:

    public class OverDemo1 {
    
        // overload methodA between short/int
    
        static void methodA(short s) {
            System.out.println(
                              "methodA(short) called");
        }
        static void methodA(int i) {
            System.out.println("methodA(int) called");
        }
    
        // overload methodB between float/double
    
        static void methodB(float f) {
            System.out.println(
                              "methodB(float) called");
        }
        static void methodB(double d) {
            System.out.println(
                             "methodB(double) called");
        }
    
        public static void main(String args[]) {
    
            // call methodA with char argument
    
            methodA('a');
    
            // call methodB with int argument
    
            methodB(Integer.MAX_VALUE);
        }
    }

What happens when this code is executed? First, methodA is called with a char argument. A char data type is 16 bits, so it seems logical that methodA(short) will be called. That's because the short type is 16 bits as well.

Next, methodB is called with an int argument. The int and float types are both 32 bits. Because a float type uses part of the bits for an exponent, it cannot fully represent a large int value without loss of precision. So methodB(double) seems like the logical choice, right?

Actually, this analysis is wrong in both cases. When you run the OverDemo1 program, the result is:

    methodA(int) called

    methodB(float) called

The point of this tip is not to discuss the intricacies of overloading, but simply to present the idea that most Java programmers don't fully understand how overloading works. It's smart to write your code so that they don't have to worry about these intricacies. This tip presents several ways to write code that avoids overloading issues. But first, let's look at one more example that illustrates how method overloading can be confusing:

    class A {
        void f() {
            System.out.println("A.f called");
        }
    }
    
    class B extends A {
        void f() {
            System.out.println("B.f called");
        }
    }
    
    public class OverDemo2 {
        static void classifyObject(A a) {
            System.out.println("classify as A");
        }
    
        static void classifyObject(B b) {
            System.out.println("classify as B");
        }
    
        public static void main(String args[]) {
    
            // create a B object referenced
            // by an A reference
    
            A aref = new B();
    
            // classify the object 
            // using overloaded methods
    
            classifyObject(aref);
    
            // call the f() method for the object
    
            aref.f();
        }
    }

The OverDemo2 program creates a B object with an A reference pointing at it. The program then calls the classifyObject method to indicate whether the A object or the B object is referenced by aref. Then the program calls the f method on the object. If you run this program, the result is:

    classify as A

    B.f called

The classifyObject method indicates that the A object is being referenced, but the f method call is on the B object. Which is right?

This example illustrates a major source of confusion with method overloading, a confusion that stems from the difference between overloading and overriding. The choice of which overloaded method to call is made by the compiler. In the OverDemo2 example above, classifyObject is called with the aref argument, of type A. The fact that aref references a B object is ignored, meaning that classifyObject(A) is called. By contrast, the choice of which f method to call is made dynamically when the program is executed, based on the actual type of object (which is a B). The f method in B overrides, not overloads, the corresponding method in A.

How do you avoid problems with overloading? One approach is to not overload at all. Instead, give methods different names, corresponding to the types of their parameters. For example, the OverDemo1 program above could be rewritten like this:

    public class OverDemo3 {
    
        static void methodShort(short s) {
            System.out.println("methodShort called");
        }
    
        static void methodInt(int i) {
            System.out.println("methodInt called");
        }
    
        static void methodFloat(float f) {
            System.out.println("methodFloat called");
        }
    
        static void methodDouble(double d) {
            System.out.println("methodDouble called");
        }
    
        public static void main(String args[]) {
    
            // call methodInt with char argument
    
            methodInt('a');
    
            // call methodFloat with int argument
    
            methodFloat(Integer.MAX_VALUE);
        }
    }

There is no overloading in this code, so which methods are called is very clear. A similar technique is used in some of the standard library classes such as DataOutputStream.

Another approach to eliminating confusion with overloading is to specify a different number of parameters for each of a set of overloaded methods. Alternatively, make sure that the parameter types are radically different from each other. Let's look at a final example to see how this works:

    class MyDate {
    
        // construct date from string 
        // like "January 17, 1959"
    
        public MyDate(String s) {
            // ...
        }
    
        // construct date from month/day/year
    
        public MyDate(int month, int day, int year) {
            // ...
        }
    
        // construct date from number of days 
        // since 1/1/1800
    
        public MyDate(int numdays) {
            // ...
        }
    }

In this example, the MyDate constructor is overloaded. It's not possible to give the various constructors different names, as illustrated in the earlier example, so they must be distinguished some other way.

The first and second constructors have different numbers of parameters, so it's easy to tell them apart. The first and third constructors both have a single parameter, but in one case it's a String, and in the other case an int, so it's easy to distinguish these.

Note that even with MyDate structured this way, there are still potential problems with understanding the code. For example, a statement like this:

    MyDate d = new MyDate(10, 12, 1959);

might be interpreted two different ways by someone who reads the code. The interpretation depends on whether the person reading the code is accustomed to specifying the month number before or after the day number. What date is being referred to here, October 12 or December 10? It's possible that additional work needs to be done to make this class easier to use. An enumerated type could be used to specify the month. Static factory methods could be used for creating dates. Unlike for constructors, you can give static factory methods distinct names that describe their function.

Some examples of parameter types not radically different from each other include:

char vs. int
int vs. float/double
classes in a related hierarchy (A vs. B in the example above)
Object vs. array types like int[]

Overloading is a useful technique, but it pays to be cautious. You don't want to end up with code that's impossible to read, or that takes advantage of arcane rules that few programmers understand. It should be possible for an average reader to look at your code and know exactly what method is being called at any point.

For more information about alternatives to overloading methods, see item 1 "Consider providing static factory methods instead of constructors" and item 26 "Use overloading judiciously" in "Effective Java Programming Language Guide" by Joshua Bloch; and Section 5.3 "Method Invocation Conversion" and Section 15.12.2 "Compile-Time Step 2: Determine Method Signature" in "The Java Language Specification Second Edition" by Gosling, Joy, Steele, and Bracha.

IMPORTANT: Please read our Terms of Use, Privacy, and Licensing policies:
http://www.sun.com/share/text/termsofuse.html
http://www.sun.com/privacy/
http://developer.java.sun.com/berkeley_license.html

Comments? Send your feedback on the Core Java Technologies Tech Tips to: jdc-webmaster@sun.com

Go to the subscriptions page to subscribe or unsubscribe to this newsletter.

ARCHIVES: You'll find the Core Java Technologies Tech Tips archives at:
http://developer.java.sun.com/developer/JDCTechTips/

Sun, Sun Microsystems, Java, Java Developer Connection, J2SE, J2EE, and J2ME are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.

Please send me newsletters in text.
Please unsubscribe me from this newsletter.