For those who have been showing an interest in FLINT I thought I would post some new timings.
These times are for polynomial division in Z[x]. As usual we expected Magma to be the implementation to beat, however the Magma div function is actually very, very slow in Z[x] except for the tiniest divisions. So what I have done is some comparisons with Magma in Q[x] but where the polynomials just happen to have integer coefficients. There are two cases where this returns the same result as it does in Z[x]: 1) exact division; and 2) division by a monic polynomial In case 1 I multiply two polynomials of length n with the given number of bits per coefficient (positive uniformly distributed random numbers), then time how long it takes to divide the product by one of the two original polynomials. In case 2, I take a random length 2n-1 polynomial and divide by a random monic length n polynomial. Here are the timings for case 1: Bits, length, iterations : FLINT Magma 10, 10, 100000 : 0.580s 1.270s 100, 10, 100000 : 0.842s 3.970s 1000, 10, 100000 : 5.624s 14.30s 10000, 10, 10000 : 19.12s 37.26s 100000, 10, 100 : 6.735s 12.63s 10, 100, 100000 : 18.92s 22.90s 100, 100, 10000 : 3.366s 11.30s 1000, 100, 10000 : 23.58s 52.25s 10000, 100, 1000 : 77.23s 134.1s 100000, 100, 100 : 183.5s 382.7s 10, 1000, 10000 : 31.69 35.61s 100, 1000, 1000 : 8.892s 21.55s 1000, 1000, 100 : 7.203s 9.670s 10000, 1000, 100 : 155.6s 220.8s 10, 10000, 1000 : 63.25s 142.2s 100, 10000, 100 : 20.11s 72.3s 1000, 10000, 100 : 164.8s : 656.0s 10, 100000, 100 : 100.5s 315.9s Here are the timings for case 2: Bits, length, iterations : FLINT Magma 10, 10, 100000 : 0.732s 1.970s 10, 100, 10000 : 7.301s 33.07s 10, 1000, 100 : 17.31s 25.160s 10, 10000, 1 : 42.34s : 97.25s 100, 10, 100000 : 1.628s 3.590s 100, 100, 1000 : 5.779s 15.13s 100, 1000, 10 : 29.73s 48.64s 1000, 10, 10000 : 1.212s 2.940s 1000, 100, 100 : 23.13s 33.47s 1000, 1000, 1 : 47.53s 117.9s 10000, 10, 10000 : 77.08s 134.17s 10000, 100, 10 : 47.80s 98.23s 100000, 10, 100 : 14.59s 44.02s 100000, 100, 1 : 76.20s 198.4s In some ways the comparison is unfair to Magma, since the Magma code must coerce the integer polynomials to the rationals, which takes time. Also, Magma cannot know that the division is exact in advance, and it probably doesn't know that the rational coefficients it sees are actually integers. But it is not my problem that integer division itself is very slow in Magma, and I have tried to amortise the cost of generating random numbers and doing coercions to Q[x] as much as possible. Then again, division of polynomials in Z[x] is not a terribly important problem, so you can certainly understand the Magma group concentrating on more important things. Probably NTL will beat both FLINT and Magma for very large divisions, especially if the output coefficients happen to be small. So that will probably be our next target. Bill. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
