Suppose we toss darts randomly at a square dartboard, whose bullseye is at the origin, and whose sides are 2 feet in length. Suppose also that theres a circle inscribed in the square dartboard. The radius of the circle is 1 foot, and its area is square feet. If the points that are hit by the darts are uniformly distributed (and we always hit the square), then the number of darts that hit inside the circle should approximately satisfy the equation:

(number in circle total)/(number of toss) = /4,

since the ratio of the area of the circle to the area of the square is /4.

We can use this formula to estimate the value of with a random number generator:

float pi_estimate = 0.0;

int number_in_circle = 0;

for (toss = 0; toss < number_of_tosses; toss++)

{

x = rand_range(-1, 1);

y = rand_range(-1, 1);

distance_squared = x*x + y*y;

if (distance_squared <= 1) number_in_circle++;

}

pi_estimate = 4*number_in_circle/((float) number_of_tosses);

This is called a Monte Carlo method, since it uses randomness (the dart tosses). Write a MIPS program that uses a Monte Carlo method to estimate . The program iterates the total number of tosses and prints out the result. Run your program while varying the number of tosses, 100, 1,000, 10,000, to obtain reasonable estimate of . 2.a [20pts] Write your program using the template (picalc_example.s).

2.b [10pts] What are the decimal and bit representation of your estimated value you obtain?

2.c [10pts] How many tosses did it give you the value close to (i.e., 3.14159) ? The relationship between the number of tosses and precision.

2.d [10pts] Would there be any change in the estimated if double were used?

picalc_example: starter code:

.text

#.align 2

.globl main

main: la $t0, toss

move $t1, $0 # init $t1 = 0

li $a0, 44 #43 = random float, 44 = random double

jal srand

L1: bge $t1, 4, exit # check loop condition

lw $t2, 0($t0) # load # of tosses

############ begin your code ################################

# current code will just print out 3 random numbers generated

L2:

jal rand_range # use rand_range function to get random number

# $f0 has the random number

# j L2

############ end your code ###################################

mov.s $f12, $f0 # move result to print argument

li $v0, 2 # 2 = print float, 3 = print double

syscall # system call for print result

addi $a0, $0, 0xA # ascii code for LF

addi $v0, $0, 0xB # syscall 11

syscall

addi $t1, $t1, 1 # increment $t1

add $t0, $t0, 4 # adjust index

j L1 # iterate outer loop

exit: li $v0, 10 # system call for exit

syscall # we are out of here

# random float range

rand_range:

addi $sp, $sp, -12

sw $t0, 0($sp)

sw $t1, 4($sp)

sw $ra, 8($sp)

jal rand # $v0 has random number

mtc1 $v0, $f20 # move the int to $fp reg, mtc1.d for double

cvt.s.w $f20, $f20 # convert int to float, cvt.d.w for double

# la $t0, rmax

# lw $t1, 0($t0)

# mtc1 $t1, $f21

# cvt.s.w $f21, $f21 # f21 = rmax

l.s $f21, rmaxf

div.s $f22,$f20,$f21 # random = rand()/rmax

l.s $f23, LB # f23 = lb

l.s $f24, diff # f24 = diff

mul.s $f25,$f22,$f24 # f25 = f22*f24

add.s $f0, $f23, $f25

lw $t0, 0($sp)

lw $t1, 4($sp)

lw $ra, 8($sp)

addi $sp, $sp, 12

jr $ra

# For seeding the random number generator

srand:

addi $sp, $sp, -4

sw $t0, 0($sp)

la $t0, rseed # Store the given seed

sw $a0, 0($t0)

lw $t0, 0($sp)

addi $sp, $sp, 4

jr $ra

# random number generator

# seed = seed * 1103515245 +12345;

rand:

addi $sp, $sp, -20

sw $t0, 0($sp)

sw $t1, 4($sp)

sw $t2, 8($sp)

sw $t5, 12($sp)

sw $ra, 16($sp)

la $t5,rseed # Get the current seed

lw $t0,0($t5)

li $t1,1103515245 # seed * 1103515245

mul $t2,$t0,$t1

add $v0,$t2,12345 # (seed * 1103515245) + 12345

li $t0,0x7FFFFFFF # ((seed * 1103515245) + 12345)&0x7FFFFFFF

and $v0,$v0,$t0

sw $v0,0($t5) # Save the seed

lw $t0, 0($sp)

lw $t1, 4($sp)

lw $t2, 8($sp)

lw $t5, 12($sp)

lw $ra, 16($sp)

addi $sp, $sp, 20

jr $ra

.data

.align 0

pi: .float 0.0

toss: .word 100, 1000, 10000

rseed: .word 1

rmax: .word 2147483647

rmaxf: .float 2147483647.0

LB: .float -1.0

UB: .float 1.0

diff: .float 2.0