アルゴリズム 「５で割る」 の計算過程

質問

割り算や掛け算を持ち合わせていないマイコンでの割り算　Ｘ÷５　を模索しています。

http://techref.massmind.org/techref/method/math/divconst.htm
ここで、２のべき乗で割る方法が示されていますが、理解できていない箇所があります。

(X/4) / (1+1/4) = (X/4) * (1 - 1/4 + 1/16 - 1/64 + 1/256 ...)
この部分なのですが、なぜ、このように変形できるのですか？

回答No.3

noname#195146 · ベストアンサー

無限級数の和の公式を逆に使っているのです。

　(x/4)/(1+1/4))の、1/(1+1/4)の部分が、 (1 - 1/4 + 1/16 - 1/64 + 1/256 ...)に対応していることが分かります。

　1/(1+1/4)を、1/(1-(-1/4))と書き直しておきます。無限等比級数の和の公式は、初項がa1、公比がrだとすれば、

　a1+a1r+a1r^2+a1r^3+…＝a1/(1-r)

です。a1＝1、r＝-1/4とすれば、右辺は1/(1-(-1/4))で、お示しの左辺と一致します。ですので、a1＝1、r＝-1/4を上式両辺に適用し、対応を分かりやすく書けば

1-1/4+1/16-1/64+1/256…＝1-1/4+1/4^2-1/4^3+1/4^4…＝1/(1-(-1/4))＝1/(1+1/4)

となります（公比がマイナスなので、奇数乗はマイナス、偶数乗がプラスになる）。

　両辺を入れ替え、両辺にx/4を掛ければ、お示しの式になります。

お礼

丁寧にありがとうございました。
無限級数の和の公式をマスターすれば理解できそうです。
示していただきました具体的な式と合わせて勉強してみます。

回答No.2

178-tall

(X/4) / (1+1/4) = (X/4) {1 / (1+1/4) } にて、右辺の後項 {1 / (1+1/4) } を無限級数展開。

そのもとは、
　1 - x^m = (1-x)*{1 + x + x^2 + … + x^(m-1) ]

(付け足し)
x へ -x を代入。
左辺は m→∞ で 1 に収束。

お礼

ありがとうございます。
無限級数展開を勉強してみます。

回答No.1

notnot

＞割り算や掛け算を持ち合わせていないマイコンでの割り算　Ｘ÷５　を模索しています。

ということであれば、「X から 5が何回引けるか」を行うのが楽だと思います。

＞(X/4) / (1+1/4) = (X/4) * (1 - 1/4 + 1/16 - 1/64 + 1/256 ...)

(1+1/4) * (1 - 1/4 + 1/16 - 1/64 + 1/256 ...) ＝ 1 だからでしょう。

お礼

早速の回答ありがとうございます。
なるほど、１になれば、両辺等しくなりますね。

割り算や掛け算のないマイコンは速度もおそく「何回引けるか」は、
８ビットでは、最悪５０回ぐらいループします。
ところが、質問したものは、７ステップで完了します（コーディング量はもっと多くなるとは思いますが）。
最良のものを、いろいろ、模索しているところです。