digits,exact_log,ndigits speed overhaul

[sagetrac-jbmohler]

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.

Component: basic arithmetic

Author: Joel Mohler

Reviewer: Bill Hart

Merged: 4.0.1.rc0

Issue created by migration from https://trac.sagemath.org/ticket/5732

[sagetrac-jbmohler]

comment:1

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.

[sagetrac-mabshoff]

comment:3

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

[sagetrac-jbmohler]

Attachment: digits_exact_log_comprehensive.patch.gz

rebased against 4.0

[wbhart]

comment:4

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

[mwhansen]

comment:5

Merged in 4.0.1.rc0.

[mwhansen]

Reviewer: Bill Hart

[mwhansen]

Author: Joel Mohler

[mwhansen]

Merged: 4.0.1.rc0