racket - Improving performance for converting numbers to lists, and base10 to base2

Question

Many Project Euler problems require manipulating integers and their digits, both in base10 and base2. While I have no problem with converting integers in lists of digits, or converting base10 into base2 (or lists of their digits), I often find that performance is poor when doing such conversions repeatedly.

Here's an example:

First, here are my typical conversions:

#lang racket
(define (10->bin num)
  (define (10->bin-help num count)
    (define sq
      (expt 2 count))
    (cond
      [(zero? count) (list num)]
      [else (cons (quotient num sq) (10->bin-help (remainder num sq) (sub1 count)))]
      )
    )
  (member 1 (10->bin-help num 19)))

(define (integer->lon int)
  (cond
    [(zero? int) empty]
    [else (append (integer->lon (quotient int 10)) (list (remainder int 10)))]
    )
  )

Next, I need a function to test whether a list of digits is a palindrome

(define (is-palindrome? lon)
  (equal? lon (reverse lon)))

Finally, I need to sum all base10 integers below some max that are palindromes in base2 and base10. Here's the accumulator-style function:

(define (sum-them max)
  (define (sum-acc count acc)
    (define base10
      (integer->lon count))
    (define base2
      (10->bin count))
    (cond
      [(= count max) acc]
      [(and
           (is-palindrome? base10)
           (is-palindrome? base2))
          (sum-acc (add1 count) (+ acc count))]
         [else (sum-acc (add1 count) acc)]))
  (sum-acc 1 0))

And the regular recursive version:

(define (sum-them* max)
  (define base10
    (integer->lon max))
  (define base2
    (10->bin max))
  (cond
    [(zero? max) 0]
    [(and
      (is-palindrome? base10)
      (is-palindrome? base2))
     (+ (sum-them* (sub1 max)) max)]
    [else (sum-them* (sub1 max))]
    )
  )

When I apply either of these two last functions to 1000000, I takes well over 10 seconds to complete. The recursive version seems a bit quicker than the accumulator version, but the difference is negligible.

Is there any way I can improve this code, or do I just have to accept that this is the style of number-crunching for which Racket isn't particularly suited?

So far, I have considered the possibility of replacing integer->lon by a similar integer->vector as I expect vector-append to be faster than append, but then I'm stuck with the need to apply reverse later on.

Answer 1

Making your existing code more efficient

Have you considered getting the list of bits using any of Racket's bitwise operations? E.g.,

(define (bits n)
  (let loop ((n n) (acc '()))
    (if (= 0 n) 
        acc
        (loop (arithmetic-shift n -1) (cons (bitwise-and n 1) acc)))))

> (map bits '(1 3 4 5 7 9 10))
'((1) (1 1) (1 0 0) (1 0 1) (1 1 1) (1 0 0 1) (1 0 1 0))

It'd be interesting to see whether that speeds anything up. I expect it would help a bit, since your 10->bin procedure currently makes a call to expt, quotient, and remainder, whereas bit shifting, depending on the representations used by the compiler, would probably be more efficient.

Your integer->lon is also using a lot more memory than it needs to, since the append is copying most of the result at each step. This is kind of interesting, because you were already using the more memory efficient approach in bin->10. Something like this is more efficient:

(define (digits n)
  (let loop ((n n) (acc '()))
    (if (zero? n)
        acc
        (loop (quotient n 10) (cons (remainder n 10) acc)))))

> (map digits '(1238 2391 3729))
'((1 2 3 8) (2 3 9 1) (3 7 2 9))

More efficient approaches

All that said, perhaps you should consider the approach that you're using. It appears that right now, you're iterating through the numbers 1…MAX, checking whether each one is a palindrome, and if it is, adding it to the sum. That means you're doing something with MAX numbers, all in all. Rather than checking for palindromic numbers, why not just generate them directly in one base and then check whether they're a palindrome in the other. I.e., instead of of checking 1…MAX, check:

• 1
• 11
• 101, and 111
• 1001, and 1111
• 10001, 10101, 11011, and 11111,
• and so on, up until the numbers are too big.

This list is all the binary palindromes, and only some of those will be decimal palindromes. If you can generate the binary palindromes using bit-twiddling techniques (so you're actually working with the integers), it's easy to write those to a string, and checking whether a string is a palindrome is probably much faster than checking whether a list is a palindrome.