Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4EC39359.8050907@bitblocks.com> (permalink) |
|---|---|
| Date | 2011-11-16 02:41 -0800 |
| From | Bakul Shah <usenet@bitblocks.com> |
| Newsgroups | comp.arch |
| Subject | Re: cost of prolog/epilog |
| References | (11 earlier) <jpm2p8-k571.ln1@ntp6.tmsw.no> <874ny93voz.fsf_-_@Niukka.kon.iki.fi> <l563p8-n081.ln1@ntp6.tmsw.no> <2011Nov14.104535@mips.complang.tuwien.ac.at> <eja7p8-oed1.ln1@ntp6.tmsw.no> |
| Organization | Sonic.Net |
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
>> <http://groups.google.com/group/comp.compilers/browse_thread/thread/ecfa5ee1512a8ab6/da010694a1916a37#da010694a1916a37>
>>
>> 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.
Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-20 19:51 +0000
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-20 22:35 +0200
Re: big-little Mark Thorson <nospam@sonic.net> - 2011-10-20 14:18 -0800
Re: big-little nmm1@cam.ac.uk - 2011-10-21 07:54 +0100
Re: big-little David Kanter <dkanter@gmail.com> - 2011-11-09 01:06 -0800
Re: big-little nmm1@cam.ac.uk - 2011-11-09 11:07 +0000
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-21 09:25 +0200
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-21 11:07 -0400
Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-21 16:28 +0000
Re: big-little nmm1@cam.ac.uk - 2011-10-21 17:07 +0100
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-21 13:25 -0400
Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-21 19:45 +0000
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-22 14:44 -0400
Re: big-little ChrisQ <meru@devnull.com> - 2011-10-22 16:57 +0000
Re: big-little nmm1@cam.ac.uk - 2011-10-22 17:40 +0100
Re: big-little ChrisQ <meru@devnull.com> - 2011-10-23 14:39 +0000
Re: big-little nmm1@cam.ac.uk - 2011-10-23 16:11 +0100
Re: big-little ChrisQ <meru@devnull.com> - 2011-10-23 17:44 +0000
Re: big-little nmm1@cam.ac.uk - 2011-10-23 18:46 +0100
Re: big-little Thomas Womack <twomack@chiark.greenend.org.uk> - 2011-10-23 19:30 +0100
Re: big-little nmm1@cam.ac.uk - 2011-10-23 19:59 +0100
Re: big-little BGB <cr88192@hotmail.com> - 2011-10-23 13:21 -0700
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-23 20:38 +0200
Re: big-little nmm1@cam.ac.uk - 2011-10-23 22:38 +0100
Re: big-little BGB <cr88192@hotmail.com> - 2011-10-23 17:56 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-24 07:58 +0100
Re: big-little BGB <cr88192@hotmail.com> - 2011-10-24 16:34 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-25 08:09 +0100
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-25 14:52 +0200
Re: big-little nmm1@cam.ac.uk - 2011-10-25 17:28 +0100
Re: big-little BGB <cr88192@hotmail.com> - 2011-10-25 13:06 -0700
Re: big-little BGB <cr88192@hotmail.com> - 2011-10-25 15:22 -0700
Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-25 19:47 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-26 08:09 +0100
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-26 12:06 +0200
Re: big-little nmm1@cam.ac.uk - 2011-10-26 10:47 +0100
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-26 11:58 +0200
Re: big-little nmm1@cam.ac.uk - 2011-10-26 10:44 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 03:45 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-26 11:45 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 09:15 -0700
Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-26 12:51 -0700
Re: big-little Andrew Reilly <areilly---@bigpond.net.au> - 2011-10-26 11:45 +0000
Re: big-little nmm1@cam.ac.uk - 2011-10-26 15:42 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 09:07 -0700
Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-26 12:53 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-26 21:05 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 13:20 -0700
Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-26 17:55 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-27 09:10 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 01:34 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-27 10:29 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 04:28 -0700
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-27 12:22 -0400
Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-27 18:08 +0000
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 11:50 -0700
Re: big-little Jean-Marc Bourguet <jm@bourguet.org> - 2011-10-27 14:10 +0200
Re: big-little nmm1@cam.ac.uk - 2011-10-27 17:58 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 13:15 -0700
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 04:10 -0700
Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-10-27 14:04 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-27 23:07 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 15:58 -0700
Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-27 22:57 +0000
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-27 16:39 -0700
Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-28 00:16 +0000
Re: big-little nmm1@cam.ac.uk - 2011-10-28 09:52 +0100
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-28 07:01 -0700
Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-28 16:45 +0000
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-29 13:13 -0700
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-30 03:36 -0700
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-30 03:55 -0700
Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-10-28 11:15 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-28 20:01 +0100
Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-29 17:46 +0000
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-29 11:30 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-29 20:02 +0100
Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-10-29 13:09 -0700
Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-29 17:42 -0700
Re: big-little nmm1@cam.ac.uk - 2011-10-30 08:16 +0000
Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-11-04 10:06 -0700
Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-11-04 15:19 -0700
Re: big-little nmm1@cam.ac.uk - 2011-11-05 09:13 +0000
Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-11-05 09:03 -0700
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 13:38 -0700
Re: big-little Robert Wessel <robertwessel2@yahoo.com> - 2011-10-26 18:44 -0500
Re: big-little Michael S <already5chosen@yahoo.com> - 2011-10-26 17:05 -0700
Re: big-little Robert Wessel <robertwessel2@yahoo.com> - 2011-10-26 21:03 -0500
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-26 14:37 -0400
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-26 15:38 -0400
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-10-26 16:06 -0400
Re: big-little BGB <cr88192@hotmail.com> - 2011-10-27 00:15 -0700
Re: big-little Morten Reistad <first@last.name> - 2011-11-03 17:30 +0100
Re: big-little "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-11-03 20:45 -0700
Re: big-little Thomas Womack <twomack@chiark.greenend.org.uk> - 2011-11-04 11:13 +0000
Re: big-little MitchAlsup <MitchAlsup@aol.com> - 2011-11-04 10:12 -0700
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-04 09:26 -0700
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-11-05 11:32 -0400
Re: big-little EricP <ThatWouldBeTelling@thevillage.com> - 2011-11-05 11:55 -0400
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-05 09:58 -0700
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-05 18:39 +0100
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-05 15:00 -0700
Re: big-little wclodius@lost-alamos.pet (William Clodius) - 2011-11-05 18:43 -0600
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-05 19:46 -0700
Re: big-little ChrisQ <meru@devnull.com> - 2011-11-11 12:31 +0000
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-11 12:39 -0700
Re: big-little Chris Gray <cg@GraySage.com> - 2011-11-11 13:28 -0700
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-11 18:03 -0700
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-12 18:25 +0100
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-12 12:02 -0700
cost of prolog/epilog (was: big-little) Kalle Olavi Niemitalo <kon@iki.fi> - 2011-11-12 22:57 +0200
Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-12 22:47 +0100
Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-14 09:45 +0000
Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-14 12:28 +0100
Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-15 16:48 +0000
Re: cost of prolog/epilog Stefan Monnier <monnier@iro.umontreal.ca> - 2011-11-15 21:35 -0500
Re: cost of prolog/epilog Bakul Shah <usenet@bitblocks.com> - 2011-11-16 02:41 -0800
Re: cost of prolog/epilog nmm1@cam.ac.uk - 2011-11-16 18:14 +0000
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-16 16:50 -0700
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-14 17:00 -0700
Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-15 10:26 +0100
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-15 09:41 -0700
Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-15 16:40 +0000
Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-15 12:44 +0100
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-15 09:01 -0700
Re: cost of prolog/epilog Chris Gray <cg@GraySage.com> - 2011-11-15 15:18 -0700
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-15 21:56 -0700
Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-16 09:21 +0100
Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-16 09:30 +0000
Re: cost of prolog/epilog John Levine <johnl@iecc.com> - 2011-11-16 10:05 +0000
Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-16 11:08 +0100
Re: cost of prolog/epilog Chris Gray <cg@GraySage.com> - 2011-11-16 16:29 -0700
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-16 11:22 -0700
Re: cost of prolog/epilog anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-17 13:27 +0000
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-17 10:30 -0700
Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-17 11:21 +0100
Re: cost of prolog/epilog Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-17 11:56 +0100
Re: cost of prolog/epilog timcaffrey@aol.com (Tim McCaffrey) - 2011-11-17 20:27 +0000
Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-18 10:57 +0100
Re: cost of prolog/epilog BGB <cr88192@hotmail.com> - 2011-11-17 10:42 -0700
Re: cost of prolog/epilog (was: big-little) "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-11-12 14:05 -0800
Re: cost of prolog/epilog (was: big-little) Bernd Paysan <bernd.paysan@gmx.de> - 2011-11-18 02:39 +0100
Re: cost of prolog/epilog torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-18 10:59 +0100
Re: cost of prolog/epilog Bernd Paysan <bernd.paysan@gmx.de> - 2011-11-18 22:06 +0100
Re: cost of prolog/epilog (was: big-little) mac <acolvin@efunct.com> - 2011-11-20 23:01 +0000
Re: cost of prolog/epilog Chris Gray <cg@GraySage.com> - 2011-11-13 13:35 -0700
Re: big-little wclodius@lost-alamos.pet (William Clodius) - 2011-11-11 22:13 -0700
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-11 23:43 -0700
Re: big-little Chris Gray <cg@GraySage.com> - 2011-11-12 14:08 -0700
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-12 19:10 -0700
Re: big-little Chris Gray <cg@GraySage.com> - 2011-11-13 13:40 -0700
Re: big-little Bakul Shah <usenet@bitblocks.com> - 2011-11-13 14:49 -0800
Re: big-little BGB <cr88192@hotmail.com> - 2011-11-13 18:51 -0700
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-24 10:12 +0200
Re: big-little Stefan Monnier <monnier@iro.umontreal.ca> - 2011-10-24 12:11 -0400
Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-24 10:28 -0700
Re: big-little nospam@ab-katrinedal.dk (Niels Jørgen Kruse) - 2011-10-24 19:38 +0200
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-24 21:02 +0200
Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-23 12:02 -0700
Re: big-little Morten Reistad <first@last.name> - 2011-11-03 00:51 +0100
Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-20 16:59 -0700
Re: big-little Anne & Lynn Wheeler <lynn@garlic.com> - 2011-10-20 21:13 -0400
Re: big-little nmm1@cam.ac.uk - 2011-10-21 08:01 +0100
Re: big-little "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-10-21 05:39 -0700
Re: big-little torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-10-24 10:18 +0200
Re: big-little Pedro Pereira <ppereira@grupopie.com> - 2011-10-21 10:40 +0100
Re: big-little Paul Gotch <paulg@at-cantab-dot.net> - 2011-10-21 12:42 +0100
Re: big-little nik Simpson <nik_s@knology.net> - 2011-10-21 11:00 -0500
Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-20 21:13 +0000
Re: big-little timcaffrey@aol.com (Tim McCaffrey) - 2011-10-20 21:43 +0000
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-21 09:23 +0200
Re: big-little Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-21 14:35 +0200
Re: big-little Rick Jones <rick.jones2@hp.com> - 2011-10-21 17:15 +0000
Re: big-little BGB <cr88192@hotmail.com> - 2011-10-21 16:41 -0700
Re: big-little jacko <jackokring@gmail.com> - 2011-10-26 14:12 -0700
csiph-web