Golomb sequence

self-describing-sequence.dylan

module: self-describing-sequence

define constant <integer-vector> = limited(<simple-vector>, of: <integer>);

define function golomb
    (golomb-sequence :: <integer-vector>, n :: <integer>)
 => (fn :: <integer>)
  without-bounds-checks
    when(golomb-sequence[n - 1] = 0)
      golomb-sequence[n - 1] := %golomb(golomb-sequence, n);
    end when;
    golomb-sequence[n - 1];
  end without-bounds-checks;
end function golomb;

define function %golomb
    (golomb-sequence :: <integer-vector>, n :: <integer>)
 => (fn :: <integer>)
  without-bounds-checks
    1 + golomb(golomb-sequence,
               n - golomb(golomb-sequence,
                          golomb(golomb-sequence, n - 1)));
  end without-bounds-checks;
end function %golomb;

define function main (name :: <string>, arguments :: <vector>)
  let i = string-to-integer(arguments[0]);
  let golomb-sequence = make(<integer-vector>, size: i, fill: 0);
  golomb-sequence[0] := 1;
  for (j from 1 to i)
    golomb(golomb-sequence, j);
  end for;
  format-out("f(%d) = %d\n", i, golomb(golomb-sequence, i));
  exit-application(0);
end function main;

main(application-name(), application-arguments());

Second version is optimized and runs in same time as C++ version.

First version:

$ time self-describing-sequence 20000000
f(20000000) = 39099
24.564 secs

Second version:

$ time self-describing-sequence 20000000
f(20000000) = 39099
0.668 secs

C++ versions (with & w/o compiler optimizations):

$ c++ -O0 -o self-describing-sequence-cc  self-describing-sequence.cc 
time ./self-describing-sequence-cc 20000000
f(20000000) = 39099
3.611 secs
$ c++ -O3 -o self-describing-sequence-cc  self-describing-sequence.cc 
$ time ./self-describing-sequence-cc 20000000
f(20000000) = 39099
0.513 secs