Charles Greathouse on Wed, 21 Aug 2013 15:43:29 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Two questions about products


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?

A quick second question: I notice that prodeuler() works like prod(X=a,b, 1.) rather than prod(X=a,b). Is this intentional? Would it be possible to give it a third argument so that prodeuler(p=a, b, 1) could be used if an integer result was desired?

Charles Greathouse
Analyst/Programmer
Case Western Reserve University