//=========================================================================
#define PROGRAMMER "SOLUTIONS, NoFrills"
#define PROG_CODE  "soln"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "HW #2C"
#define REVISION   (0)
#define TITLE      "Rounding a Floating Point Value"
#define SUBTITLE   "Extra Credit"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "02c0soln.txt"
//=========================================================================

// PROBLEM:
//
// For a variable of type double (in Turbo C/C++ v4.5), round a value to
// the number of decimal places requested by the user. The end result
// should be reasonable for any possible value of the variable.
//
// SOLUTION:
//
// First decide what is reasonable for values in the general vicinity
// of one (i.e., where the ability of a double to represent the resulting
// rounded value includes the requested decimal precision).
//
// If asked to round a value to 5 decimal places, one way to do it is
// to multiply the value by 10^5, round to the nearest integer, and then
// divide the result by 10^5.
//
// Rounding to the nearest integer is, for values that don't exceed the
// range of a long int, fairly easy.
//
// For positive values, we can just add 0.5 to the number and then
// truncate the result.
//
// For negative values, we probably should not rely on an assumption
// about what happens when a floating point value is truncated to
// an integer by the cast operator. Instead, we can multiply it by
// negative one, truncate as above, and then multiply by negative one
// again. We can accomlish my simply making the multiplier used above
// negative if the value to be rounded is negative.
//
// So, for values that don't cause overflow or underflow with a long int:
//
// 1) SET: f = floating point value to be rounded
// 2) SET: n = number of decimal places
// 3) SET: multiplier = 10^n
// 4) IF: (f < 0)
// 4.1) SET: multiplier = - multiplier
// 5) SET: f = f * multiplier
// 6) SET: f = (long int) (f + 0.5)
// 7) SET: f = f / multiplier
//
// For extremely small values, things are very easy - if we want to round
// 0.0000001 to four decimal places, the result is simply 0. To look at
// things a bit more carefully, if we want to round to, say, four decimal
// places then any value less than 0.00005 would be zero. And value
// equal to or greater than that would need to be rounded. Our threshold
// value is therefore (1/10^n)/2.
//
// Notice that the above assumes positive values, but our earlier
// algorithm takes the absolute value (in step 5) and so we are find as
// long as we do the above check after that step.
//
// But, after that step, we have multiplied by by 10^n and Step 6
// adds in the remaining 0.5. Hence the algorithm already handles very
// small values of f automatically and no modifications are needed -
// although we could possibly make the algorithm a bit faster by trapping
// this case and avoiding an unneccessary floating point division.
//
// The same is not true for very large values. Here there are actually two
// subcases - if the value is REALLY large, and if the value is just
// large enough to cause overflow problems when we use the type cast
// to truncate it.
//
// For the REALLY large values, remember that we only have so many digits
// of precision (about 15 or 16 on our system). If the value has more
// than that number of digits to the left of the place where we want to
// round, then rounding would have absolutely no effect. To give ourselves
// a bit of leeway, we'll say that we won't round if the value has more
// than 20 digits to the left of the point we want to round at.
//
// To determine how many digits a number has, simply take the base ten
// logarithm of the number. The base ten log of 1000 is 3 and the base
// ten log of 10,000 is 4. So any number with 4 digits has a base ten
// log that is greater than or equal to 3 but less than 4. By extension,
// that means that any number with 20 or more digits has a base ten
// logarithm greater than 19.
//
// As above, if we work with the value after taking the absolute value
// and scaling by the multiplier, we make our lives simpler because we
// don't have to worry about taking the logs of negative numbers and we
// have already taken how many decimal places we want into account.
//
// So, adding in the above rule to the prior algorithm gives us:
//
// 1) SET: f = floating point value to be rounded
// 2) SET: n = number of decimal places
// 3) SET: multiplier = 10^n
// 4) IF: (f < 0)
// 4.1) SET: multiplier = - multiplier
// 5) SET: f = f * multiplier
// 6) IF(log10(f) <= 19)
// 6.1) SET: f = (long int) (f + 0.5)
// 7) SET: f = f / multiplier
//
// We might still want to do our check for REALLY large values before
// modifying the original value since even multiplying and dividing a
// value by the same number usually introduces a bit of round off error.
// But we'll leave that as a future enhancement.
//
// This leaves us with the final problem - namely that the operation in
// Step 6.1 above might not work properly if the value of f on that line
// is larger than can be represented by a long int. On our system, a long
// int can represent values up to 2,147,483,647 which is only nine fuil
// digits. Using an unsigned long would not improve matters any since we
// will have still problems with numbers that have, say, thirteen digits.
//
// Let's step back an think about how we represent numbers to begin with.
// Using the notion of a positional numbering system, we can work with
// groups of digits as a package. So, for intance, we could represent the
// value
//
//   f = 123456789 as 123*(1000^2) plus 456*(1000^1) + 789*(1000^0)
//
// We essentially have a base-1000 numbering system where the "digits"
// can take on 1000 values between 0 and 999 (1000-1). So let's make
// a really big number base - say base - 2,147,483,648. With just two
// "digits" in this number base, we can represent values as large as
//
// f = 2,147,483,647*(2,147,483,648^1) + 2,147,483,647
//
// which is f = (2,147,483,648^2) - 1 = 4,611,686,018,427,387,903
//
// To make our live a bit easier (at least mentally), let's use a
// number base of 1 billion. That means that we can represent numbers
// with values up to (but not including) 10^18. But this is more than
// out 15 or 16 digits of precision that a double gives us so that is
// acceptable. We do, however, need to do our check against values
// greater than 10^18 (instead of 10^19). But that is a trivial change
// and, in fact, instead of taking the base ten log, we can simply
// compare f to 10^18.
//
// We still need to figure out what to do, exactly, to round this
// number, so let's walk through a hand example where we are limited
// to using integers no bigger than 999.
//
// Round 123456.789 to the nearest whole value (0 decimal places).
//
// If we divide by our number base (1000) we get 123.456789. This is
// easy to truncate giving us 123. By then subtracting off 123 times
// the number base, we are left with the "units digit". We then simply
// round that and add back in the amount we subtracted off.
//
// So our algorithm now looks like this:
//
// 1) SET: f = floating point value to be rounded
// 2) SET: n = number of decimal places
// 3) SET: multiplier = 10^n
// 4) IF: (f < 0)
// 4.1) SET: multiplier = - multiplier
// 5) SET: f = f * multiplier
// 6) IF(f < 1e18)
// 6.1) SET: digit1 = (long int) (f/1e9)
// 6.2) SET: f = f - (digit1*1e9)
// 6.3) SET: f = (long int) (f + 0.5)
// 6.4) SET: f = f + (digit1*1e9)
// 7) SET: f = f / multiplier
//