🚀 go-pugleaf

Alan L. Lovejoy (alovejoy@concentric.net) wrote:
: 
: I did those benchmars to prove that Smalltalk message sends are faster
: than c function calls.  To do that, I needed a benchmark that consisted

How is that possible, given that the message has to find the entry
point of the method and has to communicate parameters by mechanisms
not unavailable to C.

: mostly of function calls/message sends--and involved as little other
: code as possible.  The recursive factorial and fibonacci functions
: meet those requirements better than anything else I could think of.
: 
: To do any better, you'd need a completely synthetic benchmark.

So, compute the number p(n,k) of ways of writing n as the sum of k
positive numbers (irrespective of ordering), i.e., the number of k-way
partitions of n.  The recursion formula is

      p(n,k)  =  p( n-1, k-1 )  +  p( n-k, k )

i.e., the number of partitions that involve a 1 plus the number that
don't involve a 1.  The boundary conditions are that 
   
      p(n,k) = 1 whenever k is 1 or n  

and

      p(n,k) = 0 whenver k is less than one or greater than n.

The beauty of this application of recursion is that each call
generates two more, without the numbers growing so fast as with
factorial and/or fibonacci (which tend to overflow before 
generating an interesting amount of work).

Tom Payne (thp@cs.ucr.edu)