next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
TestIdeals :: fastExponentiation

fastExponentiation -- computes powers of elements in rings of positive characteristic quickly

Synopsis

Description

In prime characteristic p > 0, raising a sum a+b to the p-th power is more quickly done by simply computing ap and bp and adding them. The basic strategy is to break up the exponent into its base p expansion, and then use the exponent rules. For example, (x+y)3p2+5p+2 = ((x+y)3)p2((x+y)5)p(x+y)2.

i1 : R = ZZ/5[x];
i2 : f = sum( 10, i -> x^i );
i3 : time f^321;
     -- used 0.754096 seconds
i4 : time fastExponentiation(321,f);
     -- used 0.00260967 seconds

If an element in a ring of characteristic 0 is passed, fastExponentiation(n,f) simply computes fn in the usual way.

Ways to use fastExponentiation :