An example of fast numerical computation using Haskell

So here is the code: http://lpaste.net/96397

Here are my measurements:

    time ./original 1000000
    (329, 837799)

    real   0m0.183s
    user   0m0.180s
    sys    0m0.001s

    time ./new 1000000
    (329, 837799)
    
    real   0m0.017s
    user   0m0.015s
    sys    0m0.001s

There's a little work on that in Lispland as well. Some discussion, a prototype, and a link to the older SERIES package: http://pvk.ca/Blog/Lisp/Pipes/

    :tmp $ time ./collatz.native 1000000
    start: 837799 length 329

    real	0m0.782s
    user	0m0.776s
    sys	0m0.004s

    exception Error of string

    let (@@) f x  = f x
    let error fmt = Printf.kprintf (fun msg -> raise (Error msg)) fmt

    let max (a, x) (b, y) = if x > y then (a, x) else (b, y)

    let length start =
        let rec loop len a = 
            let next = if a mod 2 = 0 then a/2 else (3*a+1)/2 in 
            if a != 1 then
                loop (len+1) next
            else
                len
        in
            loop 0 start
                
    let collatz limit =
        let rec loop start longest =
            if start >= limit 
            then longest 
            else loop (start+1) (max longest (start, length start)) 
        in
            loop 1 (1,0)

    let report (start, len) = Printf.printf "start: %d length %d\n" start len

    let main () =
        let argv        = List.tl @@ Array.to_list Sys.argv in
        match argv with
        | []    -> report @@ collatz 10000
        | [n]   -> report @@ collatz @@ int_of_string n
        | _     -> error "usage: collatz [n]"

    let () = main ()

    Cython	0.47s	less

Here is the code, perhaps someone else would know how to optimize it.

CODE:

    function main(max_a0)
       longest = max_len = len = a = 0
       for a0 in 1:max_a0
          a = a0      
          len = 0
          while a != 1
             len += 1
             a = ((a%2==0) ? a : 3*a+1)/2
          end
          if len > max_len
             max_len = len
             longest = a0
          end
       end
       println("($max_len, $longest)")
    end

    @time main(1000000)

    $ julia collatz.jl 
    (329, 837799)
    elapsed time: 16.436623922 seconds (4206873264 bytes allocated)

    $ julia --version
    julia version 0.3.0-prerelease+143

     proc main(max_a0: int): int =
       var a, longest, len, max_len : int
     
       for a0 in countup(1, max_a0):
         a = a0
         len = 0
     
         while a != 1:
           len += 1
           if (a mod 2 != 0): a = (3*a + 1)
           a = a div 2
     
         if len > max_len:
           max_len = len
           longest = a0
     
       return longest
     
     # Main program starts here
     echo(main(1000000))

  next a = Just . join (,) $ (if even a then a else 3*a+1) `div` 2

  len = (+1) . V.length . V.takeWhile (/=1) . V.unfoldr next

  result = V.maximum . V.map (\x -> (len x, x)) . V.enumFromTo 1

  main = do [a0] <- getArgs
            let max_a0 = read a0 :: Word32
            print . result $ max_a0

PS: and this is how you do a proper benchmarking:

  import Criterion.Main
  main = defaultMain [
          bench "data.vector/1M" $ whnf result 10000000
         ]

Then, I implemented it in Lua and JS and compared their performance to C and Haskell. It's not meant to be a (good) benchmark. Here you go: https://gist.github.com/killercup/7718804

tl;dr

    Implementation | Time 
    -------------- | -----
    clang 3.3      | 0.40s
    luajit 2.0.2   | 0.86s
    GHC 7.6.3      | 0.49s
    Node 0.10.22   | 2.43s

  real	0m21.891s

  real	0m0.570s

Interesting that the Python Version takes so much longer.

  import sys

  check=int(sys.argv[1])
  lnum=1
  lcount=1

  for x in range(1,check):
    len=1
    a=x
    while (a>1):
      len+=1
      if a%2==0:
        a=a/2
      else:
        a=(a*3+1)/2
    if len > lcount:
      lcount=len
      lnum=x

  print lcount,lnum

[1]: http://pastebin.com/PH6DYbmr

    $time ./c_compiled_with_O2 1000000
    real	0m0.362s
    user	0m0.360s

    $time ./c_compiled_with_O3 1000000
    real	0m0.189s
    user	0m0.184s

  package main

  import (
    "log"
  )

  func main() {
    max := 1000000

    var maxa int
    var maxlength int
    for a0 := 0; a0 < max; a0++ {

      var length int
      a := a0

      for a > 1 {
        if a%2 == 0 {
          a = a/2
        } else {
          a = (3 * a + 1) / 2
        }
        length++
      }

      if length > maxlength {
        maxa = a0
        maxlength = length
      }
    }
    log.Println(maxlength, maxa)

  }

  > go version
  go version go1.1.2 linux/amd64

  > time ./collatz
  2013/12/01 13:51:31 329 837799
  ./collatz  0,34s user 0,00s system 99% cpu 0,344 total

Without start-up overhead. C versions via FFI.

https://gist.github.com/llelf/7721211 (quick'n'shitty, sorry)