"ocaml_beginners"::[] Performance of Big Combination

I had coded a bigSlowComb.ml using OCaml
for computation of Combination, and made
me wonder why it computes so slowly ?

Could any one help to tune its performance ?
below is the bigSlowComb.ml
--------------------------------------
(* ocamlc -o bigComb.exe nums.cma bigComb.ml *)
* Combination function of Big_int type, assumes 0 <= m <= n
* #load "nums.cma";; *)
open Big_int;;

let rec bi_comb (n: big_int) (m: big_int) =
if (eq_big_int m zero_big_int) or (eq_big_int m n)
then unit_big_int
else add_big_int ( bi_comb (pred_big_int n) m)
( bi_comb (pred_big_int n) (pred_big_int m)) ;;

let n, m = (big_int_of_string Sys.argv.(1)),
(big_int_of_string Sys.argv.(2)) in
print_newline (); print_string (string_of_big_int ( bi_comb n m));
print_newline ();;

Messages in this topic (1) Reply (via web post) | Start a new topic

.

> Could any one help to tune its performance ?

Well, there are a few problems here.

First, note that comb n m = comb n (n-m), so if m > n/2 you'll be wasting
time doing all of the work from m to (n-m). But that's not the big thing.

What's the big problem is the structure of your recursion. To compute
comb n m, you compute comb (n-1) m and comb (n-1) (m-1) and add them.
Let's look at a small example:

comb 6 3 -> comb 5 3 + comb 5 2
comb 5 3 -> comb 4 3 + comb 4 2
comb 4 3 -> comb 3 3 + comb 3 2
comb 3 3 -> 1
comb 3 2 -> comb 2 2 + comb 2 1
comb 2 2 -> 1
comb 2 1 -> comb 1 1 + comb 1 0
comb 1 1 -> 1
comb 1 0 -> 1
comb 4 2 -> comb 3 2 -> comb 3 1
comb 3 2 -> comb 2 2 + comb 2 1
comb 2 2 -> 1
comb 2 1 -> comb 1 1 + comb 1 0
comb 1 1 -> 1
comb 1 0 -> 1
comb 3 1 -> comb 2 1 -> comb 2 0
comb 2 1 -> comb 1 1 + comb 1 0
comb 1 1 -> 1
comb 1 0 -> 1
comb 2 0 -> 1
comb 5 2 -> comb 4 2 + comb 4 1
comb 4 2 -> comb 3 2 -> comb 3 1
comb 3 2 -> comb 2 2 + comb 2 1
comb 2 2 -> 1
comb 2 1 -> comb 1 1 + comb 1 0
comb 1 1 -> 1
comb 1 0 -> 1
comb 4 1 -> comb 3 1 + comb 3 0
comb 3 1 -> comb 2 1 -> comb 2 0
comb 2 1 -> comb 1 1 + comb 1 0
comb 1 1 -> 1
comb 1 0 -> 1
comb 2 0 -> 1
comb 3 0 -> 1

Notice how much extra work you're doing? Every call to comb (n-1) (m-1)
is redoing work already seen in the recursive calls to comb (n-1) m (i.e.
you double up on the comb (n-2) (m-1) bits). Now imagine how much extra
work you're doing when m and n get really big (especially since you aren't
choosing the smaller applicable m).

I forget if there's a nice iterative structure for computing combinations
(and I'm in a hurry, so I don't want to think now), but I do know that
memoization will be a big boost for you here. That's where you store
values that you've already computed (say in a hashtable or map), and when
you go to compute a value you first check if you've done it already -- if
so, just use that value you've storedi if not compute it, store it, use
it.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy.&quot;

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On 4/10/07, William D. Neumann < wneumann%40cs.unm.edu">wneumanncs.unm.edu> wrote:
&gt; I forget if there's a nice iterative structure for computing combinations
> (and I'm in a hurry, so I don't want to think now), but I do know that
>; memoization will be a big boost for you here. That's where you store
&gt; values that you've already computed (say in a hashtable or map), and when
>; you go to compute a value you first check if you've done it already -- if
> so, just use that value you've storedi if not compute it, store it, use
> it.

The normal way to compute combinations would be n! / (m! * (n-m)!).
Obviously, if the numbers are "big&quot; (for sufficiently large values of
big..), the factiorial might be a tricky one. Of course, for a huge n
but a small m, computing n! / (n-m)! only requires m multiplications
(unless I'm off by one), by simply computing a = n * (n-1) * (n-2) *
... * (n-m+1), which is then further divided by b = m! (again, for a
small m not very time consuming, relatively speaking).

http://en.wikipedia.org/wiki/Combination

Anyway, here's a bit faster computation..

open Big_int

let rec fac n =
if eq_big_int n zero_big_int then unit_big_int
else mult_big_int n (fac (pred_big_int n))

let rec part_fac n m =
if eq_big_int m unit_big_int then n
else mult_big_int n (part_fac (pred_big_int n) (pred_big_int m))

let bi_comp n m =
div_big_int (part_fac n m) (fac m)

let _ =
let n = big_int_of_string Sys.argv.(1)
and m = big_int_of_string Sys.argv.(2) in
print_string (string_of_big_int (bi_comp n m));
print_newline ()

Lars Nilsson

Messages in this topic (0) Reply (via web post) | Start a new topic

.

William D. Neumann wrote:
&gt;> Could any one help to tune its performance ?
>&gt;
>
> Well, there are a few problems here.
&gt;
> First, note that comb n m = comb n (n-m), so if m > n/2 you'll be wasting
> time doing all of the work from m to (n-m). But that's not the big thing.
&gt;
> What's the big problem is the structure of your recursion. To compute
> comb n m, you compute comb (n-1) m and comb (n-1) (m-1) and add them.
> Let's look at a small example:
>
>; comb 6 3 -> comb 5 3 + comb 5 2
> comb 5 3 -> comb 4 3 + comb 4 2
> comb 4 3 -> comb 3 3 + comb 3 2
> comb 3 3 -> 1
> comb 3 2 -> comb 2 2 + comb 2 1
> comb 2 2 -> 1
> comb 2 1 -> comb 1 1 + comb 1 0
> comb 1 1 -> 1
> comb 1 0 -> 1
>
[etc, long computation snipped ]
> Notice how much extra work you're doing? Every call to comb (n-1) (m-1)
> is redoing work already seen in the recursive calls to comb (n-1) m (i.e.
> you double up on the comb (n-2) (m-1) bits). Now imagine how much extra
> work you're doing when m and n get really big (especially since you aren't
> choosing the smaller applicable m).
>
> I forget if there's a nice iterative structure for computing combinations
> (and I'm in a hurry, so I don't want to think now),
Yes there is a nice simple iterative algorithm.

Hint: remember (comb n m) = n! / (m! (n-m)!) and determine how to
compute (comb n m) from (comb n (m-1)).

If you do that, don't forget William's optimisation : (comb n m) = (comb
n (m-n)) : for m > n/2, not only the second formula will run more
quickly, it will also avoid needlessly big intermediate results which
could overflow and spoil the computation.

For an approximate answer on really big n, m there are faster
approximate formulas.

Frédéric

Messages in this topic (0) Reply (via web post) | Start a new topic

.