Why is large integer division faster than slicing (numeric) strings, for accessing individual digits?

I am doing a (typical) assignment of finding primes. I thought I'd be clever and, for large numbers, skip the division process with this trick:

def div5(candidate):
    return str(candidate)[-1] == "5"

Adding 5 to itself a few thousand times seems like a waste (I only need the last member), but I wanted to be su开发者_如何学运维re.

credit to unutbu on Measure time elapsed in Python?

%>python -mtimeit -s"import intDiv" "intDiv.div5(2147483645)"
1000000 loops, best of 3: 0.272 usec per loop

%>python -mtimeit -s"import strDiv" "strDiv.str5(2147483645)"
1000000 loops, best of 3: 0.582 usec per loop

For clarification, here are the two methods I defined.

def div5(maxi): return not (maxi%5)

def str5(maxi): return str(maxi)[-1] == '5'

This is too slow. How can I analyze the last member of str(maxi), without converting the whole number (needlessly)?

Thanks to @Claudiu for help with cleaning up the eyesores.

% python -mtimeit "str(2147483645)"
1000000 loops, best of 3: 0.321 usec per loop

% python -mtimeit "2147483645 % 5"
10000000 loops, best of 3: 0.0351 usec per loop

% python -mtimeit "'2147483645'[-1]"
10000000 loops, best of 3: 0.0349 usec per loop

I'd say the bottleneck is converting to a string.

One problem is the conversion of an integer to a string. This is much more work than doing integer division. I am not sure how Python does it, but most algorithms work like

def tostring(value):
    result = ""
    while True:
        digit = value % 10
        value = value / 10
        result = chr(digit + ord('0')) + result
        if value == 0: break

    return result

That is you have more than one modulo operation per value.

Converting the number to a string will look something like this:

digits = []
while x:
    digits.append(x % 10)
    x //= 10

You can see this is going to do lots of % operations (aside from the construction of the list of digits or string).

Apart from this optimisation problem, your function isn't correct. For example, 10 doesn't end with 5, yet is divisible by 5.