On Friday 01 December 2006 05:51, Robert Bradshaw wrote: > On Nov 30, 2006, at 8:39 PM, William Stein wrote: > > On Thu, 30 Nov 2006 20:05:55 -0800, Robert Bradshaw > > > > <[EMAIL PROTECTED]> wrote: > >>> I think on a 32-bit machine it's something like 24 bytes versus 4 > >>> bytes. > >> > >> I actually implemented this as a python list, using the unsafe > >> PyList_SET_ITEM api. I could probably squeeze a bit more out of it > >> using a PyObject** directly, though I'm curious as to how much. > >> > >> I was also thinking about caching inverses in the elements (either at > >> calculation time or ring creation time (can this be done faster than > >> iterating over about half the list?)) since this is probably the most > >> expensive operation commonly done with these elements. This could > >> certainly be a saving when the element are already all in a table, > >> but I'm not sure how to (very quickly) decide to do so otherwise. > > > > Before getting into this sort of thing you should compare notes with > > Martin A. and his Givaro stuff -- doesn't it already do all this sort > > of caching!? I.e., it reduces multiplication and division to addition > > of ints, which is the same difficulty as a table lookup. > > > > William > > If I remember correctly, it stores elements as powers of a generator, > so multiplication and division boil down to addition and subtraction. > Actual subtraction and addition then have to be handled via an O(n^2) > lookup table. Caching the inverses would only be O(n) space.
No, addition is a O(n) lookup table. I've "ported" the Givaro addition to SAGE for you to have a look at it: http://sage.math.washington.edu:8101/givaro_lookup_table Martin PS: In total Givaro has O(2n) storage requirements, one "+1" table (used for addition) and one table to translate the exponents to int representation (e.g., k.gen() is identified with 2 in GF(2^e)) -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _icq: 177334829 _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
