Created
October 27, 2013 17:13
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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