Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #52762
| From | Spiros Bousbouras <spibou@gmail.com> |
|---|---|
| Newsgroups | comp.lang.forth, comp.theory |
| Subject | Re: Stack Operator Symbols |
| References | (5 earlier) <874m3un959.fsf@nightsong.com> <1fqdnTibotrDKojFnZ2dnUU7-KnNnZ2d@supernews.com> <87k2cpl42w.fsf@nightsong.com> <nlxRz.173904$EN.36366@fx30.am4> <87fundl0i7.fsf@nightsong.com> |
| Message-ID | <dviYz.337429$IO.260330@fx45.am4> (permalink) |
| Organization | virginmedia.com |
| Date | 2016-11-20 14:33 +0000 |
Cross-posted to 2 groups.
[Crossposting to comp.theory ]
On Sun, 30 Oct 2016 19:23:44 -0700
Paul Rubin <no.email@nospam.invalid> wrote:
> Spiros Bousbouras <spibou@gmail.com> writes:
> > "you wouldn't write code like this in Forth for any other purpose than
> > a benchmark".
>
> Would you code that function differently if it were for some purpose
> other than benchmarking?
For ease of reference we're talking about
def tak( x, y, z)
if y < x
tak(
tak(x-1, y, z),
tak(y-1, z, x),
tak(z-1, x, y)
)
else
z
end
end
and
def tarai( x, y, z)
if y < x
tarai(
tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y)
)
else
y # not z!
end
end
as defined in en.wikipedia.org/wiki/Tak_(function) .Note that the wikipedia
article does not give the definition in relation to any specific programming
language so we're assuming that the subtraction always gives the mathematically
correct result.
Moving to your question , my first reaction is that tak is so artificial that
it would never arise in "real" code so the short answer is that I wouldn't code
it all :-D
But if amazingly enough it did arise then I would perform some kind of
mathematical analysis to understand its behaviour. At the very least this needs
to be done to see how deeply the recursion may go so that we don't run out of
stack space. Beyond that , I was hoping to understand which integer arguments
get called during the recursion (depending on the original arguments) with the
possibility of storing them in an array or hash table or something and see if
it makes things faster. But it turns out you can do better than that ; it's
possible to "solve" the recursion completely i.e. rewrite the function in a way
which doesn't involve recursion at all.
Before I describe the solution we need some notation. We will distinguish
various cases. I use labels for each (sub)case , things like "2.1.2.2.1" .Each
subcase is associated with a condition which triggers the subcase and the
condition which triggers for example "2.1.2.2.1" is the conjunction of the
conditions which label 2 , 2.1 , 2.1.2 , 2.1.2.2 and 2.1.2.2.1 .The return
value for each subcase follows after "->" .
So for all integers x , y , z we define tak-nr(x,y,z) as follows :
(1) y>=x -> z
(2) y<x
(2.1) x<z
(2.1.1) x = y+1 -> x
(2.1.2) x > y+1
(2.1.2.1) z = x+1 -> y
(2.1.2.2) z > x+1
(2.1.2.2.1) z-x is even -> x
(2.1.2.2.2) z-x is odd -> y+1
(2.2) x=z -> y
(2.3) x>z
(2.3.1) z>=y -> y
(2.3.2) y>z
(2.3.2.1) y = z+1 -> y
(2.3.2.2) y > z+1
(2.3.2.2.1) x-y is even -> z+1
(2.3.2.2.2) x-y is odd -> y
And that's all ! I'll leave it to someone else to find an elegant way to code
the above in Forth. Sadly , real world programming problems hardly ever admit
a solution as neat as this.
A proof that tak-nr() satisfies the recursive relations is straightforward but
tedious ; one must go through all the 2* subcases , see in which subcase each
recursive call falls , calculate the final result both directly and by using
the return value from each recursive call and verify they are the same. To
prove that tak-nr() is the unique function which satisfies the recursive
relations takes a bit more work but is not hard.
Note that tarai() also has a non recursive definition and in fact a much simpler
one. Annoyingly , the wikipedia article does not mention it but it can be seen at
mathworld.wolfram.com/TAKFunction.html .
Returning to benchmarking , I don't see what advantage tak() or tarai() offer
relative to say good old Fibonacci. Or even coding an algorithm which naturally
gets expressed in a recursive manner like quicksort for example. With the
latter you even end up with a piece of code which is useful for something else
apart from benchmarking. The references given above do not provide any insights
or explain why Takeuti defined tarai() .The wolfram.com page mentions some
mathematical connections but does not give specifics.
--
I guess I should warn you , if I turn out to be particularly clear ,
you've probably misunderstood what I've said.
From a 1988 speech at the Economic Club of New York by
Alan Greenspan, Chairman of the Federal Reserve.
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-24 20:42 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-25 01:58 -0700
Re: Stack Operator Symbols november.nihal@gmail.com - 2016-10-25 10:52 -0700
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-10-27 19:13 -0400
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-27 17:08 -1000
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-28 21:53 +1000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-28 20:42 -0700
Re: Stack Operator Symbols Walter Banks <walter@bytecraft.com> - 2016-10-29 17:15 -0400
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-29 17:27 -0700
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-28 20:56 -1000
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-29 00:46 -0700
Re: Stack Operator Symbols Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-10-29 04:30 -0500
Re: Stack Operator Symbols rickman <gnuarm@gmail.com> - 2016-10-29 16:58 -0400
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-29 14:21 -0700
Re: Stack Operator Symbols Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-10-30 04:03 -0500
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-30 18:06 -0700
Re: Stack Operator Symbols Spiros Bousbouras <spibou@gmail.com> - 2016-10-31 01:43 +0000
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-30 19:23 -0700
Re: Stack Operator Symbols Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-10-31 05:13 -0500
Re: Stack Operator Symbols albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-10-31 12:42 +0100
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 12:12 +0000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 14:49 +0000
Re: Stack Operator Symbols mhx@iae.nl - 2016-10-31 13:17 -0700
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-03 16:38 +0000
Re: Stack Operator Symbols Spiros Bousbouras <spibou@gmail.com> - 2016-11-20 14:33 +0000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 08:35 +0000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-30 11:01 +0000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-30 10:01 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-11-03 14:46 -0700
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-04 23:04 +0000
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-11-05 03:16 -0400
Re: Stack Operator Symbols peter.m.falth@gmail.com - 2016-10-29 09:13 -0700
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-30 08:47 +1100
Re: Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-29 14:57 -0700
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-30 09:20 +1100
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-10-29 18:46 -0400
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-29 19:45 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-29 20:29 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-29 20:47 -0700
Re: Stack Operator Symbols Cecil Bayona <cbayona@cbayona.com> - 2016-10-29 23:15 -0500
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-29 21:37 -1000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-30 10:07 -0700
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-29 21:35 -1000
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-31 13:11 +1100
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-30 20:02 -0700
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-30 22:08 -1000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 09:02 +0000
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-11-03 20:49 +1100
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-03 15:33 +0000
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-11-03 16:55 -0400
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-03 22:21 +0000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-27 20:31 -0700
Re: Stack Operator Symbols november.nihal@gmail.com - 2016-10-28 09:52 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-28 20:32 -0700
Re: Stack Operator Symbols Mark Wills <markwills1970@gmail.com> - 2016-10-30 04:49 -0700
Re: Stack Operator Symbols Coos Haak <htrofhc@gmail.com> - 2016-10-30 14:49 +0100
Re: Stack Operator Symbols Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2016-10-31 13:31 +0100
Re: Stack Operator Symbols Coos Haak <htrofhc@gmail.com> - 2016-10-31 14:12 +0100
Re: Stack Operator Symbols Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2016-10-31 15:03 +0100
Re: Stack Operator Symbols Mark Wills <markwills1970@gmail.com> - 2016-11-03 14:22 -0700
Re: Stack Operator Symbols Coos Haak <htrofhc@gmail.com> - 2016-11-04 00:46 +0100
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-11-05 13:14 +1100
Re: Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-30 06:50 -0700
Re: Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-30 08:56 -0700
Re: Stack Operator Symbols albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-10-30 18:19 +0100
csiph-web