除算 (デジタル)
デジタル設計において除算を行うアルゴリズムはいくつか存在する。それらのアルゴリズムは、低速な除算と高速な除算の2つに分類できる。低速な除算は反復する毎に最終的な商を1桁ずつ生成していくアルゴリズムである。回復型、不実行回復型、非回復型、SRT除算などがある。高速な除算は最初に商の近似値から出発して徐々に正確な値に近づけていくもので、低速な除算よりも反復回数が少なくて済む。ニュートン-ラプソン法とゴールドシュミット法がこれに分類される。
以下の解説では、除算を Q = N/D で表し、
Q = 商 (quotient)
N = 被除数（分子 = numerator）
D = 除数（分母 = denominator）
とする。
目次 [非表示]
1 余りのある整数除算（符号なし）
2 低速な除算技法
2.1 回復型除算
2.2 非回復型除算
2.3 SRT除算
3 高速な除算技法
3.1 ニュートン-ラプソン除算
3.2 ゴールドシュミット除算
3.3 二項定理
4 大きな整数の場合
5 定数による除算
6 脚注
7 外部リンク
余りのある整数除算（符号なし）[編集]
ここで示すアルゴリズムでは、N を D で割って、商 Q と余り R (remainder) を得る。いずれの値も符号なし整数として扱う。
if D == 0 then throw DivisionByZeroException end
Q := 0 商と余りをゼロで初期化
R := 0
for i = n-1...0 do " ここで n はビット数"
R := R << 1 R を1ビット左シフト
R(0) := N(i) Rの最下位ビットを被除数のiビット目と等しく設定する
if R >= D then
R = R - D
Q(i) := 1
end
end
これは、後述の回復型と基本的には同じである。
低速な除算技法[編集]
低速な除算技法は全て次の漸化式に基づいている。
P_{j+1} = R\times P_j - q_{n-(j+1)}\times D\,\!
ここで
Pj = 部分的剰余 (partial remainder)
R = 基数 (radix)
q n － (j + 1) = 商のビット位置 n-(j+1) の桁の値。ここでビット位置は最下位ビットを 0、最上位ビットを n － 1 で表す。
n = 商の桁（ビット）数
D = 除数
である。
回復型除算[編集]
回復型（または復元型）除算 (restoring division) を固定小数点数に対して行う場合を解説する。ここで以下を前提とする。
D < N
0 < N,D < 1.
商の各桁 q は数字の集合 {0,1} のいずれかである。
二進（基数2）の基本的アルゴリズムは次の通り。
P := N
D := D << n * P と D は N や Q の倍の幅が必要
for i = n-1..0 do * 例えば、32ビットなら 31..0
P := 2P - D * シフトした値から減算を試みる
if P >= 0 then
q(i) := 1 * 結果ビットは 1
else
q(i) := 0 * 結果ビットは 0
P := P + D * 新たな部分的剰余は（回復した）シフトした値
end
end
なお、q(i) は商のi番目のビットを意味する。このアルゴリズムでは減算の前にシフトした値 2P をセーブしておいて、回復（復元）させるステップが必要だが、これはレジスタ T を例えば T = P << 1 としておいて、減算 2P － D の結果が負だった場合にレジスタ T を P にコピーすればよい。
不実行回復型除算は回復型除算とよく似ているが、2*P[i] の値をセーブしておく点が異なり、TP[i] ≤ 0 の場合でも D を加算して戻してやる必要がない。
非回復型除算[編集]
非回復型（または非復元型）除算 (non-restoring division) は商の桁の数字として {0,1} ではなく {－1,1} を使用する。引きっ放し法ともいう。二進（基数2）の基本的アルゴリズムは次の通り。
P[0] := N
i := 0
while i < n do
if P[i] >= 0 then
q[n-(i+1)] := 1
P[i+1] := 2*P[i] - D
else
q[n-(i+1)] := -1
P[i+1] := 2*P[i] + D
end if
i := i + 1
end while
このアルゴリズムで得られる商は、各桁が －1 と +1 であり、通常の形式ではない。そこで通常の二進形式への変換が必要である。例えば、次のようになる。
次の結果を {0,1} の通常の二進形式に変換する : Q = 111\bar{1}1\bar{1}1\bar{1}
ステップ:
1. 負の項のマスクを作る: N = 00010101\,
2. Nの2の補数を作る: \bar{N} = 11101011
3. 正の項のマスクを作る: P = 11101010\,
4. P\, と \bar{N} の総和: Q = 11010101\,
SRT除算[編集]
SRT除算の名は、考案者のイニシャル (Sweeney, Robertson, Tocher) に因んだもので、多くのマイクロプロセッサの除算器の実装に使われている。SRT除算は非回復型除算に似ているが、被除数と除数に基づいてルックアップテーブルを使い、商の各桁を決定する。Intel Pentium プロセッサの浮動小数点除算バグは、このルックアップテーブルの間違いが原因だった。千以上のエントリがあるテーブルのうち理論上参照しないと信じられていた5個のエントリを省略したことが原因である[1]。基数を大きくすると一度の反復で複数ビットを求められるため、高速化可能である[2]。
高速な除算技法[編集]
ニュートン-ラプソン除算[編集]
ニュートン-ラプソン除算 (Newton-Raphson Division) は、ニュートン法を用いて D の逆数を求め、その値と N の乗算を行うことで商 Q を求める。
ニュートン-ラプソン除算のステップは次の通り。
除数 (D) の逆数の近似値を計算する: X_{0}
逆数のより正確な近似値を反復的に計算する: (X_{1},\ldots,X_{S})
被除数と除数の逆数の乗算を行うことで商を計算する: Q = NX_{S}
D の逆数をニュートン法で求めるには、X=1/D で値がゼロとなる関数 f(X) を求める必要がある。明らかにそのようになる関数としては f(X)=DX-1 があるが、これは D の逆数が既にわかっていないと使えない。さらに f(X) の高次導関数が存在しないため、反復によって逆数の精度を増すこともできない。実際に使用できる関数は f(X)=1/X-D で、この場合のニュートン-ラプソンの反復は次の式で表される。
X_{i+1} = X_i - {f(X_i)\over f'(X_i)} = X_i - {1/X_i - D\over -1/X_i^2} = X_i + X_i(1-DX_i) = X_i(2-DX_i)
この場合、X_i から乗算と減算だけで計算可能であり、積和演算2回でもよい。
誤差を \epsilon_i = D X_i - 1 \, と定義すると
X_i = {1 \over D} (1 + \epsilon_i) \,
\epsilon_{i+1} = - {\epsilon_i}^2 \,
となる。
除数 D が 0.5 ≤ D ≤ 1 となるようビットシフトを施す。同じビットシフトを被除数 N にも施せば、商は変化しない。すると、ニュートン-ラプソン法の初期値として次のような線形近似が使える。
X_0 = T_1 + T_2 D \approx \frac{1}{D} \,
区間 [0.5,1] においてこの近似の誤差の絶対値をなるべく小さくするには、次の式を使用する。
X_0 = {48 \over 17} - {32 \over 17} D \, [要出典]
この近似を用いると、初期値の誤差は次のようになる。
\vert \epsilon_0 \vert \leq {1 \over 17} \approx 0.059 \,
この技法の収束は正確に二次的なので、P \, 桁の二進数の値を計算する場合のステップ数は次のようになる。
S = \left \lceil \log_2 \frac{P + 1}{\log_2 17} \right \rceil \,
ゴールドシュミット除算[編集]
ゴールドシュミット除算の名は Robert Elliott Goldschmidt に因んだもので[3]、除数と被除数の両方に共通の係数 Fi をかけていき、除数 D が 1 に収束するようにする。すると 被除数 N は商 Q に収束する。つまり、以下の式で分母が1になるようにもっていく。
Q = \frac{N}{D} \frac{F_1}{F_1} \frac{F_2}{F_2} \frac{F_{\ldots}}{F_{\ldots}}
ゴールドシュミット除算のステップは次の通り。
乗数となる係数 Fi を推定により生成する。
除数と被除数に Fi をかける。
除数が十分 1 に近くなったら、被除数を返す。さもなくばステップ1に戻ってループする。
0 < D < 1 となるよう N/D を調整済みとし、それぞれの Fi は D から次のように求める。
F_{i+1} = 2 - D_i
除数と被除数にその係数をかけると次のようになる。
\frac{N_{i+1}}{D_{i+1}} = \frac{N_i}{D_i}\frac{F_{i+1}}{F_{i+1}}
k 回の反復で十分なら、Q=N_k となる。
ゴールドシュミット法はAMDの Athlon やその後のモデルで使用されている[4][5]。
二項定理[編集]
ゴールドシュミット法は、二項定理を使ってより単純化した係数を使うことができる。D\in(\tfrac{1}{2},1] となるよう N/D を2の冪でスケーリングすることを前提とする。ここで D = 1-x となるよう x を求め、F_{i} = 1+x^{2^i} とする。すると次のようになる。
\frac{N}{1-x}
= \frac{N\cdot(1+x)}{1-x^2}
= \frac{N\cdot(1+x)\cdot(1+x^2)}{1-x^4}
= \frac{N\cdot(1+x)\cdot(1+x^2)\cdot(1+x^4)}{1-x^8}
x\in[0,\tfrac{1}{2}) なので、n ステップ後には 1-x^{2^n} と 1 の相対誤差は 2^{-n} となり、2^n の二進数の精度では 1 と見なせるようになる。このアルゴリズムをIBM方式と呼ぶこともある[6]。
大きな整数の場合[編集]
ハードウェアの実装に使われている設計技法は、一般に数千桁から数百万桁の十進数値での除算（任意精度演算）には適していない。そのような除算は例えば、RSA暗号の合同式の計算などでよく見られる。大きな整数での効率的除算アルゴリズムは、まず問題をいくつかの乗算に変換し、それに漸近的に効率的な（つまり桁数が大きいほど効率がよい）乗算アルゴリズム（英語版）を適用する。例えば、Toom–Cook multiplication やショーンハーゲ・ストラッセン法（英語版）がある。乗算への変換としては、上述したニュートン法を使った例や[7]、それより若干高速な Barrett reduction アルゴリズムがある[8]。ニュートン法は同じ除数で複数の被除数に対して除算を行う場合に特に効率的で、除数の逆数を1度計算しておくと、毎回それを流用できる。
定数による除算[編集]
定数を除数とする除算は、その定数の逆数との乗算と等価である。そのため、除数 D がコンパイル時にわかっている場合（定数の場合）、その逆数 (1/D) をコンパイル時に計算すれば、N·(1/D) という乗算のコードを生成すればよいということになる。浮動小数点数の計算であれば、そのまま適用できる。
整数の場合は、一種の固定小数点数による計算に変形する手法がある。まず、算術的に考えてみる。例えば、除数が3の場合、2/3、4/3、256/3などのどれかを使って乗算し、しかる後に2や4や256で除算すればよい。2進法であれば除算はシフトするだけで良い（16ビット×16ビット＝32ビットのような、倍長で演算結果が全て得られる計算機なら、運が良ければ上位16ビットにそのまま解が得られるようにすることもできる）。
これを整数演算でおこなう場合は、256/3は当然正確な整数にはならないので、誤差があらわれる。しかし、シフト幅をより大きくし、値の範囲に注意すれば、常に不正確な部分はビットシフトによって捨てられる[9]ように変形できることがある。
具体例として32ビットの符号なし整数で、除数が3の場合 2863311531 / 2^{33} との乗算に変換できる。まず 2863311531 との乗算を行い、その後33ビット右シフトする。この値は正確には 1/2.999999999650754 である。
場合によっては、定数による除算を一連のシフト操作と加減算に変換できることもある[10]。特に興味深いのは10による除算で、シフトと加減算で正確な商（と必要なら余り）が得られる[11]。http://ja.wikipedia.org/wiki/%E9%99%A4%E7%AE%97_(%E3%83%87%E3%82%B8%E3%82%BF%E3%83%AB)
Announcement 179: Division by zero is clear as z/0=0 and it is fundamental in mathematics
\documentclass[12pt]{article}
\usepackage{latexsym,amsmath,amssymb,amsfonts,amstext,amsthm}
\numberwithin{equation}{section}
\begin{document}
\title{\bf Announcement 179: Division by zero is clear as z/0=0 and it is fundamental in mathematics\\
}
\author{{\it Institute of Reproducing Kernels}\\
Kawauchi-cho, 5-1648-16,\\
Kiryu 376-0041, Japan\\
E-mail: kbdmm360@yahoo.co.jp\\
}
\date{\today}
\maketitle
{\bf Abstract: } In this announcement, we shall introduce the zero division $z/0=0$. The result is a definite one and it is fundamental in mathematics.
\bigskip
\section{Introduction}
%\label{sect1}
By a natural extension of the fractions
\begin{equation}
\frac{b}{a}
\end{equation}
for any complex numbers $a$ and $b$, we, recently, found the surprising result, for any complex number $b$
\begin{equation}
\frac{b}{0}=0,
\end{equation}
incidentally in \cite{s} by the Tikhonov regularization for the Hadamard product inversions for matrices, and we discussed their properties and gave several physical interpretations on the general fractions in \cite{kmsy} for the case of real numbers. The result is a very special case for general fractional functions in \cite{cs}.
The division by zero has a long and mysterious story over the world (see, for example, google site with division by zero) with its physical viewpoints since the document of zero in India on AD 628, however,
Sin-Ei, Takahasi (\cite{taka}) (see also \cite{kmsy}) established a simple and decisive interpretation (1.2) by analyzing some full extensions of fractions and by showing the complete characterization for the property (1.2). His result will show that our mathematics says that the result (1.2) should be accepted as a natural one:
\bigskip
{\bf Proposition. }{\it Let F be a function from ${\bf C }\times {\bf C }$ to ${\bf C }$ such that
$$
F (b, a)F (c, d)= F (bc, ad)
$$
for all
$$
a, b, c, d \in {\bf C }
$$
and
$$
F (b, a) = \frac {b}{a }, \quad a, b \in {\bf C }, a \ne 0.
$$
Then, we obtain, for any $b \in {\bf C } $
$$
F (b, 0) = 0.
$$
}
\medskip
\section{What are the fractions $ b/a$?}
For many mathematicians, the division $b/a$ will be considered as the inverse of product;
that is, the fraction
\begin{equation}
\frac{b}{a}
\end{equation}
is defined as the solution of the equation
\begin{equation}
a\cdot x= b.
\end{equation}
The idea and the equation (2.2) show that the division by zero is impossible, with a strong conclusion. Meanwhile, the problem has been a long and old question:
As a typical example of the division by zero, we shall recall the fundamental law by Newton:
\begin{equation}
F = G \frac{m_1 m_2}{r^2}
\end{equation}
for two masses $m_1, m_2$ with a distance $r$ and for a constant $G$. Of course,
\begin{equation}
\lim_{r \to +0} F =\infty,
\end{equation}
however, in our fraction
\begin{equation}
F = G \frac{m_1 m_2}{0} = 0.
\end{equation}
\medskip
Now, we shall introduce an another approach. The division $b/a$ may be defined {\bf independently of the product}. Indeed, in Japan, the division $b/a$ ; $b$ {\bf raru} $a$ ({\bf jozan}) is defined as how many $a$ exists in $b$, this idea comes from subtraction $a$ repeatedly. (Meanwhile, product comes from addition).
In Japanese language for "division", there exists such a concept independently of product.
H. Michiwaki and his 6 years old girl said for the result $ 100/0=0$ that the result is clear, from the meaning of the fractions independently the concept of product and they said:
$100/0=0$ does not mean that $100= 0 \times 0$. Meanwhile, many mathematicians had a confusion for the result.
Her understanding is reasonable and may be acceptable:
$100/2=50 \quad$ will mean that we divide 100 by 2, then each will have 50.
$100/10=10 \quad$ will mean that we divide 100 by10, then each will have 10.
$100/0=0 \quad$ will mean that we do not divide 100, and then nobody will have at all and so 0.
Furthermore, she said then the rest is 100; that is, mathematically;
$$
100 = 0\cdot 0 + 100.
$$
Now, all the mathematicians may accept the division by zero $100/0=0$ with natural feelings as a trivial one?
\medskip
For simplicity, we shall consider the numbers on non-negative real numbers. We wish to define the division (or fraction) $b/a$ following the usual procedure for its calculation, however, we have to take care for the division by zero:
The first principle, for example, for $100/2 $ we shall consider it as follows:
$$
100-2-2-2-,...,-2.
$$
How may times can we subtract $2$? At this case, it is 50 times and so, the fraction is $50$.
The second case, for example, for $3/2$ we shall consider it as follows:
$$
3 - 2 = 1
$$
and the rest (remainder) is $1$, and for the rest $1$, we multiple $10$,
then we consider similarly as follows:
$$
10-2-2-2-2-2=0.
$$
Therefore $10/2=5$ and so we define as follows:
$$
\frac{3}{2} =1 + 0.5 = 1.5.
$$
By these procedures, for $a \ne 0$ we can define the fraction $b/a$, usually. Here we do not need the concept of product. Except the zero division, all the results for fractions are valid and accepted.
Now, we shall consider the zero division, for example, $100/0$. Since
$$
100 - 0 = 100,
$$
that is, by the subtraction $100 - 0$, 100 does not decrease, so we can not say we subtract any from $100$. Therefore, the subtract number should be understood as zero; that is,
$$
\frac{100}{0} = 0.
$$
We can understand this: the division by $0$ means that it does not divide $100$ and so, the result is $0$.
Similarly, we can see that
$$
\frac{0}{0} =0.
$$
As a conclusion, we should define the zero divison as, for any $b$
$$
\frac{b}{0} =0.
$$
See \cite{kmsy} for the details.
\medskip
\section{In complex analysis}
We thus should consider, for any complex number $b$, as (1.2);
that is, for the mapping
\begin{equation}
w = \frac{1}{z},
\end{equation}
the image of $z=0$ is $w=0$. This fact seems to be a curious one in connection with our well-established popular image for the point at infinity on the Riemann sphere.
However, we shall recall the elementary function
\begin{equation}
W(z) = \exp \frac{1}{z}
\end{equation}
$$
= 1 + \frac{1}{1! z} + \frac{1}{2! z^2} + \frac{1}{3! z^3} + \cdot \cdot \cdot .
$$
The function has an essential singularity around the origin. When we consider (1.2), meanwhile, surprisingly enough, we have:
\begin{equation}
W(0) = 1.
\end{equation}
{\bf The point at infinity is not a number} and so we will not be able to consider the function (3.2) at the zero point $z = 0$, meanwhile, we can consider the value $1$ as in (3.3) at the zero point $z = 0$. How do we consider these situations?
In the famous standard textbook on Complex Analysis, L. V. Ahlfors (\cite{ahlfors}) introduced the point at infinity as a number and the Riemann sphere model as well known, however, our interpretation will be suitable as a number. We will not be able to accept the point at infinity as a number.
As a typical result, we can derive the surprising result: {\it At an isolated singular point of an analytic function, it takes a definite value }{\bf with a natural meaning.} As the important applications for this result, the extension formula of functions with analytic parameters may be obtained and singular integrals may be interpretated with the division by zero, naturally (\cite{msty}).
\bigskip
\section{Conclusion}
The division by zero $b/0=0$ is possible and the result is naturally determined, uniquely.
The result does not contradict with the present mathematics - however, in complex analysis, we need only to change a little presentation for the pole; not essentially, because we did not consider the division by zero, essentially.
The common understanding that the division by zero is impossible should be changed with many text books and mathematical science books. The definition of the fractions may be introduced by {\it the method of Michiwaki} in the elementary school, even.
Should we teach the beautiful fact, widely?:
For the elementary graph of the fundamental function
$$
y = f(x) = \frac{1}{x},
$$
$$
f(0) = 0.
$$
The result is applicable widely and will give a new understanding for the universe ({\bf Announcement 166}).
\medskip
If the division by zero $b/0=0$ is not introduced, then it seems that mathematics is incomplete in a sense, and by the intoduction of the division by zero, mathematics will become complete in a sense and perfectly beautiful.
\bigskip
section{Remarks}
For the procedure of the developing of the division by zero and for some general ideas on the division by zero, we presented the following announcements in Japanese:
\medskip
{\bf Announcement 148} (2014.2.12): $100/0=0, 0/0=0$ -- by a natural extension of fractions -- A wish of the God
\medskip
{\bf Announcement 154} (2014.4.22): A new world: division by zero, a curious world, a new idea
\medskip
{\bf Announcement 157} (2014.5.8): We wish to know the idea of the God for the division by zero; why the infinity and zero point are coincident?
\medskip
{\bf Announcement 161} (2014.5.30): Learning from the division by zero, sprits of mathematics and of looking for the truth
\medskip
{\bf Announcement 163} (2014.6.17): The division by zero, an extremely pleasant mathematics - shall we look for the pleasant division by zero: a proposal for a fun club looking for the division by zero.
\medskip
{\bf Announcement 166} (2014.6.29): New general ideas for the universe from the viewpoint of the division by zero
\medskip
{\bf Announcement 171} (2014.7.30): The meanings of product and division -- The division by zero is trivial from the own sense of the division independently of the concept of product
\medskip
{\bf Announcement 176} (2014.8.9): Should be changed the education of the division by zero
\bigskip
\bibliographystyle{plain}
\begin{thebibliography}{10}
\bibitem{ahlfors}
L. V. Ahlfors, Complex Analysis, McGraw-Hill Book Company, 1966.
\bibitem{cs}
L. P. Castro and S.Saitoh, Fractional functions and their representations, Complex Anal. Oper. Theory {\bf7} (2013), no. 4, 1049-1063.
\bibitem{kmsy}
S. Koshiba, H. Michiwaki, S. Saitoh and M. Yamane,
An interpretation of the division by zero z/0=0 without the concept of product
(note).
\bibitem{kmsy}
M. Kuroda, H. Michiwaki, S. Saitoh, and M. Yamane,
New meanings of the division by zero and interpretations on $100/0=0$ and on $0/0=0$,
Int. J. Appl. Math. Vol. 27, No 2 (2014), pp. 191-198, DOI: 10.12732/ijam.v27i2.9.
\bibitem{msty}
H. Michiwaki, S. Saitoh, M. Takagi and M. Yamada,
A new concept for the point at infinity and the division by zero z/0=0
(note).
\bibitem{s}
S. Saitoh, Generalized inversions of Hadamard and tensor products for matrices, Advances in Linear Algebra \& Matrix Theory. Vol.4 No.2 (2014), 87-95.http://www.scirp.org/journal/ALAMT/
\bibitem{taka}
S.-E. Takahasi,
{On the identities $100/0=0$ and $ 0/0=0$}
(note).
\bibitem{ttk}
S.-E. Takahasi, M. Tsukada and Y. Kobayashi, Classification of continuous fractional binary operators on the real and complex fields. (submitted)
\end{thebibliography}
\end{document}
アインシュタインも解決できなかった「ゼロで割る」問題
0 件のコメント:
コメントを投稿