Path: utzoo!attcan!uunet!ncrlnk!ncrcae!hubcap!gatech!bloom-beacon!tut.cis.ohio-state.edu!mailrus!ncar!noao!arizona!mike
From: mike@arizona.edu (Mike Coffin)
Newsgroups: comp.lang.scheme
Subject: Re: Efficiency of Y (Was: Limitation with lambda)
Message-ID: <7857@megaron.arizona.edu>
Date: 15 Nov 88 16:51:50 GMT
References: <8811142229.AA01756@duchamps.ads.com>
Organization: U of Arizona CS Dept, Tucson
Lines: 41

From article <8811142229.AA01756@duchamps.ads.com> (Bob Riemenschneider):
> Here's a simple experiment you can perform using your favorite Scheme.
  [three definitions of a factorial function omitted: one
   iterative, one recursive, and one using the Y combinator]
>    3.	Compute the factorial of a number using each of the three procedures,
> 	timing the results.  Make the number large enough so that you can get
> 	a reasonably accurate timing.  (I found 100 worked well for MacScheme,
> 	and 1000 for T on my Sun 3.)
> 
> I found performance of the three to be identical, leading me to believe that,
> given current Scheme compiler technology, there's no reason to avoid using Y.

I tried this using T.  When I performed the experiment as stated, I
indeed got identical times for the three definitions:
> (time (factorial-loop 100))
  virtual time = 0.36 seconds
> (time (factorial-rec 100))
  virtual time = 0.36 seconds
> (time (factorial-lfp 100))
  virtual time = 0.36 seconds


However, when I instead calculated the factorial of a small number many
times, there was a huge difference --- more than a factor of 10 ---
between the times: 

> (time (factorial-loop 10) 1000)
  virtual time = 0.18 seconds
> (time (factorial-rec 10) 1000)
  virtual time = 0.2 seconds
> (time (factorial-lfp 10) 1000)
  virtual time = 2.58 seconds

I think the benchmark, as originally stated, mostly measures the speed
of longnum arithmetic, and not the efficiency of the various contol
constructs.

-- 
Mike Coffin				mike@arizona.edu
Univ. of Ariz. Dept. of Comp. Sci.	{allegra,cmcl2}!arizona!mike
Tucson, AZ  85721			(602)621-2858