Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!news.glorb.com!news-xfer.nntp.sonic.net!posts.news.sonic.net!nnrp1.nntp.sonic.net!not-for-mail Message-ID: <4EC39359.8050907@bitblocks.com> Date: Wed, 16 Nov 2011 02:41:29 -0800 From: Bakul Shah User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7; rv:8.0) Gecko/20111103 Thunderbird/8.0 MIME-Version: 1.0 Newsgroups: comp.arch Subject: Re: cost of prolog/epilog References: <%Gctq.21959$yY3.7294@newsfe01.iad> <0v8go8-jqg1.ln1@ntp6.tmsw.no> <1ka9v9g.1jhyz5n1o6blj4N%wclodius@lost-alamos.pet> <87y5vmo130.fsf@GraySage.com> <874ny93voz.fsf_-_@Niukka.kon.iki.fi> <2011Nov14.104535@mips.complang.tuwien.ac.at> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Lines: 71 Organization: Sonic.Net NNTP-Posting-Date: 16 Nov 2011 10:41:29 GMT NNTP-Posting-Host: 2f780529.news.sonic.net X-Trace: DXC=UaA3[d=KPCG7jmAoUKdoRGm4K\QM1CV^@1OYf0H`?;XAb;H@HW?b?]AU[Zjk:d[l;FLPdlAb=\hBB X-Complaints-To: abuse@sonic.net Xref: x330-a1.tempe.blueboxinc.net comp.arch:4789 On 11/14/11 3:28 AM, Terje Mathisen wrote: > Anton Ertl wrote: >> Terje Mathisen<"terje.mathisen at tmsw.no"> writes: >>> I notice that gcc seem to have automatically converted the second >>> recursive fib_simple() call, which is really tail recursion, into a much >>> faster loop. >> >> There is no tail recursion in >> >> function fib(x:int):int >> { >> if(x>2)return(fib(x-2)+fib(x-1)); >> else return(1); >> } >> >> There is an addition after the recursion. >> >> However, gcc manages to transform code like this into a loop that >> contains only one recursion (possibly by transforming it into a >> tail-recursive version as an intermediate step); see >> >> >> for a longer discussion. > > So gcc must effectively generate a version of fib() which has a second parameter to be added to the > result of the first evaluation? > .... > OK, I see from the c.c discussion that this is close to what gcc is doing, except that it might > instead be a pattern match on the fib() dual recursion setup? > > Terje > If compilers can detect "fibonacci style" dual recursion patterns, may be they can improve an O(exp N) algorithm to an O(log N) one! Consider the following equality (easy to derive): fib(n) == fib(k+1)*fib(n-k) + fib(k)*fib(n-k-1) This translates to fib(2k) == fib(k)*(2*fib(k-1)+fib(k)) -- even n fib(2k+1) == fib(k)^2 + fib(k+1)^2 -- odd n Scheme code (using a table for small fibs): (define (fib n) (case n ((0 1 5) n) ((2 3 4) (- n 1)) (else (let* ((k (quotient n 2)) (fk (fib k))) (if (odd? (modulo n 2)) (let ((fk1 (fib (+ k 1)))) (+ (* fk fk) (* fk1 fk1))) (let ((fk-1 (fib (- k 1)))) (* fk (+ (* 2 fk-1) fk)))))))) In gambit (gci) the crossover point is at about 1000 (compared to a tail recursive tc-fib). (fib 10^6) took 1.3 seconds, while (tc-fib 10^6) took 2 minutes. Of course, at such large number bignum arithmetic makes tc-fib grow more as N^2 + GC plays a significant role: 58K GCs vs 545 GCs for fib. No idea if this is of any practical value but it is interesting that tail call optimization of fib will at most give you a linear algorithm! Are there iteration patterns that can be mapped to such dual recursion? And BTW, this is parallelizable.