Borwein算法用于在Fortran中计算Pi,收敛速度太快。

huangapple go评论98阅读模式
英文:

Borwein’s algorithm for the calculation of Pi in Fortran is converging too fast

问题

下面是Fortran中Borwein算法的实现,具有四次收敛,它确实计算出了Pi,但收敛得太快。理论上,a 每次收敛都是四次方收敛到 1/π。在每次迭代中,因此正确位数的数量被四倍增加。

! pi.f90
program main
    use, intrinsic :: iso_fortran_env, only: real128
    implicit none
    real(kind=real128), parameter :: CONST_PI = acos(-1._real128)
    real(kind=real128)            :: pi
    integer                       :: i

    do i = 1, 10
        pi = borwein(i)
        print '("Pi (n = ", i3, "): ", f0.100)', i, pi
    end do

    print '("Pi:", 11x, f0.100)', CONST_PI
contains
    function borwein(n) result(pi)
        integer, intent(in) :: n
        real(kind=real128)  :: pi
        real(kind=real128)  :: a, y
        integer             :: i

        y = sqrt(2._real128) - 1
        a = 2 * (sqrt(2._real128) - 1)**2

        do i = 1, n
            y = (1 - (1 - y**4)**.25_real128) / (1 + (1 - y**4)**.25_real128)
            a = a * (1 + y)**4 - 2**(2 * (i - 1) + 3) * y * (1 + y + y**2)
        end do

        pi = 1 / a
    end function borwein
end program main

但是在第二次迭代之后,Pi的值不再改变,如下所示,前100位数字都相同:

$ gfortran -o pi pi.f90
$ ./pi
Pi (n =   1): 3.1415926462135422821493444319826910539597974491424025615960346875056357837663334464650688460096716881
Pi (n =   2): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   3): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   4): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   5): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   6): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   7): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   8): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   9): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =  10): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi:           3.1415926535897932384626433832795027974790680981372955730045043318742967186629755360627314075827598572

(最后一个输出是正确的Pi值,供比较使用。)

这个实现中是否有错误?我不确定real128精度是否一直保持。

英文:

The following implementation of Borwein’s algorithm with quartic convergence in Fortran admittedly calculates Pi, but converges simply too fast. In theory, a converges quartically to 1/π. On each iteration, the number of correct digits is therefore quadrupled.

! pi.f90
program main
    use, intrinsic :: iso_fortran_env, only: real128
    implicit none
    real(kind=real128), parameter :: CONST_PI = acos(-1._real128)
    real(kind=real128)            :: pi
    integer                       :: i

    do i = 1, 10
        pi = borwein(i)
        print '("Pi (n = ", i3, "): ", f0.100)', i, pi
    end do

    print '("Pi:", 11x, f0.100)', CONST_PI
contains
    function borwein(n) result(pi)
        integer, intent(in) :: n
        real(kind=real128)  :: pi
        real(kind=real128)  :: a, y
        integer             :: i

        y = sqrt(2._real128) - 1
        a = 2 * (sqrt(2._real128) - 1)**2

        do i = 1, n
            y = (1 - (1 - y**4)**.25_real128) / (1 + (1 - y**4)**.25_real128)
            a = a * (1 + y)**4 - 2**(2 * (i - 1) + 3) * y * (1 + y + y**2)
        end do

        pi = 1 / a
    end function borwein
end program main

But after the second iteration, the value of Pi does not change anymore, as one can see for the first 100 digits:

$ gfortran -o pi pi.f90
$ ./pi
Pi (n =   1): 3.1415926462135422821493444319826910539597974491424025615960346875056357837663334464650688460096716881
Pi (n =   2): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   3): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   4): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   5): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   6): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   7): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   8): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =   9): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi (n =  10): 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
Pi:           3.1415926535897932384626433832795027974790680981372955730045043318742967186629755360627314075827598572

(The last output is the correct value of Pi for comparison.)

Is there an error in the implementation? I’m not sure, if real128 precision is always kept.

答案1

得分: 5

在第二次迭代中,您已经收敛到real128可以支持的位数:

ian@eris:~/work/stack$ cat pi2.f90
Program pi2

  Use, intrinsic :: iso_fortran_env, only: real128

  Implicit None

  Real( real128 ) :: pi

  pi = 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439_real128

  Write( *, '( f0.100 )' ) pi
  Write( *, '( f0.100 )' ) Nearest( pi, +1.0_real128 )
  Write( *, '( f0.100 )' ) Abs( acos(-1._real128) - Nearest( pi, +1.0_real128 ) )


End Program pi2
ian@eris:~/work/stack$ gfortran -std=f2008 -Wall -Wextra -fcheck=all pi2.f90 
ian@eris:~/work/stack$ ./a.out
3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
3.1415926535897932384626433832795027974790680981372955730045043318742967186629755360627314075827598572
.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
ian@eris:~/work/stack$ 

因此,进一步的迭代显示没有变化,因为已经达到了它能够精确表示的极限。

英文:

At the second iteration you have converged to as many digits as real128 can support:

ian@eris:~/work/stack$ cat pi2.f90
Program pi2

  Use, intrinsic :: iso_fortran_env, only: real128

  Implicit None

  Real( real128 ) :: pi

  pi = 3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439_real128

  Write( *, '( f0.100 )' ) pi
  Write( *, '( f0.100 )' ) Nearest( pi, +1.0_real128 )
  Write( *, '( f0.100 )' ) Abs( acos(-1._real128) - Nearest( pi, +1.0_real128 ) )
  
  

End Program pi2
ian@eris:~/work/stack$ gfortran -std=f2008 -Wall -Wextra -fcheck=all pi2.f90 
ian@eris:~/work/stack$ ./a.out
3.1415926535897932384626433832795024122930792206901249618089158148888330110426458929850923595950007439
3.1415926535897932384626433832795027974790680981372955730045043318742967186629755360627314075827598572
.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
ian@eris:~/work/stack$ 

Thus the further iterations show no change as it is already as accurate as it can be

huangapple
  • 本文由 发表于 2020年1月3日 23:19:54
  • 转载请务必保留本文链接:https://go.coder-hub.com/59581069.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定