...Hendrix) writes Re: balanced REDUCE: a challenge for the brave anton@mips.complang...) writes Re: balanced REDUCE: a challenge for the brave [..] To explain the...start out with a simple unbalanced reduce: : reduce ( 0 x1 ... [x2 x3 --...4 lines are normally not needed): : REDUCE ( 0 n1 ... nn xt -- ) [IS] ...a DEFER action ( a b -- c ) : REDUCE ( 0 n1 ... nn xt -- ) [IS] ...

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: balanced REDUCE: a challenge for the brave [..] And here's the first version of the code for depth-first...u2 xt recurse ( xa ) xb xt execute then ; : reduce ( 0 x1 ... xu xt -- x ) over 0... overflow. With default stacks, on iForth, your first reduce bombs out at around 8000 while Robert's reduce2...

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: balanced REDUCE: a challenge for the brave [..] To explain the problem, let's start out with a simple unbalanced reduce: : reduce ( 0 x1 ... [x2 x3 -- x4] -- x ) [..] Why not use two deques a and b: a size odd if a popleft 2/ a pushleft a pushright then b clear begin a size while...

... on the data stack, not the FP stack). However, if you reduce an arbitrary sequence of fp values with f+, a balanced reduce would normally result in less rounding errors, which is usually desirable (with f* it should not matter much). However, if you really care about an f+-reduce with less rounding errors, there are also other ways to achieve ...

... on the data stack, not the FP stack). However, if you reduce an arbitrary sequence of fp values with f+, a balanced reduce would normally result in less rounding errors, which is usually desirable (with f* it should not matter much). However, if you really care about an f+-reduce with less rounding errors, there are also other ways to achieve that:...

... this gives: [c8:~/gray:15963] gforth reduce.fs -e "10 testreduce mindepth bye"... :3 [c8:~/gray:15964] gforth reduce.fs -e "10 testreduce maxdepth bye..., for n=10. With the balanced REDUCE: [c8:~/gray:15968] gforth reduce...have now implemented a depth-first REDUCE after all (code and discussion ...-depth numbers come from the balanced division into subtrees. Other ways to...

...> With my first attempt at a balanced REDUCE this gives: [c8:~/gray:15963] gforth reduce.fs -e "10 testreduce mindepth bye" ... 3 :3 [c8:~/gray:15964] gforth reduce.fs -e "10 testreduce maxdepth bye" ... 4 and 5 for this test, for n=10. With the balanced REDUCE: [c8:~/gray:15968] gforth reduce.... 36/10 [c8:~/gray:15969] gforth reduce.fs -e "100 testreduce-ad bye"...

... can be used. Thanks. Testing with your permutation code increases the confidence that the balanced REDUCE is correct, especially for non-commutative operations. I used the following code for this testing...i2p loop ; : testreduce-perm ( n -- ) dup genperms ['] compose reduce swap genperms ['] compose reduce2 <> abort" results differ" ; :...

...min 1+ dup . ; With the unbalanced REDUCE this gives: [c8:~/gray:15960] ...0 swap 0 ?do 1 loop ' reduce ." :" . cr ; With my first attempt at...this gives: [c8:~/gray:15963] gforth reduce.fs -e "10 testreduce mindepth bye...swap 0 ?do 1 loop ['] ad reduce ." : " ad. cr ; This gives: With the...5049/100 : 5049/100 With the balanced REDUCE: [c8:~/gray:15968] gforth reduce...

..., m...@iae.nl (Marcel Hendrix) wrote: ( re: Anton's depth first version ) At least, this version can finish alltests without returnstack overflow. With default stacks, on iForth, your first reduce bombs out at around 8000 while Robert's reduce2 only gets to 4000. -marcel Been looking at this problem again, yeah, the recursion breadth first way does eat up a lot of stack...