On Dec 1, 2006, at 1:48 AM, Martin Albrecht wrote:
> > 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)) Ah, that makes sense. Why didn't I think of that :-) --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
