5

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 sure.

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.

Community
  • 1
  • 1
yurisich
  • 6,991
  • 7
  • 42
  • 63
  • 9
    How do you think string conversion works, exactly? (Hint: Computers do not think in base 10.) – Nemo Sep 19 '11 at 17:09
  • 3
    try running these two funcs to get more accurate (less noisy) results: `def div5(maxi): return not (maxi%5)`, `def str5(maxi): return str(maxi)[-1] == '5'` – Claudiu Sep 19 '11 at 17:11
  • 1
    @Nemo: Please make that an answer. –  Sep 19 '11 at 17:12
  • try it with just the conversion to str to see how much does that take – Facundo Casco Sep 19 '11 at 17:13
  • @delnan: That's OK, someone else can take it :-). – Nemo Sep 19 '11 at 17:19
  • @nemo: maybe you could write me a function that outputs that last 3 bits only? If they match "101", I should be good, right? The point is more along the lines of getting the last member of maxi without converting the whole thing to string. I'm looking for help. Not to make a fool of myself. – yurisich Sep 19 '11 at 17:28
  • @Droogans: I apologize if my response was overly flippant... But the last three bits being "101" does not mean the number is divisible by 5. All of the divisibility rules you know -- like "ends in 0 means divisible by 10" and "add the digits to check divisibility by 9" -- only work for base 10. So your whole approach here is flawed, I am afraid. – Nemo Sep 19 '11 at 21:40
  • @nemo: I took a class in digital fundamentals, so I understand how ASCII and unicode works. I was being overly flippant back in my response, and I apologize as well. I know the difference between 0b101 and 0xf, and how they are both divisible by 5. My problem wasn't stated very clearly, and I see know how I could do it better next time. – yurisich Sep 20 '11 at 11:55

3 Answers3

10
% 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.

Wooble
  • 87,717
  • 12
  • 108
  • 131
  • This technically answers the question, but it doesn't get to my point: Is there a way to get information about the last digit of an int without converting it into a string? I will give you the best answer award, and re-submit my question with a better title. Hope you re-submit an answer, as well. – yurisich Sep 20 '11 at 18:05
5

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.

Charles
  • 11,269
  • 13
  • 67
  • 105
rocksportrocker
  • 7,251
  • 2
  • 31
  • 48
  • Although I didn't select this to be the best answer, really it was. This is clear, without being overly verbose. – yurisich Sep 20 '11 at 21:40
0

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.