            ࠫ쭠 ࠡ⪠        14.12.2000
               ..  / /

                     
               ࠫ  
    1. 
    2. ७ ᫨⥫ ⬮
       2.1.  ࠫ
    3. ࠫ  㬬஢
    4. ࠫ  ४ᨢ ⬮
    5. ᪠ 㬬஢
    6. ᮢ ࠫ ⬮
    7. ᪠ ।  襭 ࠢ ४ᨨ 1 浪
    8. ࠫ   ந⥫쭮 

                ᫥   
    1. 筨 ᫨⥫ 譮⥩
    2. 譮 室 
    3.  ।⠢ ᥫ  
    4. ᫠  饩 ⮩
       4.1. ।⠢ ⥬  饩 窮  
    5. ᮡ 䬥⨪  饩 ⮩
       5.1. 襭 ࠨ᪨   饩 䬥⨪
    6. 筮 饩 䬥⨪
    7. 譮 㣫  ᫥
       7.1. 譮 믮 䬥᪨ 権
    8. ⨬樮 ८ࠧ  ணࠬ
         1. ஢  ॢ  ᫥
         2. ᪫祭  ࠦ
         3. 稢 横
    9. ஢ ⨬樮 ८ࠧ
   10. ᮡ ᫥ ࠦ  ࠭ 90
   11. 譮 ᨭ஭ ᯠࠫ

                   ࠫ  
                      1. 
             ଠ । ⬠ ᫥饥.
        -  ᫥⥫쭮 ࠡ⪨   ,
⥪騩    ⭮ ६ ⠪,     ᫥騩 
६   砥   ࠢ   

                                - 2 -

 稭,   ।騩 .
        蠣  । ⬠  -
, ⮬,  ࠢ ८ࠧ 稭   ᪠  
।뢠 ࠫ  ࠡ.    ࠫ-
,    蠣 ࠡ⪨    믮  ࠫ쭮.
,   ᫮ ஢   ।⠢  ᫥-
⥫,   : Ci = Ai + Bi  i=1,2..n,   筮 : C
= A + B, ᥬ⨪ ண ᪠ ࠫ ࠡ ⮢
஢.

             2. ७ ᫨⥫ ⬮
     ᭮ 楩  ७  ᫨⥫  ⬮ 
᫮ 権  ᫠  饩 ⮩  "䫮"  (flop).  
ॠ樨  ⬮   ࠫ ᫨⥫ ⥬ ᮡ
 ।⠢ ७ ࠫ ⬮.

                2.1.  ࠫ
     "쭮   ࠫ ࠪ,     ६ 
⥬᪮ ⨥  祭 300  室  ⢨-
,   ࠧ,  ᫥⥫쭮 ⥬⨪,  50  -  -
⢨ ᮧ ᫥⥫ ⬮,  15  -  -
⢨ ணࠬ஢  ᫥⥫쭮 ࠭."
                                       /. ࡥ 1976 ./
      ॠ樨  ᮢ६  ᫨⥫  ⥬  ᫨-
⥫ ⬮      ࠫ  ᫥ ।⢥
  ६  ࠡ.
     "⥯ ࠫ" /ࠫ쭠 ᫮/ ᫥  -
⬠  뢠  ᫮  権,    믮 ࠫ-
쭮. ⥯ ࠫ ⬠ ᫮ ஢ ࠢ n.
     樨,  ᥣ    믮  쭮 
ࠫ쭮 ᨬ     ⢠,   뢠 ﬨ
䨪஢ 㡨.
       ᫥⥫  ᫮ ᥫ:  S = A1,  S = S + Ai,
i=2,..n  㫥 ⥯ ࠫ.

           3. ࠫ  㬬஢
     ࠫ쭮 㬬஢ ᫥⥫쭮 n ᥫ   ந-
  ⠪:    ࢮ ⠯ ᪫뢠 ᥤ ᫠.  祭

                                - 3 -

㬬 ⠪ ᪫뢠 ୮,  ..  n = 2**q  ⮨
 q = log n ⠯,  ࢮ ⠯ 믮 n/2 ᫮ (⥯
ࠫ쭮 ⠯ n/2),   ஬ - n/4  . .   -
뢠  ᫮ ⮤ ᤢ,    ࠧ ⥯ -
ࠫ  ࠧ ⠯ ᫥.  ,  뢠騩 ᫥-
⥫쭮  権  ᫮,    ᤢ ( . ⥣ "fan-in
grafh.") ।⠢ ᮡ 筮 ॢ,  ᮮ⢥⢥, 믮-
 樨  뢠 ﬨ  ॢ.
     ᮡ ॠ樨 楤 㬬஢   ⮤  
 ⥪ ᫨⥫쭮 ⥬.  稨 n/2 ஢ 
ࠡ  믮 ⠪:  ࢮ ⠯ ६  -
  /  ᥤ  ⮢  ᫥⥫쭮 Ai,  ..
(A1+A2),  (A3+A4),...(An-1+An);  ⥬ ⠪ 楤  
㬬஢  祭  㬬  ⠪ .  ᫨ n = 2**q,  
१ q = log2n 蠣 砥  ᪮  㬬.  ,    
ᨭ஭ ᫥,    뫪   㬬  
ࠢ  ६ ᫥ 㬬  ᥫ     .
⮬,   ⮬  ᮡ⥩ ࠪ⨪ ᫨⥫쭮 ⥬,
ॢ ᫥   ८ࠧ,  ਬ,   楫 㢥-
祭 ᫠ 権, 믮塞  㧫, 襭 "୨" -
⬠.
      ᤢ ॠ ⠪   ⨬樨 -
஢ ᫥⥫    㧪  稫-
.     ⨬   "஢   ॢ   ᫥"
(tree-height reduction or balancing) 㤥 ࠪ⮢ ᫥ 㬬
⢥ ᥫ:  A+B+C+D+E+F+G+H,  ᫥⥫쭮 権:
(((A+B)+(C+D))+((E+F)+(G+H))).
     砭 1
      ᤢ 蠥  -㬮砭 ᫥⥫-
 ᫥    ⭮ 㬬,   
 १.
     砭 2
     浪 㬬஢  ࠢ, ᯮ ਭ樯 ࠭-
 ᪮:     ᫥⥫쭮 ᫥,
।ᠭ   짮⥫.   ਬ:    ࠦ    :
(((((((A+B)+C)+D)+E)+F)+G)+H) 頥 㬬஢ ᤢ.
     砭 3
      ᤢ  ਬ஬ ப   ࠫ-

                                - 4 -

 ⬮, 뢠 ।樮묨 ⬠, , -
ﬨ 䬨᪮ 㡨.
   /  - 饭,  , 㬥襭 ࠧ ࣠ 
   祧./
       ࠡ  㬬஢ ⮤ ᤢ  -
뢠 ⠪ ⬮ ᪠ 㬬.

           4. ࠫ  ४ᨢ ⬮
      - ᫥⥫쭮 ᫥,   ஬,  祭
ᠬ ᫥ ଠ  ᫥⥫쭮        
᪮쪮 ࠭ ᫥ ମ.   㯯 ᫥  -
 ࠫ쭮,  ᯮ १ ᫥,  믮
 । ⠯ (祭   砫 ). , -
 㯯  ᫥  뢠 "ᮬ" ࠫ쭮 ,  ᫮
㯯 - "⮩",  ᨬ쭮 ᫮ 権  㯯 "ਭ" -
ࠫ쭮 .        ᪮쪮 ।-
⠢   ࠫ ,  ࠧ騥  ਭ,  ⠪  
⮩. 樮  ᤢ  㬬஢  ᥫ  
祭  㬬   :
       1   2   3   4   5   6   7   8
    1    1+2      3+4      5+6      7+8
    2   12+3    12+34     56+7      56+78
    3  1234+5  1234+56  1234+567  1234+5678
      ࠫ쭮   ࠢ ६,  ਭ - ६,  祬
㧪 ᫨⥫ () .
       ⬥ ந ᫥  '譨' ᥫ 
ࠢ  ᫥⥫ ⬮.

               5. ᪠ 㬬஢
    ਬ஬ ࠫ ⬮, ਥ஢   -
᫨⥫,  㦨 ⮤ ᫥ ᪠ 㬬 ( -
ᨢ  㤢)    ᯠ५  権  㬬஢.
  室  㬬஢  n ᥫ  ࠭ ஬
㬬: Si = Si-1 + Ai i = 2,..n, S1 = A1. 室   ⭮
᪫뢠  ஬ s, 祭  室  ᤢ  
   樨  0 㫥.   १-
 楤 ,   ᤢ -  2 樨.  ᫨ n = 2**k, 
१ k 権 砥  १.  i=8:

                                - 5 -


     A1    0     A1      0      A1       0         A1
     A2    A1    A12     0      A12      0         A12
     A3    A2    A23     A1     A123     0         A123
     A4 +  A3 =  A34  +  A12 =  A1234 +  0      =  A1234
     A5    A4    A45     A23    A2345    A1        A12345
     A6    A5    A56     A34    A3456    A12       A123456
     A7    A6    A67     A45    A4567    A123      A1234567
     A8    A7    A78     A56    A5678    A1234     A12345678

          ⮤     ᠭ   ᫥
(,  ࠫ쭮)  㬬 :  Si =  Ali,    Ali  =
A(l-1)i + A(l-1)(i-2**(l-1)), A0i = Ai  i = 1,2,...n.
    ᫥ ஢ l = 0,1,...,log2n ࠧ,  祬,  ᫨   Ali
 i 室  ࢠ 1<= i <= n   ਭ ࠢ .
      ।     ⬠ -
 㬬஢ ᨢ D(n):
     X = D
     DO L = 1,LOG2(N)
        X = X + SHIFTR(X,2**(L-1))
     ENDDO
      ୮ 㭪樨 SHIFTR(A,l)  ᨢ (), -
祭    ,   ண ᤢ  L 権 ࠢ,   L
 ⮢  ﬨ.  ࠪ᪠  ॠ  ⬠
  ᪫ 譨 樨 ᫮  㫥,  ,   ᫥
⮣,   ࠢ  ᫥⥫ ⬮,   -  ॡ
譨 樨.
     砭:
       ࠫ    ந ⠪   樠-
⨢ 権,  ਬ, 㬭,  , 㬭 -
.
          6. "ᮢ" ࠫ ⬮
       ஢ ࠫ ⬮ ᫥  -
,      窨 ७ 設 ᫥, ⮩-
稢 ࠫ ⬮ 㦥 ⮩稢 ᫥⥫.
       ᪠ ⬮  ࠫ 
 룮묨 ⮫쪮    ࠧ୮,   ⮬  浪
 ६ ࠡ ࠫ쭮 ᨨ  ॢ ᪠ -

                                - 6 -

.  ᫮ 䬥᪨ 権  ࠫ쭮 ⬥ (n), 
 ⭮  訬 ᫥⥫쭮 - S(n).  ,  ࠫ-
 , 騩  浪 n, "ᮣᮢ"  ᫥-
⥫ ⬮  ⮩  , ᫨ ⭮襭 P(n)/S(n) ⠥-
 ࠭祭  n -> @. ࠫ   ᮣᮢ, ᫨
P(n)/S(n) ->  @  n -> @.  (@-᪮筮).
     ४ᨢ 㤢 (⮤ ᪠ 㬬)   ᮣ-
,  ⠪  ᫮ 権  ࠫ쭮 ᨨ ࠢ n * log n - n
+ 1 ⨢ n-1 ᫥⥫ 権,   (n*log n-n)/n -> @   n
-> @. ,   ᫨⥫    ᯮ.
      ᫮ ஢  n ந  ६ T = s+yn, 
᪠ୠ   m.
     , ᪠ ᫥ n-1 㬬 ந  ६
s * log n + (y(n*logn -n+1),    ᫥⥫쭮  -  m(n-1).
     ᫨ s=1000,  y = 10, m = 200 ᥪ㭤, ᪠  -
䥪⨢ ୮  n </= 32   n > 2**21.  ६:
    n    t=P(n)     t=S(n)
    8     3170       1400
   32     6190       6200
  128   15*10**3   25*10**3
 1024   0.1*10**6  0.2*10**6
2**21   419*10**6  415*10**6

     7.᪠ ।  襭 ࠢ ४ᨨ 1 浪
      - 饭,   㬥襭 ࠧ ࣠ 
   祧.  ᪠ । -  ᫥-
   ᯠࠫ ᫥⥫ ⬮,  ᭮-
  ᫥⥫쭮, 横᪮ ਬ ࠫ -
, ᫮    ⠯ 㬥蠥 () .
    ४ᨥ 1 浪 뢠 ⥬ ࠢ :
         X1 = D1
         X2 = X1 * A2 + D2
         .................
         Xi = Xi-1 * Ai + Di
         .................
         Xn = Xn-1 * An + Dn
 饬 :  Xi = Xi-1 * Ai + Di, i = 2,3,...n, X1 =  D1


                                - 7 -

    ⥬ ⭠ 夨쭮 ⥬ ࠢ Ax=d,
              Ŀ               Ŀ
          1                     d1 
  A =   -a2 1            d =    .  
         .......                   
            -an 1               dn 
                                 
     ᫥⥫  ᫥   ᠭ ⠪:
      X(1) = A(1) + D(1)
      DO i = 1,n
        X(i) = X(i-1) * A(i) + D(i)
      ENDDO

    ᨢ ᨬ  権  横   ᪮ -
᫥   ࠫ쭮 ࠡ 㤮.  ८ࠧ㥬 
   ࠫ ⮤ 横᪮ ।樨.  ᬮਬ 
ᥤ ࠢ:
         Xi-1 = Xi-2 * Ai-1 + Di-1
         Xi = Xi-1 * Ai + Di
 ⠢ ࢮ  ஥, 砥:
Xi = (Xi-2 * Ai-1 + Di-1) *  Ai + Di = Xi-2 * A1i + D1i , 
A1i = Ai * Ai-1 ,
D1i = Ai * Di-1 + Di
     , ஢    ᥩ ⥬  ࠢ,  稬
⥬ ࠢ 浪 n/2.  ᫨  楤 l ࠧ (᫨ n
= 2**l),    १ 砥 祭: Xn = Dnl.  祭
    X 室 ஢ ,  ਬ,  
  ⬠ 㬬஢.
     祢,  ᫥ Aji  Dji    ஢  ࠫ쭮
⮤ ᪠ 㬬  ࠭  㬬. ਢ ࠢ-
  ஢ i  :
     Xi = Ali * Xi-2**l + Dli ,  l = 0,1,..,log2n , i = 1,2,..,n
     Ali = Al-1i * Al-1(i-2**l-1)
     Dli = Al-1i * Dl-1(i-2**l-1) + Dl-1i
     砫 : A0i = Ai, D0i = Di
     ᫨  i   Ali,  Dli    Xi      
1 <= i <= n ,     ࠢ  .  ,  l = log2n
 ࠢ: Xi = Ali * Xi-2**l + Dli  Xi-2**l = Xi-n 室

                                - 8 -

 ,  ,  ᫥⥫쭮,  襭  ⥬ ࠢ 㤥:
: Xi = Dli,
                ⬠:
     X = D
     DO L = 1,LOG2(N)
        X = A * SHIFTR(X,2**(L-1)) + X
        A = A * SHIFTR(A,2**(L-1))
     ENDDO

         8. ࠫ   ந⥫쭮 
      饬 砥, ᪮७ ࠫ쭮 ⬠   ࠫ-
   ।  ⭮襭 Sp = <६ 믮 -
⬠   > / <६ 믮 ⬠   N  -
>.  祢,    ᪮७  ⬠ ᫮  ஢
ࠧ୮: Ci = Ai + Bi, i = 1,..,N  "" ࠫ ࠢ
N. , ॠ , ஬ ᫥,   믮-
 ࠫ쭮, ᮤঠ   ᫥⥫ ᫥.  㣮
஭,    ࠪ⨪ ।⠢   ࠫ,  騩
,  ᪮७, ॠ쭮 砥  ॠ樨 ⬠ 
⭮ 㤮.   㡮 業 ᪮७  ⮬ ⥯
ࠫ ணࠬ  ᫠ ⨯஢ ᯮ 㫠,
⭠   .    뢠 樥 ᪮-
७ 믮 ணࠬ  ࠫ ⥬   ᨬ  
⥯ ᯠࠫ ணࠬ.
     : N - ᫮ ஢ ⥬,  P -  ᯠࠫ-
  ணࠬ,   S = 1-P  -  権 ணࠬ, 믮-
塞  ᮢ饭  ६.( S+P = 1 , S,P >= 0)
     ,   , 饥 ६ 믮 ணࠬ  -
୮ ᫨⥫ S+P,   ⨯:  S+P/N,   ᪮७ 
⮬  㭪 P:  Sp = (S+P)/(S+P/N) = 1/(S+P/N)
         ᫥, :
      P = 0   S = 1  - ᪮७ ᫥ , 
      P = 1   S = 0  - ᪮७ ᫥   N ࠧ
     ᫨ P = S = 0.5,    ᪮筮 ᫥ ஢ ᪮-
७     祬  2 ࠧ.
     , ࠪ⨪ ,  ᨬ N  P ᫮,  
拉 砥   襭 P ९ணࠬ஢ ,  -
, 㢥   ࠧ୮.

                                - 9 -

  ⠢ᮭ ।  ⠡㥬  ஢ -
 :  Sp = S + P*N
     ,  P = S = 0.5   Sp = 0.5N + 0.5
     砭:
     N -  ।⠢    ᫮ ஢ ⥬,  
:᫮   ய,  ᫮  ⥯  .
   
    .,    .  ࠫ  .  .:      ,
1986.-392 .
   ⥣ .    ࠫ   ⮤ 襭  -
 ⥬. .  1991.-367 .

                        ᫥   
             1. 筨 ᫨⥫ 譮⥩
     ࢮ砫쭮 ᫨⥫ 設 ࠧࠡ뢠  ᯮ짮-
  ⮬⨧樨 ᪫⥫쭮 ᫨⥫ ࠡ (COMPUTER  -
᫨⥫), ..   믮  ⢨⥫묨 (楫묨) ᫠
 䬥᪨ ⢨:  +,-,*,/.   ᫥ﬨ -
  ࠡ⪠  ⥪⮢,  ᪮  ଠ樨,  ᫥
, ࠡ  䠬,    䬥᪨ ᫥ -
쭮 .     ।⭠     䬥᪨
᫥ﬨ 뫠  ⠥     ਬ .
      ⮬   ࠤ /..஢/:  ᮢ६   
ᥣ ᯥ   ᥣ ᯮᮡ  믮 䬥-
᪨ ᫥   ᯮᮡ ।⠢ ᥫ   .  
᪠  ४⭮  ।⠢  ⮫쪮   ⨢
ꥪ⮢,  .. ⠪ ꥪ⮢,    ।⠢ ᫥-
⥫쭮 筮 ,  ਬ,  ᨬ ண, ⠪
筮, 䠢.  㣮  - ࠡ   ᫠.  ,   設
 ।⠢  ⮫쪮  ࠭業  樮 -
,     樮 ᫠.   ⢨⥫ ᫠  
  ।⠢  ⮫쪮  ,      祭 訬
⢮. 筮.    ᯮ   ।⠢ -
ᥫ:  ଥ ᥫ  饩 ⮩   ଥ ᥫ  䨪஢
⮩.  ⨬ ⢠ ᥫ  ।  ᫥, -
뢠 - "᫥ﬨ  ".  ४  饬 砥,  -
⥫  窨 ७ "⮩ ⥬⨪",  ᫥ ᯥ-
稢  ⮡ࠦ  ।⠢  㦠饬 -

                                - 10 -

      ⬮.
      饬 砥,  筨 訡, 騥  襭 -
⥫   ,  ᫮ ࠧ :
    . 訡, 騥   ଠ樨  ।⭮ 
         - 筮 ᯮ㥬 ⥬᪮  ,
         - 譮 ᯮ㥬 ਡ ⮤,
         - ⮩稢 ᫨⥫ ⬮.
     B. 訡 ᫨⥫ 権
         - 訡  室 ,
         - 譮 믮 䬥᪨ 権.
         - 譮 㣫  ᫥,
     . 譮 ࠫ ᫥
         -  譮 ࠫ쭮 ⭮ 㤮,
         -  譮 ணࠬ ᯥ祭.

                2. 譮 室 
      室 ,  ࠦ騥, 筮 祭    䨧-
᪨ 稭,   ਡ ࠪ,  ᮤঠ 訡 -
. ᫮  x,  ஥  ਭ ਭ  ⨭ 祭
稭 X,  뢠  ਡ 祭, ᮫⭠ 稭
ࠧ    - "᮫⭠ 譮" (訡):  Dx = |X-x|.
  ⨭ 祭 x 筮 ⭮,   Dx  -
쭠 ᮫⭠ 譮,  ᫮,   襥 ᮫⭮ -
. "⭮⥫쭠 譮"  ।  稭: d
=Dx/X.  ਡ ᫠ pi = 3.14 ।쭠 ᮫⭠ -
 ࠢ 0.0016, ⭮⥫쭠 - 0.00051  0.05%. ᮫⭠ -
譮  ਡ  ᫠ । ᫮   
 , ⭮⥫쭠 - ⢮    ᫥. (-
騬 ࠬ    ᫠,  ஬  㫥,  㯮-
ॡ  ।  㣨   筮 ஡   
  .  ,   0.040 騬 ࠬ -
 40)

           3.  ।⠢ ᥫ  
      ।⠢ ᥫ   । ࠢ பᨬ-
樨 ⢨⥫ ᥫ ।⢮   設 ।-
⠢.  ।⠢ ᥫ  ⫨   -
 ।⠢ ᥫ.  ।⠢ ࠪਧ -

                                - 11 -

  訬  (M)  ᠬ  (m)  ᮫⭮ 稭  設
ᥫ.  ( ⢥ ,  ,  ᬠਢ 稭:  v  =
log(b) (M/m),  b - ᭮ 䬠, ࠢ  ⥬ ᫥-
.   । ᯮ짮 樮 ⥬ ᫥
 ।⠢ ᥫ.  ).  筮 ।⠢ 業 -
⭮ ࠧ 設 ᥫ:  D = |a2-a1|    ⭮⥫쭮:  d  =
|(a2-a1)/a1|,   a1,a2 - 祭  ᫥⥫ 設 -
ᥫ, ⠪,  a1=/=0  |a2|>|a1|.

             4. ᫠  饩 ⮩
     ⢮ ⢥ ᥫ,  ஥   ।⠢
   ଥ ᥫ  饩 ⮩, ਭ  㪢 F 
।    ⭮ ⥪ - "設 ᫠",
( ᠩ  .)  楫᫥묨 ࠬࠬ:  b, -
 t  ࢠ 祭 ⥫ [L,U].  ⢮ F ᮤন
᫮    f ᫠ : f = (+/-).d1d2...dt * b**e,   -
 ⥫,  ᫮ .d1d2...dt = (d1/b+ ....+dt/(b**t)) - ஡-
  - ᮩ,  祬:  0<=di<b,  L<=e<=U.  ᪠ 
ଠ ଠ F ।  ⥫  ᮮ⭮襭  d1
=/= 0 ;   ᫮  ࠭ 筮 ।⠢
 ᥫ,     筮 ।⠢ -
ᥫ. ᮡ F:
     -   㫥 f ୮: m<=|f|<=M,  m = b**(L-1),
                                         M = (b**U) * (1-b**(-t));
     - ⢮ F 筮  ᮤন 2*(b-1)*(b**(t-1))*(U-L+1)+1 -
ᥫ,      㣠  ᫮   ࠢ ஬-
⪨.
 ...........................................................
                뢮 業
     業 쭮 ᮫⭮ 祭 ᫠ ⢠ F.
min(f= .d1d2...dt * b**e) = min(f= (.d1d2...dt) * (b**e)) =
min(.d1d2...dt) * min(b**e) = .00...1 * b**L = 1 * b**(-t) * b**L =
b**(L-t)
     ଠ ᥫ ᫥ 몫 룫 ⠪:
.... = .10...0 * b**L = 1 * b**(-1) * b**L = b**(L-1)

      4.1.।⠢ ⥬  饩 窮  
    ਬ ⥬    饩  窮   ࠧ :

                                - 12 -

       Cray-1       - [2,48,-16384,8191],
              - [3,18,-121,121],
       IBM-360/370  - [16,6,-64,63] - 筠 筮
       IBM-360/370  - [16,14,-64,63] -  筮
    筮,   ॠ ࠡ  ᫠  饩 ⮩ 
 ଠ ᫥:  ⠭   (  筮).
ଠ ᥫ ன 㯯,筮,     㤢 ᫮
ࠧ冷,  ०,    ⢮  㣮, 襥 ᫮ ࠧ冷 
 ।⠢ 浪.  筮 ।⠢   -
⥫쭮 : d1d2..dt*b**t  .
     ଠ ⢨⥫ ᥫ  饩 ⮩  i486:  ⠭-
⭮ (୮ 筮 - Single Precision) 32 ⮢ ᫮  -
⮨    23 ⮢  ( )  8 ⮢ 浪,  
( 筮 - Double Precision):  64 ~ 52  11.   
  486  ࠡ뢠 ᫠ 襭 筮 - Extended Pre-
cision: 80 ~ 64  , 15  冷.
       楫 ᫠  ⢮ ⢥ ᥫ,  -
設  ᫠   饩  䨪஢ ⮩ ᬠਢ 
ᥪ騥 ⨯.  ᮢ⭮ ᯮ짮  ।⠢-
  筮  ⥭,  ⠪      ᢮ ଠ
।⠢  ࠧ  () ࠡ  .   ⮬,
ਬ, १ 樨 ࠭-樨: (7 .EQ. 7.0) 
易⥫쭮 '⨭' (.EQ.-   ⭮襭 "ࠢ").  筮,
ॠ  ணࠬ- । ८ࠧ .

         5. ᮡ 䬥⨪  饩 ⮩
      饬 砥, 䬥᪨ 樨  ⠬ ⭮-
 ⢠ ⢥ ᥫ F  ४.
      䬥᪨ 権 ᥫ  饩 ⮩ :
     -  ᮫⭮ 祭,  M (ᨬ쭮 ᫠) - -
設 ९;
     -  㫥 祭,  襥 m (쭮 ᫠)  -
᮫⭮ 稭 - 設 ;
     -  祭   [m:M]  ⥬     ਭ-
  F (ந  ᥫ  F,  ࠢ, 뢠-
 ।⢮ 2t  2t-1  );
     ⮬,  ⢥ ᥫ  饩  ⮩  ।  
"騥" 䬥᪨ 樨,   १ ,  ᫨ 

                                - 13 -

 室  ࠭ ⢠ F,  ਭ 訥   祭
 F.  筠 ᥬ⨪  設 権, ॠ  -
  ।  奬  䬥⨪-᪮ ன⢠ ,
 㭨䨪樨 । ⠭:  IEEE-754. 騥 ᫥ -
    䬥᪨    室 뢠  ࠡ 
.  .   ( .  ⥬᪮ ணࠬ஢.. -
,  1977- 183.),   ⭮,  ,   饩 䬥⨪
  樠⨢  ਡ⨢.

   5.1. ਬ 襭 ࠨ᪨   饩 䬥⨪
   ਬ   ࠧ來 筮 䬥⨪  . .
   )  x=9.900 y=1.000 z=-0.999  ⮣:
       1 (x+y)+z = 9.910
       2 x+(y+z) = 9.901
   )   x=1100. y=-5.000 z=5.001  ⮣:
       1 (x*y)+(x*z)  = 1.000
       2 x*(y+z)      = 1.100
   樨  +  * - 騥 設 樨.   'c-
'  뢠  '묨',     樠-
⨢  ਡ⨢  䬥⨪..
     ⥫ ਬ  ᮮ⭮襭 ࠧ  ।⠢ -
ᥫ  饩 ⮩ ਢ .  ᠩ (.  ᠩ,  . -
,  .  㫥,  設 ⮤ ⥬᪨ ᫥. . 
1980 - 277 .).
     ᯮ 筮  ᫮  0.1  ⢥ 稭 蠣  
㠫쭮 ⬥  뢠,    ⠪ 蠣 㤥
ࠢ   蠣  1.0.     ⠪,   ⢥ F  b=2,
 1/10   筮 ࠧ  ⥯ 1/2:
     1/10 = 0/2**1 + 0/2**2 + 0/2**3 + 1/2**4 + 1/2**5 + 1/2**6 + ...
⠪, 筮 ᫮  0.1 ࠢ 筮: 0.0001100011000..., 
쬥筮: 0.063146314...,  ⭠筮: 0.199999....
᫨ 䨪஢  ஡ t ࠧ冷 筮,    ᫮  
⠪ ஡    १ 筮 .


              6. 筮 饩 䬥⨪
     筮 饩  䬥⨪   ࠪਧ ।⢮
設 ᨫ.

                                - 14 -

     ᨬ쭮 ᫮  ⠪,  1.+  = 1.   ன 筮
।⠢ ᥫ    (設 ᨫ). 㡠 奬 -
᫥ ᨫ:
     EPS = 1.0
  1  EPS = 0.5 * EPS
     EPS1 = EPS + 1.0
     IF (EPS1 .GT. 1.0) GO TO 1   >
   .   ணࠬ, । ⢮ ࠧ冷, -
㥬   ।⠢    ᥫ    饩  ⮩.
(    뢠   ᫠ ࠭  ଠ
 1A2A3...An).

             7. 譮 㣫  ᫥
      믮  䬥᪨  権     
᫠  訬 ⢮  ,  祬   室  ᥫ.  
訬, 祬   ।⠢   . ਬ,  㬭-
,  ᫮    㤢. ⮬ 室 ஢-
 㣫 १ ᫥.
   ⥩訩 ᯮᮡ 㣫 ⮨  뢠   ࠧ-
.     c 祭 ⥫ १ (q-筠
஡):  X = 0.An A(n-1) A(n-2)....As A(s-1) A(s-2)....A1 .
  ,㣫 ᫮ : Xs= 0.An A(n-1)A(n-2)....As ,  訡
㣫 (᮫⭠):Dx=|Xs-X|<=q**(-[n-(s-1)]),   n-(s-1) ᫮
      Xs.  ᨬ쭮  ⭮⥫쭠 訡 
⮬ 㤥 ࠢ: dx = Dx/X <= (q**(-[n-(s-1)]))/(1/q) = q**(-(n-s)).
     㣨 饯ਭ ᯮᮡ  㣫 ⠥ "ᨬ筮"
㣫,  ஬:
 Xs = Xs + q**(-(n-s)), ᫨ |Xs-X| >= 0.5**q(-(n-s)) 
 Xs = Xs,               ᫨ |Xs-X| <  0.5**q(-(n-s))
 ⮬ ᯮᮡ 㣫 ᨬ쭮  祭 ⭮⥫-
 訡: dx <= 0.5*q**(-(n-s)+1).

         7.1. 譮 믮 䬥᪨ 権
     業 ᮫⭮  ⭮⥫쭮 譮 䬥-
 権.
     1. : X=X1+X2   X1>0 , X2>0
᮫⭠ 譮: Dx = Dx1 + Dx2 , ⭮⥫쭠: dx = dx1 + dx2
     2. ⠭: X=X1-X2   X1>X2>0

                                - 15 -

᮫⭠ 譮:Dx=Dx1 + Dx2, ⭮⥫쭠:dx=(X1*dx1 + X2*dx2)/X
     ᫨ X1 >> ( ) X2,  dx ( ࠢ)  dx1.
     ᫨ X1 ( ࠢ) X2,  dx 㤥 祭 .  ⠭
  稭 ᥫ 砥    .

     3. ந: X = X1+X2
譮: Dx = (X/X1)*Dx1 + (X/X2)*Dx2  dx = dx1 + dx2
     4. ⭮  稭: X = X1/X2
譮:Dx = (|X2|*Dx1 + |X1|*Dx2)/X2**2 , dx = dx1 + dx2
        ࠦ  । 訡 १ 
 4 䬥᪨ ⢨  㭪樨  稭 ᥫ,  -
  ,   ᮫ 訡   (ਬ,  譮⥩
室 ).    ।    訡 १ 㦭 
⨬ 訡 ⤥쭮  訡 㣫.
ਬ    訡    㬬஢  ⥫  ᥫ
(.. ஢).
      㫠   訡    㬬஢  ⥫  ᥫ
Ai(i=1,..,n)  :
   Ds = A1*da1 + A2*da2 +...+ An*dan +
        d1*(A1+A2) +..+ d(n-1)*(A1+..+An) + dn , 
dai -  ⭮⥫ 訡 ।⠢ ᥫ  ,   di - ⭮-
⥫ 訡 㣫 ᥫ   ᫥饩  樨  ᫮-
. :  dai = da  di = d , a Ks = A1+A2+..+An, ⮣:
Ds = da*Ks + d*[(n-1)*A1+(n-1)*A2 +...+ 2*A(n-1) + An]
    祢,  訩 ""  㬬 訡  ᫠, -
㥬 砫.  ⥫쭮, ᫨ 㬬㥬 ⥫ ᫠
㯮冷   ⠭,  ᨬ쭮  訡 㬬 㤥
쭮.  冷 㬬஢ ᥫ   ࠧ-
 १.  ᫨  ᫠ ⫨   㣠 -
⥫쭮,  筮 १   ﭨ ᯮᮡ 㬬-
.  㬬 15 ⥫ ᥫ,  ⮣ 訡 १-
: Ds = da*Ks + d*(14*A1+14*A2+13*A3+....+2*A14+A15).
  da*Ks    ᯮᮡ 㬬஢,    뢠.
 ᫠  : Ai = 0+ei,  i=1,...,15, ⮣:
Dss = 199*(A0+em)*d,   em = max(ei),  d - 訡 㣫  -
 䬥᪮ 樨 ᫮.
      ᫨ ஢  㬬஢  ᥫ  㯯 ( 㯯 
 ᫠   㯯   ᥫ),  訡  㬬 -

                                - 16 -

 :
     Ds1 = d*(3*A1+3*A2+2*A3+A4) <= 9*d*(A0+em)
     Ds2 = d*(3*A5+3*A6+2*A7+A8) <= 9*d*(A0+em)
     Ds3 = d*(3*A9+3*A10+2*A11+A12) <= 9*d*(A0+em)
     Ds4 = d*(3*A13+2*A14+A15) <= 5*d*(A0+em)
   業  訡 㣫 㤥 Ds <= 32*d*(A0+em),  
Dss.  ⠪ 㬬஢  㯯   訡 १.
     ਬ, ࠧ  㬬஢ ᨢ ⥫ -
ᥫ  ࠫ ,  ⥬ 稢 㬬  㬬, -
    १,  ⫨  ᫥⥫쭮 㬬஢ 
 .

          8. ⨬樮 ८ࠧ  ணࠬ
     ⨬樮 ८ࠧ  ணࠬ    ⨬쭮 -
   ᫨⥫  ஢ ⥬ ண-
ࠬ஢.  ८ࠧ,  ࠨ᪨ ,  
 冷 ᫥,  ।ᠭ 室 ⥪⮬ ணࠬ.
᫥⢨ ⠪ ८ࠧ 㦤 .   ࠪ-
 ८ࠧ ᫥騥.

            1. ஢  ॢ  ᫥
     ஢ ॢ ᫥ (tree-height reduction  or  balan-
cing) ࠦ   ᯮ짮 ୮   ய᪠
ࠡ   ⠪⮢.   ,   ᫥   㬬   ⢥    ᥫ:
A+B+C+D+E+F+G+H, 㤥 ணࠬ஢  ᫥⥫쭮 -
権: (((A+B)+(C+D))+((E+F)+(G+H)));  蠥  -㬮砭
᫥⥫쭮  ᫥    ⭮ 㬬  -
   १.

         2. ᪫祭  ࠦ
    ᪫祭  ࠦ (Common subexpession elimi-
nation) ⠪   冷 ᫥.
     ᫨  ᯮ  ࠦ 饥 ᫥,
  ᫥ ந  ࠧ,   १ ࠭ 
ॣ,   쭥襬 ᯮ  ॣ.  ᠬ ᪫-
 筮 ᫥.
     X = A + B + C + D     ---->       REG = B + C
     Y = B + E + C                     X   = A + D + REG

                                - 17 -

                                       Y   = E + REG
              3. 稢 横
     稢 横  (loop unrolling) - ᯨ뢠 横 -
⥫쭮 ஢ ᢠ:  ,  ࠧ-
 ⥫ 横   樥⮬ (䠪஬) ࠧ.
     ந 筮   ࠧ稢 横  ᫥-
⥫ ⮪ .   筮 ࠧ稢 ᯮ ⠪
뢠 䠪 ࠧ稢 (      ४⨢
).
     DO I=1,100                  DO I=1,100,4
       A(I) = B(I) + C(I)          A(I) = B(I) + C(I)

     ENDDO                         A(I+1) = B(I+1) + C(I+1)
                                   A(I+2) = B(I+2) + C(I+2)
                                   A(I+3) = B(I+3) + C(I+3)
                                 ENDDO
      ⮬  ८ࠧ ᭨ ⢮  樮-
 ६.   ⠪  ਢ  襭 ।-
ᠭ ࢮ砫쭮 浪 ᫥. ਬ:
     DO I=1,10        DO I=1,10,2
     S = S + A(I)       S = S + A(I)
     ENDDO             S1 = S1 + A(A+1)
                      ENDDO
                      S = S + S1
    , 㬬஢ ஢ ⤥쭮     -
⮢  ᫥饬 ᫮  㬬.

         9. ஢ ⨬樮 ८ࠧ
      ஢  ⨬樮  ८ࠧ     ,
筮, ।ᬠਢ 樨 (०),  "䫠" ,   -
짮  祭 ꥪ⭮ .   ।।⥫
㪠 ।ᬠਢ  ⨫ ᠭ ணࠬ, ⠪,  ࠭
90 楯 ࠭ ᪮ ७ ⠭⮬ 몠.

     10. ᮡ ᫥ ࠦ  ࠭ 90 (⠭)
         7.1.7. 믮 権
   " ᫥ ࠦ +,  , - ᨢ,   -
 - 樨 ᫮   浪"
         7.1.7.1. ᫥ ࠭

                                - 18 -

   "  易⥫쭮   ࠭ ࠦ  -
  ࠭, ᫨ 祭  ।  ⮣.  
ࠦ:  X .GT. Y .OR. L(Z)    㭪 L(Z), ᫨ X
 Y."
         7.1.7.2. ⭮ ᪮
   " ࠦ: A+(B+C)     ⥬᪨
⭮ ࠦ: (A+B)+C."
         7.1.7.3. 믮 ᫮ ஥ 権
   "...        ⥬᪨ ⭮
ࠦ  ᫮,  楫⭮ ᪮  蠥."
    ⠭ 몠 ࠭ 90 ਢ ⨬    ⨬
ୠ⨢  ८ࠧ ࠦ:
    楫 i,j;⢥   a,b,c; ந x,y,z
   ࠧ ८ࠧ:               :
     x+y   -> y+x                      i/2         -> 0.5 *i
     x*y   -> y*x                      x*i/j       -> x*(i/j)
    -x+y   -> y-x                      (x+y)+z     -> (x+y+z)
     x+z+y -> y+(x+z)                  i/j/a       -> i/(j*a)
     x*a/z -> x*(a/z)                  (x+y)+z     -> x+(y+z)
     a/b/c -> a/(b*c)                  (x*y)-(x*z) -> x*(y-z)
     a/5.0 -> 0.2*a                    x*(y-z)     -> x*y-x*z

        11. 譮 ᨭ஭ ᯠࠫ
     । ᫨⥫쭮 ࠡ ᫥⥫쭮 ணࠬ
 । ࠫ ᨭ஭ ᫨⥫ ⠪    -
, ਬ, १ 㬬஢ ⮢ ᨢ, 믮
   ᫥騬 㬬஢  㬬  ⫨ 
१ אַ 㬬஢.

                    
ᠩ .,  쪮 .,  . 設 ⮤ ⥬-
 ᫥.-.:,1980
 .,   .,  ᫥.-.:,1999.-548.
஢ ..,  ஢ ..,  襢᪨ .. 訡-誨
 ணࠬ஢  ࠭. .: 㪠. 1987.-144.
 . ⥬᪮ ணࠬ஢. ..: .1977

1

