|
⇤ ← Revision 1 as of 2006-08-21 17:35:07
Size: 1009
Comment: started describing timing tests
|
Size: 1132
Comment: added code attachments
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 13: | Line 13: |
| (TBA) | * attachment:poly_multiply_benchmark.sage (runs the timing tests) * attachment:make_graphs.sage (generates the pretty graphs) |
| Line 19: | Line 20: |
| 1. Generate a random pair of polynomials and import it into the system. | * Generate a random pair of polynomials and import it into the system. |
| Line 21: | Line 22: |
| 2. Try multiplying once, see how long that takes. If that took less than half a second, try multiplying twice, see how long that takes. Keep doubling the number of trials until we find some N such that N trials take at least half a second. | * Try multiplying once, see how long that takes. If that took less than half a second, try multiplying twice, see how long that takes. Keep doubling the number of trials until we find some N such that N trials take at least half a second. |
| Line 23: | Line 24: |
| 3. Time N trials. Divide the answer by N to find out how long each trial took. Do this five times. Report the average of the five samples, and also report the difference between the maximum and minimum (just to make sure we're not being led totally astray by irregularities). | * Time N trials. Divide the answer by N to find out how long each trial took. Do this five times. Report the average of the five samples, and also report the difference between the maximum and minimum (just to make sure we're not being led totally astray by irregularities). |
This page describes some timing tests I did to compare the speed of polynomial multiplication over Z for MAGMA, NTL and PARI. The timings were performed on sage.math.washington.edu.
Summary of results
(TBA)
Raw output data
(TBA)
The code
- attachment:poly_multiply_benchmark.sage (runs the timing tests)
- attachment:make_graphs.sage (generates the pretty graphs)
Methodology
For each pair of degree and coefficient size, and for each system (MAGMA, PARI, NTL), I did the following:
- Generate a random pair of polynomials and import it into the system.
- Try multiplying once, see how long that takes. If that took less than half a second, try multiplying twice, see how long that takes. Keep doubling the number of trials until we find some N such that N trials take at least half a second.
- Time N trials. Divide the answer by N to find out how long each trial took. Do this five times. Report the average of the five samples, and also report the difference between the maximum and minimum (just to make sure we're not being led totally astray by irregularities).