I improved the benchmarking code by reducing the number of cube computations. Interestingly, this gives a huge improvement of guile-2.9.1 performance while improving less or even worsening performance for other scheme interpreters I've tested.
This could indicate that 1. the guile-2.9.1 optimizer is able to convert the extra code I introduced to avoid unnecessary cube computation (let:s and extra args) to something with low overhead 2. guile-2.9.1 arithmetic is a bit heavy Anyhow, now guile-1.8 went up to 7.53 s, guile-2.9.1 went down to 0.53 s while python went down to 3.60 s. Attaching version 2 of the benchmarks. (BTW, on my machine the previous version is better at provoking a segfault.)
;;;; ramanujan.scm -- Compute the N:th Ramanujan number ;;;; ;;;; Copyright (C) 2018 Mikael Djurfeldt ;;;; ;;;; This program is free software; you can redistribute it and/or modify ;;;; it under the terms of the GNU General Public License as published by ;;;; the Free Software Foundation; either version 3, or (at your option) ;;;; any later version. ;;;; ;;;; This program is distributed in the hope that it will be useful, ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;;;; GNU General Public License for more details. ;;;; ;;;; You should have received a copy of the GNU General Public License ;;;; along with this program. If not, see <http://www.gnu.org/licenses/>. ;;;; ;;; Version 2 (define (ramanujan n) "Return the N:th Ramanujan number (sum of two cubes in more than one way)" (define (ramanujan? w b0) ;; Is w a Ramanujan number? (let loop ((a 1) (a3 1) (b b0) (b3 (* b0 b0 b0)) (seen #f)) (and (<= a b) (let ((s (+ a3 b3))) (cond ((< s w) (let ((a1 (+ 1 a))) ; too small => inc a (loop a1 (* a1 a1 a1) b b3 seen))) ((> s w) (let ((b1 (- b 1))) ; too large => dec b (loop a a3 b1 (* b1 b1 b1) seen))) (else (let ((b1 (- b 1))) ; found a sum! (or seen (loop a a3 b1 (* b1 b1 b1) #t))))))))) (define (iter w b0 n) ;; w is a Ramanujan candidate ;; b0 is the first second term to try ;; n is the number of Ramanujan number still to find ;; We first increase b0 until 1 + b0^3 >= w (let ((b0 (let loop ((b b0)) (if (>= (+ 1 (* b b b)) w) b (loop (+ 1 b)))))) (cond ((zero? n) (- w 1)) ; found the last number! ((ramanujan? w b0) (iter (+ 1 w) b0 (- n 1))) (else (iter (+ 1 w) b0 n))))) ; try next candidate (iter 2 1 n))
#!/usr/bin/python3 # ramanujan.py -- Compute the N:th Ramanujan number # # Copyright (C) 2018 Mikael Djurfeldt # # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 3 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program. If not, see <http://www.gnu.org/licenses/>. # # Version 2 # return the N:th Ramanujan number (sum of two cubes in more than one way) # def ramanujan (n): w = 0 # Ramanujan number candidate b0 = 1 # first second term to try while n > 0: w += 1 # try next candidate # increase initial b0 until 1 + b0^3 >=w while 1 + b0 * b0 * b0 < w: b0 += 1 a = 1 a3 = 1 b = b0 b3 = b0 * b0 * b0 count = 0 # number of ways to write w while a <= b: s = a3 + b3 if s < w: a += 1 # if sum is too small, increase a a3 = a * a * a continue elif s == w: count += 1 # found a sum! if count > 1: n -= 1 break b -= 1 # increase b both if sum too large and to find next way to write w b3 = b * b * b return w
