program ComputeLargeFactorial;
{$mode objfpc}{$H+}{$H-}
{
Calculating factorials for numbers n > 20 exceeds the capacity of standard 64-bit
integers (20! is the largest factorial fitting in a 64-bit unsigned integer, UInt64).
To compute exact factorials for arbitrarily large numbers, we implement a custom
arbitrary-precision integer (BigInt) dynamic array structure using base 1,000,000,000
(10^9). Storing 9 decimal digits per array element optimizes memory usage and
leverages modern 64-bit CPUs to perform fast, efficient arithmetic operations
with minimal digit carry propagation.
}
uses
SysUtils;
const
BASE = 1000000000; // Base 10^9 to store 9 decimal digits per block.
type
// Dynamic array where element 0 represents the least significant 9 digits.
TBigInt = array of Int64;
{
Multiplies an arbitrary-precision integer by a single standard 64-bit integer.
@param Num The current BigInt value to be multiplied in-place.
@param Multiplier The integer value to multiply with.
}
procedure MultiplyBigInt(var Num: TBigInt; Multiplier: Int64);
var
I: Integer;
Carry, Product: Int64;
begin
Carry := 0;
for I := 0 to High(Num) do
begin
Product := Num[I] * Multiplier + Carry;
Num[I] := Product mod BASE;
Carry := Product div BASE;
end;
// Append remaining carries as new high-order digits.
while Carry > 0 do
begin
SetLength(Num, Length(Num) + 1);
Num[High(Num)] := Carry mod BASE;
Carry := Carry div BASE;
end;
end;
{
Computes the factorial (n!) of an integer using linear iterative multiplication.
@param N The input integer.
@return The result as a TBigInt structure.
}
function Factorial(N: Integer): TBigInt;
var
I: Integer;
begin
// Explicitly initialize the managed result variable to prevent compiler warnings
Result := nil;
if N < 0 then
raise EArgumentException.Create('Factorial is undefined for negative numbers.');
// Initialize result to 1 (represented as single element array [1])
SetLength(Result, 1);
Result[0] := 1;
for I := 2 to N do
MultiplyBigInt(Result, I);
end;
{
Formats a TBigInt value into a human-readable decimal string.
@param Num The TBigInt to convert.
@return The formatted string representation.
}
function BigIntToString(const Num: TBigInt): string;
var
I: Integer;
BlockStr: string;
begin
if Length(Num) = 0 then
Exit('0');
// Most significant digit group does not need leading zero padding.
Result := IntToStr(Num[High(Num)]);
// Remaining digit groups must be left-padded with zeros to exactly 9 digits.
for I := High(Num) - 1 downto 0 do
begin
BlockStr := IntToStr(Num[I]);
Result := Result + StringOfChar('0', 9 - Length(BlockStr)) + BlockStr;
end;
end;
var
InputVal: Integer;
FactVal: TBigInt;
begin
try
InputVal := 25; // Example calculation for N > 20
FactVal := Factorial(InputVal);
WriteLn(Format('%d! = %s', [InputVal, BigIntToString(FactVal)]));
WriteLn(Format('Total Digits: %d', [Length(BigIntToString(FactVal))]));
except
on E: Exception do
WriteLn(ErrOutput, 'Error: ', E.Message);
end;
end.
{
run:
25! = 15511210043330985984000000
Total Digits: 26
}
