OK I committed the FLINT code to the repository. If you aren't using an Opteron you need to remove the -march and -mtune parts from the makefile or replace them with ones suitable for your system.
Also you need to put in the directories where GMP can be found. You'll want GMP with Pierrick Gaudry's AMD64 patches if you are using AMD 64 and Jason Martin's patches if you are using Intel (Core Duo). FLINT doesn't have fast computation of binomial coefficients at this moment, so we don't beat Magma for powering of length 2 polynomials and possibly other very short lengths. It amazes me that they went to the trouble.... especially considering how other more obvious things have been overlooked. Bill. On 28 Aug, 01:49, Bill Hart <[EMAIL PROTECTED]> wrote: > Yeah, Magma and singular probably just do it using binomial > coefficients. > > >time f:=(1+2*x+x^2)^(2^12); > > Time: 2.040 > > This is equivalent to (1+x)^(2^13) but as you see, the time is much > greater in Magma for the former. > > Still: > > > time f:=(x+x^2)^(2^13-1); > > Time: 0.450 > > which means Magma will do the evaluation using binomial coefficients > in a fairly flexible way. > > Bill. > > On 28 Aug, 01:33, Bill Hart <[EMAIL PROTECTED]> wrote: > > > You can get access to the development version of FLINT at its svn > > repository: > > >https://flint.svn.sourceforge.net/svnroot/flint/trunk > > > But to be honest, I had to hack FLINT a little due to some bugs this > > question exposed. I hadn't yet implemented aliasing in all the FLINT > > multiplication functions so I substituted a suboptimal multiplication > > function for an optimal one. > > > FLINT is also not ready for prime time. It may not even compile on > > your machine! But in case it does, make fmpz_poly-test. The final test > > it does is of the polynomial powering function. The test code itself > > is at the bottom of the file fmpz_poly-test.c. > > > I'll commit the new code and test code within the next half hour or > > so. > > > I'll fix the aliasing problems soonish, but that is going to take > > longer to fix, maybe a couple of days. The time difference is not > > noticeable though. > > > Bill. > > > On 28 Aug, 01:13, [EMAIL PROTECTED] wrote: > > > > Wow, that's fast! Where can I download this? > > > > On Mon, 27 Aug 2007, Bill Hart wrote: > > > > > I wrote up a ridiculously naive polynomial powering function in FLINT. > > > > Here is a basic FLINT program for computing the above powers: > > > > > fmpz_poly_t poly, power; > > > > fmpz_poly_init(power); > > > > fmpz_poly_init(poly); > > > > fmpz_poly_set_coeff_ui(poly, 0, 1); > > > > fmpz_poly_set_coeff_ui(poly, 1, 1); > > > > fmpz_poly_power(power, poly, (1UL<<13)); > > > > > Here are the times: > > > > > real 0m1.190s > > > > user 0m0.960s > > > > sys 0m0.232s > > > > > If I replace 2^13 with 2^13-1 I get: > > > > > real 0m0.758s > > > > user 0m0.628s > > > > sys 0m0.128s > > > > > I'm sure there's plenty we can do to speed that up. For a start the > > > > system time could trivially be all but wiped out by allocating all the > > > > required memory up front. There's probably also some FFT caching I > > > > could do but haven't. > > > > > Polynomial evaluation should probably be used beyond some point, but > > > > we haven't implemented that yet. > > > > > Bill. > > > > > On 27 Aug, 18:32, [EMAIL PROTECTED] wrote: > > > >> I was recently contacted by Niell Clift, who is arguably the foremost > > > >> expert on addition chains. Though he's most concerned with computing > > > >> minimal addition chains, which aren't always optimal and can take a > > > >> ridiculous amount of time to compute, I believe that some of the work > > > >> that he's done can be used to construct a rather generic addition > > > >> chain package. I don't expect to beat numeric exponentiation, but > > > >> polynomial exponentiation seems oddly slow. > > > > >> Already, there seems to be a cutoff point where my work on addition > > > >> chains can be used to improve the speed of exponentiation. > > > > >> (x^n)(x+1) constructs the polynomial x^n and evaluates it (this uses > > > >> my polynomial evaluation code) > > > > >> The for loop performs binary exponentiation (I pick 2^13 and 2^13-1 to > > > >> make this easy). This puzzles me -- binary exponentiation in python > > > >> currently beats the pants off of whatever is getting used for the > > > >> polynomials. What gives? > > > > >> sage: x = polygen(ZZ) > > > >> sage: n = 2^13 > > > > >> sage: time a = (x+1)^n > > > >> CPU time: 16.82 s, Wall time: 16.82 s > > > > >> sage: time a = (x^n)(x+1) > > > >> CPU time: 2.47 s, Wall time: 2.47 s > > > > >> sage: %time > > > >> sage: z = x+1 > > > >> sage: for i in range(13): > > > >> ... z = z*z > > > >> CPU time: 2.46 s, Wall time: 2.46 s > > > > >> sage: n = 2^13-1 > > > > >> sage: time a = (x+1)^n > > > >> CPU time: 3.66 s, Wall time: 3.66 s > > > > >> sage: time a = (x^n)(x+1) > > > >> CPU time: 0.91 s, Wall time: 0.91 s > > > > >> sage: %time > > > >> sage: z = x+1 > > > >> sage: y = z > > > >> sage: for i in range(12): > > > >> ... z = z*z > > > >> ... y*= z > > > >> CPU time: 1.61 s, Wall time: 1.61 s --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
