# HW 3
# OK to post
taylor(exp(x),x=0, 5);
diff((x-5)/(x-2),x);

Help := proc(): 
print(`EstimateProbGCD(N,K)`): 
end:
#gcd v.s. EAnew -- gcd is better
#
#                           0.015, 0.984
#                             0. , 0.437
#                           0.015, 0.531
#                              0., 0.515
#                           0.015, 0.265

#EA v.s. EAnew -- EAnew is better
#                           1.171, 0.562
#                           0.375, 0.187
#                           0.750, 0.484
#                           0.218, 0.203


# My guess is that EA is slower than EAnew because 
# function calls are just expensive enough to make it slower.

EAbet:=proc(m,n) local m1,n1,r1,q1:
m1:=m:
n1:=n:
r1:=max(m1,n1):
q1:=min(m1,n1):

while q1>0 do
m1:= r1 mod q1:
n1 := q1:
r1:=max(m1,n1):
q1:=min(m1,n1):
od:

r1:
end:

# estimate probability that two integers between 1 and N are relatively prime, by doing K experiments
EstimateProbGCD := proc(m,n) 
local i1, total, a, b:
i1:=1:
total:=0:
while i1 < n+1 do
a:=rand(1..m)():
b:=rand(1..m)():
if gcd(a,b)=1 then
 total:= total+1:
fi:

i1:= i1 + 1:
od:

RETURN(evalf(total/n)):
end:

# results of running EstimateProbGCD(10^10,10^4); several times
# obtained values ranging from 0.602 to 0.612
# answers are close


# exact value: ?? not sure; testing indicates it's in a similar range (around 0.6)