Hi, MrSneaky-ga:
You are correct, the largest integer X such that X! < 2^8192 is 966.
To compare 966! and 2^8192 I think it's satisfactory to compare the
numerical values of their natural logarithms:
ln(966!) = SUM ln(k) FOR k = 1 to 966 ~ 5677.8
ln(2^8192) = ln(2) * 8192 ~ 5678.3
Considering that the binary exponent 8192 is given here (number of
bits in a kilobyte), the approximation 966! is actually surprisingly
close. Roughly:
(966! / 2^8192) ~ 0.65
So when one jumps to 967!, one overshoots 2^8192 be a considerable margin.
I did these numbers both with the Windows calculator (and rounded to
one decimal of accuracy) and with Gnu Octave, a free open source
mathematical modelling environment similar to Matlab. Since there are
only 966 terms in the summation, I have little doubt that rounding
effects do not affect the result of the comparison. In the earlier
problem there were almost two orders of magnitude more terms to add,
so I went to some trouble to do the comparision with very limited
amounts of numeric calculation.
In general adding a series of positive number is one of the most
stable calculations, so far as effects of rounding errors are
concerned. When the terms of summation are all roughly the same
magnitude, the behavior of the rounding errors is a nice application
of the "random walk" principle (in one dimension). If A is the
average absolute size of a rounding error in a single summand, then
the total rounding error in adding up N terms has an expected
(average) absolute value of about A times the square root of N (for
sufficiently large N). This assumes the individual terms are equally
likely to have been rounded up as down, so that there's no
"systematic" direction to the rounding errors.
Thus, if our individual terms had rounding errors of (say) +/- 0.01,
we'd expect the summation of 966 of those terms to have a combined
error of something like 31 times that:
SQRT(966) = 31.08...
Of course if the actual logarithm computations are in double
precision, then the rounding errors will be many orders of magnitude
smaller than that. But if the computations were done in single
precision, it might give one a moment's pause to know that the actual
difference in logarithms above is about 0.42.
Since ln(966) ~ 6.873...
the absolute size of individual rounding errors in (well done) single
precision would be roughly 0.000002.
So even with "worst case" rounding (systematically to one direction or
the other), summing up 966 terms would not introduce significant error
in the comparison.
Some basic aspects of rounding errors are discussed by Donald Knuth in
the 2nd volume of his Art of Computer Programming series. For an
excerpt of that material, see here:
[Floating point arithmetic errors]
http://w3rum.upr.clu.edu/htmldocs/fortran/ch4-6.html
regards, mathtalk-ga |
