(*  BFD.nb *)
(*  *)
(*  Example: *)
(*  *)
(*    BFD[ { 6, 9, 20 } ] = 43 *)
(*  *)
(*  Modified: *)
(*  *)
(*    28 November 2007 *)
(*  *)
(*  Author: *)
(*  *)
(*    Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis, Stan Wagon *>
(*  *)
(*  Reference: *)
(*  *)
(*    Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis, Stan Wagon *>
(*    Faster Algorithms for Frobenius Numbers, *)
(*    The Electronic Journal of Combinatorics, *)
(*    Volume 12, 2005, #R27. *)
(*  *)
(*  Parameters: *)
(*  *)
(*    Input, A, a list of "denominations". *)
(*  *)
(*    Output, the Frobenius number of A. *)
(*  *)

BFD[A_] := ( 
     Clear [ S, P ];
     h = t = a = First [ A ];
     b = Rest [ A ];
   
    Q = Array [ 0 & , a];
   S[_] = a * A[[-1]];
   S[a] = 0;
   P[a] = Length[b];
   
     While [ h != 0,
        { v, Q[[h]], h } = { h, 0, If [ h == t, 0, Q[[h]] ] };
        Do [
           e = Mod[ b[[j]] + v, a ];
           w = b[[j]] + S[v];
           If [ w < S[e], 
              S[e] = w;
              P[e] = j;
              If [ Q[[e]] == 0,
                 If [ h == 0,
                    t = Q[[e]] = h = e,
                    t = Q[[e]] = Q[[t]] = e
                  ]
               ]
            ],
           { j, P[v] }
         ]
      ];
     Max [ S /@ Range [ a - 1 ] ] - a );