Optimization in Typed Racket… Is this going too far?

Question

A question about typed/racket. I'm currently working my way through the Euler Project problems to better learn racket. Some of my solutions are really slow, especially when dealing with primes and factors. So for some problems, I've tried to make a typed/racket version and I find no improvement in speed, quite the opposite. (I try to minimize the impact of overhead by using really big numbers, calculations are around 10 seconds.)

I know from the Racket docs that the best optimizations happen when using Floats/Flonums. So... yeah, I've tried to make float versions of problems dealing with integers. As in this problem with a racket version using integers, and a typed/racket one artificially turning integers to floats. I have to use tricks: checking equality between two numbers actually means checking that they are "close enough", like in this function which checks if x can be divided by y :

(: divide? (-> Flonum Flonum Boolean))
(define (divide? x y)
  (let ([r (/ x y)])
    (< (- r (floor r)) 1e-6)))

It works (well... the solution is correct) and I have a 30%-40% speed improvement.

How acceptable is this? Do people actually do that in real life? If not, what is the best way to optimize typed/racket solutions when using integers? Or should typed/racket be abandoned altogether when dealing with integers and reserved for problems with float calculations?

Answer 1

In most cases the solution is to use better algorithms rather than converting to Typed Racket.

Since most problems at Project Euler concern integers, here is a few tips and tricks:

1. The division operator / needs to compute the greatest common division between the denominator and the numerator in order to cancel out common factors. This makes / a bad choice if you only want to know whether one number divides another. Use (= (remainder n m) 0) to check whether m divides n. Also: use quotient rander than / when you know the division has a zero remainder.

2. Use memoization to avoid recomputation. I.e. use a vector to store already computed results. Example: https://github.com/racket/math/blob/master/math-lib/math/private/number-theory/eulerian-number.rkt

3. First implement a naive algorithm. Then consider how to reduce the number of cases. A rule of thumb: brute force works best if you can reduce the number of cases to 1-10 million.

4. To reduce the number of cases look for parametrizations of the search space. Example: If you need to find a Pythagorean triple: loop over numbers m and n and then compute a = m^2 - n^2, b = 2mn, and, c = m^2 + n^2. This will be faster than looping over a, b, and, c skipping those triples where a^2 + b^2 = c^2 is not true.

5. Look for tips and tricks in the source of math/number-theory.

Answer 2

Not aspiring to be an real answer since I can't provide any general tips soegaard hasn't posted already, but since I recently have done "Amicable numbers Problem 21", I thought may as well leave you my solution here (Sadly not many Lisp solutions get posted on Euler...).

(define (divSum n)
  (define (aux i sum)
    (if (> (sqr i) n)
        (if (= (sqr (sub1 i)) n)  ; final check if n is a perfect square
            (- sum (sub1 i))
            sum)
        (aux (add1 i) (if (= (modulo n i) 0)
                          (+ sum i (/ n i))
                          sum))))
  (aux 2 1))


(define (amicableSum n)
  (define (aux a sum)
    (if (>= a n)
        sum
        (let ([b (divSum a)])
          (aux (add1 a)
               (if (and (> b a) (= (divSum b) a))
                   (+ sum a b)
                   sum)))))
  (aux 2 0))

> (time (amicableSum 10000))
cpu time: 47 real time: 46 gc time: 0

When dealing with divisors one can often stop at the square-root of n like here with divSum. And when you find an amicable pair you may as well add both to the sum at once, what saves you an unnecessary computation of (divSum b) in my code.