On Wednesday 08 April 2009 02:17:48 am Bill Hart wrote:
> * n.bits takes much longer than n.binary(), but the latter needs to
> compute the former first!!!
This is sage types and lack of C-level optimization killing your performance.
The binary method does it's work using gmp (mpir, I guess now). I think it
could be fixed with-out a lot of fuss.
> * n.exact_log can be done faster for small bases by making careful use
> of the identity log_m(n) = log_2(n)/log_2(m) (I wrote a crappy broken
> python implementation and timed this - I don't know how to write it
> properly as I don't know enough about Sage yet)
I have a patch that's taken a long time for me to be happy with (but I think I
just about am now), which overhauls exact_log. It results in 50x speedups
for small input and selected large input.
For example:
----------------------------------------------------------------------
| Sage Version 3.4, Release Date: 2009-03-11 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: digits
sage: n=3^1000
sage: m=5^34
sage: timeit("n.exact_log(m)")
625 loops, best of 3: 997 ns per loop
sage: m=5
sage: timeit("n.exact_log(m)")
625 loops, best of 3: 4.47 µs per loop
The conversion to RIF field and computation of the log hideously dominates for
small input. In this case, "small" means something like 3000 bits, which
seems to me this is the vast majority of the likely input for this function.
My patch degrades gracefully to RIF computations with a fixed cutoff.
I will submit it later today to trac.
--
Joel
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
