Author: Jim McKeeth

To follow-up with my Parallel For Loops skill sprint last week (lots of good resources there), today I did a deep dive into the Parallel Programming Library (PPL) including Futures, Tasks and custom thread pools.

Here are the slides:

http://www.slideshare.net/slideshow/embed_code/44497276

And you can download my Tasks and Futures sample to see how to create, start, check and cancel both Tasks and Futures. Check out the C++ Parallel Examples to see how to use Futures and the PPL in C++.

Until the replay of my Skill Sprint is posted, you can watch this video from Allen Bauer covering the Parallel Programming Library Architecture from CodeRage 9.

Be sure to sign up for and check out the other Skill Sprints.

This is some code I wrote a long time ago as part of the TDAG mailing list. It calculates Factorials, the number of Combinations and Permutations. This is the mathematics, it calculates the number of Combinations and Permutations, it doesn’t create each different Combination and Permutation.

They take Cardinals as parameters because it doesn’t make sense to accept negative numbers. Keep in mind that factorials get big really, really quickly, so if you use too large of numbers then it will overflow even the Int64.

unit FactCombPerm;

interface

// Parameters are Cardinal because Int64 isn't Ordinal
//  Besides, Factorial(100) will overflow Int64 already.
function Factorial(const ANumber: Cardinal): Int64; overload;
function Factorial(const ANumber: Cardinal;
                   const AStop: Cardinal): Int64; overload;
function CombinationUnOpt(const ACount, AChoose: Cardinal): Int64;
function Combination(const ACount, AChoose: Cardinal): Int64;
function Permutation(const ACount, AChoose: Cardinal): Int64;

implementation

function Factorial(const ANumber: Cardinal): Int64; overload;
// n! = n * (n-1) . . . n(2)
var
  lCtr: Cardinal;
begin
  Result := 1;
  for lCtr := ANumber downto 2 do
    Result := Result * lCtr;
end;

function Factorial(const ANumber: Cardinal;
                   const AStop: Cardinal): Int64; overload;
// Factorial with a stop point (needed in the optimized Combination routine
// if no AStop is specified then is the same as Factorial
var
  lCtr: Cardinal;
begin
  Result := 1;
  if ANumber >= AStop then
    for lCtr := ANumber downto AStop do
      Result := Result * lCtr;
end;

function CombinationUnOpt(const ACount, AChoose: Cardinal): Int64;
// n!
// n_C_k = ----------
// k!(n - k)!
begin
  if AChoose < ACount then
    Result := Factorial(ACount)
      div (Factorial(AChoose) * Factorial(ACount - AChoose))
  else
    Result := 0;
end;

function Combination(const ACount, AChoose: Cardinal): Int64;
// n!
// n_C_k = ----------
// k!(n - k)!
// with optimizations even!
begin
  if AChoose < ACount then
    Result := Factorial(ACount, succ(ACount - AChoose))
      div (Factorial(AChoose))
  else
    Result := 0;
end;

function Permutation(const ACount, AChoose: Cardinal): Int64;
// n!
// n_P_k = --------
// (n - k)!
begin
  if AChoose < ACount then
    Result := Factorial(ACount)
      div Factorial(ACount - AChoose)
  else
    Result := 0;
end;

end.

My original optimization had a bug in it, but Bryan Mayland fixed it for me. This is old code, and there are probably some options to optimize it better. I’d love input, suggestions, etc.