new magma on sage.math
William Stein
I just installed the 64-bit MAGMA 2.13 binary on SAGE.
William
Bill Hart
out the window.
So they didn't dump their algorithm because of round off errors, or
some bug.
Bill Hart
But now they really screwed up their algorithm, because I can use MAGMA
to multiply 2400 degree polynomials considerably faster than they do it
themselves.
Anyhow, I found another trick for going to 2^(l+2) digit numbers for
the same cost (a factor of 4 times higher degree than what you'd
normally get), which is obviously what they are using.
But I know quite a few additional tricks now. So they are still
beatable, in some cases by quite a healthy margin I think.
Bill.
Bill Hart
MAGMA binary issue, which I presume William told you about? I.e. which
binary of MAGMA did you measure against?
It interests me that MAGMA appears 2 times faster for some bit lengths.
It doesn't seem possible if they are actually using GMP for the
multiplications, though I note for the range we are really interested
in, the timings are the same.
Bill.
David Harvey
On Oct 24, 2006, at 12:34 AM, Bill Hart wrote:
> Now MAGMA uses SS/FFT down to degree 16 at least, for 1000 bit.
>
> But now they really screwed up their algorithm, because I can use
> MAGMA
> to multiply 2400 degree polynomials considerably faster than they
> do it
> themselves.
!!! :-)
David
David Harvey
On Oct 24, 2006, at 7:25 AM, Bill Hart wrote:
>
> David, did your comparative GMP/Magma timings take into account this
> MAGMA binary issue, which I presume William told you about? I.e. which
> binary of MAGMA did you measure against?
I'm not sure. I think it must have been the V12, 64-bit one. I can
run them all again if you like, but it might take a day or two in
between everything else.
BTW if you are running tests on sage.math, be aware that the default
version of GMP on sage.math is not the latest, it's only something
like 4.1.3. You should link against the versions in the SAGE
distribution, or compile GMP 4.2.1 yourself. It *does* make a
difference.
> It interests me that MAGMA appears 2 times faster for some bit
> lengths.
> It doesn't seem possible if they are actually using GMP for the
> multiplications, though I note for the range we are really interested
> in, the timings are the same.
I recall that MAGMA seems to switch algorithms when at least one of
the integers goes beyond about 1700 bits. Suddenly it jumps in speed
by a factor of 2 or 4 or something. GMP has no such discontinuity.
You can see this on the graph
http://sage.math.washington.edu/home/dmharvey/magma-vs-everyone/ZZ-
mult/graph.png
i.e. the vertical line.
David
David Harvey
On Oct 24, 2006, at 12:34 AM, Bill Hart wrote:
> Now MAGMA uses SS/FFT down to degree 16 at least, for 1000 bit.
>
> But now they really screwed up their algorithm, because I can use
> MAGMA
> to multiply 2400 degree polynomials considerably faster than they
> do it
> themselves.
I think part of the problem may be that they only tune their
algorithm crossover points for a specific architecture, and hope that
these are sensible settings for other architectures too. But this is
just speculation.
David
William Stein
>
> David, did your comparative GMP/Magma timings take into account this
> MAGMA binary issue, which I presume William told you about? I.e. which
> binary of MAGMA did you measure against?
We didn't have MAGMA-2.13 back then. All we had was the MAGMA-2.12 binary,
which is 64-bit.
> It interests me that MAGMA appears 2 times faster for some bit lengths.
> It doesn't seem possible if they are actually using GMP for the
> multiplications, though I note for the range we are really interested
> in, the timings are the same.
I suspect they don't use GMP for small integers, by the way. I could
be completely wrong.
William
William Stein
Cool!
Amusingly, until MAGMA 2.12-20 (after I had pointed out the problem), if
you
did "Factorial(10^6)" in MAGMA it took massively longer than
doing "&*[1..10^6]" (!!!). The problem was that Factorial
was doing 1*2*3*4*..., whereas &* does the product in a more
intelligent way, that makes better use of multiplying large numbers.
(By the way "&*" is MAGMA's notation for what is "prod()" in Python.)
---------------------
was@sage:/usr/local/magma.old$ ./magma.exe
Magma V2.11-10 Tue Oct 24 2006 04:53:24 on sage [Seed = 242660762]
Type ? for help. Type <Ctrl>-D to quit.
> time n:=Factorial(10^6);
[Interrupt twice in half a second; exiting]
Total time: 20.429 seconds, Total memory usage: 0.76MB
was@sage:/usr/local/magma.old$
was@sage:/usr/local/magma.old$ ./magma.exe
Magma V2.11-10 Tue Oct 24 2006 04:53:52 on sage [Seed = 259503359]
Type ? for help. Type <Ctrl>-D to quit.
> time n := &*[1..10^6];
Time: 5.800
William Stein
That could be. If so, though, for various reasons I strongly suspect that
architecture would be AMD Opterons, i.e., what sage.math is.
William
Bill Hart
If not, this will probably explain the timing difference.
William Stein
> Did you compile GMP with Pieck Gaudries "patch" for AMD 64 systems?
>
> If not, this will probably explain the timing difference.
No, I didn't apply this patch yet. I'm on it.
William
William Stein
>
> Did you compile GMP with Pieck Gaudries "patch" for AMD 64 systems?
>
> If not, this will probably explain the timing difference.
The system-wide "sage" on sage.math now has the patched version of GMP.
It is also available as
www/sage/packages/standard/gmp-4.2.1.p1.spkg
and will be in the next version of SAGE.
It does seem faster on a few random tests. E.g.,
GMP-4.2.1 no patch:
sage: time n=factorial(2*10^6)
CPU times: user 4.00 s, sys: 0.31 s, total: 4.30 s
GMP-4.2.1.p1 -- patched
sage: time n=factorial(10^6*2)
CPU times: user 3.33 s, sys: 0.31 s, total: 3.65 s
64-bit MAGMA 2.13:
sage: t = magma.cputime()
sage: m = magma("Factorial(10^6*2)")
sage: magma.cputime(t)
4.8600000000000003
Probably MAGMA is using their own algorithm here...
-- William
William Stein
>
> If not, this will probably explain the timing difference.
The system-wide "sage" on sage.math now has the patched version of GMP.
It is also available as
www/sage/packages/standard/gmp-4.2.1.p1.spkg
and will be in the next version of SAGE.
It does seem faster on a few random tests. E.g.,
GMP-4.2.1 no patch:
sage: time n=factorial(2*10^6)
CPU times: user 4.00 s, sys: 0.31 s, total: 4.30 s
GMP-4.2.1.p1 -- patched
sage: time n=factorial(10^6*2)
CPU times: user 3.33 s, sys: 0.31 s, total: 3.65 s
64-bit MAGMA 2.13:
sage: t = magma.cputime()
sage: m = magma("Factorial(10^6*2)")
sage: magma.cputime(t)
4.8600000000000003
Maybe MAGMA is using their own algorithm here... but maybe not:
sage: t = magma.cputime()
sage: m = magma("&*[1..10^6*2]")
sage: magma.cputime(t)
6.1200000000000001
-- William