Reversing Digits

September 4, 2015

The answers are different in Scheme and Python, which surprised me. First the Scheme version, which uses digits and undigits from the Standard Prelude:

(define (timing rev)
  (time
    (let ((count 0))
      (do ((n 1 (+ n 1)))
          ((< 2000000 n) count)
        (when (= n (rev n))
          (set! count (+ count 1)))))))

(define (rev1 n) ; iterative
  (let loop ((n n) (z 0))
    (if (zero? n) z
      (loop (quotient n 10)
            (+ (* z 10) (modulo n 10))))))

(define (rev2 n) ; recursive
  (define (rev n r)
    (if (zero? n) r
      (rev (quotient n 10)
           (+ (* r 10) (modulo n 10)))))
  (rev n 0))

(define (rev3 n) ; numeric split
  (undigits (reverse (digits n))))

(define (rev4 n) ; string split
  (string->number
    (list->string
      (reverse
        (string->list
          (number->string n))))))

> (timing rev1)
(time (let ((...)) ...))
    22 collections
    1731 ms elapsed cpu time, including 0 ms collecting
    1729 ms elapsed real time, including 1 ms collecting
    192005856 bytes allocated, including 185119744 bytes reclaimed
2998
> (timing rev2)
(time (let ((...)) ...))
    27 collections
    1747 ms elapsed cpu time, including 0 ms collecting
    1751 ms elapsed real time, including 0 ms collecting
    224007136 bytes allocated, including 227317600 bytes reclaimed
2998
> (timing rev3)
(time (let ((...)) ...))
    132 collections
    2918 ms elapsed cpu time, including 0 ms collecting
    2911 ms elapsed real time, including 1 ms collecting
    1116478688 bytes allocated, including 1112394288 bytes reclaimed
2998
> (timing rev4)
(time (let ((...)) ...))
    317 collections
    2527 ms elapsed cpu time, including 47 ms collecting
    2560 ms elapsed real time, including 18 ms collecting
    2668524480 bytes allocated, including 2669892448 bytes reclaimed
2998

The iterative and recursive versions are about the same, the version that uses the convenience functions from the Standard Prelude is the worst, and the version that converts back and forth to a string is in the middle. Which is what I expected.

Now the Python version:

from time import clock

def rev(n): # iterative
	r = 0
	while n > 0:
		r = r * 10 + n % 10
		n = n // 10
	return r

print "iterative:"
start = clock()
count = 0
for n in xrange(100000):
    if n == rev(n):
        count += 1
print count
print (clock() - start) * 1000

def rev(n, r=0): # recursive
    if n == 0: return r
    return rev(n // 10, r*10 + n%10)

print ""
print "recursive:"
start = clock()
count = 0
for n in xrange(100000):
    if n == rev(n):
        count += 1
print count
print (clock() - start) * 1000

def rev(n): # convert to string
	return int("".join(reversed(str(n))))

print ""
print "convert to string:"
start = clock()
count = 0
for n in xrange(100000):
    if n == rev(n):
        count += 1
print count
print (clock() - start) * 1000

Running that script produces this output at ideone:

iterative:
1099
184.628

recursive:
1099
265.007

convert to string:
1099
354.793

That surprised me. The recursive version is substantially slower than the iterative version. Apparently Python has slow function-calling performance.

You can run the program at http://ideone.com/vzwkwD. You will see there that the version the converts to a string is very fast, which surprises me. Obviously the underlying cost models of Chicken Scheme, which is used by ideone, and Chez Scheme, which I run at home, are very different.

Advertisements

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);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: