The Science of Programming/Lather, Rinse, Repeat

From Wikibooks, open books for an open world
Jump to navigation Jump to search

As CME, Chapter 7 notes, suppose:

   

That is to say, y is some function of x. If that is so, then:

   

is sometimes denoted:

   

with the apostrophe indicating differentiation.

Because of Sway's liberal views on naming variables, we can use the same notation. Consider defining a line:

   var f = line(3,-5);      //equivalent to y = 3x - 5

where the line constructor is just a wrapper for a call to the plus constructor:

   function line(m,b)
       {
       plus(term(m,1),term(b,0));
       }

Then, we can differentiate our line thusly:

   var f' = f . diff();

Since f represents a line and the differentiation of a line yields the slope of a line and the slope of the line is always a constant m, we would expect that evaluating at different points would always yield the slope:

   sway> f' . toString();
   STRING: 3x^0 + 0x^-1
    
   sway> f' . value(0);
   EVALUATION ERROR: :mathError
   stdin,line 9: exponentiation: cannot divide by zero

What happened? The problem is the second term of f'. We end up evaluating that term with x = 0. What is x ^ -1 when x is zero? It's . That's what caused the divide-by-zero error. What should we do about it? Whenever a term's exponent goes to zero, we should force the exponent to stay at zero, when differentiating.

Here's a new version of diff for term:

   function diff()
       {
       if (n == 0)
           {
           term(0,0);
           }
       else
           {
           term(a * n,n - 1);
           }
       }

Does it work? After remaking, f and f', we have

   sway> f' . toString();
   STRING: 3x^0 + 0x^0
    
   sway> f' . value(0);
   REAL_NUMBER: 3.000000000
   sway> f' . value(5);
   REAL_NUMBER: 3.000000000

we see that it does.

If we repeat the differentiation process again, we find out how fast the slope is changing at any given point. For a line, the slope never changes so we would expect the derivative of the derivative (also known as the second derivative) always to yield zero.

   var f'' = f' . diff();
   
   sway> f'' . toString();
   STRING: 0x^0 + 0x^0
   sway> f'' . value(0);
   INTEGER: 0
   sway> f'' . value(5);
   INTEGER: 0

Confirmed.

More on visualization[edit | edit source]

We really need to do something about our visualization. It's printing out terms that we really don't need to see. Let's simplify the output by making term's toString method more complicated. Please implement the following rules for term's toString method:

  1. if the coefficient is zero, toString should return "0"
  2. if the exponent is zero, toString should return "" + a
  3. if both the coefficient and the exponent are 1, toString should return "x"
  4. if the exponent is one, toString should return "" + a + "x"
  5. if the coefficient is one, toString should return "x^" + n
  6. otherwise, toString should return "" + a + "x^" + n

Earlier rules take precedence over later rules. After implementing these rules and remaking f, f', and f'', we get the following visualizations:

   sway> f . toString();
   STRING: 3x + -5
   sway> f' . toString();
   STRING: 3 + 0
   sway> f'' . toString();
   STRING: 0 + 0

Somewhat better. Now we need to improve plus to throw away constant terms with a value of zero. We can do this in the main body of the plus constructor:

  1. if the first argument is equivalent to zero, have plus return the second argument
  2. if the second argument is equivalent to zero, have plus return the first argument
  3. otherwise, have plus return this

Your logic should look like this:

   function plus(p,q)
       {
       ...
       if (p is equivalent to zero)
           {
           q;
           }
       else if (q  is equivalent to zero)
           {
           p;
           }
       else
           {
           this;
           }
       }

How do we determine if an argument to plus is equivalent to zero? Since we are representing zero as a term with a zero coefficient, we could use logic like this:

   if (p is :term && p . coefficient == 0)

Now our hack of using a term to represent zero is starting to raise its ugly head. Our code is becoming non-obvious to someone who might be reading our code (for maintenance purposes, perhaps) without benefit of reading this text. Zero is a constant, in that it doesn't ever change; zero is always zero. A term, on the other hand, often changes, depending on the value of the independent variable. This leads to a cognitive dissonance that increases the difficulty of understanding our code.

Let's solve this problem by building a 'constant' constructor. This constructor will have all the methods of term, but will better represent a value that never changes. Here is an attempt:

   function constant(value)
       {
       function toString() { "" + value; }
       function diff() { ... }
       function y(x) { ... }
       this;
       }

The implementations of diff and y are left as an exercise and should implement the following logic:

  • the differential of a constant is a constant zero
  • the y value of a constant is always the value of the constant, regardless of the value of the independent variable

Now, we can test for a zero object in plus like this:

   if (p is :constant && p . value == 0)

See how this code is much more understandable. We now update our diff method in term to take advantage of our new constant constructor.

   function term(coefficient,exponent)
       {
       ...
       function diff()
           {
           if (n == 0)
               {
               constant(0);
               }
           else
               {
               term(a * n,n - 1);
               }
           }
       ...
       this;
       }

With these changes and after remaking f, f', and f'' with the new versions of plus, term and constant, we get the following visualizations:

   sway> f . toString();
   STRING: 3x + -5
   sway> f' . toString();
   STRING: 3
   sway> f'' . toString();
   STRING: 0

Much better.

Successive Differentiations of Complex Polynomials[edit | edit source]

It's rather uneventful to repeatedly differentiate a line. Higher-order polynomials[1] are a little more interesting. Rather than build up a high order polynomial of many terms piece by piece, as in:

   var a = term(1,0);
   var b = plus(term(2,1),a);
   var c = plus(term(3,2),b);
   var y = plus(term(4,3),c);

We can build it up en masse:

   var y = plus(term(4,3),plus(term(3,2),plus(term(2,1),term(1,0))));

or since this whole scale building can be hard to read, build y using infix operator syntax:

   var y = term(4,3) plus term(3,2) plus term(2,1) plus term(1,0);

No matter how you make y (it's all a matter of preference), we can differentiate it successively:

   var y' = y . diff();
   var y'' = y' . diff();
   var y''' = y'' . diff();
   
   sway> y . toString();
   STRING: 4x^3 + 3^x2 + 2x + 1
   sway> y' . toString();
   STRING: 12x^2 + 6^x + 2
   sway> y'' . toString();
   STRING: 24x + 6
   sway> y''' . toString();
   STRING: 24

To check numerically, let's evaluate y'' at x = 1 and 2.

   sway> y'' . value(1);
   INTEGER: 30
   sway> y'' . value(2);
   INTEGER: 54

The object y''' should represent the constant 24:

   sway> y''' . value(1);
   INTEGER: 24
   sway> y''' . value(2);
   INTEGER: 24

Everything looks good.

Questions[edit | edit source]

1. Justify mathematically each of the simplifying visualization rules for a term.

2. Add simplification to the minus constructor. The simplification is similar to plus but is a tiny bit trickier.

3. Add simplification to the times constructor. You should return constant zero if either argument is zero and if one of the arguments is constant one, return the other. Otherwise, return this.

4. Add simplification to the div constructor. You should return constant zero if the numerator (the first argument) is constant zero. You should return the numerator if the denominator (the second argument) is constant one. Otherwise, you should return this.

5. Represent and plot in sway using gnuplot. What is ? Plot it versus x. What does it represent? What is ? Plot it versus x. What does it represent? What is ? Plot it versus x.

6. Use both sway or pencil and paper to do 1-3 on p. 82.

Footnotes[edit | edit source]

  1. The higher the order of a polynomial, the larger the largest exponent in the terms making up the polynomial.


Guzzintas and other Cipherin' · As Time Goes By