From the benchmark page:
sage: R.<x,y,z> = PolynomialRing(GF(13))
sage: time _ = expand((x+y+z+1)**100)
CPU times: user 0.07 s,...
Since (a+b)^p=a^p+b^p over a finite field with charachteristic p and
a^p+b^p has got only two terms this gives the idea to expand the
exponent of the polynom in base p and use this in the powering:
# still a naive code, because sage is not use that the computation of
(a+b+c+..)^p is easy
def fastpower(f,e,p):
if e<0:
return fastpower(f,-e,p)**-1
if e<p:
return f**e
return f**(e%p)*fastpower(f**p,e//p,p)
By this code the above task:
time _ = expand(fastpower(x+y+z+1,100,13))
takes only 0.01 sec. (the original code takes 0.14 sec. on my
computer).
For exponent=500:
time _ = expand(fastpower(x+y+z+1,500,13))
takes only 0.12 sec. (the original code takes 13.79 sec.), means an
about 115 times faster code.
<robert.gerb...@gmail.com> wrote: > From the benchmark page: > sage: R.<x,y,z> = PolynomialRing(GF(13)) > sage: time _ = expand((x+y+z+1)**100) > CPU times: user 0.07 s,...
> Since (a+b)^p=a^p+b^p over a finite field with charachteristic p and > a^p+b^p has got only two terms this gives the idea to expand the > exponent of the polynom in base p and use this in the powering:
> # still a naive code, because sage is not use that the computation of > (a+b+c+..)^p is easy > def fastpower(f,e,p): > if e<0: > return fastpower(f,-e,p)**-1 > if e<p: > return f**e > return f**(e%p)*fastpower(f**p,e//p,p)
> By this code the above task: > time _ = expand(fastpower(x+y+z+1,100,13)) > takes only 0.01 sec. (the original code takes 0.14 sec. on my > computer).
> For exponent=500: > time _ = expand(fastpower(x+y+z+1,500,13)) > takes only 0.12 sec. (the original code takes 13.79 sec.), means an > about 115 times faster code.
On 10 Okt., 11:32, John Cremona <john.crem...@gmail.com> wrote:
> There is a trac ticket about this, quite an old one. I don't have
> time to search for it now, but it would be worth checking out.
I do remember that there has been a thread, likely on sage-devel, and
perhaps also a ticket, but I have not been able to find it.
Since we are likely to talk about libSingular polynomials here, I
think it would be the best solution if the Singular team would
consider to add a special case for finite fields. I don't know why
they don't.
