|Bill Allombert on Sun, 25 Aug 2013 10:48:42 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Two questions about products|
On Wed, Aug 21, 2013 at 09:42:43AM -0400, Charles Greathouse wrote: > I seem to remember that prod() used to use binary splitting, forming > subproducts of roughly equal size so that > > prod(i=1, #v, v[i]) > > was substantially faster than > > s=1; for(i=1, #v, s*=v[i]); s > > for v a decent-sized vector of integers > 1. But this is no longer true; in > particular, emulating (what I remember to be) the old behavior > > fakeprod(v,start=1,end=#v)=if(end-start<3, prod(i=start,end,v[i]), > fakeprod(v,start,(start+end)\2)*fakeprod(v,(start+end)\2+1,end)) > > is substantially faster, even though large vectors are passed repeatedly: > > v=vector(10^5,i,i); > default(timer, 1) > prod(i=1,#v,v[i]); > fakeprod(v); > > When did this change -- or do I misremember? Can binary splitting be > implemented again? You are confusing prod() is an iterator with prescribed behaviour, with factorback which does binary splitting. Cheers, Bill.