Holding off on evaluating variables

There is a difference between performing a calculation and solving a problem.

I’ve been considering the equation of a circle, x^2 + y^2 = r^2. Except, you see, that’s not the entire thing. There’s a bit that we’ve dropped because it’s  zeroes (and therefore doesn’t affect our equation):

(x-h)^2 + (y-k)^2 = r^2.

This equation contains the full information–everything that is necessary to draw and position a circle on a cartesian graph. You see, the and k move the circle around the graph. When the circle is on the origin, they are both zero and often dropped from the formula. When figuring something quickly with a circle, the shortened form is more than adequate. However, without them, part of the story is lost.

Similarly, if we have the task of working a problem it is tempting to perform the arithmetic along the way. If we resist, however, at the end we produce a general solution that may be used for other similar problems.

Programming can work the same way. We may write a program to perform a calculation. This would involve lots of hardcoding, many assumptions making it analogous to our “arithmetic along the way”.

Alternatively, try leaving the variables in, or not doing the arithmetic along the way, and preserve the information in the equation which would otherwise be lost.

Naive Programming

I think that may always be the case, especially when the resulting program is a function of what I’m asked to do! I was instead considering how, give experience in mathematical reasoning and programming, one writes increasingly concise code.

Because of the intense usefulness of Maths in programming, I cannot grok my fellow students’ disapproval of the subject. One of the major ways my code has grown less naive is in the borrowing of mathematical concepts.

Naive:

// print the sum of numbers x through y.
int sum(int x, int y) {
  int s = 0;
  for (int i = x; i <= y; i++)
    s += i;

  return s;
}

Insightful:

// print the sum of numbers x through y.
int sum(int x, int y) {
  return y*(y+1)/2 - x*(x+1)/2; 
}

I cannot remember a time when a working insightful function has been worse then the naive equivalent. Even in my contrived example above the naive_sum() has inputs which would yield undefined output such as the case where y <= x while the insightful_sum() would degrade more gracefully.

In the naive style, we’d have to add conditionals to validate inputs that the maths would accept, meaning increased line count, reduced legibility, increased chance of errors, and increased nativity. The only advantage I can see to the naive style is the reduction in mathematically cluttered code.

Helping a little, old (rich) lady

One day, on the drive home from work, I witnessed an elderly lady in battered clothes struggling. Her wheelie basket, piled with laundry, had gotten stuck. In an unexpected and unprecendented pang of empathy, I stopped and offered assistance. Delighted to have me after, apparently, struggling for some time I was quickly able to pop the stuck wheel out of its prison (the sewer grate).

Preparing to leave, she stops me. “Before you leave, I have a reward to offer!”

She has my attention now. “I can give you 1,000,000 dollars or I can give you thirty daily payments starting today of one penny. I shall double each subsequent payment.”

To be kind, I offer the “lower” payment of a penny. I don’t need any old ladies millions of dollars. She gives me a penny and departs.

Sitting back in my office, I stop and think about what I’ve done. I realize that each day she pays me (for all thirty of them) I can expect 2^{day-1} cents. Considering it further, I begin to understand that the miracle of a doubling scheme such as this is that every subsequent day I will receive exactly one more cent than all the previous days combined.

A few weeks later, it now takes a rather large dump truck to deliver the little copper coins. Wondering how many dollars this all amounts to I quickly scribble on a pad of paper: \frac{2^{30}}{100} = \$10,737,418.

Just something to remember when you see an elderly lady in need.

Little Gödel

One day, little Gödel went to class. For whatever reason—perhaps, an unhappy love affair or a bad hangover—little Gödel’s teacher did not feel like teaching. Instead, he instructed the class to sum all of the integers to one hundred, that is, to calculate \sum_{i=1}^{100}.

The teacher correctly expected most of the class to do what I now consider the most inefficient method of performing this operation; they started as follows:

1+2 = 3\\  3 + 3 = 6\\  4 + 6 = 10\\  ...

At about this point, little Gödel walks up to his school master and writes 5025 on the chalk board and proclaims, “I’m done!” Perplexed by the rapidity with which little Gödel solved this problem, the instructor inquires him to “show his work”.

Little Gödel goes on to illustrate that while thinking about the problem he realized that
100 + 0 = 100\\  99 + 1 = 100\\  98 + 2 = 100\\  97 + 3 = 100\\  ...\\  51 + 49 = 100

“This means we have 50*100 or \frac{1}{2}n*n 100’s to sum. But summing the same number over and over is multiplication, that’s easy! However we can’t add 50 to anything–there is no other number between 0 and n that hasn’t been used which will sum to 100. Therefore, at the end of our multiplying spree we must add 50 or \frac{1}{2}n.

Therefore, the sum must be \frac{1}{2}n * n + \frac{1}{2}n.” He quickly simplifies this equation to
\sum_{i=1}^{n} = \frac{n^2 + n}{2}

We all learned something that day! Too bad about the teacher, though.