Optimized way for checking if the given number is a Palindrome

Question

I wrote two functions to check if a number (Integer) is a Palindrome or not.

The first function reverses the number without affecting the datatype whereas the second function converts the numbers into string, reverses the string, then converts it back into an Integer to compare the given number.

Approach #1

def is_palindrome(n):
    """
        This function checks if a number is a Palindrome
        or not.
    """
    result = 0
    temp = n
    while temp > 0:
        result *= 10
        result += temp % 10
        temp //= 10
    return result == n

Approach #2

def is_palindrome_str(n):
    """
        This function checks if a number is a Palindrome
        or not.
    """
    return int(str(n)[::-1]) == n

By comparing the execution time, I found that The first approach takes longer than the second.

I do not understand why the second approach where conversion takes place is faster than the one one which reverses the number by breaking each digit and joining them back in a temp variable.

Can they be further optimized or Is there a better way to check if a number is a Palindrome or not?

(As I'm a beginner, I do not understand how the conversion approach works behind the scenes so additional help would be really appreciated.)

Answer 1

Your first version takes longer because Python has to do more work.

When using CPython (the Python implementation you would download from python.org or would find as the python or python3 executable on your computer), your Python code is compiled into bytecode, and then the core evaluation loop executes each bytecode in turn in a big loop. That big loop is implemented in C and compiled to machine code suitable for your specific OS and CPU architecture. The built-in int and str types are also implemented entirely in C code, including what code runs when you use [...] indexing on them or use operators.

What makes one version fast and the other slow, then, is the relative speeds of the operations executed by C code vs. doing the same thing with a lot of Python code (translated into bytecode).

The dis module can show you what bytecode is produced (as human-readable representation). Here is the bytecode for your first function:

>>> import dis
>>> dis.dis(is_palindrome)
  6           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (result)

  7           4 LOAD_FAST                0 (n)
              6 STORE_FAST               2 (temp)

  8     >>    8 LOAD_FAST                2 (temp)
             10 LOAD_CONST               1 (0)
             12 COMPARE_OP               4 (>)
             14 POP_JUMP_IF_FALSE       46

  9          16 LOAD_FAST                1 (result)
             18 LOAD_CONST               2 (10)
             20 INPLACE_MULTIPLY
             22 STORE_FAST               1 (result)

 10          24 LOAD_FAST                1 (result)
             26 LOAD_FAST                2 (temp)
             28 LOAD_CONST               2 (10)
             30 BINARY_MODULO
             32 INPLACE_ADD
             34 STORE_FAST               1 (result)

 11          36 LOAD_FAST                2 (temp)
             38 LOAD_CONST               2 (10)
             40 INPLACE_FLOOR_DIVIDE
             42 STORE_FAST               2 (temp)
             44 JUMP_ABSOLUTE            8

 12     >>   46 LOAD_FAST                1 (result)
             48 LOAD_FAST                0 (n)
             50 COMPARE_OP               2 (==)
             52 RETURN_VALUE

and this is the second:

>>> dis.dis(is_palindrome_str)
  6           0 LOAD_GLOBAL              0 (int)
              2 LOAD_GLOBAL              1 (str)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 LOAD_CONST               1 (None)
             10 LOAD_CONST               1 (None)
             12 LOAD_CONST               2 (-1)
             14 BUILD_SLICE              3
             16 BINARY_SUBSCR
             18 CALL_FUNCTION            1
             20 LOAD_FAST                0 (n)
             22 COMPARE_OP               2 (==)
             24 RETURN_VALUE

You don't have to understand the effect of each bytecode in those outputs, but you can see that one listing is a lot bigger.

So int(str(number)[::-1]) does plenty of work too, but it's faster because the work is done in native code that is more efficient than a big loop that has to handle all possible bytecode operations.

For very large numbers, it could be more efficient to write a loop that exits early by working from the outside in (take the magnitude of the number from math.log10(...), pair that up with 1 and work your way towards the middle testing and returning the moment you get a False result) but I suspect that even then string conversion wins.

The only small improvement I can offer is that you don't convert back to int():

def is_palindrome_str_faster(n):
    return (v := str(n)) == v[::-1]

The above (ab)uses the Python 3 assignment expression syntax. You can also write it as:

def is_palindrome_str_faster(n):
    v = str(n)
    return v == v[::-1]

with virtually no difference in bytecode produced or performance.

Using the timeit module to compare the methods:

>>> timeit('ip(12345654321)', 'from __main__ import is_palindrome as ip')
1.8687424899544567
>>> timeit('ip(12345654321)', 'from __main__ import is_palindrome_str as ip')
0.5467583388090134
>>> timeit('ip(12345654321)', 'from __main__ import is_palindrome_str_faster as ip')
0.42572025093249977