Fortran big integers
last modified November 14, 2026
Every integer type has a largest value, and a computation that goes past it
does not stop: the bits wrap around and the program continues with a wrong
answer. The default integer holds up to 2,147,483,647, an int64 up
to 9,223,372,036,854,775,807, and 21 factorial is already larger than the
second of those. When a program needs exact values beyond the hardware limits,
it must store the number itself, one decimal digit per array element, and
implement the arithmetic on those digits.
This article first shows the overflow in both integer kinds, then builds an arbitrary-precision integer from an allocatable array of decimal digits: multiplication by a small factor, addition of two such numbers, schoolbook multiplication of two of them, and a packed representation that stores nine digits per element. The examples compute 100!, Fibonacci numbers up to 200, 2 to the 256th and 2 to the 1000th, and check every result against an independent route.
Where the built-in integers stop
huge(x) returns the largest value of the kind of x.
The factorial function grows faster than any fixed-width type can follow:
13 factorial exceeds the default integer, and 21 factorial exceeds
int64. gfortran performs the multiplication and keeps the low 32
or 64 bits of the product, which is a negative number for a result that
overflowed the signed range. The constant itself cannot even be written in the
source, because the compiler rejects an integer literal that does not fit its
kind.
program g1
use iso_fortran_env, only: int64
implicit none
integer :: i
integer :: small
integer(int64) :: wide
print '(a, i0)', 'huge(default integer) = ', huge(0)
print '(a, i0)', 'huge(int64) = ', huge(0_int64)
small = 1
do i = 2, 13
small = small * i
end do
print '(a, i0)', '13! in a default integer = ', small
wide = 1_int64
do i = 2, 20
wide = wide * int(i, int64)
end do
print '(a, i0)', '20! in an int64 = ', wide
wide = wide * 21_int64
print '(a, i0)', '21! in an int64 = ', wide
print '(a, i0)', '21! / 21 in an int64 = ', wide / 21_int64
end program g1
Thirteen factorial comes out as 1,932,053,504 instead of
6,227,020,800, and twenty-one factorial as -4,249,290,049,419,214,848 instead
of 51,090,942,171,709,440,000. Dividing the wrapped value by 21 gives
-202,347,145,210,438,802 rather than 20 factorial, which shows that the damage
cannot be undone afterwards. Only twenty factorial fits an int64,
and the constant for 21 factorial is rejected by the compiler with "Integer too
big for its kind".
$ gfortran g1.f90 -o g1 $ ./g1 huge(default integer) = 2147483647 huge(int64) = 9223372036854775807 13! in a default integer = 1932053504 20! in an int64 = 2432902008176640000 21! in an int64 = -4249290049419214848 21! / 21 in an int64 = -202347145210438802
A number as an array of digits
The type big holds an allocatable array digit and a
count of the digits in use. The digits are stored in reverse order, least
significant first, because arithmetic starts at the units and a carry moves
towards the higher positions. The constructor allocates sixteen places and
fills them from the integer; the multiplication routine multiplies every digit
by a small factor, keeps the remainder as the new digit and carries the
quotient to the next position. When the carry needs a place that does not
exist, the array is doubled with move_alloc.
module bignum
implicit none
private
public :: big, big_from_int, mul_small, print_big
type :: big
integer, allocatable :: digit(:)
integer :: count = 0
end type big
contains
function big_from_int(value) result(b)
integer, intent(in) :: value
type(big) :: b
integer :: x
allocate (b%digit(16))
x = value
b%count = 0
if (x == 0) then
b%count = 1
b%digit(1) = 0
return
end if
do while (x > 0)
b%count = b%count + 1
b%digit(b%count) = mod(x, 10)
x = x / 10
end do
end function big_from_int
subroutine mul_small(b, factor)
type(big), intent(inout) :: b
integer, intent(in) :: factor
integer, allocatable :: wider(:)
integer :: i, carry, total
carry = 0
do i = 1, b%count
total = b%digit(i) * factor + carry
b%digit(i) = mod(total, 10)
carry = total / 10
end do
do while (carry > 0)
if (b%count == size(b%digit)) then
allocate (wider(2 * size(b%digit)))
wider(1:b%count) = b%digit(1:b%count)
call move_alloc(wider, b%digit)
end if
b%count = b%count + 1
b%digit(b%count) = mod(carry, 10)
carry = carry / 10
end do
end subroutine mul_small
subroutine print_big(b)
type(big), intent(in) :: b
integer :: i
do i = b%count, 1, -1
write (*, '(i1)', advance='no') b%digit(i)
end do
print *
end subroutine print_big
end module bignum
program g2
use bignum
implicit none
type(big) :: factorial
integer :: i
factorial = big_from_int(1)
do i = 2, 100
call mul_small(factorial, i)
end do
print '(a)', '100! ='
call print_big(factorial)
print '(a, i0)', 'number of decimal digits: ', factorial%count
end program g2
Multiplying by 2, then 3, up to 100 builds 100 factorial exactly: 158 digits, starting with 9332621544 and ending with twenty-four zeros. Every intermediate product is exact, because the only operation is a digit times a factor of at most 100 plus a carry below 100, which fits easily in a default integer. The array grows from 16 to 256 places along the way, each growth copying the digits to a wider array and moving the new storage into the old variable.
$ gfortran g2.f90 -o g2 $ ./g2 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 number of decimal digits: 158
Adding two big numbers
Addition is the same grade-school algorithm: add the digits in the same position together with the carry from the previous position, write the remainder and carry the quotient. The only complication is that the two numbers may have different lengths, so a helper returns zero for a position beyond the end. The sum needs at most one digit more than the longer operand, and leading zeros are trimmed when the addition is finished. Two big numbers added repeatedly produce the Fibonacci sequence to any length.
module bigadd
implicit none
private
public :: big, big_from_int, add, print_big
type :: big
integer, allocatable :: digit(:)
integer :: count = 0
end type big
contains
function big_from_int(value) result(b)
integer, intent(in) :: value
type(big) :: b
integer :: x
allocate (b%digit(16))
x = value
b%count = 0
if (x == 0) then
b%count = 1
b%digit(1) = 0
return
end if
do while (x > 0)
b%count = b%count + 1
b%digit(b%count) = mod(x, 10)
x = x / 10
end do
end function big_from_int
subroutine add(a, b, sum)
type(big), intent(in) :: a, b
type(big), intent(out) :: sum
integer :: i, carry, total, digits
digits = max(a%count, b%count)
allocate (sum%digit(digits + 1))
carry = 0
do i = 1, digits
total = digit_of(a, i) + digit_of(b, i) + carry
sum%digit(i) = mod(total, 10)
carry = total / 10
end do
sum%count = digits
if (carry > 0) then
sum%count = sum%count + 1
sum%digit(sum%count) = carry
end if
do while (sum%count > 1 .and. sum%digit(sum%count) == 0)
sum%count = sum%count - 1
end do
end subroutine add
integer function digit_of(b, position) result(d)
type(big), intent(in) :: b
integer, intent(in) :: position
if (position <= b%count) then
d = b%digit(position)
else
d = 0
end if
end function digit_of
subroutine print_big(b)
type(big), intent(in) :: b
integer :: i
do i = b%count, 1, -1
write (*, '(i1)', advance='no') b%digit(i)
end do
print *
end subroutine print_big
end module bigadd
program g3
use bigadd
implicit none
type(big) :: a, b, sum
integer :: i
a = big_from_int(1)
b = big_from_int(1)
do i = 3, 100
call add(a, b, sum)
a = b
b = sum
end do
print '(a)', 'fib(100) ='
call print_big(b)
print '(a, i0)', 'digits: ', b%count
do i = 101, 200
call add(a, b, sum)
a = b
b = sum
end do
print '(a)', 'fib(200) ='
call print_big(b)
print '(a, i0)', 'digits: ', b%count
end program g3
The hundredth Fibonacci number has 21 digits and the two hundredth has 42, both printed exactly. The loop keeps three values, the two previous numbers and the sum, and rotates them with ordinary assignment; because the type has an allocatable component, the assignment copies the digits rather than sharing them. The same code would reach the thousandth number in a few thousand additions.
$ gfortran g3.f90 -o g3 $ ./g3 fib(100) = 354224848179261915075 digits: 21 fib(200) = 280571172992510140037611932413038677189525 digits: 42
Multiplying two big numbers
The schoolbook method multiplies every digit of one number by every digit of
the other and adds the products into a result array at the position given by
the sum of the two indexes. With n digits on each side this takes
n**2 digit multiplications, which is slow for thousands of digits
but perfectly adequate for the sizes here. The result array is allocated with
a%count + b%count places, the largest possible length of the
product.
module bigmul
implicit none
private
public :: big, big_from_int, mul, mul_small, print_big, same
integer, parameter :: room = 400
type :: big
integer, allocatable :: digit(:)
integer :: count = 0
end type big
contains
function big_from_int(value) result(b)
integer, intent(in) :: value
type(big) :: b
integer :: x
allocate (b%digit(room))
x = value
b%count = 0
do while (x > 0)
b%count = b%count + 1
b%digit(b%count) = mod(x, 10)
x = x / 10
end do
if (b%count == 0) then
b%count = 1
b%digit(1) = 0
end if
end function big_from_int
subroutine mul_small(b, factor)
type(big), intent(inout) :: b
integer, intent(in) :: factor
integer :: i, carry, total
carry = 0
do i = 1, b%count
total = b%digit(i) * factor + carry
b%digit(i) = mod(total, 10)
carry = total / 10
end do
do while (carry > 0)
b%count = b%count + 1
b%digit(b%count) = mod(carry, 10)
carry = carry / 10
end do
end subroutine mul_small
subroutine mul(a, b, product)
type(big), intent(in) :: a, b
type(big), intent(out) :: product
integer :: i, j, carry, total
allocate (product%digit(a%count + b%count))
product%digit = 0
do i = 1, a%count
carry = 0
do j = 1, b%count
total = product%digit(i + j - 1) + &
a%digit(i) * b%digit(j) + carry
product%digit(i + j - 1) = mod(total, 10)
carry = total / 10
end do
product%digit(i + b%count) = carry
end do
product%count = a%count + b%count
do while (product%count > 1 .and. &
product%digit(product%count) == 0)
product%count = product%count - 1
end do
end subroutine mul
logical function same(a, b) result(equal)
type(big), intent(in) :: a, b
equal = a%count == b%count .and. &
all(a%digit(1:a%count) == b%digit(1:b%count))
end function same
subroutine print_big(b)
type(big), intent(in) :: b
integer :: i
do i = b%count, 1, -1
write (*, '(i1)', advance='no') b%digit(i)
end do
print *
end subroutine print_big
end module bigmul
program g4
use bigmul
implicit none
type(big) :: x, square, doubled
integer :: i
x = big_from_int(1)
do i = 1, 128
call mul_small(x, 2)
end do
print '(a)', '2^128 ='
call print_big(x)
call mul(x, x, square)
print '(a)', '2^128 squared ='
call print_big(square)
doubled = big_from_int(1)
do i = 1, 256
call mul_small(doubled, 2)
end do
print '(a, l1)', 'same as doubling 256 times: ', same(square, doubled)
print '(a, i0)', 'digits in the answer: ', square%count
end program g4
The program squares 2 to the 128th and gets the 78-digit 2 to the 256th. To prove that the multiplication is right, it also computes the same power by doubling 256 times, and the comparison of the two digit arrays reports true. The value 2^256 is the number of different 256-bit keys, so the printed digits are also the size of the key space of a 256-bit cipher.
$ gfortran g4.f90 -o g4 $ ./g4 2^128 = 340282366920938463463374607431768211456 2^128 squared = 115792089237316195423570985008687907853269984665640564039457584007913129639936 same as doubling 256 times: T digits in the answer: 78
Where int64 gives up
The 93rd Fibonacci number is 12,200,160,415,121,876,738, just above the
int64 limit, and the built-in loop produces
-6,246,583,658,587,674,878 instead. Adding 2 to the 64th power to that value, in
floating point, returns about 1.22e19, which is the true answer and shows that
the wrapped value is exactly the correct one minus 2 to the 64th. The digit
array does not care about the limit and prints all twenty digits.
module bigadd
implicit none
private
public :: big, big_from_int, add, print_big
type :: big
integer, allocatable :: digit(:)
integer :: count = 0
end type big
contains
function big_from_int(value) result(b)
integer, intent(in) :: value
type(big) :: b
integer :: x
allocate (b%digit(16))
x = value
b%count = 0
do while (x > 0)
b%count = b%count + 1
b%digit(b%count) = mod(x, 10)
x = x / 10
end do
if (b%count == 0) then
b%count = 1
b%digit(1) = 0
end if
end function big_from_int
subroutine add(a, b, sum)
type(big), intent(in) :: a, b
type(big), intent(out) :: sum
integer :: i, carry, total, digits
digits = max(a%count, b%count)
allocate (sum%digit(digits + 1))
carry = 0
do i = 1, digits
total = digit_of(a, i) + digit_of(b, i) + carry
sum%digit(i) = mod(total, 10)
carry = total / 10
end do
sum%count = digits
if (carry > 0) then
sum%count = sum%count + 1
sum%digit(sum%count) = carry
end if
end subroutine add
integer function digit_of(b, position) result(d)
type(big), intent(in) :: b
integer, intent(in) :: position
if (position <= b%count) then
d = b%digit(position)
else
d = 0
end if
end function digit_of
subroutine print_big(b)
type(big), intent(in) :: b
integer :: i
do i = b%count, 1, -1
write (*, '(i1)', advance='no') b%digit(i)
end do
print *
end subroutine print_big
end module bigadd
program g5
use bigadd
use iso_fortran_env, only: int64
implicit none
type(big) :: a, b, sum
integer :: i
print '(a, i0)', 'fib(92) in int64: ', fib64(92)
print '(a, i0)', 'fib(93) in int64: ', fib64(93)
print '(a, es14.6)', 'plus 2^64 gives: ', real(fib64(93), 8) + &
18446744073709551616.0_8
a = big_from_int(1)
b = big_from_int(1)
do i = 3, 93
call add(a, b, sum)
a = b
b = sum
end do
print '(a)', 'fib(93) with digits:'
call print_big(b)
print '(a, i0)', 'digits: ', b%count
contains
integer(int64) function fib64(n) result(r)
integer, intent(in) :: n
integer(int64) :: previous, current, next
integer :: i
previous = 1_int64
current = 1_int64
do i = 3, n
next = previous + current
previous = current
current = next
end do
r = current
end function fib64
end program g5
The two results sit next to each other for comparison: the int64
function returns a negative number at 93, and the digit array returns
12200160415121876738. The floating-point line is a check rather than a repair:
adding 2**64 to the wrapped value recovers the magnitude, but the exact digits
are already lost once the addition overflowed.
$ gfortran g5.f90 -o g5 $ ./g5 fib(92) in int64: 7540113804746346429 fib(93) in int64: -6246583658587674878 plus 2^64 gives: 1.220016E+19 fib(93) with digits: 12200160415121876738 digits: 20
Reading the digits
Once the number is a list of decimal digits, questions about its digits are
simple loops. The sum of the digits is a sum over the array, the number of
trailing zeros is a scan from the units upward, and the leading digit is the
last stored element, since the storage is reversed. These statistics are how a
program checks a big-number routine against a mathematical property: the number
of trailing zeros of n! must equal the number of factors of five
in the numbers from 1 to n.
module bignum
implicit none
private
public :: big, big_from_int, mul_small, digit_sum, trailing_zeros
type :: big
integer, allocatable :: digit(:)
integer :: count = 0
end type big
contains
function big_from_int(value) result(b)
integer, intent(in) :: value
type(big) :: b
integer :: x
allocate (b%digit(16))
x = value
b%count = 0
do while (x > 0)
b%count = b%count + 1
b%digit(b%count) = mod(x, 10)
x = x / 10
end do
if (b%count == 0) then
b%count = 1
b%digit(1) = 0
end if
end function big_from_int
subroutine mul_small(b, factor)
type(big), intent(inout) :: b
integer, intent(in) :: factor
integer, allocatable :: wider(:)
integer :: i, carry, total
carry = 0
do i = 1, b%count
total = b%digit(i) * factor + carry
b%digit(i) = mod(total, 10)
carry = total / 10
end do
do while (carry > 0)
if (b%count == size(b%digit)) then
allocate (wider(2 * size(b%digit)))
wider(1:b%count) = b%digit(1:b%count)
call move_alloc(wider, b%digit)
end if
b%count = b%count + 1
b%digit(b%count) = mod(carry, 10)
carry = carry / 10
end do
end subroutine mul_small
integer function digit_sum(b) result(total)
type(big), intent(in) :: b
total = sum(b%digit(1:b%count))
end function digit_sum
integer function trailing_zeros(b) result(n)
type(big), intent(in) :: b
n = 0
do while (n < b%count .and. b%digit(n + 1) == 0)
n = n + 1
end do
end function trailing_zeros
end module bignum
program g6
use bignum
implicit none
type(big) :: factorial
integer :: i, zeros, fives
factorial = big_from_int(1)
do i = 2, 100
call mul_small(factorial, i)
end do
zeros = trailing_zeros(factorial)
fives = 0
i = 5
do while (i <= 100)
fives = fives + 100 / i
i = i * 5
end do
print '(a, i0)', 'digits: ', factorial%count
print '(a, i0)', 'digit sum: ', digit_sum(factorial)
print '(a, i0)', 'leading digit: ', factorial%digit(factorial%count)
print '(a, i0)', 'trailing zeros: ', zeros
print '(a, i0)', 'factors of five: ', fives
print '(a, l1)', 'they agree: ', zeros == fives
end program g6
100 factorial has 158 digits, its digits sum to 648, it begins with 9 and ends with 24 zeros. The factor count is 20 from the multiples of 5, 4 more from the multiples of 25 and 1 more from 100, which is 24, and the two independent computations agree. A digit sum is also the first check of a newly written multiplication routine, because a wrong digit anywhere changes it.
$ gfortran g6.f90 -o g6 $ ./g6 digits: 158 digit sum: 648 leading digit: 9 trailing zeros: 24 factors of five: 24 they agree: T
Nine digits per element
One decimal digit per integer wastes 97 percent of every element, and the
schoolbook multiplication then does far more work than necessary. The usual
compromise stores nine decimal digits in each element, since every product of
two such values plus a carry stays below 2 to the 64th power. The base is
1,000,000,000, the carry arithmetic is done in int64, and printing
writes the highest element plainly and every other one with the
i9.9 descriptor, which restores the leading zeros.
module packed
use iso_fortran_env, only: int64
implicit none
private
public :: big, start, double_it, to_string
integer, parameter :: base = 1000000000
integer, parameter :: room = 200
type :: big
integer :: limb(room) = 0
integer :: count = 0
end type big
contains
function start(value) result(b)
integer, intent(in) :: value
type(big) :: b
b%limb(1) = value
b%count = 1
end function start
subroutine double_it(b)
type(big), intent(inout) :: b
integer(int64) :: carry, total
integer :: i
carry = 0
do i = 1, b%count
total = 2_int64 * int(b%limb(i), int64) + carry
b%limb(i) = int(mod(total, int(base, int64)))
carry = total / int(base, int64)
end do
if (carry > 0) then
b%count = b%count + 1
b%limb(b%count) = int(carry)
end if
end subroutine double_it
function to_string(b) result(text)
type(big), intent(in) :: b
character(len=400) :: text
integer :: i, position
write (text, '(i0)') b%limb(b%count)
position = len_trim(text) + 1
do i = b%count - 1, 1, -1
write (text(position:position + 8), '(i9.9)') b%limb(i)
position = position + 9
end do
end function to_string
end module packed
program g7
use packed
use iso_fortran_env, only: real64
implicit none
type(big) :: power
character(len=400) :: text
integer :: i, n, total
power = start(1)
do i = 1, 1000
call double_it(power)
end do
text = to_string(power)
n = len_trim(text)
total = 0
do i = 1, n
total = total + iachar(text(i:i)) - iachar('0')
end do
print '(a, i0)', 'digits: ', n
print '(a, i0)', 'predicted by log10: ', &
floor(1000.0_real64 * log10(2.0_real64)) + 1
print '(a, i0)', 'limbs of nine digits: ', power%count
print '(a)', '2^1000 ='
do i = 1, n, 60
print '(a)', text(i:min(i + 59, n))
end do
print '(a, i0)', 'digit sum: ', total
end program g7
Doubling a thousand times produces 2 to the 1000th in 34 elements, less than
a ninth of the 302 digits the decimal version would need. The digit count is
302, and it matches floor(1000*log10(2)) + 1 computed in floating
point, which is a different algorithm agreeing with the integer one. The sum of
the 302 digits is 1366, a value a reader can check with any other bignum
library. The number is printed in lines of sixty digits, broken only for
display.
$ gfortran g7.f90 -o g7 $ ./g7 digits: 302 predicted by log10: 302 limbs of nine digits: 34 2^1000 = 107150860718626732094842504906000181056140481170553360744375 038837035105112493612249319837881569585812759467291755314682 518714528569231404359845775746985748039345677748242309854210 746050623711418779541821530464749835819412673987675591655439 460770629145711964776865421676604298316526243868372056680693 76 digit sum: 1366
Next steps
The data types article explains the kinds
whose limits are printed in the first program, and the
allocatable arrays article describes the
growth by move_alloc used by the digit array. The
arrays article covers the array sections that
the print and compare routines pass around, the
operators article explains the integer
division and remainder that produce each digit, and the
floating-point article shows why the
logarithm check is reliable only to the precision of the type.
Source
Fortran 2018 standard (J3/18-007r1)
Fortran-lang: learning resources
In this article we have seen 13 factorial and 21 factorial wrap around in the
built-in integer kinds, stored a number as an array of decimal digits, grown
that array with move_alloc, multiplied by a small factor to build
100 factorial, added two big numbers to reach the 200th Fibonacci number,
multiplied two big numbers to square 2 to the 128th, compared the result with
repeated doubling, met the 93rd Fibonacci number at the int64
limit, counted digits and trailing zeros, and packed nine digits into each
element to compute 2 to the 1000th. The previous article,
Fortran floating-point arithmetic,
explains the rounding that limits the built-in types.
Author
List all Fortran tutorials.