import java.io$.$FileWriter;

import java.io$.$IOException;

import java.io$.$PrintWriter;

import java.math.BigInteger;

import java.util.Random;

import java.util.concurrent.TimeUnit;

public class Project$\_1\{$

BigInteger ONE $=$ BigInteger.ONE;

BigInteger ZERO $=$ BigInteger.ZERO;

BigInteger TWO $=$ BigInteger.TWO;

public static void main$($String$[]$ args$)\{$

new Project$\_1()$;

$\}$

public Project$\_1()\{$

BigInteger n;

BigInteger FIRST $=$ new BigInteger$("10000000000000819")$;

long endTime $=$ System.currentTimeMillis$()+$ TimeUnit.HOURS.toMillis$(1)$; $//$ endTime $=$ an hour after current time

long timeDA, timeRA, elapsedTimeDA, elapsedTimeRA;

String outputFile $=$ "DAvsRA$\_$results.csv$"$;

PrintWriter output $=$ null;

$//$open output stream

try $\{$

output $=$ new PrintWriter$($new FileWriter$($outputFile$))$;

n $=$ FIRST;

while $($System$.$currentTimeMillis$()<$ endTime$)\{$

$//$ Deterministic approach

timeDA $=$ System.currentTimeMillis$()$;

boolean primeDA $=$ isPrime$($n$)$;

elapsedTimeDA $=$ System.currentTimeMillis$()-$ timeDA;

String deterministicAnswer $=$ primeDA $?$ "YES" : $"$NO$"$;

$//$ Randomized approach $($Monte Carlo$)$

timeRA $=$ System.currentTimeMillis$()$;

boolean primeRA $=$ isProbablyPrime$($BigInteger $)$; $/////$ fix

$\}$

$\}$ catch $($IOException ex$)$

$\{$

System.exit$(1)$;

$\}$

$\}$

public boolean isPrime$($BigInteger n$)\{$

BigInteger s $=$ n$.$sqrt$()$;

if $($n$.$compareTo$($ONE$)==0)$ return false;

BigInteger i;

for $($i $=$ TWO; i$.$compareTo$($s$)<=0$; i $=$ i$.$add$($TWO$))\{$

if $($n$.$mod$($i$).$compareTo$($ZERO$)==0)\{$return false;$\}$

$\}$

return true;

$\}$

private long exp$($int b$,$ int x$)\{$

return $($long$)$ Math.pow$($b$,$x$)$;

$\}$

public boolean isProbablyPrime $($int n$,$ int iterations$)\{$

if $($n $<=1)$ return false;

if $($n $==2)$ return true;

Random rand $=$ new Random$()$;

for $($int i $=0$; i $<$ iterations; i$++)\{$

int a $=2+$ rand.nextInt$($n $-2)$;

if $($exp$($a$,$ n $-1)\%$ n $!=1)$

return false;

$\}$

return true;

$\}$

$/**$

public void dataPrinter $($BigInteger n$,$ long timeDA, String deterministicAnswer, long timeRA, String randomizedAnswer$)\{$

$\}$

$**/$

$\}$ COP$4534$ Project $1$

Objective

Students will be able to design algorithms using a randomization technique and conduct a comparison

study of the performance of a randomized algorithm vs$.$ a deterministic algorithm.

Assignment Problem

Suppose that you are given a positive integer number n and you are asked to conduct a primality test,

i$.$e$.$ to determine if n is prime. Design and implement a computational experiment to contrast the

performance of a randomized algorithm vs$.$ a deterministic algorithm. The following requirements must

be used in your study.

Please consult the class slides for a discussion on these approaches.

Requirements

$$ Your application will test large numbers stored as BigInteger objects.

$$ The program will run a primality test on consecutive values from FIRST, i$.$e$.,$

FIRST, FIRST $+1,$ FIRST $+2,$ FIRST $+3...$

where FIRST $=10000000000000819.$

$$ Two approaches will be run on each value of the sequence above, a deterministic method and a

randomized method.

$$ The deterministic approach will be based on Prog$15\_05.$

$$ The randomized method will be based on Corollary of Fermat$$s Little Theorem.

$$ The program will run for one hour, testing, in a loop, values from the sequence above.

$$ In each iteration of the loop, the following steps will be run

o Step $1.$ Determine if current value is prime using deterministic approach.

o Step $2.$ Record the time it took to complete Step $1.$

o Step $3.$ Record answer of Step $1($YES$/$NO$).$

o Step $4.$ Determine if current value is prime using randomized approach.

o Step $5.$ Record the time it took to complete Step $4.$

o Step $6.$ Record answer of Step $4($YES$/$NO$).$

$$ Values recorded by each approach will be saved in a $.$csv file to be open in Excel later. Format

your $.$csv file as follows:

Value, Time of DA$,$ Prime? $($According to DA$),$ Time of RA$,$ Prime? $($According to RA$)$

Value, Time of DA$,$ Prime? $($According to DA$),$ Time of RA$,$ Prime? $($According to RA$)$

Value, Time of DA$,$ Prime? $($According to DA$),$ Time of RA$,$ Prime? $($According to RA$)$

$...$

For example $($the numbers below are not taken from a real example; they are offered to

illustrate the content of the file$)$

Value, Time of DA$,$ Prime? $($According to DA$),$ Time of RA$,$ Prime? $($According to RA$)$

$10000000000000819,5,$ YES, $0\mathrm{.}2,$ YES

$10000000000000820,5\mathrm{.}2,$ NO$,0\mathrm{.}1,$ NO

$10000000000000821,4\mathrm{.}9,$ NO$,0\mathrm{.}2,$ NO

$...$

In Excel, this would look:

Value Time of

DA

Prime?

$($According to DA$)$

Time of

RA

Prime?

$($According to RA$)$

$100000000000008195$ YES $0\mathrm{.}2$ YES

$100000000000008205\mathrm{.}2$ NO $0\mathrm{.}1$ NO

$100000000000008214\mathrm{.}9$ NO $0\mathrm{.}2$ NO

$...$

$$ i just need help with the code