Surely it would be worth testing self.gcd(m)==m early on in the exact_log function, i.e. that m divides self? I may be naive but I would implement this by testing m|a, if so dividing a by m, and continuing. The current method describes itself as "extremely stupid code" but it still trying to be clever!.
John 2009/4/8 Bill Hart <goodwillh...@googlemail.com>: > > Here's some timings for exact_log: > > In Sage: > > def random(n): > a = ZZ.random_element(n) > return a > > def z_exact_log_test(m, n, k): > for i in range(0, m) : > a = random(n) + 2 > b = random(k) > c = a^b > d = c.exact_log(a) > if b != d: > print "Error", b, "!=", d > > time z_exact_log_test(100000, 64, 1000) > > 4.72s > > In Magma: > > t:=Cputime(); > for i := 0 to 100000 do > a := Random(64) + 2; > b := Random(1000); > c := a^b; > d := Ilog(a,c); > if d ne b then > print "Error"; > end if; > end for; > Cputime(t); > > 0.72s > > Bill. > > > On 8 Apr, 07:17, Bill Hart <goodwillh...@googlemail.com> wrote: >> I've been looking through the methods for ZZ with a view to doing a >> Magma/Sage comparison for marketing purposes. I've been noticing a few >> issues as I go. There's going to be lots of these, so I think I should >> give my list in small blocks. I can file trac tickets for them once >> someone verifies that these are really not just me not knowing enough >> python, or whatever. >> >> ZZ >> ==== >> >> Speed Issues: >> >> * n.bits takes much longer than n.binary(), but the latter needs to >> compute the former first!!! >> * n.coprime_integers uses a hopelessly slow algorithm (we should at >> least use a sieve) >> * n.factor is bizarrely slow for small integers (e.g. n < 1,000,000) >> by a HUGE factor >> * 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) >> >> Missing doc strings: >> >> * n.base_extend >> * n.additive_order >> * n.category >> * n.db (doesn't give an example) >> * n.degree >> >> Missing methods: >> >> * n.euler_phi >> * n.random (random integer less than n - I will believe you if you >> tell me this is not the python way) >> >> Weird names: >> >> * n.divide_knowing_divisible_by (perhaps div_exact, exact_quotient, >> divide_exact would be better) >> >> Documentation issues: >> >> * n.dump says "Same as self.save(filename, compress)", but compress is >> not discussed in save docstring >> >> Bill. > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
