Re: 3n+1 problem

Raffael Cavallaro wrote:

On Apr 17, 1:51 pm, namekuseijin <namekusei...@xxxxxxxxx> wrote:
Cross escreveu:

I apologise for the confusion. My solution was not the ace
solution. My solution  is at 0.067 seconds.

The input set is from 1 to 100000.

In Scheme:

;http://icpcres.ecs.baylor.edu/onlinejudge/external/1/100.pdf

(define (cycle-length n)
   (do ((i n (if (odd? i) (+ 1 (* 3 i)) (/ i 2)))
        (length 1 (+ 1 length)))
     ((= i 1) length)))

(define (max-cycle-length from to)
   (do ((n from (+ 1 n))
        (r 1 (max r (cycle-length n))))
     ((> n to) r)))

Timings in one native-compiled implementation and one jit-compiled:

Larceny v0.97b1 (beta test) (Aug 25 2008 10:57:44,
precise:Win32:unified) larceny.heap, built on Mon 08/25/2008

 > (load "uva-3n_plus_1-max-cycle-length.scm")

 > (time (max-cycle-length 1 100000))
Words allocated: 0
Words reclaimed: 0
Elapsed time...: 468 ms (User: 468 ms; System: 0 ms)
Elapsed GC time: 0 ms (CPU: 0 in 0 collections.)
351

Welcome to MzScheme v4.0.2 [3m], Copyright (c) 2004-2008 PLT Scheme
Inc.  > (load "uva-3n_plus_1-max-cycle-length.scm")
 > (time (max-cycle-length 1 100000))
cpu time: 1014 real time: 1014 gc time: 0
351
 > (time (max-cycle-length 1 100000))
cpu time: 983 real time: 982 gc time: 0
351

I don't have Gambit, Bigloo or Stalin available right now, so
getting down to C++ speed is difficult.  I'm curious about your C++
implementation though...

--
a game sig:http://tinyurl.com/d3rxz9

using your version (suitably translated to common lisp as necessary)
and the same inputs (1 100000) I get these timings for various scheme
and lisp implementations:

CCL: 0.334 seconds
LispWorks: 0.59 seconds
sbcl: 0.363 seconds
gambit: 2.626 seconds
mzscheme (jit): 1.9 seconds
larceny: 0.513

OCaml: 0.161 seconds (on 2GHz laptop)


let cycle_length n =
let rec loop n length =
if n > 1 then
loop ( if n land 1 > 0 then 3*n + 1 else n / 2 ) (succ length)
else length
in loop n 1 ;;

let max_cycle_length low high =
let m = ref 0 in
for n = low to high do
m := max !m (cycle_length n)
done ;
!m ;;
.