cint university / 301 / ced, the cint editor

301-04: big exact numbers

This is lesson 301-04 of CU-301.1, checked against cint 0.2.0.

You will compute 100 factorial and a binomial coefficient to the last digit in I1024, see why each conversion is written where the value is used and find the first factorial that does not fit.

the program

The factorial of n, written n!, multiplies every whole number from 1 to n. The binomial coefficient "n choose k" counts the ways to pick k things from n: there are 2598960 different five-card hands in a deck of 52. Both grow far past I64:

// Big exact numbers: factorials, binomial coefficients and a digit count.

// n factorial, exact in I1024.
I1024 factorial(I64 n) {
    I1024 f = 1;
    for k in 1..=n {
        f *= k as I1024;
    }
    return f;
}

// n choose k: the number of ways to pick k things from n.
I1024 choose(I64 n, I64 k) {
    I1024 c = 1;
    for i in 1..=k {
        c = c * ((n - k + i) as I1024) / (i as I1024);
    }
    return c;
}

// The number of decimal digits in x, for x above 0.
I64 digits(I1024 x) {
    I1024 rest = x;
    I64 n = 0;
    while (rest > 0) {
        rest /= 10;
        n += 1;
    }
    return n;
}

void main() {
    I1024 f = factorial(100);
    "100! = {f}\n";
    "100! has {digits(f)} digits\n";
    "52 choose 5 = {choose(52, 5)}\n";
    "100 choose 50 = {choose(100, 50)}\n";
    "170! has {digits(factorial(170))} digits\n";
    "171! has {digits(factorial(171))} digits\n";
}

Run this program in ced

run it

$ cint run bignum.ci
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
100! has 158 digits
52 choose 5 = 2598960
100 choose 50 = 100891344545564193334812497256
170! has 307 digits
fault[E_OVERFLOW]: the exact result is outside the type's range
  --> bignum.ci:7:11
   |
 7 |         f *= k as I1024;
   |           ^ mul.checked.i1024
   |
   = operation: mul.checked.i1024
   = operand-count: 2
   ...
   = operand: I1024 171
   ...
   = stack-depth: 1
   = called from: bignum.ci:39:23
   = fuel-consumed: 969 (not part of the fault record)
   = state: the program stopped; stdout holds what it wrote before the fault

The first ... stands for three lines that hold numbers of more than 300 digits: 170!, the exact 171! and I1024.max. The second stands for the revision, source-map and address lines. Each value printed above agrees with math.factorial and math.comb in Python 3.13 on Ubuntu 24.04, digit for digit.

what happened

I1024 holds numbers up to about 8.99 times 10³⁰⁷. 100! has 158 digits, so it fits. 170! has 307 digits and still fits. 171! is 171 times larger, with 310 digits, and the multiplication that makes it faults. The record names the operands, 170! and 171, both as I1024 values, and gives the exact product in full.

The conversion is written at the multiplication. f is an I1024 and k is an I64, and cint never mixes two widths on its own. Leave out the conversion and the program is refused before it runs:

error[C2001]: type mismatch
  --> noas.ci:4:14
   |
 4 |         f *= k;
   |              ^
   |

k as I1024 widens k at the one place it meets f. The conversion is visible on the line where the two widths meet, so a reader does not have to look elsewhere to find it.

choose divides exactly at every step. After step i, c holds (n - k + i) choose i, which is a whole number. So the multiplication comes first, and the division that follows leaves no remainder. Dividing first, as in c * ((n - k + i) / i), would round away part of the answer at most steps.

digits works on a local variable. A parameter cannot be assigned in cint, so x /= 10 inside digits is error C2060. The function puts x into the local rest and divides that.

carrying the harmonic sum further

Lesson 201-09 added 1 + 1/2 + 1/3 and so on as an exact fraction in I64. Its second version, which adds over the least common denominator, stopped at 1/47, because the denominator of H(47) is 63245806209101973600, too large for I64. The second version goes on to 100 with I256 in place of I64 in gcd, add_unit and h, and with k as I256 at the call:

$ cint run harmonic256.ci
H(47) = 280682601097106968469/63245806209101973600
H(100) = 14466636279520351160221518043104131447711/2788815009188499086581352357412492142272

The denominator of H(100) has 40 digits. Run on, the same program prints H(170) and faults while adding 1/179, when a denominator times 179 passes I256.max.

elsewhere

The same factorial loop in C with double, built with GCC 13.3 and -O2 -Wall -Wextra on Ubuntu 24.04 for x86-64, printed 100! as a number of 158 digits whose first 15 digits are right. The exact 100! ends in 24 zeros, and the double version ends in 813248. 171! printed as inf. The same double loop for 100 choose 50 printed 100891344545564219663900999680, right in its first 15 digits and wrong after them. A double holds 53 binary digits, which is about 16 decimal digits, so most larger whole numbers in it are rounded.

Python's int grows to any size, so math.factorial(171) and much larger values are exact. It has no fault for a value outside a chosen type, because it has no fixed types. In cint the program states a fixed width, and every plain operator is checked against it.

walk-through

I1024 factorial(I64 n) takes a small count and returns a large value. A function's parameter and return types need not match.

f *= k as I1024 is the same as f = f * (k as I1024). The conversion applies to k alone, and the result is then multiplied into f, so no parentheses are needed.

while (rest > 0) compares an I1024 with the literal 0. The literal takes the type of rest, so no conversion is written.

{f} prints all 158 digits. Printing works the same for every integer type.

try this

1. Print 100 choose k for k from 0 to 100. Which k gives the largest value?
2. Add the digits of 100! together. A parameter cannot be assigned, so work on a copy, as digits does. What is the sum?
3. Write a loop that multiplies an I512 by 1, 2, 3 and so on, printing each number after it multiplies, until it faults. Which is the largest factorial an I512 holds?

I64 digit_total(I1024 x) {
    I1024 rest = x;
    I64 total = 0;
    while (rest > 0) {
        total += (rest % 10) as I64;
        rest /= 10;
    }
    return total;
}

reference

wide integers, conversions, checked arithmetic, division, print formats

Back to 301: wider numbers.