cs249 Homework 2 Solutions

2.1
---

1) factorial(200) overflows

To estimate the upper bound, I entered various values of
1 * 10 ^x to find the biggest value of x that didn't overflow.

>>  1e300
ans = 1.0000e+300

>> 1e310
ans = Inf

So it's between 10^300 and 10^310.  Proceeding by bisection,
I narrowed it down to:

>> 1e308
ans = 1.0000e+308

>> 1e309
ans = Inf

So the biggest number is about 10^308


2) Similarly, I narrowed it down to:

>> 1e-323
ans =  9.8813e-324

>> 1e-324
ans =  0

So the smallest number is about 10^-323.

Notice that the range is not symmetric.  Also notice that
for very small values we can't record the mantissa with
as much precision.


2.2
---

Here is fibonacci2.m

function f = fibonacci2 (n)
% f = fibonacci2 (n)
% takes an integer argument, n, and returns the nth
% element of the Fibonacci sequence that begins (1, 1, ...)
   t1 = 1 / sqrt (5);
   t2 = (1 + sqrt (5)) / 2;
   t3 = (1 - sqrt (5)) / 2;
   f = t1 * (t2^(n+1) - t3^(n+1));
end

And here are the test runs...

>> fibonacci2 (10)

ans =

   89.0000

>> fibonacci2 (100)

ans =

   5.7315e+20

>> help fibonacci2

  f = fibonacci2 (n)
  takes an integer argument, n, and returns the nth
  element of the Fibonacci sequence that begins (1, 1, ...)


2.3
---

Here is pdf.m

function f = pdf (x, theta, sigma, zeta)
% f = pdf (x, theta, sigma, zeta)
% computes the probability density function of the
% lognormal distribution with parameters theta, sigma and
% zeta
   t1 = x - theta;
   denom = t1 * sqrt (2 * pi) * sigma;
   exponent = -1/2 * (log (t1) - zeta)^2 / sigma^2;
   f = exp (exponent) / denom;
end


2.4
---

1) Here is quadratic.m

function f = quadratic (a, b, c)
% f = quadratic (a, b, c)
% compute one of the roots of the polynomial a x^2 + b x + c
    determ = sqrt (b^2 - 4 * a * c);
    b
    determ
    numer = -b + determ;
    f = numer / 2 * a;
end

3) Here is the result of the tests

>> quadratic (1, 1000000.000001, 1)

ans =    -1.000007614493370e-06

>> quadratic (1, -1000000.000001, 1)

ans =    1000000

The actual roots are 1,000,000 and 1e-6.  In this case the larger
root is computed with pretty good accuracy, but the smaller one is
not that good (only 6 of 15 digits are correct).

4) The problem is that when we subract b^2 - sqrt(4ac), the operands
are pretty close to each other.  I added a couple of statements to
print the values of b and determ:

function f = quadratic (a, b, c)
% f = quadratic (a, b, c)
% compute one of the roots of the polynomial a x^2 + b x + c
    determ = sqrt (b^2 - 4 * a * c);
    b
    determ
    numer = -b + determ;
    f = numer / 2 * a;
end

And here's what I got:

>> quadratic (1, 1000000.000001, 1)

b =     1.000000000001000e+06

determ =     9.999999999990000e+05

ans =    -1.000007614493370e-06


For the other computation, b and determ are different signs,
so their difference is big, and therefor precise...

>> quadratic (1, -1000000.000001, 1)

b =   -1.000000000001000e+06

determ =    9.999999999990000e+05

ans =    1000000



5) Yup, it's complex...

>> quadratic (1, 2, 3)

ans = -1.00000000000000 + 1.41421356237310i