Lecture Notes for Advanced Programming II

30 November 2001 - Assignment 4 Code Review

The Test Cases

1. The empty input.

2. 1/1 - trivial answer.

3. 1/5 - trivial answer.

4. -4/-2 - negative inputs.

5. -4/2 - negative inputs.

6. 355/113 - a pi approximation.

7. 100/0.2 - fractional inputs.

8. 99999999999999999999999999999999/
   33333333333333333333333333333333 - big inputs.

9. pi/e - illegal inputs.

10. 4/2 9/3 - multiple inputs.

The Results

• 23 programs total, 19 effective.

  • One program didn't compile

  • Three programs read from the command line.

• Seven programs produced no proper output.

Line Statistics - Newlines

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

Line Statistics - Semicolons

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

Procedure Statistics

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

File Statistics

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

A First Cut

• Apply the usual first design.

  int main()
    while (input(cin, problem))
      solve(problem)
      print(cout, problem)
  

• What gets passed from solve() to print()?

• Try turning the problem inside out - use an object.

  int main()
    long_division p
    while (p.input(cin))
      p.solve())
      p.output(cout)
  

Object-Oriented Long Division

• Implement a scratch-pad like object.

  • This worked well, at first.

  • But, it got complicated fairly quickly.

  • The problem is objects lump things together.

    • And makes it complicated to separate things.

• Go back to the original design and try again.

  int main()
    while (input(cin, problem))
      solve(problem)
      print(cout, problem)
  

• Apply wishful thinking to the simplest part.

Writing Out Long Division

• What do I need to output a long division problem?

  • My first brain-storm: the numerator, denominator, and quotient.

  • Everything else can be re-computed, including the remainder.

  • This means the answer can be checked too.

    • This last was a mistake; output is now doing too much.

• The solution is now

  struct solution {
    bignum numerator, denominator, quotient
    }
  
  int main()
    while (input(cin, problem))
      solution s = solve(problem)
      print(cout, s)
  

• This is nice, output is completely separate from division.

  • Not quite - the answer has to be correct.

Formatting Long Division

• The key to formatting long division is the right-most digit.

  • Not quite, it's the (implicit) decimal point.

  • The digits of the quotient set the position.

• This was simple and worked amazingly well.

  for (unsigned i = (quo[0] == '-' ? 2 : 1); i < quo.length(); i++) {
    rmd_pos++;
    if (quo[i] != '0') {
      const string & n = *di++;
      print(os, rmd_pos, n);
      print(os, rmd_pos, *di++);
      print(os, rmd_pos, string(n.length(), '-'));
      }
    }
  

  • It handled negative numbers "automatically".

  • It didn't handle numbers with fractions.

• But the checking part was making things complicated.

A Useful Design Rule

• Each function should do one thing only.

  • Doing more than one thing quickly gets complicated.

  • This implies the functions are well-defined in the first place.

• Putting checking in output was dumb.

• But where do the intermediate values come from now?

• My second brain-storm: the solution provides them.

  typedef vector division;
  typedef division::iterator d_iter;
  typedef division::const_iterator d_citer;
  
  int main() {
  
    string den;
  
    while (cin >> den) {
      string num;
      if (!(cin >> num)) {
        cerr << "Input error.\n";
        return EXIT_FAILURE;
        }
      cout << "\n";
      const division d = long_divide(num, den);
      output(cout, d);
      }
    }
  

How to Do Long Division

• Divide the numerator from left-to-right, digit by digit.

  for (str_itr i = num.begin(); i != num.end();  i++)
    n = n*10 + (*i - '0');
    q = q*10;
  
    const bignum m = n/d;
    if (m != 0)
      if (div.size() != 3)
        div.push_back(n.str());
      div.push_back((m*d).str());
      n = n - m*d;
      q = q + m;
  

Simple and Complicated Long Division

• The previous code only divides non-negative integers.

  • It doesn't handle negative or fractional values.

• Don't complicate the algorithm, wrap it.

  const bool positive =
    ((den[0] == '-') && (num[0] == '-')) || 
    ((den[0] != '-') && (num[0] != '-'));
  str_abs(den);
  str_abs(num);
  
  str_pair n_parts = split(num);
  str_pair d_parts = split(den);
  
  const unsigned shift = d_parts.second.length();
  right_shift(n_parts, shift);
  right_shift(d_parts, shift);
  
  division d = ld(n_parts.first, d_parts.first);
  
  d[0] = string(positive ? "" : "-") + d[0];
  d[1] = den;
  d[2] = num;
  str_pair rem = make_pair(*(d.rbegin()), n_parts.second);
  left_shift(rem, shift);
  *(d.rbegin()) = unsplit(rem);
  return d;
  

Data Structures

• Figure out what the proper data structure is and use it.

  • "Proper" means easiest to use.

• It's easier to chop and shift strings.

• It's easier to do arithmetic on numbers.

• Switching between the two's easy.

• Also, implementing big nums is hard, so keep it simple.

  • Only natural numbers, no negative or fractional values.

This page last modified on 30 November 2001.