On Tue, Jul 27, 2010 at 1:58 PM, Luis Finotti <luis.fino...@gmail.com> wrote: > Hi, > > I have an algorithm that has pieces that perform computations on Z/ > p^i*Z for different values of i. I can count the operations for each > piece, but to have an overall complexity, I need to know how the > difference pieces compare. > > So, can anyone tell me how many bit operations are performed, in Sage, > in a product of two elements of Z/n*Z (in terms of n and size of the > input)? (I am particularly interested in cases where n=p^i for > various i's, but it would be nice to know in general for future > reference.) What about in Z? (A general reference would be fine too, > of course.)
For anything that doesn't fit inside a single word, Sage uses the mpz functions in MPIR to do arithmetic. There are a variety of algorithms used--from the classical O(n^2) to various Karatsuba/Toom-Cook ones to Schönhage–Strassen for large values. The latter, if you're interested in asymtotics, is O(n log n log log n). IIRC, The reduction (division) has similar asymptotics. - Robert -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
