
% Homework 2 Solutions
% factorial.m
% CS 1109, Summer 2011
% July 13

% This script determines the value of the smallest number whose factorial
% has at least 1 million digits.

clc
clear

logSum = 0;
i = 0; 

% On each pass through the loop, we compute log(i!), with i increasing
% after every pass through the loop. The loop terminates when the number of
% digits in i! exceeds 1 million (10^6). At this point, i contains the
% number of interest.
while (floor(logSum) + 1 < 10^6)
    i = i + 1;
    logSum = logSum + log10(i);
end

fprintf('The smallest number with a million digit factorial is %d\n', i);

% Why can't we use ceil(log10(x)) instead of floor(log10(x))+1 to compute 
% the number of digits in x? This is because the ceiling gives us the 
% incorrect answer for numbers that are exact powers of 10. For example, 
% if x is 1000 (which has 4 digits), log10(x) = 3 and therefore
% ceil(log10(x)) = 3 which is incorrect. On the other hand,
% floor(log10(x))+1 = 4, which is indeed what we want.

% Common mistakes / other observations:
% 
% 1) By far, the most common mistake on this problem was people using
% prod(1:n) to explicitly compute the factorial of a number, rather than
% accumulating the sum of logarithms as suggested in the homework handout.
% This results in the erroneous identification of 171 as the smallest
% number with a million-digit factorial, due to numeric overflow. The
% correct answer is 205022.
%
% 2) Other people lost points for failing to adhere to the code standards
% -- for example, missing comments, not indenting code properly etc.
% Remember to go through the checklist in the problem handout before you
% submit solutions!



