SITUATION
I need to make a program for my math course on combinations and permutations. If you want to calculate them, you have to deal with factorials, and I wrote 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 wrote this code in my TCombinazioni class:
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 arises when you enter large numbers, because factorial grows very fast. Here you see an example.
On the left you can see that pin 11440 is correct, but on the right it is incorrect. I know that this kind of computation is “dangerous” because I deal with large integers, even if they are declared as Int64 .
Int64 type is the largest type of integer as far as I know, but is there any other possibility if I try to do calculations with large integers?
Possible satellite (s)
Very easily, I could establish that n and k cannot be greater than 10, for example (but I prefer not to do this)
Using floating point arithmetic. I thought I could use the getSoluzioni function with the return value of Extended (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 will not accept the result.
I considered point 2 because Extended has a wider range of values than Int64. Is Delphi's Expanded Division More Accurate Than Int64 Division?
I would like to have a decent result, for example, with n = 14 and k = 8.
source share