binary-reduce ( ... seq start quot: ( ... elt1 elt2 -- ... newelt ) -- ... value )


Vocabulary
sequences

Inputs
seqa sequence
startan object
quota quotation with stack effect ( ... elt1 elt2 -- ... newelt )


Outputs
valuean object


Word description
Like reduce, but splits the sequence in half recursively until each sequence is small enough, and calls the quotation on these smaller sequences. If the quotation computes values that depend on the size of their input, such as bignum arithmetic, then this algorithm can be more efficient than using reduce.

Notes
The quotation may update values below its two inputs. The left half is reduced before the right half, and intermediate results are kept out of the quotation's row.

Examples
Computing factorial:
USING: prettyprint sequences math ; 40 <iota> rest-slice 1 [ * ] binary-reduce .
20397882081197443358640281739902897356800000000


Definition


: binary-reduce
( ... seq start quot: ( ... elt1 elt2 -- ... newelt ) -- ... value )
pick dup slice?
[ [ seq>> ] 3dip [ from>> 0 max ] [ to>> 0 max over - ] bi ]
[ length 0 max 0 swap ] if (binary-reduce) ; inline