PHPで分数が有限小数かどうか判定する

$ \displaystyle \frac{1}{4} $の結果は $ 0.25 $ と有限小数で表せるが、 $ \displaystyle \frac{1}{3} $の結果は $ 0.3333... $ という循環小数だ。そして、「PHPの演算誤差」で述べたように、PHPには演算誤差があるため、計算結果が循環小数になるかどうか分からない。

そこで今回は、分数の約分と素因数分解を駆使して、その分数が有限小数になるかどうか判定するプログラムを紹介する。「ユークリッドの互除法」「エラトステネスのふるい」といった定番アルゴリズムを使う。

（2021年2月17日）PHP8対応

プログラムを実行する

サンプル・プログラム

ダウンロード（PHP8対応）

剰余を使って判定する方法

$ \displaystyle \frac{234}{555} $を例に考える。

筆算の要領で剰余を求めていく。
\[ \displaystyle
\begin{eqnarray}
2340\ \ \% \ \ 555 &=& 120 \\
1200\ \ \% \ \ 555 &=& 90 \\
900\ \% \ 555 &=& 345 \\
3450\ \ \% \ \ 555 &=& 120 \\
...
\end{eqnarray}
\]
ふたたび $ 120 $ が出てくるので、小数第2位～4位が繰り返される循環小数であることが分かる。
剰余を配列の要素として、ふたたび要素が出てくるかどうかを調べることで、循環小数かどうかを調べることができる。要素の数は、最大でも（分母－１）個である。
途中で剰余が $ 0 $ になれば有限小数である。

素因数分解を使って判定する方法

剰余を使って判定する方法では、分母が大きくなければなるほど大きな配列を用意しなければならない。ここでは、最小限の大きさの配列で済む方法を考える。

まず、 $ \displaystyle \frac{234}{555} $を約分すると、 $ \displaystyle \frac{78}{185} $になる。ここで、剰余を使って判定してもいいのだが、さらに別の方法を使う。
有限小数の定義から、分母は $ \displaystyle 2^\alpha 5^\beta $（α，β≧0）である。
つまり、分母を素因数分解し、2または5以外の素因数が出てこなければ有限小数ということになる。
$ \displaystyle 185 = 5 \times 37 $ であるから、これは循環小数だ。

では $ \displaystyle \frac{1443}{7696} $ はどうか――。
分子も分母も大きな整数だが、約分すると $ \displaystyle \frac{3}{16} $ と小さくなる。$ \displaystyle 16 = 2 \times 2 \times 2\ \times 2 $ であるから、これは有限小数だ。

このように、分数を約分し、分母を素因数分解することで、有限小数かどうかの判定が可能となることが分かった。
PHPでプログラムを作るには、分数の約分を行うのに最大公約数を求める「ユークリッドの互除法」、素因数分解では素数を求める「エラトステネスのふるい」という定番アルゴリズムを用いることにする。

解説：ユークリッドの互除法

  95: /**
  96:  * 最大公約数を求める（ユークリッドの互除法）
  97:  * @param   int   $m, $n 整数
  98:  * @return  int 最大公約数
  99: */
100: function gcdEuclidean($m, $n) {
101:     if ($n == 0)    return $m;
102:     return gcdEuclidean($n, (int)$m % $n);
103: }

2つの整数の最大公約数を求める「ユークリッドの互除法」は再帰呼び出し関数となっている。
その原理については、「Wikipedia：最大公約数」を参照していただきたい。

解説：素因数分解

125: /**
126:  * 素因数分解
127:  * @param   array $primes  素因数を格納する配列
128:  * @param   int   $n       素因数分解する整数
129:  * @return  array $primes
130: */
131: function primeDecomposition($n, &$primes) {
132:     $max = floor(sqrt($n));
133:     EratosthenesSieve($max, $primes);
134:
135:     //2から平方根までの素因数を求める
136:     for ($i = 2; $i <= $max; $i++) {
137:         if (isset($primes[$i])) {
138:             do {
139:                 $b = $n % $i;
140:                 if ($b == 0) {
141:                     $primes[$i]++;
142:                     $n = floor($n / $i);
143:                 }
144:             } while ($b == 0);
145:         }
146:     }
147:     //残った素数
148:     if ($n > $max)  $primes[$n] = 1;
149:
150:     return $primes;
151: }

素因数分解はユーザー関数 primeDecomposition で行う。

因数が2つ以上ある場合、因数の値は元の整数の平方根より小さいことは自明である。そこで、元の整数の平方根を最大値 $max とし、2以上 $max 以下の素数の一覧を求め、これを配列に格納する。
素数一覧を求めるのに使うのが「エラトステネスのふるい」と呼ばれる定番アルゴリズムだ。その原理については、「Wikipedia：エラトステネスの篩」を参照していただきたい。
エラトステネスのふるいは、ユーザー関数 EratosthenesSieve に実装している。
素数一覧は配列 $primes に入って返される。要素数は、2以上 $max 以下の素数の数だけに絞られる。

素数一覧が求められたら、2以上 $max 以下の整数でループを回し、素因数分解を行う。
ユーザー関数 EratosthenesSieve で得られた素数表 $primes に対し、因数が1個なら値1を、2個なら値2を代入していく。

解説：有限小数かどうか

153: /**
154:  * 有限小数かどうか
155:  * @param   int $denominator 分母
156:  * @param   int $numerator   分子
157:  * @return  bool TRUE/FALSE
158: */
159: function isFiniteDecimal($denominator, $numerator) {
160:     $gcd = gcdEuclidean($denominator, $numerator);      //最大公約数
161:     $max = $denominator / $gcd;                     //約分した分母
162:
163:     //分母に2, 5以外の素因数が含まれているかどうか
164:     $primes = array();
165:     primeDecomposition($max, $primes);
166:     $res = TRUE;
167:     foreach ($primes as $key=>$val) {
168:         if ($key != 2 && $key != 5 && $val > 0) {
169:             $res = FALSE;
170:             break;
171:         }
172:     }
173:     return $res;
174: }