Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: Algorithms, long division in particular
Posted:
Feb 24, 1995 6:47 PM


This is a long posting, so if you are not interested or in a hurry, perhaps you might want to skip it or save it for later.
On Thu, 23 Feb 1995, Tad Watanabe wrote:
> On Thu, 23 Feb 1995, Edward S. Miller wrote: > > > Now for my personal spin on algorithms. Humans have spent countless > > effort to develop efficient means for accomplishing all sorts of tasks. > > In mathematics, we see dozens or thousands of algorithms put to use, > > depending on our level of immersion and experience. The long division > > algorithm and the multiple digit multiplication algorithm (again, the > > one I use based on the distributive law) are the earliest instances I > > recall of iterated algorithms with multiple _different_ operations; > > division is the first with a nontrivial ending condition. > > Could you expand on this a little?
Certainly. In the algorithm I call long division, when approaching 345 divided by 16, my first step is to compare 16 to 34 and decide (usually by estimation, sometimes by emulating the next specified step) that 16 is about half of 34. I need then multiply 16 by 2. Then I subtract32 from 34. I carry down a digit. Then I iterate the process. I stop when the remaining number is actually less than my divisor.
I have to start with the appropriate bookkeeping technique to preserve digit alignment. Sometimes, but not in this particular problem, the carry down still doesn't make the current step dividend large enough, so I carry down another digit; I don't just stop. I also have to place a zero in the appropriate position of the quotient because of our positional numeration system.
There are multiple other arithmetic operations involved in the algorithm as well as estimation skills. The decision to terminate is unlike the multiplication algorithm stop point in the sense that you can't just keep on until you have nothing to work with.
As for understanding the algorithm, in the case of no remainder problems, the algorithm is literally the reverse of the multiplication algorithm except that the rows would be added one at a time instead of all at once. Each single digit multiplication is present and executed. Try doing 42 times 37 and then 1554 divided by 42. The remainder, of course, complicates things a little but divisions with remainders can be viewed as the reverse of a compound multiplication and addition exercise.
> > > > Throughout subsequent mathematics we encounter such algorithms of all > > types. Sometimes, in "real life," for physical, temporal, or economic > > reasons, it is necessary to use algorithms for single or repeated > > operations. We do need to teach our students how to apply algorithms. I > > happen to prefer long division because if we have to wait for > > factoring or Euclid's algorthm or Horner's algorithm or L'Hopital's rule, > > we're dead before we start. > > > > But you are not advocating teaching in the sense of imposing algorithms > on students whether or not they make sense, are you? Or, are you saying > that there are contexts in schooling (which I happen to believe is a part > of "real" life), there are occasions we should? >
In reverse order, I meant "real life" as opposed to objects and actions which only exist in thoughts and discussions without being actualized. For example, many fine discussions about strategies for and consequences of colonizing other planets have happened, but planets have not been colonized (by humans, at least) in "real life". Of course "real life" includes schooling. Sorry if that wasn't clear.
An example of an algorithm used in "real life" schooling for physical and economic reasons is when I actually, in the middle of some other problem, / 2 evaluate x sin x dx by hand using integration by parts twice because / I don't happen to have a computer handy in class that day. Honest, it happens on Mondays and Wednesdays in calculus.
Furthermore, there are times when it is necessary to just learn when an algorithm is applicable and how to use it for the sake of expedience (in nonschooling situations, at least). I learned the braking algorithm for my car, I know it doesn't often work on ice, but I certainly didn't design a brake nor did I invent the concept of braking independently. Sometimes it is necessary to go with thousands of years of accumulated human knowledge and methods in some areas so that you can think in others. An interesting account along these lines is contained in the book "Planet of the Apes" by Pierre Boulle.
And finally, I never "impose" an algorithm on a student or anyone else for that matter. I do demonstrate algorithms which I think make sense (or perhaps more accurately, which I think will make sense to the audience) and try to help the students understand it at some level. I rarely try to prove that an algorithm works in a rigorous way until the precalculus/calculus stage of the game.
On the other hand, if a student uses a selfdeveloped algorithm or one learned from someone other than myself with which I am not familiar, I try to prove it rigorously for myself. If I do, I allow the student to use it. If I find a counterexample I either provide it to the student or give a good hint, depending on the nature of the example. Sometimes I am stuck without proof or counterexample, in which case I caution the student that the algorithm may be unreliable and ask her to convince me that it is. Sometimes she does and sometimes she doesn't. If she does, I allow its use; If she doesn't, I do not allow its use.
After ten years in the classroom, not a single class goes by where I do not improve one of my own algorithms and where no student shows me one I haven't seen before which works as well or better than the one I use. On the other hand, some 20 years after learning long division, it is still the algorithm which makes the most sense to me.
Ed
 Edward S. Miller edmiller@lcsc.edu
Division of Natural Sciences VOICE 2087992810 LewisClark State College FAX 2087992064 500 8th Avenue Lewiston ID 835012698 USA 



