では，逆数を求めるアルゴリズムについて考えて見ましょう．導入講義「アルゴリズムとデータ構造」程度の知識があれば，次のようなアルゴリズムを考案するのは容易でしょう．最初に1をnで割ってみます．もちろん，nの方が大きいので，1を10倍したものを割ることにします．それでもnより小さいなら，更に10倍します．このようにしてn以上になれば，その数をnで割ったときの商と余りを求めます．商の方はどこかに置いておいて，余りを10倍してnで割り，その商と余りを求めます．基本的にはこの計算を繰り返します．余りが0になれば，割り切れたので，それまでに得られた商を順に出力すれば答が得られます．循環小数の場合には余りが0になることはありません．その場合には循環部分を見つける必要があります．循環部分は商の列が同じなので，同じ商の列が見つければよいと考える人もいるかも知れませんが，それは間違いです．割り算はいつも現在の余りを10倍してから行っているので，以前に見たのと同じ余りが得られれば，それ以降の計算は同じように進むはずです．したがって，循環部分を求めるには，余りを求めるたびに，その余りは以前に出現したものかどうかを判定すればよいことになります．単純には，商と余りを配列に順に入れて行き，余りを得るたびに，過去の余りを調べて同じものがあるかどうかを判定すればよいことになります．これをプログラムに近い形で書くと次のようになります．

r[0] = 1 //最初の余りは1
i = 1.
repeat　　//以下を繰り返す
　　q[i] = r[i-1]*10/n; // 前回の余りを10倍したものをnで割ったときの商
　　r[i] = r[i-1]*10 mod n; // nで割ったときの余り
　　if i番目の余り r[i]が以前に求めたj番目の余りr[j], j<iと同じ
　　then 循環部分はj番目から始まるので，それを報告して終了
　　if 余りが0　then 割り切れたことを報告して終了
　　どちらでもなければ，iを1増やして繰り返す．

　上記のアルゴリズムにはループがありますが，これは同じ余りが見つかるか，余りが0になったときに終わります．nで割ったときの余りは0からn-1までの整数ですから，n通りしかありません．したがって，ループの繰り返し回数は最大でもn回です．余りを求めるたびに，それが以前にあったかどうかを調べるのに，ループの i 回目では i に比例する時間がかかります．i の値を 1 から順に n まで変化させて i の値を足しこむとき，総和はn(n-1)/2，すなわち，n の2乗に比例する値となります．この計算時間を改善することはできるでしょうか．上の方法では余りを順に配列に蓄えましたが，R という余りが i 回目のループで得られたときに，r[R] = i として，R という余りが i 回目に得られたことを示すようにすればよいのです．すなわち，

r[1] = 0 //余り1は0回目に出現している．
r[2], ... , r[n-1]はすべて -1 という負の値に初期化しておく．
R=1
i=1
repeat　　//以下を繰り返す
　　q[i] = R*10/n; // 前回の余り R を 10 倍したものを n で割ったときの商
　　R = R*10 mod n; //新たな余りの計算
　　if R=0 then 割り切れたことを報告して終了．
　　if r[R] >= 0 then 循環部分はr[R]番目から始まることを報告して終了．
　　r[R] = i; // 余りRは i 回目に出現
　　どちらでもなければ，iを1増やして繰り返す．

このプログラムでは，毎回の操作が定数時間でできることは明らかですから，実行時間はO(n)であることが分かります．つまり，最悪でも n に比例する程度の時間で計算を終わることができます．
このように，逆数 1/n の計算は，最悪でも n に比例する時間でできることが分かりましたが，作業領域についても n に比例するだけの量を必要としています．n が10,0000,0000を超えるような場合，この作業領域はかなりの大きさになります．
　極端な場合，作業領域として定数個しか使えないような状況であったとすれば，逆数の計算はできるでしょうか．最初は，そんなの無理に決まっていると思ってしまうのも無理はありませんが，実は簡単な仕掛けで十分です．問題は，毎回同じ余りが以前に出たかどうかを調べることにあります．上のアルゴリズムでは，過去に出た余りを配列に入れて蓄えていましたから，そこを見れば過去に出たかどうかが分かるのですが，記憶しておかなくても同じことができます．記憶する代わりに，同じ計算を初めからやり直せばよいのです．余りを次々と計算すること自体は簡単です．たとえば，次のプログラムは余りの計算を k 回行います．

r = 1;
for i=1 to k
　　r = r*10 mod n;

このようにして，ループの k 回目で余り R が得られたとき，余りを k-1 個だけ順に生成してみて，その中に R に等しいものがあるかどうかを調べればよいのです．具体的には次の通りです．

r = 1; i=1;
repeat
　　r = r*10 mod n;
　　if r = 0 then 割り切れたことを報告して終了．
　　R = 1;
　　for j=1 to i-1
　　　　R = R*10 mod n;
　　　　if r = R then 循環部分が i 番目から始まることを報告して終了．
　　i=i+1;

　もちろん，循環小数として出力するためには細部を詰める必要がありますが，考え方は上に述べた通りです．このアルゴリズムは配列を一切していないのが最大の特徴です．したがって，作業領域としては定数個の変数だけで十分です．実行時間は n の2乗に比例しますが，これは最初のアルゴリズムと同じです．
　実は，これよりも格段に優れたアルゴリズムが知られています．割り切れるかどうかは，与えられた整数 n が2と5以外の素因数をもつかどうかに依存します．よって，与えられた整数 n を2と5で割り切れるだけ割ってみて，最終的に1になるかどうかを見れば，割り切れるかどうかが分かります．いま，2では p 回，5では q 回だけ割り切れるものとしましょう．割り切れなかったとき，循環部分が何桁目から始まるかを求める必要がありますが，その桁は max(p, q) + 1 として与えられることが証明されています．詳しくは下記の文献を参照して下さい．

W.G. Leavitt, ``A Theorem on Repeating Decimals,'' American Mathematical Monthly. Vol. 74, No. 6 (Jun.-Jul.,1967) , pp. 669-673

循環部分の最初の桁が分かっているので，その桁に至るまで商と余りの計算を繰り返し，そのときの余りを記憶しておいて，次はその余りが生じるまで同じ計算を繰り返すというだけでよいのです．なぜそんなことが証明できるのかに興味のある人は，オイラーのファイ関数というものを勉強して下さい．とにかく，この方法だと，定数個の変数を用いるだけで，しかもnに比例する時間O(n)で逆数の計算ができます．