🚀 go-pugleaf

In article <1992Oct14.175140.12286@cbfsb.cb.att.com>
 dal3@cbnewsg.cb.att.com (dale.e.parson) writes:
   ...
   In article <92Oct14.033708.24102@acs.ucalgary.ca>
    quigley@acs.ucalgary.ca (Martyn Thomas Quigley) writes:
   >I've never been comfortable with this, but for a different reason.
   >Children invariably start from 1 and work up, they simply do not
   >start from n and work down.  Ask them.
   >
   >Martyn
 [Parson then goes on to dispute this.]

I missed Quigley's posting, presumably due to some techical problems
we're having with news, so I'll follow-up to Parson's quote of Quigley
instead.

The choice of doing factorial in an iterative process (i.e. by
succesively converting to easier and easier problems with the same
solution) is *independent* of the choice of order in which to do the
multiplications.  The version that has been under discussion here
happens to count down, but there is an every-bit-as-iterative version
that counts up.  You can even work from the middle out if you are a
masochist.

I earlier formulated a reply to Harvey's claim that I was pulling a
rabbit out of the hat by doing a thinking-aloud of how the iterative
version is arrived at.  I was technically unable to post it then; now
I have additional reason to do so, because I had (foresightedly)
marked with an bracketed comment the point where the thinker could
have gone down a different path by choosing to start by multiplying
the smallest numbers together rather than the largest.

In article <1bf1qlINNgj5@agate.berkeley.edu>
 bh@anarres.CS.Berkeley.EDU (Brian Harvey) writes:

   [concerning n! = 1*n! followed by a*b! = (a*b)*(b-1)!]

   ...  My problem with it is that it's
   not something anyone would naturally think of.  The original problem is to
   compute n! and instead of getting CLOSER to the solution by computing (n-1)!
   you get FARTHER AWAY by computing x*n! instead.  This turns out to
   be helpful but it's a total rabbit-from-hat. ...

   That's an example of what I call "turning computer programming into
   trigonometry" -- making it boring and confusing and full of facts
   to memorize, instead of an immediate source of power. ...

I've got a factorial problem, like maybe
   6 * 5 * 4 * 3 * 2 * 1.

Gee, I wonder if I can transform that into a simpler problem with the
same answer.  What would make it simpler?  Well the problem I've got
is 6 numbers multiplied together.  Five numbers multiplied together
would be simpler.  I wonder if I can find five numbers that when
multiplied together gives the same result?

  6 * 5 * 4 * 3 * 2 * 1 =  __ * __ * __ * __ * __.


Well, I can't just put the numbers I've got into the blanks, because
I've got one more number than blank.  (Thats the whole point.)  Maybe
there is some way to put two numbers into one blank.  I guess I can't
really get something for nothing -- if I only want to have 4
multiplications left to do, I better do one of my 5 now.  If I
multiply two of the numbers together now and put the product in one of
the blanks, that would be a way to get two numbers into one blank.
[Here different students will make different choices which two numbers
to multiply together, yielding different but equally correct iterative
factorial procedures.  I make the choice that leads to the version
we've been talking about.]  Maybe I'll multiply the first two
together, the 6 and the 5, to get 30.  So I have

  6 * 5 * 4 * 3 * 2 * 1 = 30 * 4 * 3 * 2 * 1.

That was great, I got the problem down from a five multiplication
problem to a four multiplication problem.  I bet I could transform it
the same way into a three multiplication problem:

        ... = 120 * 3 * 2 * 1.

If I keep going like this, one multiplication at a time, eventually it
will all boil down to a single number
       .... = 720.
I guess I could call that a "zero multiplication" problem.  And that's
the answer, since it is equal to all the preceding problems, all the
way back to the original factorial one.

Ok, so now I want to write a procedure that could solve any problem of
this form.  What specifics do I have to give it to tell it which
problem of this form to solve?  Well, I could give it the numbers to
multiply together. ...  No, that's silly, there could be arbitrarily
many of them.  I certainly don't want to say that the way to compute
100!  is by multiplying together 100 times 99 times ... all day.  I
wonder if there is some more concise description of these problems
.... oh I see, the numbers after the first always are consecutive,
down to one.  So I could describe the problems by saying "30 times 4
down to 1" or "120 times 3 down to 1" or that kind of thing.  Oh... in
fact the "down to 1" part just means its a factorial ... so I've got
problems like "30 times 4!" or "120 times 3!".  So what I want is a
procedure to multiply some number times some factorial ...

   factorial_product(a, b) =>  a*b!
 
Well, I did those by transforming them to smaller one, like this

   factorial_product(a, b) = factorial_product(a*b, b-1)

Of course, I have to stop making the factorial part smaller
eventually, when it can't get any smaller -- lets see that's when
there were zero multiplications left -- oh ok, that's 0!, like my last
step in the example was really 720 * 0!, though I didn't really think
of it that way, but I guess it makes sense...

   factorial_product(a, b) = if b=0 then a else factorial_product(a*b, b-1)

Ok, so now I have a general way of solving problems of the form one
number times the other number.  Wait a second, that wasn't what I
really wanted ... I really wanted just to do factorials.  Well, ok, I
could just trick my procedure into doing plain factorials by telling
it to multiply by 1, since that doesn't change anything ...

   factorial(n) = factorial_product(1, n)

[Voila, a rabbit!  Is this what you call "boring ... facts to
 memorize"?  I'd call it more like a general problem solving
 heuristic, fit to go into the personal tool-kit right alongside
 'Gee, I wonder if there is a smaller problem which, if I knew the
  answer to it, would make it easy to find the answer to this
  problem?']