å精度浮åå°æ°ç¹åã§ããã¨ããã® double
ã§ãããç¾ä»£ã«ããã¦ã¯ãã¯ã double
ãããµã¤ããã«ãªããå精度ã¨å¼ã°ãã¦ãã float
ã¯å®è³ªçã«ãå精度ãã®ãããªæè¦ã«ãªã£ã¦ããæ°ããã¾ãã
ãªã«ããããè¨ç®ãããã¨ãã«ãè¨ç®çµæã¯ double
ã ã¨ãã¦ãè¨ç®éä¸ã¯ double
ãããé«ã精度ã§è¡ãå¿
è¦ãããå ´åã¯ãã°ãã°ããã¾ã*1ã
ããããå ´åã« 64-bit ã 113-bit ã®ä»®æ°é¨ãæã¤ long double
ã __float128
ãªã©ã®åãæ±ããç°å¢ãªãããã使ãã®ãæã§ãããããã§ãªãç°å¢ããã°ãã°ããã¾ãããå°æ¥ __float128
ãããµã¤ããã«ãªã£ãã¨ãã«ã__float256
ãªãã«ã¯ãªã«ãæã¤æããªã...ãã¨ãªã£ã¦ãã¾ãã¾ãã
å
é¨å®è£
ã¨ãã¦å¤åé·æ´æ°ã使ããããªä»»æç²¾åº¦ã®åãä½¿ãæ¹æ³ãããã¾ããããããæ¨æºã§ç¨æããã¦ããªãè¨èªããã°ãã°ããã¾ã*2ããé度é¢ãæ°ã«ãªã£ã¦ãã¾ãã
ã¨ããããä»åããã®æ°åã¯ããµã¤ããã®æµ®åå°æ°ç¹æ°ã ãã使ã£ã¦ãããé«ã精度ã§è¨ç®ããæ¹æ³ã«ã¤ãã¦è§¦ãããã¨æãã¾ãã
å°å
¥
䏿¦ãåå¨ç $\pi$ ã«ã¤ãã¦èãã¦ã¿ã¾ãããã
$$
\pi = {\small 3.141592653589793}{\footnotesize 238462643383279}{\scriptsize 502884197169399}{\tiny 375105820974944592307{\dots}}.
$$
ãããæ®éã« double
ã§è¡¨ããã¨ããã¨ä»¥ä¸ã®ããã«ãªãã¾ãã
$$
\begin{aligned}
\roundcirc{\pi} &= {\small 3.141592653589793}{\footnotesize 115997963468544}{\scriptsize 185161590576171}{\tiny 875} \\
&= 7074237752028440\times 2^{-51}.
\end{aligned}
$$
$\hat\pi_1 = \roundcirc{\pi}$ ã¨ãã¦ãä¸è¨ãæãç«ã¡ã¾ãã
$$
\pi - \hat\pi_1 = {\small 1.224646799147353}{\footnotesize 177226065932275}{\scriptsize 001058209749445}{\tiny 923078164062862{\dots}}\times 10^{-16}
$$
ãã£ã¦ã$\hat\pi_2 = \roundcirc{\pi - \hat\pi_1}$ ã¨ããã¨ä¸è¨ã®ããã«ãªãã¾ãã
$$
\begin{aligned}
\hat\pi_2 &= ({\small 1.224646799147353}{\footnotesize 207173764029458}{\scriptsize 396604625692124}{\tiny 677580063796256} \\
&\qquad\quad + {\tiny 12680683843791484832763671875}\times 10^{-60})\times 10^{-16} \\
&= 4967757600021511\times 2^{-105}.
\end{aligned}
$$
åæ§ã«ãã¦
$$
\begin{aligned}
\hat\pi_3 &= \roundcirc{\pi - (\hat\pi_1 + \hat\pi_2)} \\
&= -({\small 2.994769809718339}{\footnotesize 665887016354211}{\scriptsize 984016705500952}{\tiny 339037967798563} \\
& \qquad \quad + {\tiny 706161978508415962547495152434873233460166375152766704559326171875}\times 10^{-60}) \times 10^{-33} \\
&= 8753721960665020 \times 2^{-161}
\end{aligned}
$$
ã¨ããã¨ã
$$
\pi - (\hat\pi_1 + \hat\pi_2 + \hat\pi_3) \approx 1.112\times 10^{-49}
$$
ã¨ãªãã$\hat\pi_1$ ã¨æ¯ã¹ã¦ 3 åç¨åº¦ã®æ¡æ°ã§ä¸è´ãã¦ãããã¨ããããã¾ãï¼3 åç¨åº¦ã®æ¡æ°ã使ã£ã¦ããã®ã§ããã¯ããï¼ã
ãã ãããã¡ãã $\hat\pi_1 \oplus \hat\pi_2 \oplus \hat\pi_3$ ã®ããã«è¨ç®ãã¦ãã¾ã㨠$\hat\pi_1$ ã¨åç¨åº¦ã®ç²¾åº¦ã«è½ã¡ã¦ãã¾ããããå
é¨è¡¨ç¾ã¨ãã¦ã¯ $(\hat\pi_1, \hat\pi_2, \hat\pi_3)$ ã®ããã«å¥åã§æã£ã¦ãããã®ã¨ãã¾ãã
ãã® $(\hat\pi_1, \hat\pi_2)$ ã $(\hat\pi_1, \hat\pi_2, \hat\pi_3)$ ã®ãããªè¡¨ç¾ãããããã double-double, triple-double ã¨å¼ãã§ãã¾ãã
ä¸è¨ã®ä¾ã§ã¯ããä½ããã®ææ®µã§å¥éä¸ãã宿°ã 3 ã¤ã® double ã«åè§£ãã¦è¡¨ããã¨ãããã¨ã ãããã¾ãããããã¡ãããããè¨ç®ã«ä½¿ãæ¹æ³ãå¿
è¦ã«ãªã£ã¦ãã¾ãã
ããªãã¡ããã¨ãã° double 㨠double-double ã®åãç©ã triple-double ã¨ãã¦å¾ãï¼å
é¨çã«ã¯ double ã®æ¼ç®ã®ã¿ãç¨ããï¼æ¹æ³ãªã©ã«ã¤ãã¦ã話ãã¦ããã¾ãã
æ¬é¡
ä»åã¯ãdouble 㨠double ã®åã¨ç©ã double-double ã¨ãã¦è¡¨ãæ¹æ³ã«ã¤ãã¦è¿°ã¹ããã以å¤ã«ã¤ãã¦ã¯æ¬¡å以éã«ãããã¨æãã¾ã*3ã
ãããæããã¨æãããã¯ããããªãã®ã§ãããæµ®åå°æ°ç¹æ° $a$, $b$ ã«å¯¾ã㦠$(a\oplus b)-(a+b)$ ã $(a\otimes b)-(a\times b)$ ã¯ï¼underflow ãªã©ã絡ãè°è«ã¯å¥éããã¨ãã¦ãåºæ¬çã«ï¼åããã©ã¼ãããã®æµ®åå°æ°ç¹æ°ã¨ãã¦è¡¨ããã¨ãã§ãã¾ãã
ããªãã¡ãdouble å士ã®åã»ç©ã®èª¤å·®ã double ã§æ£ç¢ºã«è¡¨ããã¨ãããã¨ã§ãããã£ã¦ãdouble å士ã®åã»ç©ã誤差ãªã double-double ã¨ãã¦è¡¨ããã¨ãããã¨ã«ãªãã¾ãã
ãã¦ããå¤ã¨ãã¦ã¯è¡¨ãããã¨ããäºå®ã ãã§ã¯å®éã«è¨ç®ã§ãããã¨ã«ãªããªãã®ã§ãæç¶ãã«ã¤ãã¦èª¬æãã¦ããã¾ãããã¡ããã表ããã¨ããäºå®ã«ã¤ãã¦ãã¡ããã¨è¨¼æãã¾ãã
è¨å·ã«é¢ãã¦
ä»»æã®å®æ° $x \gt 0$ ã«å¯¾ãã¦ã$2^k\le x\lt 2^{k+1}$ ãªãæ´æ° $k$ ã䏿ã«åå¨ããã®ã§ããã® $k$ ãç¨ã㦠$\hfloor{x} = 2^k$ ã¨å®ç¾©ãã¾ãã
ã¾ãã便å®ä¸ $\hfloor0 = 0$ ã¨ãã¦ããã¾ãã
ä»»æã®å®æ° $x\ge 0$ ã¨æ´æ° $k$ ã«å¯¾ãã¦æããã« $\hfloor{x\cdot 2^k} = \hfloor x\cdot 2^k$ ãæãç«ã¡ã¾ãã
Property 1: ä»»æã®å®æ° $a$, $b$ ã«å¯¾ã㦠$\hfloor{|a|}\ge \hfloor{|b|}$ ãªãã° $\hfloor{|a+b|}\le 2\hfloor{|a|}$ ãæãç«ã¤ã
Proof
Case 1: $\hfloor{|a|} = \hfloor{|b|} = 0$
ãã®ã¨ãã$a = b = 0$ ã§ããã$\hfloor{|a+b|} = 2\hfloor{|a|} = 0$ ã§ããã
Case 2: $\hfloor{|a|} = \hfloor{|b|} \gt 0$
æ´æ° $k$ ã¨å®æ° $a', b' \in (-2\lldot -1]\sqcup[1\lldot 2)$ ã䏿ã«åå¨ãã¦
$$
\begin{aligned}
2^k &= \hfloor{|a|} = \hfloor{|b|}, \\
a &= a'\cdot 2^k, \\
b &= b'\cdot 2^k
\end{aligned}
$$
ãæãç«ã¤ãããã§ $|a'+b'|\lt 4$ ã§ããã$\hfloor{|a'+b'|}\le 2$ ã¨ãªãã
$$
\begin{aligned}
\hfloor{|a+b|}
&= \hfloor{|(a'+b')\cdot 2^k|} \\
&= \hfloor{|a'+b'|}\cdot 2^k \\
&\le 2\cdot 2^k \\
&= 2\hfloor{|a|}.
\end{aligned}
$$
Case 3: $\hfloor{|a|} \gt \hfloor{|b|}$
ãã®ã¨ãã$|a| \gt |b|$ ãæãç«ã¤ã
$$
\begin{aligned}
\hfloor{|a+b|}
&\le \hfloor{|a| + |b|} \\
&\le \hfloor{|a| + |a|} \\
&= \hfloor{2|a|} \\
&= 2\hfloor{|a|}. \quad\qed
\end{aligned}
$$
Property 2: ä»»æã®å®æ° $a, b\ge 0$ ã«å¯¾ãã¦ã$a\le b$ ãªãã° $\hfloor a\le \hfloor b$ ãæãç«ã¤ã
Proof
ãã®ã¨ãã$a\le b$ ãã $\hfloor a\lt 2\hfloor b$ ã§ãããããªãã¡ã$\hfloor{a}\le \hfloor b$ ãæãç«ã¤ã$\qed$
æ£è² ã®ã¼ãã«ã¤ãã¦ã0.0
ã $0_+$ã-0.0
ã $0_-$ ã¨è¡¨è¨ãã¾ãã以ä¸ã§ã¯åã« $0$ ã¨æ¸ããå ´å㯠$0_+$ ãæå³ãããã®ã¨ãã¾ãã
ç¹ã« $0_-$ ã«ã¤ãã¦èããªãã¦ããããªã¨æã£ã¦ãã主ãªçç±ã¯ä¸è¨ã®éãã§ãã
- $\roundcirc0 = 0_+$ ã§ãããã
- æçµçã«å®è£
ããã颿°ã«ããã¦ãå
¥åã $0_-$ ã ã£ãå ´åã¯å¥éå¦çããã°ãããã
- double-double, triple-double ã®è¨ç®éä¸ã§ $0_-$ ãåºã¦ããªãã®ãæå¾
ããããã
- è¨ç®éä¸ã§ $0_-$ ãåºã¦ããå ´åã§ãã$\pm\infty$ ã $0_{\pm}$ 以å¤ã¨ã®æ¼ç®ã§ã¯ç¬¦å·ã¯å½±é¿ããªããã
ãã¦ãdouble ã¨ãã¦èãã¦ããå¤ãã¡ãæ¹ãã¦å®å¼åãã¦ããã¾ãã
$-1022\le k\le 1023$ ã«å¯¾ãã¦ãä¸è¨ãå®ç¾©ãã¾ãããããã符å·ãã¨ã®æ£è¦åæ°ã®éåã§ãã
$$
\begin{aligned}
F_k^- &= \{-m\cdot 2^{k-52} \mid m\in [2^{52}\lldot 2^{53})\cap\Z\}, \\
F_k^+ &= \{+m\cdot 2^{k-52} \mid m\in [2^{52}\lldot 2^{53})\cap\Z\}.
\end{aligned}
$$
ã¾ãã鿣è¦åæ°ã®éåãä¸è¨ã§å®ç¾©ãã¾ã*4ã
$$
\begin{aligned}
F_{-1023}^- &= \{-m\cdot 2^{-1022-52} \mid m\in[1\lldot 2^{52})\cap\Z\}, \\
F_{-1023}^+ &= \{+m\cdot 2^{-1022-52} \mid m\in[1\lldot 2^{52})\cap\Z\}.
\end{aligned}
$$
ã¾ããèãããæ°å
¨ä½ãããªãéå $F$ ãä¸è¨ã§å®ç¾©ãã¾ãã
$$
F = \left(\bigsqcup_{k=-1023}^{1023} {(F_k^-\sqcup F_k^+)}\right) \sqcup \{-\infty, 0, +\infty\}.
$$
ãã¨ãã°ä¸è¨ãæãç«ã¡ã¾ãã
$$
\begin{aligned}
1 &\in F_0^+, \\
-2^{-1074} &\in F_{-1023}^-, \\
2^{1024} &\notin F, \\
1+2^{-53} &\notin F, \\
0.1 &\notin F.
\end{aligned}
$$
ããã«ãä¸è¨ã®æ§è³ªãæãç«ã¡ã¾ãã
- $(F\smallsetminus \{-\infty, +\infty\})\subset \Q$
- ä»»æã®å®æ° $x$ ã«å¯¾ã㦠$x\in F \iff -x \in F$
- ä»»æã®å®æ° $x$ ã«å¯¾ã㦠$x\in F \implies x\equiv 0\pmod{2^{-1074}}$
- ä»»æã® $x, y \in (F_{-1023}^-\sqcup F_{-1023}^+)$ ã«å¯¾ã㦠$x\pm y\in F$
Lemma 3: ä»»æã® $k\in[-1022\lldot 1023]\cap\Z$ ããã³ $m\in[1\lldot 2^{53})\cap\N$ ã«å¯¾ãã¦ã$$\{-m\cdot 2^{k-52}, +m\cdot 2^{k-52}\}\subset F$$ãæãç«ã¤ã
Proof
ä»»æã® $k\in[-1022\lldot 1023]$ ããã³ $m\in[1\lldot 2^{53})\cap\N$ ã«å¯¾ã㦠$m\cdot 2^{k-52} \in F$ ã示ãã°ååãä¸è¨ã§ $P(k)$ ãå®ç¾©ãã$k$ ã«é¢ããæ°å¦çå¸°ç´æ³ã§ç¤ºãã
$$ P(k) \iff \Forall{m\in[1\lldot 2^{53})\cap\N}{m\cdot 2^{k-52}\in F}. $$
To-be-proved 1: $P(-1022)$
ä»»æã® $m\in[1\lldot 2^{-53})\cap\N$ ã«å¯¾ãã$m\cdot 2^{k-52} \in F_{-1023}^+\sqcup F_{-1022}^+$ ãæãç«ã¤ã
To-be-proved 2: $k\lt 1023 \wedge P(k) \implies P(k+1)$
$m\in[2^{52}\lldot 2^{53})\cap\N$ ã®ã¨ã $m\cdot 2^{(k+1)-52}\in F_{k+1}^+$ ãæãç«ã¤ã
$m\in[1\lldot 2^{52})\cap\N$ ã®ã¨ãã$2m\in[2\lldot 2^{53})\cap\N$ ã㤠$m\cdot 2^{(k+1)-52} = (2m)\cdot 2^{k-52}$ ãæãç«ã¡ã$P(k)$ ããå¾ãã$\qed$
tiesToEven ã«ãã丸ãã«ã¤ãã¦ãå®ç¾©ãã¾ãããã$\circ\colon \R\to F$ ãæ¬¡ã®ããã«å®ç¾©ãã¾ãã
ãã ããé¾å¤ã¨ã㦠$\Theta_{\infty} = (2-2^{-53})\cdot 2^{1023}$ ããã³ $\Theta_0 = 2^{-53}\cdot 2^{-1022}$ ã¨ãã¦ããã¾ãã
$$
\roundcirc{x} = \begin{cases}
+\infty, & \text{if}\: x \ge \Theta_{\infty}; \\
\roundcirc{x\cdot\hfloor{x}^{-1}\cdot 2^{52}}\cdot\hfloor{x}\cdot 2^{-52}, & \text{if}\: x\in[2^{53}\lldot\Theta_{\infty}); \\
\floor{x}, & \text{if}\: x\in[2^{52}\lldot 2^{53}) \wedge (x\bmod 1)\lt \tfrac12; \\
\floor{\frac{2x+1}4}\cdot 2, & \text{if}\: x\in[2^{52}\lldot 2^{53}) \wedge (x\bmod 1) = \tfrac12; \\
\ceil{x}, & \text{if}\: x\in[2^{52}\lldot 2^{53}) \wedge (x\bmod 1)\gt \tfrac12; \\
\roundcirc{x\cdot\hfloor{x}^{-1}\cdot 2^{52}}\cdot\hfloor{x}\cdot 2^{-52}, & \text{if}\: x\in[2^{-1022}\lldot 2^{52}); \\
\roundcirc{x+2^{-1022}}-2^{-1022}, & \text{if}\: x\in(\Theta_0\lldot 2^{-1022}); \\
0, &\text{if}\: x\in[0\lldot \Theta_0]; \\
\roundcirc{-x}, & \text{if}\: x\lt 0.
\end{cases}
$$
ç¹ã«ã$x\in F\iff \roundcirc x=x$ ã§ããã¾ã $x\bmod 1=\tfrac12$ ã®ã¨ã $\floor{\frac{2x+1}4}\cdot 2 \in \{\floor x, \ceil x\}$ ã§ãã
ã¾ãã$(x, y)\in \R\times F$ ã㤠$y\le x$ ãªãã° $y\le \roundcirc x$ï¼$\le$ ã $\ge$ ã§ç½®ãæããå½é¡ãåæ§ï¼ã§ãã
ä»»æã®å®æ° $x$ ã«å¯¾ãã¦ã$|\roundcirc x|\lt \infty$ ãªãã°ä¸è¨ãæãç«ã¡ã¾ãã
$$
|\roundcirc x-x| \le \begin{cases}
\hfloor{|x|}\cdot 2^{-53}, & \text{if}\: |x|\ge 2^{-1022}; \\
2^{-1022-53}, & \text{if}\: |x|\lt 2^{-1022}.
\end{cases}
$$
ããã«ãä»»æã®å®æ° $x$ ã¨æ´æ° $k$ ã«å¯¾ã㦠$x\equiv 0\pmod{2^k}$ ãªãã° $\roundcirc x\equiv 0\pmod{2^k}$ ãæãç«ã¡ã¾ãã
é »åºãªã®ã§ãæ¹ãã¦è§¦ãã¦ããã¾ãã
Lemma 4 (Sterbenz): $x, y\in F\smallsetminus{\{-\infty, +\infty\}}$ ã«ã¤ãã¦ã$\frac x2\le y\le 2x$ ãªãã° $x\ominus y=x-y$ ãæãç«ã¤ã
Proof
$x=y$ ã®ã¨ãã¯æããï¼ç¹ã« $x=y=0$ ãå«ãï¼ãä¸è¬æ§ã失ãã $x\gt y\gt 0$ ã¨ãã*5ãã¾ãã$x-y\le \frac x2$ ã«æ³¨æããã
Case 1: $y\in F_{-1023}^+$
$x\le 2y$ ããã$x\in F_{-1023}^+\sqcup F_{-1022}^+$ ã§ããã
Case 1-1: $x\in F_{-1023}^+$
ããæ´æ° $m_x$, $m_y$ ($0\lt m_y\lt m_x\lt 2^{52}$) ã«å¯¾ã㦠$x = m_x\cdot 2^{-1074}$ ããã³ $y = m_y\cdot 2^{-1074}$ ãæãç«ã¤ã
$$ x - y = (m_x-m_y)\cdot 2^{-1074} $$
ã§ããã$m_x-m_y\in[1\lldot 2^{52})\cap\N$ ã§ããããã$x-y\in F_{-1023}^+$ ã§ããã
Case 1-2: $x\in F_{-1022}^+$
ããæ´æ° $2^{52}\le m_x\lt 2^{53}$, $1\le m_y\lt 2^{52}$ ã«å¯¾ã㦠$x = m_x\cdot 2^{-1074}$ ããã³ $y = m_y\cdot 2^{-1074}$ ãæãç«ã¤ã
$$ x - y = (m_x-m_y)\cdot 2^{-1074} $$
ã§ãããããã§ã$m_x-m_y\in[1\lldot 2^{53})\cap\N$ ã§ããããã$x-y\in F_{-1023}^+\sqcup F_{-1022}^+$ ã§ããã
Case 2: ããæ´æ° $-1022\le k\le 1023$ ã«å¯¾ã㦠$y\in F_k^+$
Case 1 åæ§ã« $x\in F_k^+\sqcup F_{k+1}^+$ ã§ããã
Case 2-1: $x\in F_k^+$
ããæ´æ° $2^{52}\le m_y\lt m_x\lt 2^{53}$ ã«å¯¾ã㦠$x = m_x\cdot 2^{k-52}$ ããã³ $y = m_y\cdot 2^{k-52}$ ãæãç«ã¤ã
$$ x - y = (m_x-m_y)\cdot 2^{k-52} $$
ã§ãããã㤠$m_x-m_y\in[1\lldot 2^{52})\cap\N$ ã§ãããããLemma 3 ãã $x-y\in F$ ãå¾ãã
Case 2-2: $x\in F_{k+1}^+$
ããæ´æ° $2^{52}\le m_x\lt 2^{53}$ ããã³ $2^{52}\le m_y\lt 2^{53}$ ã«å¯¾ã㦠$x = m_x\cdot 2^{k+1-52}$ ããã³ $y = m_y\cdot 2^{k-52}$ ãæãç«ã¤ã
$$
\begin{aligned}
x-y &= m_x\cdot 2^{k+1-52} - m_y\cdot 2^{k-52} \\
&= (2m_x-m_y)\cdot 2^{k-52}
\end{aligned}
$$
ã¨æ¸ããã$x-y\le\tfrac x2$ ããã$2m_x-m_y\le m_x\lt 2^{53}$ ãå¾ããCase 2-1 åæ§ã«ãã¦ã$x-y\in F$ ãå¾ãã$\qed$
Lemma 5: æ´æ° $m\in[1\lldot 2^{106})$ ããã³ $k\in[-1022\lldot 1023-53]$ ã«å¯¾ã㦠$x = m\cdot 2^{k-52}$ ã¨è¡¨ããã¨ãããã $(x_h, x_l)\in F^2$ ãåå¨ã㦠$x=x_h+x_l$ ãæãç«ã¤ã
Proof
$m_h = \floor{m/{2^{53}}}$ ããã³ $m_l = (m\bmod 2^{53})$ ã¨ãã㨠$m = m_h\cdot 2^{53} + m_l$ ãæãç«ã¤ã
$$
\begin{aligned}
x_h &= (m_h\cdot 2^{53}) \cdot 2^{k-52} \\
&= m_h\cdot 2^{(k+53)-52}, \\
x_l &= m_l\cdot 2^{k-52}
\end{aligned}
$$
ã¨ããã¨ã$(x_h, x_l)\in F^2$ ã㤠$x = x_h + x_l$ ãæãç«ã¤ã$\qed$
$x, y\in F\smallsetminus{\{-\infty, +\infty\}}$ ã«å¯¾ãã¦ã$(x\oplus y)-(x+y)$ ããªãã¡ $x\oplus y$ ã®èª¤å·®ã«ã¤ãã¦èãã¾ãã
Lemma 6: $x, y\in F$ ã $x\gt 0$ ã㤠$\hfloor x\ge \hfloor{|y|}$ ã㤠$x+y\lt \Theta_{\infty}$ ãæºããã¨ããããã®ã¨ãã$(x\oplus y)-x \in F$ ã㤠$(x\oplus y)-(x+y)\in F$ ãæãç«ã¤ã
Proof
Case 1: $\hfloor{|y|} \le \hfloor x\cdot 2^{-55}$
ãã®ã¨ã $|y|\lt \hfloor x\cdot 2^{-54}$ ã§ããã$x\oplus y=x$ ã§ããããã$(x\oplus y)-x = 0$ ã㤠$(x\oplus y)-(x+y)=-y$ ã§ããã
æããã« $0, -y\in F$ ã§ããã
Case 2: $\hfloor{|y|} = \hfloor x\cdot 2^{-54}$
ãã®ã¨ã $\hfloor x\cdot 2^{-54}\le |y|\lt \hfloor x\cdot 2^{-53}$ ã§ãããã¾ãã$x\in F$ ãã $\hfloor{x}\le 2^{1023}$ ã§ããããã$\hfloor{|y|}\le 2^{1023-54}$ ã§ãããã¾ãã$x\notin F_{-1023}^+$ ã§ããã
Case 2-1: $x = \hfloor x$ ã㤠$-\hfloor x\cdot 2^{-54}\lt y\lt -\hfloor x\cdot 2^{-53}$
ãã®ã¨ã $x\oplus y = x-\hfloor x\cdot 2^{-53}$ ã§ããããã
$$
\begin{aligned}
(x\oplus y)-x &= -\hfloor x\cdot 2^{-53} \\
&= -2\hfloor{|y|}, \\
(x\oplus y)-(x+y) &= -y-2\hfloor{|y|} \\
&= |y| - 2\hfloor{|y|}
\end{aligned}
$$
ã§ããã$\hfloor{|y|}\le 2^{969}$ ãã $2\hfloor{|y|}\in F$ ã§ããã$|y|-2\hfloor{|y|}\in F$ ã Sterbenz lemma ããå¾ãã
Case 2-2: $x = \hfloor x$ ã㤠$y = -\hfloor x\cdot 2^{-54}$
$x\oplus y = x$ ã§ãããããCase 1 åæ§ã«ãã¦å¾ãã
Case 2-3: $x = \hfloor x$ ã㤠$y\gt 0$
$x\oplus y = x$ ã§ãããããCase 1 åæ§ã«ãã¦å¾ãã
Case 2-4: $x \gt \hfloor x$
$x\oplus y = x$ ã§ãããããCase 1 åæ§ã«ãã¦å¾ãã
Case 3: $\hfloor{|y|} = \hfloor x\cdot 2^{-53}$
ãã®ã¨ã $\hfloor x\cdot 2^{-53}\le |y|\lt \hfloor x\cdot 2^{-52}$ ã§ããã
$x=\hfloor x$ ã®ã¨ãã$y\lt 0$ ãªãã° $x\oplus y\in\{x-\hfloor x\cdot 2^{-52}, x-\hfloor x\cdot 2^{-53}\}$ ã§ããã$y\gt 0$ ãªãã° $x\oplus y = x$ ã§ããã
$x\gt \hfloor x$ ã®ã¨ãã$y\lt 0$ ãªãã° $x\oplus y\in\{x-\hfloor x\cdot 2^{-52}, x\}$ ã§ããã$y\gt 0$ ãªãã° $x\oplus y\in\{x, x+\hfloor x\cdot 2^{-52}\}$ ã§ããã
Sterbenz lemma ã«æ°ãã¤ãã¤ã¤ãç·æ¬ãã¦ã$y\lt 0$ ãªãã°
$$
\begin{aligned}
(x\oplus y)-(x+y) &\in \{-y-\hfloor x\cdot 2^{-52}, -y-\hfloor x\cdot 2^{-53}, -y\} \\
&= \{-y-2\hfloor{|y|}, -y-\hfloor{|y|}, -y\} \\
&= \{|y|-2\hfloor{|y|}, |y|-\hfloor{|y|}, |y|\} \subset F
\end{aligned}
$$
ã§ããã$y\gt 0$ ãªãã°
$$
\begin{aligned}
(x\oplus y)-(x+y) &\in \{-y, -y+\hfloor x\cdot 2^{-52}\} \\
&= \{-y, -y+2\hfloor{|y|}\} \\
&= \{-y, -y+2\hfloor{y}\} \subset F
\end{aligned}
$$
ã§ããã
Case 4: $\hfloor x\cdot 2^{-52} \le \hfloor{|y|} \le \hfloor x$
$|y|\gt 0$ ã«æ³¨æããã
Case 4-1: $y\lt 0$
Case 4-1-1: $y\in F_{-1023}^-$ ã㤠$x\in F_{-1023}^+$
ããæ´æ° $m_x, m_y\in[1\lldot 2^{52})$ ã«å¯¾ã㦠$x = m_x\cdot 2^{-1022-52}$ ã㤠$y = -m_y\cdot 2^{-1022-52}$ ãæãç«ã¤ã
$$
x + y = (m_x-m_y)\cdot 2^{-1022-52}
$$
ã§ããã$|m_x-m_y| \in [0\lldot 2^{53})\cap\N$ ãã $x+y = x\oplus y$ ãå¾ãã
ãã£ã¦ã$(x\oplus y)-x = y$ ã㤠$(x\oplus y)-(x+y) = 0$ ãæãç«ã¤ã
Case 4-1-2: $y\in F_{-1023}^-$ ãã¤ãããæ´æ° $k\ge -1022$ ã«å¯¾ã㦠$x\in F_k^+$
$$
\begin{aligned}
\hfloor x
&\le \hfloor{|y|}\cdot 2^{52} \\
&\lt 2^{52}\cdot 2^{-1022-52}\cdot 2^{52} \\
&= 2^{-1022+52}
\end{aligned}
$$
ã§ããããã$x\lt 2^{-1022+52}$ ã¨ãªããã¾ãã$x+y\equiv 0\pmod{2^{-1022-52}}$ ãæãç«ã¤ã
$x+y\lt 2^{-1022}$ ã®ã¨ã $x+y\in F_{-1023}^+$ ãã $x\oplus y=x+y$ ãå¾ãããã以é㯠$x+y\ge 2^{-1022}$ ã¨ããã
ãã®ã¨ãã
$$
\begin{aligned}
|(x\oplus y)-(x+y)|
&\le (x+y)\cdot 2^{-53} \\
&\lt x\cdot 2^{-53} \\
&\le 2^{-1022+52}\cdot 2^{-53} \\
&= 2^{-1022-1}
\end{aligned}
$$
ãã $(x\oplus y)-(x+y)\in F_{-1023}^+$ ãæãç«ã¤ã
ã¾ãã$y\in F_{-1023}^-$ ãã $(x\oplus y)-x = ( (x\oplus y)-(x+y) ) + y \in F$ ãå¾ãã
Case 4-1-3: ããæ´æ° $k\ge -1022$ ã«å¯¾ã㦠$y\in F_k^-$
ãã®ã¨ããããæ´æ° $k'\ge k$ ã«å¯¾ã㦠$x\in F_{k'}^+$ ã§ãããCase 4-1-2 åæ§ $x+y\ge 2^{-1022}$ ã®å ´åã«ã¤ãã¦èããã
ã¾ãã$\frac x2\le |y|\le 2x$ ã®ã¨ã㯠Sterbenz lemma ãã $x\oplus y=x+y$ ãå¾ãããã$-y \lt \frac x2$ ã¨ããã
ãã®ã¨ã $\tfrac x2\lt x+y$ ã§ããããã£ã¦ $\tfrac x2\le x\oplus y$ ã§ãããããSterbenz lemma ãã $(x\oplus y)-x\in F$ ã§ããã
ãã¦ã
$$
\begin{aligned}
\hfloor x &\le \hfloor{|y|}\cdot 2^{52} \\
&= 2^{52}\cdot 2^{k-52}\cdot 2^{52} \\
&= 2^{k+52}
\end{aligned}
$$
ãã $x\lt 2^{k+53}$ ã§ããã
$x+y\equiv 0 \pmod{2^{k-52}}$ ãããããæ´æ° $0\le m\lt 2^{105}$ ãåå¨ã㦠$x+y = m\cdot 2^{k-52}$ ãæãç«ã¤ã
$x\oplus y\equiv 0\pmod{2^{k-52}}$ ã㤠$|(x\oplus y)-(x+y)| \le (x+y)\cdot 2^{-53}$ ã§ãããããããæ´æ° $0\le m'\lt 2^{52}$ ãåå¨ã㦠$(x\oplus y)-(x+y) = m'\cdot 2^{k-52}$ ãæãç«ã¤ããã$(x\oplus y)-(x+y)\in F$ ãå¾ãã
Case 4-2: $y\gt 0$
Case 4-2-1: $y\in F_{-1023}^+$ ã㤠$x\in F_{-1023}^+$
Case 4-1-1 åæ§ã«ãã¦å¾ãã
Case 4-2-2: ããæ´æ° $k\ge -1022$ ã«å¯¾ã㦠$x\in F_k^+$
ãã®ã¨ãã$x+y\ge 2^{-1022}$ ãæãç«ã¤ã
$|(x\oplus y)-(x+y)|\le (x+y)\cdot 2^{-53}$ ãã Sterbenz lemma ãå¾ãã$(x\oplus y)-(x+y)\in F$ ã¨ãªãã
$x+y\le 2x$ ã®ã¨ã $x\oplus y\le 2x$ ã§ãããããSterbenz lemma ãã $(x\oplus y)-x\in F$ ãå¾ãã
以éã¯ããã§ãªãå ´åãèãããããªãã¡ $y\gt x$ ã¨ããã$\hfloor x=\hfloor y$ ã㤠$\hfloor{x+y} = 2\hfloor x$ ãæãç«ã¤ã
ãã£ã¦ããã $m_x, m_y\in [2^{52}\lldot 2^{53})\cap\N$ ã«å¯¾ã㦠$x = m_x\cdot 2^{k-52}$ ã㤠$y = m_y\cdot 2^{k-52}$ ãæãç«ã¤ã
$$ x\oplus y \in \{(m_x+m_y-1)\cdot 2^{k-52}, (m_x+m_y)\cdot 2^{k-52}, (m_x+m_y+1)\cdot 2^{k-52}\} $$
ã§ããã
$$ (x\oplus y)-x \in \{(m_y-1)\cdot 2^{k-52}, m_y\cdot 2^{k-52}, (m_y+1)\cdot 2^{k-52}\} \subset F_k^+ $$
ãæãç«ã¤ã$\qed$
ãã¦ãå®éã«ãã£ã¦ããã¾ãã$a+b$ ã $a\times b$ ãªã©ã«å¯¾ãã¦ãäºã¤ã®æµ®åå°æ°ç¹æ° $h$, $l$ ã§ãã£ã¦ï¼èª¤å·®ãªãï¼$h+l$ ã¨è¡¨ãããã®ãæ±ãã¾ãã
ä»å¾ã®å¿ç¨ãè¦æ®ãã㨠$a\oplus b$ ã $a\otimes b$ ã鿣è¦åæ°ã«ãªãå ´åã¯é¤å¤ãã¦ãããæ°ããã¾ããã鿣è¦åæ°ã¡ããã仲éå¤ãã«ãã¦å¿é¿æãå¼·ããã®ãå«ãªã®ã§ãã§ããéãã±ã¢ãã¦ããã¾ãã
å
æãåºæ¬çãªæä½ã§ãããLemma 6 ç¸å½ã®åæããªãã¨è¨¼æã¯é¢åã§ãã
- å
¥å: $(a, b)\in F\times F$
- åºå: $(s_h, s_l)\in F^2$
- äºåæ¡ä»¶:
- $|a+b| \lt \Theta_{\infty}$, and
- $\hfloor{|a|}\ge \hfloor{|b|}$
- äºå¾æ¡ä»¶:
- $s_h = a\oplus b$, and
- $s_h + s_l = a + b$
- æç¶ã:
- $s_h \gets a\oplus b$ ã§åæåããã
- $z \gets s_h\ominus a$ ã§åæåããã
- $s_l \gets b\ominus z$ ã§åæåããã
- $(s_h, s_l)$ ãåºåããã
Claim 7: ä¸è¨ã®æç¶ãã®å®è¡å¾ãäºå¾æ¡ä»¶ãæãç«ã¤ã
Proof
$s_h = a\oplus b$ ã¯æãããªã®ã§ã$s_h+s_l = a+b$ ã示ãã
Case 1: $a\lt 0$
$a\gt 0$ ã§æãç«ã¤ãªãã° $a\lt 0$ ã§ãæãç«ã¤ãã¨ã示ãã
$$
\begin{aligned}
s_h^{\pm} &= (\pm a)\oplus (\pm b), \\
z^{\pm} &= s_h^{\pm}\ominus (\pm a), \\
s_l^{\pm} &= (\pm b)\ominus z^{\pm}
\end{aligned}
$$
ã¨ããï¼è¤å·åé ï¼ããã®ã¨ãã
$$
\begin{aligned}
s_h^- &= (-a)\oplus(-b) \\
&= -(a\oplus b) \\
&= -s_h^+, \\
z^- &= s_h^- \ominus (-a) \\
&= -(s_h^+ \ominus a) \\
&= -z^+, \\
s_l^- &= (-b)\ominus z^- \\
&= -(b\ominus z^+) \\
&= -s_l^+
\end{aligned}
$$
ã§ããããã$s_h^- + s_l^- = -(s_h^+ + s_l^+)$ ãæãç«ã¤ã
ãã£ã¦ã$s_h^+ + s_l^+ = a+b$ ãªãã° $s_h^- + s_l^- = -(a + b) = (-a) + (-b)$ ãæãç«ã¤ã
Case 2: $a = 0$
$$
\begin{aligned}
s_h &= 0\oplus b = b, \\
z &= b\ominus 0 = b, \\
s_l &= b\ominus b = 0
\end{aligned}
$$
ããã$s_h + s_l = b = a + b$ ãæãç«ã¤ã
Case 3: $a\gt 0$
Lemma 6 ããã$z = s_h\ominus a = s_h - a$ ãå¾ããã¾ãã
$$
\begin{aligned}
s_l &= b\ominus z \\
&= b - (s_h - a) \\
&= (a+b)-s_h \\
&= (a+b)-(a\oplus b)
\end{aligned}
$$
ã§ããã$\qed$
$\hfloor{|a|}\ge \hfloor{|b|}$ ãäºåã«ä¿è¨¼ã§ããªãå ´å㯠$|a|\ge |b|$ ã§åå²ããã°ããã§ãã
ãããã $\hfloor{\bullet}$ ã®é¨åãå®è£
ãããããå¿
è¦ã¯ããã¾ããã
$a$, $b$ ã®å¤§å°ã«ãããªãäºç¨®ãªã©ãèæ¡ããã¦ãã¾ãããããã§ã¯å²æãã¾ãã
丸ã
次以éã§ä½¿ããµãã«ã¼ãã³ã§ãã$\textsc{Round}(a, k)$ ã¨ãã¦ä½¿ãã¾ãã
ã$a$ ã®ä»®æ°é¨ã $53-k$ bits ã«ä¸¸ããå¤ãã¨ãã®éã®èª¤å·®ã«åé¢ãã¾ãã
- å
¥å: $(a, k)\in F \times \N$
- åºå: $(a_h, a_l)\in F^2$
- äºåæ¡ä»¶:
- $|a| \le 2^{1023-k}$, and
- $k\in[1\lldot 52]$
- äºå¾æ¡ä»¶:
- $a_h + a_l = a$,
- $a_h \equiv 0 \pmod{\hfloor{|a|}\cdot 2^{-(52-k)}}$, and
- $|a_l| \le \hfloor{|a|}\cdot 2^{-(53-k)}$.
- æç¶ã:
- $c \gets 2^k+1$ ã§åæåããã
- $a_c \gets a\otimes c$ ã§åæåããã
- $a_h \gets (a\ominus a_c)\oplus a_c$ ã§åæåããã
- $a_l \gets a \ominus a_h$ ã§åæåããã
- $(a_h, a_l)$ ãåºåããã
Claim 8: ä¸è¨ã®æç¶ãã®å®è¡å¾ãäºå¾æ¡ä»¶ãæãç«ã¤ã
Proof
$a = 0$ ã®ã¨ãã¯æããã$a\gt 0$ ã§æãç«ã¦ã° $a\lt 0$ ã§æãç«ã¤ãã¨ãæãããªã®ã§ã以é $a\gt 0$ ã¨ããã
Case 1: $a\ge 2^{-1022}$
$a\cdot (2^k+1) \ge 2^{-1022}$ ã«æ³¨æãã$\hfloor{(2^k+1)\cdot a} = 2^{52}$ ã¨ããã
ããã§ãªãå ´å㯠$a$ ã $\hfloor{(2^k+1)\cdot a}^{-1}\cdot 2^{52}$ åãããã¨ã§å¸°çã§ããã
ç¹ã«ã$|a\cdot(2^k+1)| \le 2^{1023-1}\cdot (2^1+1)\lt \Theta_{\infty}$ ã«æ³¨æããã
ã¾ã $2^{51}+\tfrac12 \le 2^k\cdot a$ ã示ãã$2^{51}\le \tfrac12(2^k+1)\cdot a$ ã§ããããã$\tfrac12(2^k+1)\cdot a\le 2^k\cdot a-\tfrac12$ ã示ãã°ååã
$$
\begin{aligned}
&\phantom{{}\iff{}} \tfrac12(2^k+1)\cdot a\le 2^k\cdot a-\tfrac12 \\
% &\iff \tfrac12\cdot 2^k\cdot a + \tfrac12\cdot a \le 2^k\cdot a-\tfrac12 \\
&\iff \tfrac12\cdot a \le \tfrac12\cdot 2^k\cdot a-\tfrac12 \\
&\iff a\le 2^k\cdot a-1 \\
&\iff 1\le (2^k-1)\cdot a \\
&\iff 1\le \tfrac{2^k-1}{2^k+1}\cdot (2^k+1)\cdot a
\end{aligned}
$$
$k\ge 1$ ã®ã¨ã $\tfrac{2^k-1}{2^k+1}\ge \tfrac13$ ã§ããã$(2^k+1)\cdot a\ge 2^{52}$ ããå¾ãã
ãã¦ã
$$
\begin{aligned}
(2^k+1)\cdot a
&= 2^k\cdot a + a \\
&= \floor{2^k\cdot a + a} + ( (2^k\cdot a + a)\bmod 1)
\end{aligned}
$$
ã§ããã
$\hfloor{2^k\cdot a} \ge 2^{51}$ ã㤠$2^k\cdot a\in F$ ã§ããããã$( (2^k\cdot a)\bmod 1)\in\{0, \tfrac12\}$ ã§ããã
ã¾ãã$\hfloor a\ge 2^{51-k}$ ã§ããããã$a\equiv 0\pmod{2^{-k-1}}$ ãæãç«ã¤ãç¹ã«ã$a\equiv 0\pmod{2^{-53}}$ ã§ããã
Case 1-1: $( (2^k\cdot a)\bmod 1) = 0$
$$
\begin{aligned}
(2^k+1)\cdot a
&= 2^k\cdot a + \floor{a} + (a\bmod 1).
\end{aligned}
$$
$r = (a\bmod 1)$ ã¨ããã¨ãä¸è¨ãæãç«ã¤ã
- $r\le \tfrac12 \wedge (2^k+1)\otimes a = 2^k\cdot a + \floor{a}$, or
- $r\ge \tfrac12 \wedge (2^k+1)\otimes a = 2^k\cdot a + \floor{a} + 1$.
$r\le \tfrac12$ ã®ã¨ãã
$$
\begin{aligned}
a - ( (2^k+1)\otimes a)
&= (\floor{a} + r) - (2^k\cdot a + \floor{a}) \\
&= -(2^k\cdot a - r)
\end{aligned}
$$
ã§ãããã¾ãã$r\ge \tfrac12$ ã®ã¨ãã
$$
\begin{aligned}
a - ( (2^k+1)\otimes a)
&= (\floor{a} + r) - (2^k\cdot a + \floor{a} + 1) \\
&= -(2^k\cdot a - (r-1) )
\end{aligned}
$$
ã§ããã
Case 1-1-1: $2^k\cdot a\gt 2^{52}$
remark: $( (2^k\cdot a)\bmod 1) = 0$ ãã $2^k\cdot a-1\ge 2^{52}$ ãæãç«ã¤ã
$r\le \tfrac12$ ã®ã¨ãããã $r'\in\{0, 1\}$ ã«å¯¾ã㦠$a\ominus ( (2^k+1)\otimes a) = -(2^k\cdot a-r')$ ã㤠$|r-r'|\le \tfrac12$ ãæãç«ã¤ã
ãã£ã¦ã
$$
\begin{aligned}
&\phantom{{}={}} (a\ominus ( (2^k+1)\otimes a) ) + ( (2^k+1)\otimes a) \\
&= -(2^k\cdot a-r') + (2^k\cdot a + \floor a) \\
&= \floor a + r'
\end{aligned}
$$
ã¨ãªãã$\hfloor a=2^{52-k}$ ãã $a\le 2^{52}-\frac12$ ã§ããããã$|\floor a + r'|\le 2^{52}$ ã§ããã$\floor a+r'\in F$ ã§ããã
ãã£ã¦
$$ (a\ominus ( (2^k+1)\otimes a) ) \oplus ( (2^k+1)\otimes a) = \floor a+r' $$
ã¨ãªãã$\floor a+r'\equiv 0\pmod 1$ ã㤠$1 = \hfloor{a}\cdot 2^{-(52-k)}$ ã§ããã
ãã£ã¦ $a_h \equiv 0 \pmod{\hfloor a\cdot 2^{-(52-k)}}$ ã§ãããã¾ãã$a_l = a-(\floor a+r') = r-r'$ ã§ããããã$|a_l|\le \hfloor a\cdot2^{-(53-k)}$ ã§ããã
ã¾ãã$r\ge \tfrac12$ ã®ã¨ãããã $r'\in\{0, 1\}$ ã«å¯¾ã㦠$a\ominus ( (2^k+1)\otimes a) = -(2^k\cdot a-r')$ ã㤠$|(r-1)-r'|\le \tfrac12$ ãæãç«ã¡ã$r\le \tfrac12$ ã®å ´åã¨åæ§ã«ãã¦å¾ããç¹ã«ã
$$
\begin{aligned}
a_l
&= a - a_h \\
&= (\floor a+r) - (\floor a+r'+1) \\
&= (r-1)-r'
\end{aligned}
$$
ã§ããã
Case 1-1-2: $2^k\cdot a\le 2^{52}$
ãã $r'\in\{0, \tfrac12, 1\}$ ã«å¯¾ã㦠$a\ominus ( (2^k+1)\otimes a) = -(2^k\cdot a-r')$ ãæãç«ã¤ã
$r\le \tfrac12$ ã®ã¨ã $|r-r'|\le \tfrac14$ã$r\ge \tfrac12$ ã®ã¨ã $|(r-1)-r'|\le \tfrac14$ ãæãç«ã¤ã
ãã£ã¦ãCase 1-1-1 åæ§ã«ãã¦
$$ (a\ominus ( (2^k+1)\otimes a) ) \oplus ( (2^k+1)\otimes a) = \floor a+r' $$
ã¨ãªãã$\floor a+r'\equiv 0\pmod{\tfrac12}$ ã㤠$\tfrac12 = \hfloor{a}\cdot 2^{-(52-k)}$ ã§ããã
ããªãã¡ã$a_h\equiv 0\pmod{\hfloor a\cdot 2^{-(52-k)}}$ ã㤠$|a_l|\le \hfloor a\cdot 2^{-(53-k)}$ ãæãç«ã¤ã
Case 1-2: $( (2^k\cdot a)\bmod 1) = \tfrac12$
ãã®ã¨ãã$\hfloor{2^k\cdot a} = 2^{51}$ ã§ããã
$$
\begin{aligned}
(2^k+1)\cdot a
&= 2^k\cdot a - \tfrac12 + \floor{\tfrac12+a} + ( (\tfrac12+a)\bmod 1).
\end{aligned}
$$
$r = ( (\tfrac12+a)\bmod 1)$ ã¨ããã¨ãä¸è¨ãæãç«ã¤ã
- $r\le \tfrac12 \wedge (2^k+1)\otimes a = 2^k\cdot a - \tfrac12 + \floor{\tfrac12+a}$, or
- $r\ge \tfrac12 \wedge (2^k+1)\otimes a = 2^k\cdot a + \tfrac12 + \floor{\tfrac12+a}$.
note: $\tfrac12+a = \floor{\tfrac12+a} + ( (\tfrac12+a)\bmod 1)$ ã§ããã
$r\le \tfrac12$ ã®ã¨ãã
$$
\begin{aligned}
&\phantom{{}={}} a - ( (2^k+1)\otimes a) \\
&= (-\tfrac12 + \floor{\tfrac12+a} + r) - (2^k\cdot a - \tfrac12 + \floor{\tfrac12+a}) \\
&= -(2^k\cdot a-r)
\end{aligned}
$$
ã§ããã $r\ge \tfrac12$ ã®ã¨ãã
$$
\begin{aligned}
&\phantom{{}={}} a - ( (2^k+1)\otimes a) \\
&= (-\tfrac12 + \floor{\tfrac12+a} + r) - (2^k\cdot a + \tfrac12 + \floor{\tfrac12+a}) \\
&= -(2^k\cdot a-(r-1) )
\end{aligned}
$$
ã§ããã$\hfloor a=2^{51-k}$ ããã$a\le 2^{51}-\tfrac14$ ã§ãããã¨ã«æ³¨æã㦠Case 1-1-2 ã¨åæ§ã«ãã¦å¾ãã
Case 2: $a\lt 2^{-1022}$
Case 2-1: $a\times (2^k+1)\le 2^{-1022}$
ãã®ã¨ãã$a_c = a\times c$ ã㤠$(a_h, a_l) = (a, 0)$ ãæãç«ã¤ã
$|a_l| \le \hfloor a\cdot 2^{-(53-k)}$ ã¯æããã§ããããã$a \equiv 0 \pmod{\hfloor a\cdot 2^{k-53}}$ ã示ãã
$\hfloor a=2^{i-1022-52}$ ã¨ããã¨ãããæ´æ° $2^i\le m_a\lt 2^{i+1}$ ãåå¨ã㦠$a = m_a\cdot 2^{-1022-52}$ ãæãç«ã¡ã$m_a\cdot 2^{-1022-52} \equiv 0 \pmod{2^{-1022-52}}$ ã¨ãªãã
$a\times 2^k \lt 2^{-1022}$ ãã $(i-1022-52)+k\lt -1022$ ãæãç«ã¤ããã
$$
\begin{aligned}
&\phantom{{}\implies{}} m_a\cdot 2^{-1022-52} \equiv 0 \pmod{2^{-1022-52}} \\
&\implies m_a\cdot 2^{-1022-52} \equiv 0 \pmod{2^{i-1022-52+k-1-52}} \\
&\iff m_a\cdot 2^{-1022-52} \equiv 0 \pmod{\hfloor a\cdot 2^{k-53}}
\end{aligned}
$$
ãå¾ãã
Case 2-2: $a\times (2^k+1)\gt 2^{-1022}$
$\hfloor{(2^k+1)\cdot a}^{-1}\cdot 2^{52}$ åãããã¨ã§ãCase 1 ã«å¸°çã§ãããç¹ã«ã$r'\in\{0, 1\}$ ã«å¯¾ãã¦
$$
\hfloor{(2^k+1)\cdot a}\cdot 2^{-52}\cdot(\floor{\hfloor{(2^k+1)\cdot a}^{-1}\cdot 2^{52}\cdot a}+r')\in F
$$
ãªã©ãæãç«ã¤ãã¨ã«æ³¨æããã$\qed$
ç©
ãã¦ããã¡ããåºæ¬çãªæä½ã§ããFMA ã使ããåæã§ããã°æ¬¡ã®ããã«ã§ãã¾ãã
- å
¥å: $(a, b)\in F\times F$
- åºå: $(p_h, p_l)\in F^2$
- äºåæ¡ä»¶:
- $|a\times b|\lt \Theta_{\infty}$, and
- $a\times b \equiv 0 \pmod{2^{-1074}}$
- äºå¾æ¡ä»¶:
- $p_h = a\otimes b$, and
- $p_h + p_l = a \times b$
- æç¶ã:
- $p_h \gets a\otimes b$ ã§åæåããã
- $p_l \gets \roundcirc{a\times b + (-p_h)}$ ã§åæåããã
- $(p_h, p_l)$ ãåºåããã
Claim 9: ä¸è¨ã®æç¶ãã®å®è¡å¾ãäºå¾æ¡ä»¶ãæãç«ã¤ã
Proof
$p_h = a\otimes b$ ã¯æããã§ããã$\roundcirc{a\times b + (-p_h)} = a\times b - p_h$ ã証æããã°ååã
$ab = 0$ ã®å ´åã¯æããã$ab\gt 0$ ã®å ´åã§æãç«ã¦ã° $ab\lt 0$ ã®å ´åã§æãç«ã¤ã®ãæãããªã®ã§ã$a, b\gt 0$ ã¨ããã
Case 1: $ab\ge 2^{-1022}$
$\hfloor a=\hfloor b=2^{52}$ ã¨ãããããã§ãªãå ´åã¯ããããã $\hfloor a^{-1}\cdot 2^{52}$, $\hfloor b^{-1}\cdot 2^{52}$ åãããã¨ã§å¸°çã§ããã
宿° $|\varepsilon|\le 2^{-53}$ ãåå¨ã㦠$a\otimes b = ab+\hfloor{ab}\cdot\varepsilon$ ãæãç«ã¤ã
$2^{104}\le ab\lt 2^{106}$ ã§ããããã$\hfloor{ab}\le 2^{105}$ ã§ããã
$$
\begin{aligned}
|(a\otimes b) - (a\times b)|
&\le \hfloor{ab}\cdot\varepsilon \\
&\le 2^{105}\cdot 2^{-53} \\
&= 2^{52}
\end{aligned}
$$
ã§ãããProperty 3 ãã $(a\otimes b)-(a\times b)\in F$ ãå¾ãã
Case 2: $ab\lt 2^{-1022}$
ãã®ã¨ãã$a\otimes b = a\times b$ ãæãç«ã¡ã$(p_h, p_l) = (ab, 0)$ ã¨ãªãã$\qed$
äºåæ¡ä»¶ã® $a\times b\equiv 0\pmod{2^{-1074}}$ ããªãå ´åã®åä¾ã¯ããã¨ãã° $(a, b) = (1.5, 2^{-1074})$ ã§ãã
$$
\begin{aligned}
a\times b &= 1.5\cdot 2^{-1074}, \\
a\otimes b &= 2\cdot 2^{-1074}, \\
(a\otimes b)-(a\times b) &= 0.5\cdot 2^{-1074}\notin F
\end{aligned}
$$
ã§ããäºåæ¡ä»¶ã¨ã㦠$|a\times b|\gt \Theta_0$ ã課ããã¨ãã¦ããã¾ããããªãã§ããã
ç¹ã«ã$|a\times b|\ge 2^{-1022}$ ã§ãã ãã§ããã$(a, b) = ( (2-2^{-52})\cdot 2^{-971}, 2-2^{-52})$ ãªã©ãèããã¨ã
$$
\begin{aligned}
a\times b &= (2-2^{-51}+2^{-105})\cdot 2^{-970}, \\
a\otimes b &= (2-2^{-51})\cdot 2^{-970}
\end{aligned}
$$
ã§ããã$a\times b \ge 2^{-1022}$ ã§ãã $(a\otimes b) - (a\times b) = 2^{-1075}\notin F$ ã§ãã
FMA ã使ããªãå ´åã§ãå¯è½ã§ãããµãã«ã¼ãã³ Round ãç¨ãã¦æ¬¡ã®ããã«ã§ãã¾ãã
- å
¥å: $(a, b)\in F\times F$
- åºå: $(p_h, p_l)\in F^2$
- äºåæ¡ä»¶:
- $|a\times b| \lt \Theta_{\infty}$,
- $a\times b\equiv 0\pmod{2^{-1074}}$, and
- $\max{\{|a|, |b|}\}\le 2^{1023-27}$
- äºå¾æ¡ä»¶:
- $p_h = a\otimes b$, and
- $p_h + p_l = a \times b$
- æç¶ã:
- $(u_h, u_l) \gets \textsc{Round}(a, 27)$ ã§åæåããã
- $(v_h, v_l) \gets \textsc{Round}(b, 27)$ ã§åæåããã
- $p_h \gets a\otimes b$ ã§åæåããã
- $p_l \gets ( ( ( (u_h\otimes v_h) \ominus p_h)\oplus (u_h\otimes v_l) ) \oplus (u_l\otimes v_h) ) \oplus (u_l \otimes v_l)$ ã§åæåããã
- $(p_h, p_l)$ ãåºåããã
Claim 10: ä¸è¨ã®æç¶ãã®å®è¡å¾ãäºå¾æ¡ä»¶ãæãç«ã¤ã
Proof
Claim 9 åæ§ $a, b\gt 0$ ã¨ãã¦ã$p_h+p_l = a\times b$ ã示ãã
Case 1: $ab\ge 2^{-1022}$
Claim 9 åæ§ã$\hfloor a=\hfloor b=2^{52}$ ã¨ãããRound ã®äºåæ¡ä»¶ãæãç«ã£ã¦ãããã¨ã«æ³¨æããã
Round ã®äºå¾æ¡ä»¶ãã $u_h \equiv v_h \equiv 0 \pmod{2^{27}}$ ã㤠$|u_l|, |v_l|\le 2^{26}$ ãæãç«ã¤ã
$$
\begin{aligned}
a\times b
&= (u_h+u_l) \times (v_h+v_l) \\
&= \underbrace{u_h\times v_h}_{[2^{104}\lldot 2^{106})}
+ \underbrace{u_h\times v_l}_{[-2^{79}\lldot 2^{79}]}
+ \underbrace{u_l\times v_h}_{[-2^{79}\lldot 2^{79}]}
+ \underbrace{u_l\times v_l}_{[-2^{52}\lldot 2^{52}]}
\end{aligned}
$$
ã¨æ¸ããããã宿° $|\varepsilon|\le 2^{-53}$ ãåå¨ã㦠$|(a\otimes b)-(a\times b)| \le \hfloor{ab}\cdot \varepsilon$ ãæãç«ã¤ããã
$$
\begin{aligned}
a\otimes b
&= \underbrace{u_h\times v_h\vphantom{\hfloor x}}_{[2^{104}\lldot 2^{106})}
+ \underbrace{u_h\times v_l\vphantom{\hfloor x}}_{[-2^{79}\lldot 2^{79}]}
+ \underbrace{u_l\times v_h\vphantom{\hfloor x}}_{[-2^{79}\lldot 2^{79}]}
+ \underbrace{u_l\times v_l\vphantom{\hfloor x}}_{[-2^{52}\lldot 2^{52}]}
+ \underbrace{\hfloor{ab}\cdot \varepsilon}_{[-2^{52}\lldot 2^{52}]}
\end{aligned}
$$
ãæãç«ã¤ã
$m_u = u_h/2^{27}$ ããã³ $m_v = v_h/2^{27}$ ã¨ãã㨠$u_h\times v_h = (m_u\times m_v)\times 2^{54}$ ã¨ãªãã
$m_u, m_v\in[2^{25}\lldot 2^{26})\cap\N$ ã§ããããã$u_h \otimes v_h = u_h\times v_h$ ãæãç«ã¤ã
$u_h\times v_l = (m_u \times v_l)\times 2^{27}$ ã§ããã$|m_u\times v_l|\le 2^{51}$ ã§ããããã$u_h\otimes v_l = u_h\times v_l$ ãæãç«ã¤ã
åæ§ã«ãã¦ã$u_l\otimes v_h = u_l\times v_h$ ã§ããã
ã¾ãã$|u_l\times v_l| \le 2^{52}$ ã§ããããã$u_l\otimes v_l = u_l\times v_l$ ã§ããã
ãã£ã¦ãSterbenz lemma ãã
$$
\begin{aligned}
&\phantom{{}={}} (u_h\otimes v_h) \ominus p_h \\
&= (u_hv_h) - (u_hv_h + u_hv_l + u_lv_h + u_lv_l + \hfloor{ab}\cdot\varepsilon) \\
&= -(u_hv_l + u_lv_h + u_lv_l + \hfloor{ab}\cdot\varepsilon)
\end{aligned}
$$
ãæãç«ã¤ã
ããã§ã$a\otimes b = p_h \equiv 0 \pmod{2^{52}}$ ã㤠$u_hv_h\equiv 0\pmod{2^{54}}$ ã§ããããã$u_hv_h-p_h\equiv 0\pmod{2^{52}}$ ãæãç«ã¤ã
ã¾ãã$u_hv_l\equiv 0\pmod{2^{27}}$ ã§ããããã
$$
\begin{aligned}
(u_hv_h-p_h)+u_hv_l
&= -(u_lv_h + u_lv_l + \hfloor{ab}\cdot\varepsilon) \\
&\equiv 0 \pmod{2^{27}}
\end{aligned}
$$
ãã¤
$$
\begin{aligned}
|(u_hv_h-p_h)+u_hv_l|
&\le |u_lv_h| + |u_lv_l| + \hfloor{ab}\cdot|\varepsilon| \\
&\le 2^{79} + 2^{52} + 2^{52} \\
&\lt 2^{80}
\end{aligned}
$$
ã§ãããããæ´æ° $0\le m\lt 2^{53}$ ã«å¯¾ã㦠$|(u_hv_h-p_h)+u_hv_l| = m\cdot 2^{27}$ ã¨æ¸ããã
ãã£ã¦ã
$$
\begin{aligned}
( (u_h\otimes v_h)\ominus p_h)\oplus (u_h\otimes v_l)
&= u_hv_h - p_h + u_hv_l \\
&= -(u_lv_h + u_lv_l + \hfloor{ab}\cdot \varepsilon)
\end{aligned}
$$
ãå¾ãã
note: $|u_hv_l|$ ãä¸çã«è¿ãã¨ã¯éããªãã®ã§ãSterbenz lemma ã¯ä½¿ããªããã¨ã«æ³¨æããã
åæ§ã«ãã¦ã$-(u_lv_h + u_lv_l + \hfloor{ab}\cdot\varepsilon)\equiv 0\pmod{2^{27}}$ ã㤠$u_lv_h\equiv 0\pmod{2^{27}}$ ã§ããããã
$$
\begin{aligned}
( (u_hv_h-p_h)+u_hv_l)+u_lv_h
&= -(u_lv_l + \hfloor{ab}\cdot\varepsilon \\
&\equiv 0 \pmod{2^{27}}
\end{aligned}
$$
ãã¤
$$
\begin{aligned}
|( (u_hv_h-p_h)+u_hv_l)+u_lv_h|
&= |u_lv_l| + \hfloor{ab}\cdot|\varepsilon| \\
&\le 2^{52} + 2^{52} \\
&= 2^{53}
\end{aligned}
$$
ã§ããã$u_lv_l+\hfloor{ab}\cdot\varepsilon\in F$ ãå¾ãã
ããªãã¡
$$
\begin{aligned}
&\phantom{{}={}} ( ( (u_h\otimes v_h) \ominus p_h)\oplus (u_h\otimes v_l) )\oplus (u_l\otimes v_h) \\
&= -(u_lv_h + u_lv_l + \hfloor{ab}\cdot\varepsilon) \oplus u_lv_h \\
&= -(u_lv_l + \hfloor{ab}\cdot\varepsilon)
\end{aligned}
$$
ãå¾ãã
æå¾ã«ã$\hfloor{ab}\cdot\varepsilon\le 2^{52}$ ã㤠$\hfloor{ab}\cdot\varepsilon\equiv 1$ ãã $\hfloor{ab}\cdot\varepsilon\in F$ ã§ããããã
$$
\begin{aligned}
&\phantom{{}={}} ( ( ( (u_h\otimes v_h) \ominus p_h)\oplus (u_h\otimes v_l) )\oplus (u_l\otimes v_h) )\oplus (u_l\otimes v_l) \\
&= -(u_lv_l + \hfloor{ab}\cdot\varepsilon) \oplus u_lv_l \\
&= -\hfloor{ab}\cdot\varepsilon
\end{aligned}
$$
ã¨ãªãã
ãããã£ã¦ã$p_h = a\times b + \hfloor{ab}\cdot \varepsilon$ ã㤠$p_l = -\hfloor{ab}\cdot\varepsilon$ ã§ããããã$p_h+p_l = a\times b$ ãæãç«ã¤ã
Case 2: $ab\lt 2^{-1022}$
$a\otimes b = a\times b$ ã«æ³¨æããã
$r\ge 0$ ã«å¯¾ã㦠$(r_h, r_l) = \textsc{Round}(r, 27)$ ã¨ãã㨠$r_h\equiv 0\pmod{\hfloor r\cdot 2^{-25}}$ ã㤠$|r_l| \le \hfloor r\cdot 2^{-26}$ ãæãç«ã¤ã
ãã£ã¦ã
$$
\begin{aligned}
|r_l| &\le \hfloor r\cdot 2^{-26} \\
&\le 2^{-26}\cdot r, \\
r_h &= r - r_l \\
&\le r + r\cdot 2^{-26} \\
&= (1+2^{-26})\cdot r
\end{aligned}
$$
ãæãç«ã¤ããã£ã¦ã
$$
\begin{aligned}
u_hv_h &= ab - (u_hv_l + u_lv_h + u_lv_l) \\
&\le ab + |u_hv_l| + |u_lv_h| + |u_lv_l| \\
&\le ab + (1+2^{-26})\cdot a\cdot 2^{-26}\cdot b + 2^{-26}\cdot a\cdot (1+2^{-26})\cdot b + 2^{-52}\cdot ab \\
&= (1 + 2\cdot (1+2^{-26})\cdot 2^{-26} + 2^{-52})\cdot ab \\
&\lt 2ab \\
&\lt 2^{-1021}
\end{aligned}
$$
ã§ããã$u_hv_h\in F_{-1023}^+\sqcup F_{-1022}^+$ ãå¾ãã
åæ§ã«ãã¦ã
- $u_hv_l$,
- $u_lv_h$,
- $u_lv_l$,
- $u_hv_l + u_lv_h + u_lv_l$, and
- $u_lv_h + u_lv_l$
ã¯ãã¹ã¦ $F$ ã®å
ã§ãããã¨ã示ããããã$(p_h, p_l) = (ab, 0)$ ãå¾ãã$\qed$
$a\le 2^{1023-27}$ ãäºåã«ä¿è¨¼ã§ããªãå ´åã¯ã$a\gt 2^{1023-27}$ ãã©ããå¤å®ã㦠true ãªã $a\otimes 2^{-53}$ ãªã©ã渡ããçµæã $2^{53}$ åããã°ããã§ãï¼$b$ ã«ã¤ãã¦ãåæ§ï¼ã
åèæç®
ãã¨ãã
ä»åã¯ãdouble-double ã triple-double ãå®è£
ããéã®åºæ¬æä½ã®ã¿ãå°å
¥ãã¾ããã
鿣è¦åæ°ã«ã¤ãã¦ã触ãã¾ãããããããããããªãã®ã§é¿ããããã®ãã¨ããå°è±¡ã¯æãã¦ããå ´ååããé¢åã«ãªããã®ãã¨ããå°è±¡ãå¼·ã¾ã£ã¦ãã¾ã£ã¦ããããããã¾ããï¼ ããããªãã®ã§é¿ãããã¨ããã®ããã¯ãã·ãªæ°ã¯ãã¾ããã
次åãããªãæ°ãå¤ãã£ã¦ double-double ã§ã¯ãªããªã«ãã®è©±ãå§ããããããã¾ããï¼ ãã®ã¨ãã®æ°åã§ãã¼ããæ±ºã¾ãã®ã§ä»æ¹ãªãã§ããã
æ¯åº¦ã®ãã¨ã§ãããSterbenz lemma ã大活èºããã¾ããã$\roundcirc x=x$ ã示ããããªã£ããã¾ã Sterbenz lemma ã使ããªããçããã¾ã§ããæ°ããã¾ãã
ãã¡ãããmod ã®æ§è³ªãªã©ããã以å¤ã®ãã®ã使ãå±é¢ããã°ãã°ããã¾ãããSterbenz lemma ããæè»½ã©ããã®é »åºãã¿ã¼ã³ã¨ããæãã§ããã
ãªããç²ãã¦ãã¾ãã¾ããã証æã®æ¹éãå
¨ç¶æãã¤ããªãã£ãããå ´ååããããã°ãæ¹æ³ã§æ¸ãçµããã¨æã£ããã¾ã¨ãããããã¨ã«æ°ã¥ãããããªã«ãèããããªããªã£ãããã·ã³ãã«ã«åãæ¸ãã¦ããããã²ãã¨ããæãã§ãã
ãæ°æã¡ãã¼ããæµããããã«æ¸ããªããªã£ã¦ãã¾ãããä¸èª¿ï¼
ãã£ãã¨å
æ°ã«ãªã£ã¦ç¶ç·¨ãåå¼·ãããã§ãããcorrect rounding ã«èå³ã®ãããã©ãã®ãã©ã®ç¨åº¦ãããã¯ç¥ããªãã§ããããã³ã¡ããã¯ç¥ãããã£ã¦ããã®ã§ã
ããã
ãããã§ãã