On Jan 3, 2007, at 3:14 PM, William Stein wrote:
What's the status with multi-modular methods? I was thinking of
starting on this, but wasn't sure if you had done anything.
I haven't done anything beyond what's in the current release.
One thing for you to do is to fix the asymptotically fast matrix_modn
echelon algorithm. I had to disable it since it was causing core
dumps
on 64-bit linux (sage.math).
While we're on the topic of modn matrix code, I want to publicise the
existence of a certain header file, longlong.h, that is a core part
of GMP. It contains a bunch of macros for doing assembler-level word
multiplies on a variety of processors. It should be possible to write
some pyrex declarations to make these look like C functions.
For example, on a 64-bit machine like sage.math, there's a macro that
computes the product of two unsigned 64-bit integers, into a 128-bit
product, in a single machine opcode. That's four cycles, compared to
three cycles for a 32-bit multiply (but you are getting four times as
much work done). In fact the opteron can do them in 2 cycles back-to-
back on independent data, which is, needless to say, insanely fast.
There are also macros for 128-bit addition. So it's very efficient to
write a loop that computes the dot product of two vectors, and does a
modular reduction at the end. e.g. if the matrix was 16x16, you could
work with primes about 59 bits long.
The macros are portable, in the sense that longlong.h simulates it
with half-length products if the full-length is not available on that
platform. The file is also completely independent from GMP; you can
use it in non-GMP code quite easily.
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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
