不要使用浮点数来表示阶乘;阶乘是整数的乘积,因此最好用整数表示。
阶乘增长很快,因此使用实数可能很诱人,因为实数可以表示1.0e + 30之类的巨大数字。但是浮点数仅在其大小上是精确的。它们的尾数仍然有限,它们可能很大,因为它们的指数可能很大。
32位实数可以表示精确的整数,最大约为1600万。之后,只有每个偶数整数最多可以表示3200万,而每个第四个整数最多可以表示6400万。64位整数更好,因为它们可以表示9兆位以内的精确整数。
64位整数可以进一步移动1024倍:它们可以表示2 ^ 63或大约9百万个整数(9e + 18)整数。这足以代表20 !:
20! = 2,432,902,008,176,640,000
2^63 = 9,223,372,036,854,775,808
Fortran允许您根据其应代表的小数位数选择一种整数:
integer, (kind=selected_int_kind(18))
使用它可以对64位整数进行计算。这将使您的阶乘最多为20!。不过,它不会比这更进一步:大多数计算机仅支持最大64位的整数,因此selected_int_kind(19)
会给您一个错误。
这是程序的64位整数置换部分。注意所有类型转换如何表示地板和天花板消失。
program permute
implicit none
integer, parameter :: long = selected_int_kind(18)
integer, parameter :: n = 20
integer, dimension(1:n) :: orig
integer, dimension(1:n) :: perm
integer(kind=long) :: k
do k = 1, n
orig(k) = k
end do
do k = 0, 2000000000000000_long, 100000000000000_long
call ith_perm(perm, orig, n, k)
print *, k
print *, perm
print *
end do
end program
function fact(n)
implicit none
integer, parameter :: long = selected_int_kind(18)
integer(kind=long) :: fact
integer, intent(in) :: n
integer :: i
fact = 1
i = n
do while (i > 1)
fact = fact * i
i = i - 1
end do
end function fact
subroutine ith_perm(perm, orig, n, i)
implicit none
integer, parameter :: long = selected_int_kind(18)
integer, intent(in) :: n
integer(kind=long), intent(in) :: i
integer, dimension(1:n), intent(in) :: orig
integer, dimension(1:n), intent(out) :: perm
integer, dimension(1:n) :: work
integer :: k
integer(kind=long) :: f, j
integer(kind=long) :: fact
work = orig
j = i
do k = 1, n
f = fact(n - k)
perm(k) = work(j / f + 1)
work = pack(work, work /= perm(k))
j = mod(j, f)
end do
end subroutine ith_perm