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

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

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

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

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

Here a few more timings.

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:

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:

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.

#include

int main()

{

int num=12345,l=0,val=0;

for(;num;val=val*10+(num%10),num/=10);

printf(“number = %d\n”,val);

}