[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mon, Mar 31, 2008 at 12:43 PM, John Cremona [EMAIL PROTECTED]
wrote:
There was some discussion a week or so ago about a more efficient
implentation of cyclotomic polynomials, which led to trac#2654. I
have tried various alternatives of the prototype code posted there,
finding that the speed varied enormously as a result of
trivial-seeming changes.
The key operation needed is to replace f(x) by f(x^m) for various
positive integers m, where f is an integer polynomial. Doing
{{{
f = f(x**m)
}}}
was very slow, especially for large m. Faster is to apply this function:
{{{
def powsub(f,m):
assert m0
if m==1: return f
g={}
d=f.dict()
for i in d:
g[m*i]=d[i]
return f.parent()(g)
}}}
Is there a better way? And is this operation needed elsewhere, in
which case the function should be available generally?
I thought of using sparse polynomials, but the algorithm also needs
exact polynomial division whcih (as far as I can see) is not available
for sparse integer polys.
Suggestions welcome, so we can put a decent patch in for this
important function!
Hi John,
Sure a special function to compute f(x^n) quickly seems like a good idea.
By the way, I just did some cyclotomic polynomial benchmarking
in on Intel Core 2 Duo 2.6Ghz laptop. Here are the results:
n| Sage 2.11 | newcyc at #2654 | PARI | Magma
10^5 | 1.29 | 0.37 | 1.24 | 0.02
10^6 | ? | 32.89 | 123.8 | 0.20
10^7 | ? | ? | ?| 2.37
Magma crushes everything else yet again...
Relevant code:
{{{id=15|
///
}}}
{{{id=8|
def newcyc(n):
assert n0
plist = n.prime_divisors()
X = PolynomialRing(ZZ,'X').gen()
f = X-1
m = n
for p in plist:
f = f(X**p)//f(X)
m //= p
return f.subs(X**m)
///
}}}
{{{id=9|
time f= newcyc(10^5)
///
CPU time: 0.37 s, Wall time: 0.37 s
}}}
{{{id=21|
time f= newcyc(10^6)
///
CPU time: 32.89 s, Wall time: 33.06 s
}}}
{{{id=22|
time f= newcyc(10^7)
///
}}}
{{{id=24|
time f = cyclotomic_polynomial(10^5)
///
CPU time: 1.29 s, Wall time: 1.29 s
}}}
{{{id=25|
time f = cyclotomic_polynomial(10^6)
///
CPU time: 129.18 s, Wall time: 129.54 s
}}}
{{{id=26|
time f = cyclotomic_polynomial(10^7)
///
}}}
{{{id=27|
///
}}}
{{{id=12|
def h(n):
print magma.eval('time f := CyclotomicPolynomial(%s);'%n)
///
}}}
{{{id=16|
h(10^5)
///
Time: 0.020
}}}
{{{id=13|
h(10^6)
///
Time: 0.200
}}}
{{{id=17|
h(10^7)
///
Time: 2.370
}}}
{{{id=7|
def g(n):
print gp.eval('gettime; f = polcyclo(%s); gettime/1000.0'%n)
///
}}}
{{{id=11|
g(10^5)
///
1.243
}}}
{{{id=18|
g(10^6)
///
123.78700
}}}
{{{id=19|
g(10^7)
///
}}}
{{{id=20|
///
}}}
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mar 31, 2008, at 6:09 PM, William Stein wrote: Relevant code: [snip] To profile this properly, you shouldn't do it just at powers of ten, since the running time will depend heavily on the factorisation pattern of n. I guess you should do some examples with lots of small prime factors, examples with high prime powers, examples with just a prime, etc. david --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mar 31, 2008, at 3:43 PM, John Cremona wrote:
There was some discussion a week or so ago about a more efficient
implentation of cyclotomic polynomials, which led to trac#2654. I
have tried various alternatives of the prototype code posted there,
finding that the speed varied enormously as a result of
trivial-seeming changes.
The key operation needed is to replace f(x) by f(x^m) for various
positive integers m, where f is an integer polynomial. Doing
{{{
f = f(x**m)
}}}
was very slow, especially for large m. Faster is to apply this
function:
{{{
def powsub(f,m):
assert m0
if m==1: return f
g={}
d=f.dict()
for i in d:
g[m*i]=d[i]
return f.parent()(g)
}}}
Is there a better way? And is this operation needed elsewhere, in
which case the function should be available generally?
I thought of using sparse polynomials, but the algorithm also needs
exact polynomial division whcih (as far as I can see) is not available
for sparse integer polys.
Suggestions welcome, so we can put a decent patch in for this
important function!
Perhaps if you have a bound for the size of the coefficients you
could do a modular approach. Work mod N where the coefficients are
guaranteed to be at most N. Usually I guess N will fit into a single
word, so the polynomial arithmetic will be much faster than working
over ZZ.
david
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mon, Mar 31, 2008 at 3:24 PM, David Harvey [EMAIL PROTECTED] wrote: On Mar 31, 2008, at 6:09 PM, William Stein wrote: Relevant code: [snip] To profile this properly, you shouldn't do it just at powers of ten, since the running time will depend heavily on the factorisation pattern of n. I guess you should do some examples with lots of small prime factors, examples with high prime powers, examples with just a prime, etc. I know. I just had about 10 minutes to spend on this, and thought people might be interested in a data point. It might even inspire somebody (you!) to do something better :-). Perhaps if you have a bound for the size of the coefficients you could do a modular approach. Work mod N where the coefficients are guaranteed to be at most N Would your new mod N poly arithmetic code be useful for this? -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mon, 31 Mar 2008, William Stein wrote:
Hi John,
Sure a special function to compute f(x^n) quickly seems like a good idea.
By the way, I just did some cyclotomic polynomial benchmarking
in on Intel Core 2 Duo 2.6Ghz laptop. Here are the results:
Relevant code:
{{{id=15|
///
}}}
{{{id=8|
def newcyc(n):
assert n0
plist = n.prime_divisors()
X = PolynomialRing(ZZ,'X').gen()
f = X-1
m = n
for p in plist:
f = f(X**p)//f(X)
You're evaluating f twice as often as you need to!
m //= p
return f.subs(X**m)
///
}}}
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mon, 31 Mar 2008, John Cremona wrote:
There was some discussion a week or so ago about a more efficient
implentation of cyclotomic polynomials, which led to trac#2654. I
have tried various alternatives of the prototype code posted there,
finding that the speed varied enormously as a result of
trivial-seeming changes.
The key operation needed is to replace f(x) by f(x^m) for various
positive integers m, where f is an integer polynomial. Doing
{{{
f = f(x**m)
}}}
was very slow, especially for large m. Faster is to apply this function:
{{{
def powsub(f,m):
assert m0
if m==1: return f
g={}
d=f.dict()
for i in d:
g[m*i]=d[i]
return f.parent()(g)
}}}
Is there a better way? And is this operation needed elsewhere, in
which case the function should be available generally?
The operation f(x^k)/f(x) can be implemented in a rather pretty way. I don't
know if this would be useful elsewhere -- I'll try and hack this up tonight.
I thought of using sparse polynomials, but the algorithm also needs
exact polynomial division whcih (as far as I can see) is not available
for sparse integer polys.
Suggestions welcome, so we can put a decent patch in for this
important function!
John
--
John Cremona
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mar 31, 2008, at 3:09 PM, William Stein wrote:
On Mon, Mar 31, 2008 at 12:43 PM, John Cremona
[EMAIL PROTECTED] wrote:
There was some discussion a week or so ago about a more efficient
implentation of cyclotomic polynomials, which led to trac#2654. I
have tried various alternatives of the prototype code posted there,
finding that the speed varied enormously as a result of
trivial-seeming changes.
The key operation needed is to replace f(x) by f(x^m) for various
positive integers m, where f is an integer polynomial. Doing
{{{
f = f(x**m)
}}}
was very slow, especially for large m. Faster is to apply this
function:
{{{
def powsub(f,m):
assert m0
if m==1: return f
g={}
d=f.dict()
for i in d:
g[m*i]=d[i]
return f.parent()(g)
}}}
Is there a better way? And is this operation needed elsewhere, in
which case the function should be available generally?
I thought of using sparse polynomials, but the algorithm also needs
exact polynomial division whcih (as far as I can see) is not
available
for sparse integer polys.
Suggestions welcome, so we can put a decent patch in for this
important function!
Hi John,
Sure a special function to compute f(x^n) quickly seems like a good
idea.
I will second this.
By the way, I just did some cyclotomic polynomial benchmarking
in on Intel Core 2 Duo 2.6Ghz laptop. Here are the results:
n| Sage 2.11 | newcyc at #2654 | PARI | Magma
10^5 | 1.29 | 0.37 | 1.24 | 0.02
10^6 | ? | 32.89 | 123.8 | 0.20
10^7 | ? | ? | ?| 2.37
It's not computing the coefficients that's expensive, it's creating
the polynomial.
sage: import sage.rings.polynomial.cyclotomic as c
sage: time L = c.cyclotomic_coeffs(10^5)
CPU time: 0.00 s, Wall time: 0.00 s
sage: time L = c.cyclotomic_coeffs(10^6)
CPU time: 0.03 s, Wall time: 0.03 s
sage: time L = c.cyclotomic_coeffs(10^7)
CPU time: 0.25 s, Wall time: 0.25 s
This is better than Magma. This is still clearly a bug, an I am
writing a patch to address this.
- Robert
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mar 31, 2008, at 3:09 PM, William Stein wrote: On Mon, Mar 31, 2008 at 12:43 PM, John Cremona [EMAIL PROTECTED] wrote: ... By the way, I just did some cyclotomic polynomial benchmarking in on Intel Core 2 Duo 2.6Ghz laptop. Here are the results: n| Sage 2.11 | newcyc at #2654 | PARI | Magma 10^5 | 1.29 | 0.37 | 1.24 | 0.02 10^6 | ? | 32.89 | 123.8 | 0.20 10^7 | ? | ? | ?| 2.37 Magma crushes everything else yet again... Fixed up the ZZ[x] constructor, now we crush Magma (I don't feel bad taking credit 'cause I wrote the original cyclotomic coefficient code). sage: time f = cyclotomic_polynomial(10^5) CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 sage: time f = cyclotomic_polynomial(10^6) CPU times: user 0.01 s, sys: 0.01 s, total: 0.02 s Wall time: 0.02 sage: time f = cyclotomic_polynomial(10^7) CPU times: user 0.15 s, sys: 0.08 s, total: 0.22 s Wall time: 0.24 sage: time f = cyclotomic_polynomial(next_prime(10^5)) CPU times: user 0.05 s, sys: 0.01 s, total: 0.05 s Wall time: 0.06 sage: time f = cyclotomic_polynomial(ZZ.random_element(10^5, 10^6)) CPU times: user 0.02 s, sys: 0.00 s, total: 0.03 s Wall time: 0.06 http://trac.sagemath.org/sage_trac/ticket/2654 - Robert --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: polynomials: cyclotomic, sparse etc
On Mar 31, 2008, at 8:18 PM, Robert Bradshaw wrote: By the way, I just did some cyclotomic polynomial benchmarking in on Intel Core 2 Duo 2.6Ghz laptop. Here are the results: n| Sage 2.11 | newcyc at #2654 | PARI | Magma 10^5 | 1.29 | 0.37 | 1.24 | 0.02 10^6 | ? | 32.89 | 123.8 | 0.20 10^7 | ? | ? | ?| 2.37 Magma crushes everything else yet again... Fixed up the ZZ[x] constructor, now we crush Magma (I don't feel bad taking credit 'cause I wrote the original cyclotomic coefficient code). sage: time f = cyclotomic_polynomial(10^5) CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 sage: time f = cyclotomic_polynomial(10^6) CPU times: user 0.01 s, sys: 0.01 s, total: 0.02 s Wall time: 0.02 sage: time f = cyclotomic_polynomial(10^7) CPU times: user 0.15 s, sys: 0.08 s, total: 0.22 s Wall time: 0.24 sage: time f = cyclotomic_polynomial(next_prime(10^5)) CPU times: user 0.05 s, sys: 0.01 s, total: 0.05 s Wall time: 0.06 sage: time f = cyclotomic_polynomial(ZZ.random_element(10^5, 10^6)) CPU times: user 0.02 s, sys: 0.00 s, total: 0.03 s Wall time: 0.06 http://trac.sagemath.org/sage_trac/ticket/2654 mate that's awesome. david --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
