Write a non-recursive routine
to compute the factorial of n
according to Equation .
Calculate the running time predicted by
the detailed model given in Section
and the simplified model given in Section .
Write a non-recursive routine
to compute according to Equation .
Calculate the running time predicted by
the detailed model given in Section
and the simplified model given in Section .
Write a program that determines the values
of the timing parameters of the detailed model
( , , , , , ,
, , , , ,
and )
for the machine on which it is run.
Using the program written for Project ,
determine the timing parameters of the detailed model
for your computer.
Then, measure the actual running times
of Programs , and
and compare the measured results with those predicted by
Equations , and (respectively).
Given a sequence of n integers, ,
and a small positive integer k,
write an algorithm to compute
without multiplication.
Hint: Use Horner's rule and bitwise shifts.
Verify Equation experimentally as follows:
Generate a large number of random sequences of length n,
.
For each sequence, test the hypothesis that the probability
that is larger than all its predecessors in the sequence
is .
(For a good source of random numbers, see Section ).