あまり算

100 桁の自然数を 7 で割った余りを求める、13 で割った値を求める、といった場合は、標準モジュールの Math::BigInt を使うことができます。今回は、敢えて Math::BigInt を使わずに、余りを求めてみました。なお、今回のプログラムでは、被除数の桁数は制限がありませんが、除数は剰余算を正常に計算できる範囲内である必要があります。

自然数を 3 (または 9) で割った場合の、余りの求め方をご存知のことと思います。各桁の数字を合計して 3 (または 9) で割って余りを求める方法ですが、この方法はどうして成り立つのでしょうか。求め方は知っているが、理由については知らないという場合は少し考えてみてください。

自然数をある除数で割った余りを求める場合、各桁毎に余りを求めて、その余りを合計して、さらに合計した値を除数で割る方法があります。この方法は、すべての除数が該当します。除数 3 (または 9) は少し特殊で、各桁の数字が１であると仮定した場合、すべての桁で余りが１になります。したがって、各桁の数字は、各桁毎に割った場合の各桁毎の余り (正確には余らすことのできる数) を示しています。そのため、各桁の数字を合計するという簡略化した方法が成立します。

3 と 9 以外の除数では、各桁毎の余りが違うため別の方法が必要になります。7 を例にすると、1 % 7 = 1, 10 % 7 = 3, 100 % 7 = 2, 1000 % 7 = 6, ... のように桁毎に余りが異なります。各桁が１であるとした場合の各桁別の余りを「余り係数」と呼ぶこととすると、この余り係数に各桁の数をかけると、その桁の余り (正確には余らすことのできる数) を算出することができます。後は、3 や 9 と同じ方法で計算することができます。

余り係数を求めるのに、その桁の数字を１にして下位の桁を 0 にする 1000 % 7 = 6 のようなやり方では、少し桁数が大きくなるとすぐに破綻してしまいます。もっとよい方法があります。前の桁の余り係数を 10 倍にして、除数で割ってやると該当の桁の余り係数を求めることができるのです。 1000 % 7 = 6 の代わりに、100 の余り係数を使って (2 * 10) % 7 = 6 のようにすることができます。この方法では、「(除数 - 1) * 10」を超えることがないので、どんなに大きな桁数でも余り係数を求めることができます。

次のプログラムは、今まで述べてきたものをそのままコードとして記述したものです。被除数はプログラムの冒頭で生成し、除数はプログラムの引数として渡すようにしています。プログラムでは被除数の生成桁数を検算しやすいように 8 にしていますが、これを 100 や 1000 のようにするとどんなに大きな桁数の余りも求めることができます。

use strict;
my $num = int(rand 9) + 1;
$num .= int rand 10 while length $num < 8;  # 被除数の桁数の指定
my $divisor = shift;
my ($rema, $coeff) = (0, 1);

foreach my $n (split //, reverse $num) {
  $coeff %= $divisor;
  last unless $coeff;
  $rema = ($rema + $coeff * $n) % $divisor if $n;
  $coeff *= 10;
}

print "$num % $divisor = $rema\n";

余り係数は上のプログラムのように各桁毎にその都度求めることもできますが、先に余り係数を求めておいてそれを各桁に適用することもできます。割り算の商と余り係数の関係は、次のようになります。(数字)... は、丸括弧内の数字が無限に繰り返されることを示します。

割り算の商がが割り切れる場合 (上の例では 1 / 4) は、余り係数もある桁で 0 になります。余り係数が 0 になった桁よりも上位の桁はすべて 0 になるので、その桁で計算を打ち切ることができます。商が割り切ることができない場合は、すべて循環小数になり、余り係数も同様に循環します。循環小数にも２種類があり、小数点以下１位からなるもの (1 / 7 や 1 / 13) と小数点以下２位以降からなるもの (1 / 6 や 1 / 14) があります。循環小数が２種類あるように、余り係数も２種類あります。

循環小数が小数点以下１位から始まる場合は、余り係数も１の位から循環します。除数 7 の場合、丸括弧内の余り係数が１の位から順番に適用されて丸括弧内の数字を使い終わったら、最初の余り係数に戻って再び順番に適用が繰り返されます。循環小数が小数点以下２位以降から始まる場合は、最初の丸括弧外の余り係数は１度だけ適用されます。除数 6 の場合、１の位に余り係数１が適用され、10 の位以降は余り係数 6 が適用されることになります。また除数 14 の場合、１の位に余り係数１が適用され、10 の位以降は丸括弧内の余り係数が順番に繰り返し適用されます。

次のプログラムは、呼び出すたびに次の桁の余り係数を返すクロージャと呼ばれるサブルーチンを利用しています。

use strict;
my $num = int(rand 9) + 1;
$num .= int rand 10 while length $num < 8;
my $rema = 0; my $divisor = shift;
my $cff_ref = coeff();

foreach my $n (split //, reverse $num) {
  my $coeff = $cff_ref->();
  last unless $coeff;
  $rema = ($rema + $coeff * $n) % $divisor if $n;
}

print "$num % $divisor = $rema\n";

sub coeff {
  my ($i, @coeff, $offset) = (1);

  while (1) {
    $i %= $divisor;
    if (($offset) = grep { $i == $coeff[$_] } 0 .. $#coeff) {
      my $idx = -1;
      return sub { $idx == $#coeff ? $idx = $offset : $idx++; $coeff[$idx] };
    } else {
      push @coeff, $i;
      $i *= 10;
    }
  }
}

クロージャとは、無名サブルーチンとその無名サブルーチンに捕捉されている my 変数のセットのことです。言葉では少しわかりにくいので、等差数列を返す簡単な例を挙げてみます。$step_2 と $step_3 には、それぞれサブルーチンの戻り値として無名サブルーチンのリファレンスが代入されます。

通常のサブルーチンでは、サブルーチンが戻り値を返して終了すると my 変数は消滅します。しかし、クロージャでは、無名サブルーチンの中に書かれている my 変数は消滅することはありません。この my 変数の $num と $step は step サブルーチンが呼び出されるたびに生成されるもので、 $step_2 と $step_3 では別々の変数を捕捉していることになります。したがって、&$step_2 で呼び出されると 2 増やした値を返し、&$step_3 で呼び出されると 3 増やした値を返します。このように、クロージャではクロージャを生成するサブルーチンを呼び出すたびに、別のサブルーチンリファレンスを返し、別の変数が捕捉されるという特徴があります。

余り算のクロージャを生成するサブルーチンは、１度のみの呼び出しなのでその点では簡単です。むろん、何度も呼び出すことができますし、$divisor に別の除数を設定するとまったく別のクロージャを生成できます。 coeff サブルーチンは等差数列を返す例とは違い、必要な余り係数を生成してそれを配列に格納するという、一仕事を終えてから無名サブルーチンのリファレンスを返します。

余り係数を求める部分のコードは前のプログラムと同じですが、違うのは求めた余り係数を配列に格納しているところです。余り係数を配列に格納する前に配列をチェックして、同じ余り係数が配列にある場合は、その位置を $offset にセットして余り係数を求めるのを打ち切ります。余り係数を求めるのが終わったら、無名サブルーチンのリファレンスを返して coeff サブルーチンは終了します。無名サブルーチンが捕捉している my 変数は、サブルーチン内に書かれている $idx, $offset, @coeff の３つです。

いくつか例を見てみることにします。まず、除数が 7 の場合です。coeff サブルーチンでは、配列 @coeff に (1, 3, 2, 6, 4, 5) の余り係数が格納されます。除数 7 ではすべての余り係数が循環するので、$offset には 0 がセットされます。また除数 14 では @coeff に (1, 10, 2, 6, 4, 12, 8) が格納され、最初の余り係数は１の位にのみ適用されるため $offset には１がセットされます。無名サブルーチンにに使われているもう１つの変数 $idx には、最初に -1 をセットしておきます。これで、クロージャを生成することができたので、あとはこれを使うだけです。

上のコードが、クロージャを呼び出している部分です。$cff_ref->() でクロージャを呼び出すと、無名サブルーチン内のコードが実行されます。無名サブルーチン内では、$idx の現在の値が配列の末尾を指しているか否かをチェックし、末尾を指している場合は $idx に $offset をセットして配列の循環部の最初の要素の添字に戻し、末尾を指していない場合は単に $idx をインクリメントします。そして、最後に $idx が指す配列の要素 (その桁位置の余り係数) を返しています。

完全循環小数

２つ目の問題として、前の節の「あまり算」にも関連する「完全循環小数」を取り上げます。 (完全循環小数というものは一般的ではありませんが) 完全循環小数とは、1/N の分数を小数に直した場合に、循環部が N - 1 の桁数になるものです。1/N が割り切れない場合は循環小数になりますが、循環部は N 以上にはなりません。そういう意味で、完全循環小数とは、最長の循環部を持つ循環小数のことです。

上の例で、行の先頭に * が付いているのが完全循環小数です。一番小さな完全循環小数は、除数が 7 の場合です。20 以下では、17 と 19 も完全循環小数です。右側に記してあるそれぞれの桁での余りが、１から N - 1 まですべて揃うのが完全循環小数の特徴です。

次のプログラムは、分数を小数化した結果を表示します。コマンドラインに除数となる２つの引数 ($num1 < $num2) を指定すると、その間の完全循環小数以外も含まれた除数のすべてが小数化されて表示されます。

use strict;
my ($num1, $num2) = @ARGV;
$num2 = $num1 unless $num2;

for (my $divisor = $num1; $divisor <= $num2; $divisor++) {
  my ($divident, $ans) = (10, '0.');
  my ($pos, %residue) = (0);

  while (1) {
    my $quotient = int($divident / $divisor);
    $ans .= $quotient;
    $divident = $divident % $divisor;
    if ($divident == 0) { print " 1/$divisor = $ans\n"; last; }
    if (exists $residue{"$divident:$quotient"}) {
      $ans =~ s/(\.\d{$residue{"$divident:$quotient"}})(\d+)./$1($2)/;
      print +(length($2) == $divisor - 1 ? '*' : ' '), "1/$divisor = $ans\n";
      last;
    }
    $residue{"$divident:$quotient"} = $pos; $pos++; $divident *= 10;
  }
}

プログラムは短く複雑でなく、見ていただけると分かりますので簡単に説明します。プログラムの while ループでは、小数点以下第１位から始めて、各桁毎の余りと割った値を %residue ハッシュに記録していきます。ハッシュのキーは余りと割った値をつないだもの ("$divident:$quotient")、ハッシュの値には小数点以下の位置を記録しておきます。ここで注意を要するのは、余りと割った値の両方を記録しておく必要があることです。1/6, 1/12 や 1/14 の例のように、余りが同じでも循環部に含まれない場合があるからです。

各桁の余りと割った値を計算したら、%residue ハッシュのキーをチェックします。すでに存在する場合は、循環部の抽出が終わったことになります。循環部を計算して完全循環小数の場合は先頭に * を付けて、循環部を丸括弧で囲んで出力し、while ループから抜けます。除数 21 から 30 までの出力は、次のようになります。1/25 のように割り切れる場合は、丸カッコなしで出力されます。先頭に * が付いていないものは、通常の循環小数になります。

完全循環小数は、100 以下では９つ、1000 以下では 60、10000 以下では 467 あります。100 以下の循環小数は、以下のとおりです。