On Tue, Sep 1, 2009 at 9:23 AM, Rolandb <[email protected]> wrote:
>
>
>
> On 1 sep, 11:08, Robert Bradshaw <[email protected]> wrote:
> > On Aug 29, 2009, at 11:05 PM, Rolandb wrote:
> >
> > > Hi,
> >
> > > Using math.log has a disadvantage; it is less accurate.
> >
> > > sage: print n(math.log(2),100)
> > > sage: print n(log(2),100)
> > > 0.69314718055994528622676398300
> > > 0.69314718055994530941723212146
> >
> > Yes, it is. Accuracy vs. speed is a common tradeoff one needs to make.
> >
> > If you're going for a numerical answer, log(2).n(1000) will give you
> > 1000 bits of precision. Adjust as you see fit for your application.
> >
> > - Robert
>
> Hi Robert,
>
> I tested several solutions and I found that there is a much better
> approach.
>
> def expon1(mx,g): return int(ln(mx)/ln(g))+1
> def expon2(mx,g): return floor(log(mx)/log(g))+1
> def expon3(mx,g): return floor(ln(mx)/ln(g))+1
> def expon4(mx,g): return floor(math.log(mx)/math.log(g))+1
> def expon5(mx,g): return floor(n(log(mx),100)/n(log(g),100))+1
>
> def expon6(mx,g):
> if g>mx: return 1
> k=0
> m=g
> while m*g<=mx:
> m=m*g
> k+=1
> return k+2
>
> 1. 625 loops, best of 3: 1.15 ms per loop
> 2. 625 loops, best of 3: 998 µs per loop
> 3. 625 loops, best of 3: 993 µs per loop
> 4. 625 loops, best of 3: 6.77 µs per loop
> 5. 625 loops, best of 3: 696 µs per loop
> 6. 625 loops, best of 3: 7.71 µs per loop
>
> Roland
>
> The last method is best, although I didn't expected it to be.
>
If you are really computing floor(log(a,b)) with a,b integers, you should
use the exact_log function. It will blow away anything you are doing
above, e.g.,:
sage: timeit('expon6(256,2)')
625 loops, best of 3: 7.03 µs per loop
sage: timeit('256.exact_log(2)')
625 loops, best of 3: 616 ns per loop
Note that exact_log is a method on Sage integers, so you have to do
a.exact_log(b). Make sure to read a=5; a.exact_log? to make sure it does
what you want. You can also do a.exact_log?? to appreciate the nontrivial
code David Harvey wrote to make exact_log very fast and correct.
--
William
--~--~---------~--~----~------------~-------~--~----~
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-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
