## Reversing Digits

### September 4, 2015

After Tuesday’s exercise on Lychrel numbers, I answered a question about Lychrel numbers over at Stack Overflow, using a recursive function to extract and reverse the digits one-by-one. I was challenged by a reader who claimed “using `int("".join(reversed(str(n))))` has got to be far more efficient than using your recursive function. Your function is clever, but clever isn’t always best.” He was wrong, of course: arithmetic on numbers is better than converting a number to a string, creating a generator to reverse the individual characters of the string, appending them one-by-one to a new string, and converting the new string back to a number, which I demonstrated to him in a timing experiment.

Your task is to find the best way to reverse the digits of a positive integer, in the language of your choice. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 8 Responses to “Reversing Digits”

1. Paul said

In Python. On my machine, the clear winner is “reverse”. The “arithmetic” version is the slowest.

```def reverse(n): return int(str(n)[::-1])
def reverse2(n): return int("".join(reversed(str(n))))
def reverse3(n, r=0):
if n == 0: return r
return reverse3(n // 10, r * 10 + n % 10)

from util.timers3 import Timer
from time import clock

def bm(method, N, n):
t0 = clock()
for _ in range(N):
x = method(n)
print(method.__name__, clock() - t0)

n = 123451234512345
print("number:", n)
for m in (reverse, reverse2, reverse3):
bm(m, 10000000, 12345)

"""
number: 12345
reverse 10.065856912671778
reverse2 17.162799552531382
reverse3 29.920382914088076

number: 123451234512345
reverse 10.152792060510894
reverse2 17.137077804119585
reverse3 29.87959194145961
"""
```
2. Paul said

Oeps. In my last post the number was hardcoded. Anyway, thease timings are OK:
number: 12345123451234512345123451234512345
reverse 0.17244116711310897
reverse2 0.32812997116085263
reverse3 2.555884828145366

3. Paul said

The function below is some 7% faster with repeated use than “reverse”.

```rs = slice(None, None, -1)
def reverse0(n): return int(str(n)[rs])
```
4. Rutger said

Reader is right for large numbers.

E.g. n = 2 ** 2048 is a number with 616 digits. Using Paul’s reverse algorithms, we see that the mathematical version is ~40 times slower than the string reverse int cast version.

On the other hand, for example for n = 32 the math version is ~2 times faster.

The answer to this question is therefor:

if n < threshold:
return reverse3(n)
else:
return reverse0(n)

with an environment dependent threshold value (threshold = 1000 here).

5. Paul said

Here a few more timings.

```rs = slice(None, None, -1)
def reverse0(n): return int(str(n)[rs])
def reverse1(n): return int(str(n)[::-1])
def reverse2(n): return int("".join(reversed(str(n))))

def reverse4(n): # iterative math version
r = 0
while n:
r = r * 10 + n % 10
n //= 10
return r

def reverse(n): # iterative math combined with reverse0
if n > 1000:
return int(str(n)[rs])
r = 0
while n:
r = r * 10 + n % 10
n //= 10
return r

import timeit
N = 1000000
def bm(m, n, N):
name = m.__name__
stmt = "{name}({n})".format(**locals())
setup = "from __main__ import {name}; n = {n}".format(**locals())
print ("{:12.2f}".format(
min(timeit.repeat(stmt, setup, number=N, repeat=5))),
end="")

print("\nN={}".format(N))
nums = (2, 23, 123, 1234, 12345, 123456789)
methods = (reverse0, reverse1, reverse2, reverse4, reverse)
print("         n    ", end="")
for m in methods: print("{:>12s}".format(m.__name__), end = "")
print()
for n in nums:
print("{:10d}".format(n), end="")
for m in methods:
bm(m, n, N)
print()
"""
n        reverse0    reverse1    reverse2    reverse4     reverse
2        0.87        0.92        1.55        0.52        0.61
23        0.87        0.93        1.50        0.89        0.97
123        0.89        0.94        1.54        1.32        1.41
1234        0.90        0.95        1.59        1.73        0.98
12345        0.91        0.96        1.63        2.13        1.00
123456789        0.96        1.01        1.80        4.05        1.05
"""
```
6. matthew said

Presumably the string reverse function in Python mainly involves a couple of calls to no doubt highly optimized library functions for reading and writing bignums, rather than rattling around the byte code interpreter loop a bazillion times for the arithmetic solution. In a properly compiled language like Haskell though, the string solution will still win out, but only for much larger inputs, we need 1000 digits or so before rev2 beats rev1:

```rev1 :: Integer -> Integer
rev1 = aux 0 where
aux a 0 = a
aux a n = aux (10*a + d) n' where (n',d) = quotRem n 10

rev2 :: Integer -> Integer
rev2 = read . reverse . show
```

On the other hand, the string implementation only wins because the library has better algorithms for radix conversion, various divide and conquer strategies are possible, for example, but we can do the same thing arithmetically.

Here, we determine how many digits are needed with integer log 10, split the number in half, recurse and then rejoin the reversed halves. For the base case we just use the iterative solution, taking care to produce a reverse of the right width (and we can do this with efficient fixed width Ints rather than variable width Integers). With a nice integer log implementation by Remco Niemeijer taken from an earlier Programming Praxis problem, it takes about 3 seconds to reverse a million digit number, versus a minute for the string solution:

```-- Remco Niemeijer's integer log code from Programming Praxis, 2010
ilog10 :: Integer -> Int
ilog10 n = f (div ubound 2) ubound where
ubound = until (\e -> 10 ^ e > n) (* 2) 1
f lo hi | mid == lo   = if 10 ^ hi == n then hi else lo
| 10 ^ mid < n = f mid hi
| 10 ^ mid > n = f lo mid
| otherwise   = mid
where mid = div (lo + hi) 2

rev3 :: Integer -> Integer
rev3 n = aux n (1+ilog10 n) where
aux :: Integer -> Int -> Integer
aux n k
-- Base case, use the linear algorithm
| k <= 6 = toInteger (aux2 0 (fromInteger n) k)
| otherwise = let
k1 = k `div` 2
k2 = k - k1
-- Split in to roughly equal halves
(n2,n1) = quotRem n (10^k1)
-- Recurse
n1' = aux n1 k1
n2' = aux n2 k2
-- And rejoin
in n1'*(10^k2)+n2'
-- aux2 is like rev1 above, but always runs k times.
aux2 :: Int -> Int -> Int -> Int
aux2 a n 0 = a
aux2 a n k = aux2 (10*a + d) n' (k-1) where (n',d) = quotRem n 10
```
7. sealfin said

Reblogged this on A Modern Prometheus and commented:
The following is the METAL BASIC 1.0ß source code output by a pre-compiler I wrote as a potential A level Computing project.

```cls

k_LIMIT = 100000

print "Method #1:"
t = timer
number_reversed = 0
for i = 1 to k_LIMIT
if i mod 10 <> 0 then
number_reversed = number_reversed + 1
multiplier = 1
l_MULTIPLIER_LOOP:
multiplier = multiplier * 10
if int( i / multiplier ) <> 0 then goto l_MULTIPLIER_LOOP
multiplier = multiplier / 10

i_copy = i
result = 0
l_LOOP:
digit = i_copy mod 10
i_copy = int( i_copy / 10 )
result = result + digit * multiplier
multiplier = multiplier / 10
if i_copy <> 0 then goto l_LOOP
end if
next i
print number_reversed; " integers were reversed in "; timer - t; " seconds."

print

print "Method #2:"
t = timer
number_reversed = 0
for i = 1 to k_LIMIT
if i mod 10 <> 0 then
number_reversed = number_reversed + 1
s\$ = str\$( i )
s_reversed\$ = ""
for k = len( s\$ ) to 0 step -1
s_reversed\$ = s_reversed\$ + mid\$( s\$, k, 1 )
next k
result = val( s_reversed\$ )
end if
next i
print number_reversed; " integers were reversed in "; timer - t; " seconds."```
8. Mayur Lokare said

#include
int main()
{
int num=12345,l=0,val=0;
for(;num;val=val*10+(num%10),num/=10);
printf(“number = %d\n”,val);
}