誤差なしRPN電卓の実装

手計算に対する電卓の違いと言えば、常に小数で演算することがあるだろう。今やすっかり計算機のある世界に慣れて当たり前になってしまい、あまり気にすることもなくなったが、例えば「1を3で割る」といった計算に対して表示される 0.3333333 という値は、本当に期待していたものではないこともあるのではないだろうか。一部の関数電卓には分数計算機能が備わっているが、そういう特殊機能でなく、電卓が丸ごと分数計算に特化されていて、いつでも気軽に分数での計算ができる、そんな電卓があってもよい。そういう動機で、マイコンを使った物理的なRPN電卓や、Webブラウザ上で動作するRPN電卓として常に分数での計算ができる電卓を実装してみた。特にマイコンはプログラムを格納するフラッシュメモリ容量が小さいため、できるだけ単純に、プログラムサイズが小さくなるように意識して実装した。ここではその概要を紹介する。

基本設計

取り扱う数値（有理数）は分母、分子の非負整数を表すそれぞれの文字列と、符号（正負）の組み合わせで表すことにした。符号は分子または分母の整数に入れてしまうこともできるが、整数計算部では常に非負整数だけを取り扱うことにしたほうがアルゴリズムが簡単になるためである。実装は Arduino の拡張C言語、またはJavaScriptで記述してあるが、いずれも単純なC言語に比べて文字列を簡単に取り扱うことができる。ここではArduinoの記述（ソースコード全体はこちら）に基づき紹介していくが、JavaScript版もほぼ同様である。分数の構造体定義は以下のようになる。

struct FRAC {
  String u, b;
  int sign;
};

ここで分子、分母を表すu, bは Arduino の String 型であり、そのまま整数として表示できる、'0'から'9'の10種類の文字だけからなる文字列である。10進数の一桁に1バイトを消費するため、BCD(二進化十進数表現、１桁あたり4ビット)のような表現に比べると2倍のメモリを消費し非効率ではあるが、 String 型を用いることで長さの管理が自動的に行われ、桁あふれの心配なく非常に大きな整数を扱うことができる。

符号ビットに int 型を用いているが、分母・分子に要するメモリに比べれば微々たるもので無視できる。もちろん、このような分数表記を用いれば全ての有理数が表現でき、四則演算の結果が表現できなくなることはない。ただし平方根は無理数になる場合があるため、ここでは扱わないことにする。

無限長の整数演算

分数演算を実装する前にまず、分母・分子に用いる無限長非負整数の四則演算を実装する。分数演算を行うために加減算と乗算が必要であることは自明であるが、分数の約分を行うために最大公約数を求める必要があり、そのために除算や剰余（割った余り）の演算が必要になる。非負整数のみを扱うため符号の処理は不要であるが、減算の結果が負数とならないよう、数の大小を比較する関数も必要になる。

加算は、小学校で学んだ筆算と同じ手順を単に下の桁から繰り返す。下のコードでは、桁位置を表す変数 i を減算しながら各桁の和を求め、その値が10を超えた場合は繰り上がりを行うという、筆算そのものの処理である。

#define VAL(a) ((a) - '0')
        
  len = a.length();
  for(i = len-1; i >= 0; i--) {
    int sum = VAL(a.charAt(i)) + VAL(b.charAt(i)) + carry;
    if(sum > 9) {
      sum -= 10;
      carry = 1; // 繰り上がり
    }
    else {
      carry = 0;
    }
    c = String(sum) + c;
  }

上の加算のアルゴリズムは文字列 a, b の長さが同一であることを前提としている。そのため、加算を行う前に、短い方の文字列の前に0を追加して長さを合わせる処理を行っている。減算も同様に下の桁から、繰り下がりを勘案しながら筆算を行う手順で行う。値が近い数同士の減算では、最終的に 000012 のように前に0が並ぶことがあるため、これを除去する正規化関数 iNorm() を用意して処理している。

積の演算も基本的に筆算の手順による。ただし九九の実装（n桁 x 1桁の積の計算）を省くため、各桁では乗数の回数だけ加算を行う方法で実装している。ちょうど、手回しの機械式計算機で乗算を行うようなイメージである。この関数は短いので、コード全体を示す。

String iMul(String a, String b) {
  String c, amul;
  int i, j;

  c = "0";
  amul = a;
  for(j = b.length() - 1; j >= 0; j--) {
    for(i = 0; i < VAL(b.charAt(j)); i++) {
      c = iAdd(c, amul);
    }
    amul = amul + "0"; // 左シフト
  }
  return iNorm(c);
}

除算もやはり、筆算の手順で行う。これもやはり機械式計算機と同様に、各桁の長さをあわせたうえで引けるだけ引いていき、大小関係が変化したところで次の桁に移る方法で実装している。これ以上引けなくなったところで残った数が剰余になるので、これはグローバル変数に保存しておき、別の剰余を取得する関数で参照できるようにしている。つまり、剰余を求めるには除算を行い、その後に剰余取得関数を呼び出すことになる。

加減乗除が揃うと分数の実装がほぼ可能となるが、そのまえに最大公約数を求める関数も作っておく。これは分数を約分する際に必要となり、有名な互除法の教科書的アルゴリズムである。上記のように、割り算関数 iDiv() を実行してから剰余取得関数 iRem() を呼び出すことで剰余を得ている。以下にそのコードを示す。

String iGCD(String a, String b) {
  String c, r;

  if(iComp(a, b) < 0) {
    c = b;    b = a;    a = c;
  }
  for(;;) {
    iDiv(a, b);
    r = iRem();
    if(iComp(r, "0") == 0) {
      return b;
    }
    a = b;
    b = r;
  }
}

分数演算

以上で無限長整数の四則演算が実装できたので、つぎは分数の四則演算であるが、まずは約分を実装する。いくつかの例外処理を省いたコアな処理は以下の３行だけである。

  gcd = iGCD(a.u, a.b);
  a.u = iDiv(a.u, gcd);
  a.b = iDiv(a.b, gcd);

次に加算の計算である。ここでは難しいことを考えずに、他方の分母の値で通分してから、最後に計算結果を約分する方法で実装している。分数の加算関数 fAdd() の冒頭は以下のようになる。

struct FRAC fAdd(struct FRAC a, struct FRAC b) {
  struct FRAC c;

  c.b = iMul(a.b, b.b);
  a.u = iMul(a.u, b.b);
  b.u = iMul(b.u, a.b);

演算結果の分母は c.b そのものであるが、分子は a.u と b.u を加算または減算したものとなる。というのは、符号は別の変数で保持しているためであり、符号が互いに異なる場合は減算となる。

分数の差の演算 $a - b$ は、$b$ の分数の符号を反転して加算の関数を呼び出す、つまり $a + (-b)$を計算するだけである。乗除算の演算は非常に単純で、分母・分子同士、または分母と分子を入れ替えて乗算を行うだけである。

小数への変換

演算結果を分数として表示するだけであれば必要ないが、結果はもちろん、小数としても確認したい。そこで小数に変換する関数も実装した。小数は分子を分母で除算することで得られるが、実装済みの整数除算関数は小数点以下の計算を行わないので、必要な小数点以下の桁数 n に対し、分子を$10^n$倍してから除算を行うことで実装している。より具体的には、商として得たい有効数字の文字数分だけ分子の文字列長が長くなるよう、分子の文字列末尾に0を追加してから除算を行い、得られた商の文字列の適切な位置に文字列処理で小数点を挿入することで実現している。

結果が 0.0000000xxx のように非常に小さな値になる場合のほか、さらに絶対値が小さな数や、逆に非常に大きな数のために 1.2345e+10, 9.876e-12 のような指数表記を行うアルゴリズムも実装している。各表示文字列生成関数では、符号(-)や指数部の有無にかかわらず、常に同じ長さの文字列が生成されるようにしているためややトリッキーな実装となっているが、これらが泥臭いだけで処理の原理は以上のように単純である。

電卓では小数入力を扱う必要があるが、これは小数点以下の桁数 $n$ に合わせて分母に$10^n$を代入するだけである。例えば 12.34 であれば 1234/100 のような値を分母・分子に設定するだけである。

プログラムサイズ

この分数演算ライブラリの実装は非常にコンパクトで、Arduino 標準の String 型を処理する関数群を含めたコンパイル済みバイナリ全体で11kB以下に収まる（表示用小数文字列の生成関数を含む場合。分数演算だけであれば9kB以下）。ホビー用マイコンとしてもっともポピュラーな Arduino Uno, Arduino Nano 等はフラッシュメモリの空きが30kBしかなく、電卓として機能させるにはさらにディスプレイを制御するためのライブラリ等も必要となるが、それを加えてもフラッシュに十分収まる。上の写真はホビーRPN電卓を誤差なしRPN電卓に改造するためのコードのコンパイル結果であるが、SSD1306 OLEDディスプレイを制御する U8glib を含めたコンパイル後のスケッチは約20kBで、余裕を持ってフラッシュメモリに収まった。

なお、ATmega328 CPU と Arduino の開発環境の組み合わせでは倍精度実数をそのまま扱うことが出来ない（C言語の実数はfloat(32bit)しか実装されておらず、doubleを指定しても32bit演算となる。66bit浮動小数を扱うにはfp64libなどを使用する必要がある）。また、実数を10進数の小数として表示するためにはsprintf関数なども必要となる。それに対し、この分数演算のコードは何らの外部ライブラリも必要とせず、小数の文字列の入出力も可能である。

ただし単純さ、コンパクトさを最優先とした実装であるため、電卓には過不足ないが、一般の数値計算には実行速度の観点で不向きである。具体的な実装のソースコードは以下で参照できる（いずれも電卓用のキー入力処理等を含む）。

Arduino IDE 版ソースコード
ウェブアプリ用 JavaScript版ソースコード（ブラウザのソースコード表示機能で参照してください）