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.