Delphi factorial operations precision

Question

SITUATION

I need to make a program for my maths course about Combinations and Permutations. If you want to calculate them you have to deal with factorials and I have written this typical recursive function:

//TCombinazioni is a class that I have created to solve Combinations
function TCombinazioni.fattoriale(const x: integer): Int64;
begin

 Result:= 1;
 if x > 0 then
  begin
   Result:= fattoriale(x-1)*x;
  end;

end;

PROBLEM

I have written this code in my class TCombinazioni:

function TCombinazioni.getSoluzioni: Int64;
begin
  //C(n,k) = (n+k-1)! / (k! * (n-1)!)
  Result := fattoriale(n+k-1) div (fattoriale(k) * fattoriale(n-1));    
end;

The code itself is correct and if n and k (both integers) are small the function returns the desired number. The problem comes out when you input big numbers because the factorial grows up very quickly. Here you see an example.

On the left you can see that the output 11440 is correct but on the right it is not correct. I know that this kind of computation is "dangerous" because I am dealing with big integers, even if they are declared as Int64.

The type Int64 is the biggest type of integer as far as I know, but is there any other possibility if I am trying to make calculations with big integers?

Possible soluton(s)

Very easy, I could set that n and k cannot be greater than 10 for example (but I prefer not doing so)
Using floating point arithmetic. I was thinking that I could use the getSoluzioni function with an Extended return value (instead of Int64). Since the result of these operations must be an integer, I could check if the double has a decimal part equal to zero. If not, I'll not accept the result.

I was considering point number 2 because Extended has a wider range of values than Int64. Is the Extended division in Delphi more precise than Int64 division?

I would like to be able to have a decent result with at least n=14 and k=8 for example.

SOLUTION: As David suggested me I have found a BigIntegers unit online by Rudy Velthuis that is very good. That allows me to calculate C(32,28) which is very impressive! ( C(32,28) = 55317304280338408 if you can read it ) — Alberto Miola
At first you would better to exploit algorithmic approach as David described. — MBo
For the record, Int64 is signed integer with a size of 64 bits. You have UInt64 which is a unsigned integer with a size of 64 bits, so you lose negative values but you can represent more positive ones — Agustin Ortu
@agustin true but it does not help much with factorial where growth is, er, well, factorial — David Heffernan
@David sure, Big Integers will suffice better in this case. Just a small point I made for clarification — Agustin Ortu

David Heffernan David Heffernan · Accepted Answer · 2017-01-07T14:55:19

Extended has 64 bits of precision so no gain there. Plus it greatly complicates the coding. You could certainly make the calculation less prone to overflow by rewriting it to do the divisions as you go along. That will help to a degree. So when you find the same factor in both numerator and denominator simply remove it from both.

But really what you need is a big integer library. Search the web to find one.

Delphi factorial operations precision

1 Answers