Skip to content

Instantly share code, notes, and snippets.

@schie
Created October 27, 2013 17:13
Show Gist options
  • Save schie/7185148 to your computer and use it in GitHub Desktop.
Save schie/7185148 to your computer and use it in GitHub Desktop.
This is java program implements the psuedo-random number generator: X(n+1) = (7^5 * X(n)) mod(2^31 - 1) to approximate the value of pi
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class PRNG {
private long seed = 0;
private final long mod = Integer.MAX_VALUE,
seven_pow = (long)Math.pow(7, 5);
/** Creates a PRNG with the seed x0 */
public PRNG(int x0){
// Convert x0 to positive nonzero equivalent form
if(x0 <= 0)
while(x0 <= 0)
x0 += 10;
seed = (seven_pow * x0) % mod;
}
/** Return the next random number */
public int next_rand(){
int this_rand = (int)seed;
// Set next random number
seed = (seven_pow * seed) % mod;
return this_rand;
}
/** Returns the greatest common denominator **/
private int gcd(int x, int y){
if(x < 0)
while(x < 0)
x += 10;
if(y < 0)
while(y < 0)
y += 10;
return (y == 0 ? x: gcd(y, x % y));
}
/** Returns an approximation of Pi */
public double approximate_pi(int n){
if(n < 0)
while(n < 0)
n += 10;
int x = next_rand(),
y = next_rand(),
relative_prime_count = 0, // aka rpc
gcd = 0;
double pi = -1; // will hold the approximation, returns -1 if rpc <= 0
// count the number of random relatively prime integers in 'n' iterations
for(int i = 0; i < n; i++){
gcd = gcd(x, y);
// increment rpc if two psuedo-random integers are relatively prime
relative_prime_count = (gcd == 1 ? relative_prime_count + 1 : relative_prime_count + 0);
x = next_rand();
y = next_rand();
}
pi = (relative_prime_count > 0 ? Math.sqrt(6 * n / (double) relative_prime_count) : pi);
return pi;
}
public static void main(String[] args){
System.out.print("Enter the seed: ");
try{
BufferedReader bufferRead = new BufferedReader(new InputStreamReader(System.in));
// Get seed
String s = bufferRead.readLine();
PRNG rand = new PRNG(Integer.parseInt(s));
System.out.print("Enter number of iterations: ");
// Get the number of iterations
s = bufferRead.readLine();
System.out.println("Approximation of Pi: " + rand.approximate_pi(Integer.parseInt(s)));
}
catch(IOException e)
{
e.printStackTrace();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment