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. I suspect that this technique has higher benefit for finite fields of higher algebraic order, and also that the overhead of using Givaro rather than c ints for Z/pZ would overwhelm any advantage (but would be happy to be proven wrong). Robert --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
