2009/12/18 Robert Bradshaw <rober...@math.washington.edu>: > On Dec 18, 2009, at 2:20 PM, John Cremona wrote: > >> That looks brilliant. I think it would be fine to have the faster >> version in unreadable mpfr provided that the "real" formula was >> included as comments. >> >> Robert, can you post some version of what you have so far so I can see >> how you have made it faster? > > Essentially, I used double complex values--the code otherwise looks > pretty much the same. I'll be putting it up on trac shortly.
Hmmm -- it's not so great to have the speedup if it's not multi-precision. The AGM algorithm is doubly exponential (i.e. the number of correct digits doubles with each iteration) so in single/double precision you hardly even need to have a loop. Obviously that's still useful, as long as we have a multi version as well. John > >> About principal vs. optimal. Neither are standard terms, I invented >> them yesterday. Don't be tricked into thinking that the "principal" >> value is in any way canonical. Only the "optimal" version has that >> claim. > > Sure. > >> >> John >> >> 2009/12/18 Robert Bradshaw <rober...@math.washington.edu>: >>> >>> On Dec 17, 2009, at 9:58 PM, William Stein wrote: >>> >>>> On Thu, Dec 17, 2009 at 9:35 PM, David Roe <r...@math.harvard.edu> >>>> wrote: >>>>> Hey John, >>>>> I worked on it tonight, and I'm not sure how much you want to >>>>> optimize it. >>>>> Is a factor of 2 or 3 speedup worth making the code much less >>>>> readable (I'd >>>>> include comments, but...)? I could also probably improve a few >>>>> things and >>>>> get maybe 10% and leave it mostly as is. >>>>> David >>>> >>>> I posted some remarks on the ticket. My initial benchmarks suggest >>>> that John's implementation of AGM may be about 10 times slower than >>>> PARI's, and that Magma's (which is only in the real case) may be 10 >>>> times faster than PARI... making John's 100 times slower than Pari? >>>> Hopefully I'm wrong, but that's what I get. So I hope there is a >>>> way >>>> to speed it up by more than a factor of 2 or 3. >>> >>> I implemented the optimal and principle options for CDF, which are >>> very fast (15x pari): >>> >>> sage: a = CDF(-0.95,-0.65) >>> sage: b = CDF(0.683,0.747) >>> sage: a.agm(b) >>> 0.338175462986 - 0.0135326969565*I >>> sage: a.agm(b, algorithm='optimal') >>> -0.371591652352 + 0.319894660207*I >>> sage: a.agm(b, algorithm='pari') >>> 0.080689185076 + 0.239036532686*I >>> sage: %timeit a.agm(b) >>> 100000 loops, best of 3: 2.24 µs per loop >>> sage: %timeit a.agm(b, algorithm='optimal') >>> 100000 loops, best of 3: 2.42 µs per loop >>> sage: %timeit a.agm(b, algorithm='pari') >>> 10000 loops, best of 3: 32.2 µs per loop >>> sage: %timeit a.real() # nearly trivial call for >>> comparison >>> 1000000 loops, best of 3: 575 ns per loop >>> >>> I was also able to shave off about 30 (out of 180) microseconds for >>> your agm via a more efficient versions of >>> >>> one = self.parent().one_element() >>> two = one+one >>> half = one/two >>> eps = two**(2-self.prec()) >>> >>> One could write the algorithm directly against mpfr (I'm guessing for >>> much more than a 2-3x speedup), but that would make for really hard >>> to >>> read code. Another option might be to use the CDF for <=53-bit (it >>> only performs basic arithmatic, so IEEE standards should be just as >>> good as mpfr), and the more generic code for larger precisions >>> (where, >>> at the limit, the overhead won't matter at all). Wouldn't help much >>> for intermediate precisions though. >>> >>> Another note on the code--inplace operations aren't actually inplace >>> (due to immutability of real numbers). >>> >>> - Robert >>> >>> -- >>> To post to this group, send an email to sage-devel@googlegroups.com >>> To unsubscribe from this group, send an email to >>> sage-devel+unsubscr...@googlegroups.com >>> For more options, visit this group at >>> http://groups.google.com/group/sage-devel >>> URL: http://www.sagemath.org >>> >> >> -- >> To post to this group, send an email to sage-devel@googlegroups.com >> To unsubscribe from this group, send an email to >> sage-devel+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/sage-devel >> URL: http://www.sagemath.org > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-devel > URL: http://www.sagemath.org > -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
