fortran66のブログ

fortran について書きます。

浮動小数点数では結合則が成り立たない

IEEE754 の規格では、加減乗除の二項演算について、実数とその浮動小数点数表現の構造が保たれることを要求しています。つまり、加算の場合を例にとると、

a + b = c

fl(a) + fl(b)= fl(a + b) = fl(c)

この性質があるので、実数の可換な性質は保たれます。(overflow とかしなければ)

fl(a) + fl(b)= fl(a + b) = fl(b + a) = fl(b) + fl(a)

一方、実数で成り立つもっと基本的な演算規則である結合則の方は、三項演算に相当していて、規格からの要請もなく(たぶんw)成り立たない場合があります。「桁落ち」や「積み残し」が問題化するのは結合則からのズレに還元できると思います。結合則が成り立たない場合、演算の順序を明示的に指示する必要が出てきます。

(a + b) + c = a + (b + c)

(fl(a) + fl(b)) + fl(c) = fl(a + b) + fl(c) 

/=

fl(a) + (fl(b) + fl(c)) = fl(a) + fl(b + c) 


プログラムで、見てみることにしてみます。

プログラム

乱数で実数を生成して、交換子と結合子を計算してして、交換則と結合則からのずれを見てみます。ズレがなければ 0.0 になるはずです。

    program Console1
      implicit none
      integer, parameter :: kd = kind(1.0d0), nmax = 100
      real(kd) :: x(2, nmax), y(3, nmax), z(nmax)
      integer :: i
      call random_seed()
    
      print *, 'commutator'
      call random_number(x)  
      z = comm_plus(x(1, :), x(2, :))   
      print *, 'non-commutative =', count(z /= 0.0_kd), '/', nmax

      print *, 'associator' 
      call random_number(y)  
      z = assoc_plus(y(1, :), y(2, :), y(3, :))
      print *, 'non-associative =', count(z /= 0.0_kd), '/', nmax
      print '(e30.15)', pack(z, z /= 0.0_kd)   
      
      do i = 1, nmax
        if (z(i) /= 0.0_kd) print *,  y(:, i)
      end do  
      
    contains
      real(kd) pure elemental function comm_plus(x, y)
        real(kd), intent(in) :: x, y
        comm_plus = (x + y) - (y + x)
      end function comm_plus
      
      real(kd) pure elemental function comm_mult(x, y)
        real(kd), intent(in) :: x, y
        comm_mult = (x * y) - (y * x)
      end function comm_mult
      
      real(kd) pure elemental function assoc_plus(x, y, z)
        real(kd), intent(in) :: x, y, z
        assoc_plus = ((x + y) + z) - (x + (y + z))
      end function assoc_plus 

      real(kd) pure elemental function assoc_mult(x, y, z)
        real(kd), intent(in) :: x, y, z
        assoc_mult = ((x * y) * z) - (x * (y * z))
      end function assoc_mult 
    end program Console1

計算結果

計算結果から分かるように、交換則の方は確かに満たされていますが、結合則の方は2割程度の確率で満たされていないことが分かります。

ステパノフの本や関数型言語の本などでは、結合則を根底において、モノイド、半群、群などの造を導入して、結合則による演算順序の組み換えを縦横に使って並列動作などさせていますが、整数や文字列のような離散値の場合はよいとして、浮動小数点数の場合は結合則が崩れているので、実数の演算の問題にどこまで適用できるのか慎重に見極める必要がある気がします。


 commutator
 non-commutative =           0 /         100
 associator
 non-associative =          22 /         100
        -0.222044604925031E-15
         0.222044604925031E-15
        -0.444089209850063E-15
         0.222044604925031E-15
         0.222044604925031E-15
         0.222044604925031E-15
        -0.222044604925031E-15
         0.222044604925031E-15
         0.222044604925031E-15
         0.222044604925031E-15
        -0.444089209850063E-15
        -0.222044604925031E-15
         0.222044604925031E-15
        -0.222044604925031E-15
         0.111022302462516E-15
         0.444089209850063E-15
         0.111022302462516E-15
         0.111022302462516E-15
         0.222044604925031E-15
         0.222044604925031E-15
         0.222044604925031E-15
         0.444089209850063E-15
  0.197336647554121       0.583104599529825       0.230515619550751
  0.478456421601024       0.365995662803589       0.695310195955152
  0.765030199209025       0.821438970892834       0.822794756357349
  0.154500948792594       0.776532299353388       0.343291349327081
  0.123168650301795       0.892064457677992       0.624841959267652
  5.340595195978214E-002  0.883762457929461       0.282097598062034
  0.271274877739308       0.990276136982007       0.295042576304925
  0.385678503561146       0.550016479450929       0.368699724012741
  0.649285046006193       0.772531681072521       0.291322963201651
  6.278512502868444E-002  0.484351337035122       0.846490729577704
  0.791263186492663       0.730073920942973       0.590455112135355
  0.599791134233700       0.716285730192570       0.379474641874127
  0.271981838214423       0.686661556999306       0.655546444804149
  9.427993838386348E-002  0.387223376386792       0.590407433074261
  0.295995343550855       0.100678724962143       0.578481472642591
  0.631307369405927       0.834670683810024       0.762999289601546
  0.634957778719910       0.129886627681722       0.170474343695826
  0.131887838808105       6.074681699437982E-002  0.581256123449080
  8.217122777577210E-002  0.437050020391703       0.846554402242005
  0.522359744366527       0.748392434610684       0.567776991641634
  0.555136565205923       0.518809881107340       0.750619304274506
  0.487565338352254       0.577165852794002       0.970361542180519
続行するには何かキーを押してください . . .