While trying to solve problem 31 (very fast multiplication) in ocaml I've found myself trying various methods. The only algorithm I know well is the regular arithmetic one that takes O(n^2). I know this won't be fast enough, but I learned some interesting things anyhow. The num library's multiply is pretty fast but it takes more than twice the amount of time than is required by problem 31.

I have tested 3 primary methods:

a) using the built-in Num library (which the server admin kindly added to the compiling command)
b) using the built-in array type and module
c) using the Bigarray module

I tested each with some very large numbers and got some timing results. My conclusion was to not ask the admin to also add bigarray.cmxa. First I'll post the data and then the source code. The input file contained 4 input pairs totaling 18,451 bytes. This was run on a sempron 2400.

I won't post the comparison here, but I noticed that the -unsafe flag did speed up the Array implementation, whereas it did not speed up the Bigarray implementation.

num implementation:

real    0m0.437s
user    0m0.138s
sys     0m0.015s
real    0m0.500s
user    0m0.107s
sys     0m0.015s
real    0m0.453s
user    0m0.139s
sys     0m0.015s

array implementation:

real    0m3.700s
user    0m3.357s
sys     0m0.015s
real    0m3.702s
user    0m3.311s
sys     0m0.015s
real    0m3.695s
user    0m3.342s
sys     0m0.000s

bigarray implementation:

real    0m4.744s
user    0m4.467s
sys     0m0.000s
real    0m4.773s
user    0m4.466s
sys     0m0.015s
real    0m4.758s
user    0m4.482s
sys     0m0.030s

It seems that caml has trouble doing lots of manipulations on either kind of array. Bigarrays are quite a bit slower than regular arrays however. Is the performance problem limited to writes or reads, or does it affect both?

For the heck of it I timed the following for comparison:

a) max_int+1 writes to an int array
b) max_int+1 writes to an int ref
c) max_int+1 reads from the array

writing to the array:

real    0m2.094s
user    0m1.983s
sys     0m0.015s
real    0m2.063s
user    0m2.077s
sys     0m0.000s
real    0m2.062s
user    0m1.999s
sys     0m0.000s

writing to the ref:

real    0m2.099s
user    0m1.999s
sys     0m0.000s
real    0m2.085s
user    0m2.109s
sys     0m0.000s
real    0m2.075s
user    0m1.999s
sys     0m0.015s

reading from an array

real    0m2.137s
user    0m1.968s
sys     0m0.015s
real    0m2.078s
user    0m1.983s
sys     0m0.015s
real    0m2.076s
user    0m2.077s
sys     0m0.015s

reading from a reference

real    0m2.097s
user    0m2.093s
sys     0m0.015s
real    0m2.080s
user    0m1.983s
sys     0m0.015s
real    0m2.082s
user    0m2.077s
sys     0m0.015s

(note that 2 seconds is about how long it takes a loop to count from 0 to max_int, so that the reading/writing basically took no resources)

It seems that, as long as you compile with -unsafe, arrays are just as fast as references. This makes sense because references are essentially one element arrays. But the drawback is that any programming in ocaml that requires very fast manipulation of referenced values or arrays is going to be slow. Because of the discussion in the following link, I think this is because of ocaml's garbage collector. Not that it's a bad garbage collector! It's just not suited for tasks like problem 31. Fast Multiplication.

http://groups.google.com/group/comp.lang.functional/browse_thread/thread/d71644093332cf87/313e6ab8393a64f52

multiplication code
num implementation

open Num
let multiply n =
  for i=1 to n do
    Scanf.scanf
      "\n%s %s"
      (fun num1 num2 ->
	let num1 = num_of_string num1 in
	let num2 = num_of_string num2 in
	print_endline
	  (string_of_num
	     (mult_num num1 num2))   
      )
  done;;
Scanf.scanf "%i" (multiply);
exit 0;

array implementation

let a = Array.create 10000 0;;
let b = Array.create 10000 0;;
let res = Array.create 20000 0;;
let decompstr array str strlen len =
  match array with
    'a' ->
      if strlen<len then
	for i=strlen to len do a.(i) <- 0 done;
      for i=0 to strlen-1 do
	a.(i) <- (int_of_char str.[strlen-i-1]) - 48
      done;
  | 'b' ->
      if strlen<len then
	for i=strlen to len do b.(i) <- 0 done;
      for i=0 to strlen-1 do
	b.(i) <- (int_of_char str.[strlen-i-1]) - 48
      done;;
let mularray len =
  for i=0 to 2*len-1 do res.(i) <- 0 done;
  let remainder = ref 0 in
  for i=0 to len - 1 do
    for j=0 to len - 1 do
      let result = a.(i) * b.(j) + !remainder + res.(i+j) in
      remainder := result/10;
      res.(i+j) <- result - !remainder*10;
    done;
    res.(i+len) <- !remainder;
    remainder := 0;
  done;;
let recompstr len =
  let beg = ref (-1) in
  let pos = ref (len-1) in
  while(!beg<0) do
    if !pos <= 0 then
      (
       beg := 0;
      )
    else
      if res.(!pos) <> 0 then
	beg := !pos
      else
	decr pos;
  done;
  for i = 0 to !pos do
    print_char (char_of_int (res.(!pos-i)+48))
  done;;
let multiply n =
  for i=1 to n do
    Scanf.scanf
      "\n%s %s"
      (fun num1 num2 ->
	let len1 = String.length num1 in
	let len2 = String.length num2 in
	let max =
	  if len1>len2 then len1 else len2 in
	decompstr 'a' num1 len1 max;
	decompstr 'b' num2 len2 max;
	mularray max;
	recompstr (2*max);
	print_endline "";
	flush stdout;
      )
  done;;
Scanf.scanf "%i" (multiply);
exit 0;

bigarray implementation

open Bigarray;;
open Bigarray.Array1;;
let a = create int c_layout 10000;;
let b = create int c_layout 10000;;
let res = create int c_layout 20000;;
let decompstr array str strlen len =
  match array with
    'a' ->
      if strlen<len then
	for i=strlen to len do a.{i} <- 0 done;
      for i=0 to strlen-1 do
	a.{i} <- (int_of_char str.[strlen-i-1]) - 48
      done;
  | 'b' ->
      if strlen<len then
	for i=strlen to len do b.{i} <- 0 done;
      for i=0 to strlen-1 do
	b.{i} <- (int_of_char str.[strlen-i-1]) - 48
      done;;
let mularray len =
  for i=0 to 2*len-1 do res.{i} <- 0 done;
  let remainder = ref 0 in
  for i=0 to len - 1 do
    for j=0 to len - 1 do
      let result = a.{i} * b.{j} + !remainder + res.{i+j} in
      remainder := result/10;
      res.{i+j} <- result - !remainder*10;
    done;
    res.{i+len} <- !remainder;
    remainder := 0;
  done;;
let recompstr len =
  let beg = ref (-1) in
  let pos = ref (len-1) in
  while(!beg<0) do
    if !pos <= 0 then
      (
       beg := 0;
      )
    else
      if res.{ !pos } <> 0 then
	beg := !pos
      else
	decr pos;
  done;
  for i = 0 to !pos do
    print_char (char_of_int (res.{ !pos-i } + 48) )
  done;;
let multiply n =
  for i=1 to n do
    Scanf.scanf
      "\n%s %s"
      (fun num1 num2 ->
	let len1 = String.length num1 in
	let len2 = String.length num2 in
	let max =
	  if len1>len2 then len1 else len2 in
	decompstr 'a' num1 len1 max;
	decompstr 'b' num2 len2 max;
	mularray max;
	recompstr (2*max);
	print_endline "";
	flush stdout;
      )
  done;;
Scanf.scanf "%i" (multiply);
exit 0;

testing array write speed

let a = [|0|]
for i=0 to max_int do
  a.(0) <- 3;
done

testing ref write speed

let temp = ref 0;;
for i=0 to max_int do
  temp := 3
done

reading from the array

let a = [|0|];;
for i=0 to max_int do
  ignore (a.(0))
done

reading from the reference

let a := 0;;
for i=0 to max_int do
  ignore (!a)
done