Dag Rune Sneeggen

Development and miscellaneous!

Posts tagged with "code"

Java: (slightly advanced) Optimized Fermat Primality Test

Java: Arithmetic and Geometric Progression (Mathematics)

Java: Random element from array.

Javascript: Fancy menu

Javascript: Random Colouring

Wednesday, 14. June 2006, 20:31:20

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.

3 comments

Tuesday, 13. June 2006, 01:53:11

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!

3 comments

Tuesday, 6. June 2006, 19:43:54

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.

8 comments

Monday, 5. June 2006, 16:37:24

code, javascript

This is a script, which you can actually see in action at http://wallpapersilhouettes.com/.
Created for the ground up by me, it basically enables you to have a nice mouseover effect as well as a text field which changes at the same time. Not so fancy coding, but people seem to like the effect the menu provides.

var img_act = new Image();
img_act.src = "./images/active.png";
var img_inact = new Image();
img_inact.src = "./images/inactive.png";

function doActive(name, txt) {
    document[name].src = eval("img_act.src");
    setText("txt");
}
function doInactive(name) {
    document[name].src = eval("img_inact.src");
    setText('');
}
function setText(txt) {
    var nav = document.getElementById("spantext");
    nav.innerHTML = txt;
}

You all so need html similar to this:

<a href="./" onMouseOver="doActive('link1','TEXT');" onMouseOut="doInactive('link1')">
    <img src="./images/inactive.png" name="link1">
</a>

<span id="spantext">TEXT WILL COME HERE</span>

Possible improvements:

This script will only pop up a text in the span when there is a mouseover, you could have it be something to default as well.
It could change the text of multiple areas.
The most immediate improvment is of course to give the setText function a second argument, which could be the id of the tag you want to work with. This is also quite trivial I might add

No comments

Saturday, 3. June 2006, 12:33:38

code, javascript

A nice and simple way to get a random colouring on say, links or background when you place your mouse over an object.

function genColour(id) {
    var item = document.getElementById(id);
    var rnd_r = String(Math.floor(Math.random()*255));
    var rnd_g = String(Math.floor(Math.random()*255));
    var rnd_b = String(Math.floor(Math.random()*255));
    var rnd_rgb = 'rgb(' + rnd_r + ', ' + rnd_g + ', ' +  + rnd_b + ')';
    setColour(id, rnd_rgb);
}
function setColour(id,col) {
    var item = document.getElementById(id);
    item.style.borderColor = col;
}

Then you of course need something similar like this:

<a style="border-color: #000000; border-style: solid;" id="item1" href="."
onMouseOver="genColour('item1')" onMouseOut="setColour('item1', '#000000')">Text</a>

Possible improvements:

Draw a random item from an array of pre-defined colours.

Make onMouseOut detect the previous(original) colour dynamically.

2 comments

Blog search

November 2009January 2010