Dag Rune Sneeggen

Posts tagged with "java"

Java: (slightly advanced) Optimized Fermat Primality Test

Wednesday, June 14, 2006 8:31:20 PM

This little class enables you to use Fermat's Little Theorem, to check if a number is a (probable) prime or not. Probable because not all positive answers from Fermat's Little Theorem will actually be prime. Those "Carmichael numbers" are pretty rare though, Fermat Primality Test is actually used in the notorious PGP encryption software. Optimized because it uses a much faster algorithm for calculating the modular exponentiation.

You will need to import these packages:

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

ATT: You have to seed your random generator only once

Random generator = new Random();

Here is the main class:

class FermatPrime {    
    public static boolean doTest (BigInteger p, int prob) {        
        for (int c = 0; c < prob; c++) {
            if(!doModPow(p)) {
                return false;
            }
        }
        return true;
    }
    public static boolean doModPow (BigInteger n) {
        long rndnum = 1 + generator.nextInt(99);
        BigInteger b = BigInteger.valueOf(rndnum);
        return b.modPow((n.subtract(n.ONE)), n).equals(n.ONE);
    }    
}

The doTest method takes two arguments. The first argument is the actually number you want to test for primality. The second argument is how many times you want to run the primality test, in otherwords how much certainty you want.

Example usage:

if (FermatPrime.doTest(BigInteger.valueOf(101L), 5)) {
    System.out.println("We got ourselves a probable prime! :)");
} else {
    System.out.println("Doh, not a prime! :(");
}

Update:
With a some friendly help from 'YAT_Archivist' over at the Sun Java Forums, I've improved the code.

9 comments

Java: Arithmetic and Geometric Progression (Mathematics)

Tuesday, June 13, 2006 1:53:11 AM

code, java, mathematics

For those who doesn't know what this means in mathematics, please see Arithmetic Progression(wikipedia.org) and Geometric Progression(wikipedia.org).
A quick summary could be: when you have a string of numbers which is either the previous number added with a number d, or when the previous number is multipled with a number k.

This class will enable you to find any number in such a sequence which you specify, as well as finding the sum of such a sequence:

class Aritmetic {
    long a;
    double d;      
    public Aritmetic(long a, double d) {
        this.a = a;
        this.d = d;       
    } 
    public double calcTerm(long i) { return (a + ((i - 1)*d)); }
    public double calcSum(long i) { return (i * (calcTerm(1L) + calcTerm(i))/2); }
}
class Geometric {
    long a;
    double k;    
    public Geometric(long a, double k) {
        this.a = a;
        this.k = k;        
    } 
    public double calcTerm(long i) { return (Math.pow(k, (i - 1))*a); }
    public double calcSum(long i) { return (a * ((Math.pow(k, (i)) - 1)/(k - 1))); }
}

Here you have two classes, one for arithmetic and one for geometric progression. They will both have to be initiated with two arguments. The first argument, a, is the starting number of the sequence. The second argument, d or k, is the difference in an arithmetic sequence and the common ratio in the geometric sequence. (If that sounded insane to you, please see the previously mentioned wikipedia entries for a better explanation!)

The method calcTerm with calculate the value of the i-th term. That is, the number which the sequence gives at position i.
The method calcSum will calculate the value of the sum from the starting number to the i-th term.

Example Usage:

Arithmetic atest = new Arithmetic(1, 2);
System.out.println("Arithmetic Term: " + atest.calcTerm(64));
System.out.println("Arithmetic Sigma: " + atest.calcSum(64));

Geometric gtest = new Geometric(1, 2);
System.out.println("Geometric Term: " + gtest.calcTerm(64));
System.out.println("Geometric Sigma: " + gtest.calcSum(64));

This little example happens to show why the mathematician who invented chess wanted his rice beans to double, as opposed to increase by two per square on the chess board!

7 comments

Java: Random element from array.

Tuesday, June 6, 2006 7:43:54 PM

code, java, technical

This is a short, simple, and (hopefully) idiot-proof way of getting a random element from an array of length.

The entire magic consists of one simple class:

class pickRand {
    public static String get (String[] array) {
        int rnd = generator.nextInt(array.length);
        return array[rnd];
    }
}

Which can be used like this:

String[] fruits = { "apple", "apricot","orange", "pear", "plum", "peach",  "watermelon"};

String ret = pickRand.get(fruits);
System.out.println(ret);

This methode will require you to use the Random module located in java.util, which you import like this:

import java.util.Random

ATT: You need to have this line executed only once in your application, to create an instance of the random generator:

Random generator = new Random();

If this is executed more than once, you might not get fairly distributed random values!

Possible improvements:

Very easily you can add a second argument to pickRand to enable it to pick many elements, but this can just as easily be done by calling the method several times.
Currently this works on Strings, but by changing String[] to int[] or long[] or any other type, as well as changing which type the class returns you can use any other Java type.

14 comments