Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#5732 closed enhancement (fixed)

[with patch, positive review] digits,exact_log,ndigits speed overhaul

Reported by: jbmohler Owned by: somebody
Priority: major Milestone: sage-4.0.1
Component: basic arithmetic Keywords:
Cc: Merged in: 4.0.1.rc0
Authors: Joel Mohler Reviewers: Bill Hart
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The Integer.exact_log method is very slow for small input simply because it has never been optimized for this usage. The attached patch provides a specialized case for small input to exact log. It also adds a super-fast path for cases when the exact_log can conveniently be computed by log 2 estimation.

Attachments (1)

digits_exact_log_comprehensive.patch (26.2 KB) - added by jbmohler 12 years ago.
rebased against 4.0

Download all attachments as: .zip

Change History (7)

comment:1 Changed 12 years ago by jbmohler

Some timings:

new patch
sage: n=5^1000
sage: m=2975982357823879528793587928793592
sage: timeit("n.exact_log(m)")
625 loops, best of 3: 714 ns per loop
sage: n=5^50
sage: m=33
sage: timeit("n.exact_log(m)")
625 loops, best of 3: 2.49 µs per loop
Vanilla sage 3.4
sage: n=5^1000
sage: m=2975982357823879528793587928793592
sage: timeit("n.exact_log(m)")
625 loops, best of 3: 620 µs per loop
sage: n=5^50
sage: m=33
sage: timeit("n.exact_log(m)")
625 loops, best of 3: 92.2 µs per loop

I really like the first example :), but it's a bit of a pathology. There's a relatively narrow band of cases where the log base 2 estimate is quickly provable and exactly correct.

comment:2 Changed 12 years ago by jbmohler

  • Summary changed from digits,exact_log,ndigits speed overhaul to [with patch, needs review] digits,exact_log,ndigits speed overhaul

comment:3 Changed 12 years ago by mabshoff

  • Milestone changed from sage-3.4.1 to sage-3.4.2

This is quote a nice speedup, but unless it gets reviewed soon it will not be in 3.4.1. Since I do not consider this a blocker I am reassigning this to 3.4.2 until it gets a review.

Cheers,

Michael

Changed 12 years ago by jbmohler

rebased against 4.0

comment:4 Changed 12 years ago by wbhart

  • Summary changed from [with patch, needs review] digits,exact_log,ndigits speed overhaul to [with patch, positive review] digits,exact_log,ndigits speed overhaul

I've tested the code using:

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

for all sorts of values m, n, k, small large, etc. Everything passes.

The documentation is sufficient, the code reads well and appears correct. There are doctests.

It is also fast as advertised:

def zlog(m, n, k):
    for i in range(0, m/1000):
        a = ZZ.random_element(n)+2
        b = ZZ.random_element(k)
        c = a^b
        for i in range (0, 1000):
            c.exact_log(a)

Old sage 4.0:

sage: time zlog(100000, 2^100, 100)
CPU times: user 23.19 s, sys: 0.19 s, total: 23.38 s
Wall time: 23.40 s

sage: time zlog(100000, 100, 100)
CPU times: user 3.46 s, sys: 0.02 s, total: 3.48 s
Wall time: 3.48 s

new times with patch:

sage: time zlog(100000, 2^100, 100)
CPU times: user 1.90 s, sys: 0.03 s, total: 1.93 s
Wall time: 1.93 s

sage: time zlog(1000000, 100, 100)
CPU times: user 0.49 s, sys: 0.06 s, total: 0.55 s
Wall time: 0.55 s

comment:5 Changed 12 years ago by mhansen

  • Resolution set to fixed
  • Status changed from new to closed

Merged in 4.0.1.rc0.

comment:6 Changed 12 years ago by mhansen

  • Authors set to Joel Mohler
  • Merged in set to 4.0.1.rc0
  • Reviewers set to Bill Hart
Note: See TracTickets for help on using tickets.