mod255の計算

質問

こんにちは。
今日はmod255の計算について困ったことがあり、質問しました。

私は今、mod255の計算をする回路を作っています。
mod255とはある値を255で割ったときの余りを求めることですよね。

しかし、回路ではあまり除算(回路の性質上、逆数を取って乗算する)を使いません。
理由は、計算に時間がかかることと、回路規模がが大きくなるため。

ある値が255以上か判定してから順次255を引くことも考えましたが、動作が不規則なため使っていません。

そこで、私はmod255を除算を使わず、減算で実現しようと次のような計算法を考えました。

例、239+157をmod255する場合。

239+157=396を2進数に変換すると

11101111
+10011101
------------
110001100

ここで、計算結果の右から9番目の1を一番右に移動して加算すると

10001101になります。

これを10進に変換すると141になります。

よって、396-255=141となり396をmod255ができていますよね。

これで、問題解決だと思ったのですが、
ある値が511でこの計算をすると結果が10000000となり
256になってしまいます。

このことから考えて、この計算法は万能ではないみたいです。

この計算法のどこを改善するとmod255を計算できるようになるのでしょうか？
また、皆さんなら、どんな方法でmod255を実現しますか？

よろしく、お願いします。

回答No.1

noname#47894 · ベストアンサー

mod255　の計算結果は、本来、255より小さな値になるのではないでしょうか？

511（111111111）の場合、ただ255　を引くだけだと
111111111-100000000+1＝100000000
となってしまうので、
もう一度同じ計算をして、
100000000-100000000+1=000000001　とすればよいのでは？

右から9桁（より左も含めて）が、0になるまで、繰り返すように処理しないと、255より小さくならないと思われます。
終了判定をどうするかが、ポイントでしょうか。

お礼

回答、ありがとうございました。
やはり、条件判断をして複数回計算するしかなさそうですね。

回答No.4

Tacosan

#2 です. 処理によっては考えようもあるんだけど, #3 の回答を参考にして, 何も考えず実用性を無視 (苦笑) して遊んでみる:
まず, #3 のように与えられた長い 2進数を LSB から 8bit = 1octet ごとに区切ります. すると, 「元の長い 2進数を 255 で割った余り」は「区切って得られる数の和を 255 で割った余り」と等しくなります. そこで, 問題は「多くの octet を足して 255 で割った余りを求める」問題となります.
これを, 「最終段から」逆順に考えてみます.
１．最終段: 1octet のとき. このとき, 255 を 0 にしてその他はそのままにすることになります. ということで, 8bit 全体の NAND をとり, これと各bit の AND をとります.
２．その 1つ手前: 2octed のとき. ひねりようがないので, 2個の octet を足します. 9bit 目を再度 LSB に足し込めば１になります.
３．さらに 1つ手前: 3octet のとき. CSA で 2octet に減らすことができます. キャリーは 9bit 目に行きますが, これは (ちょうど空いている) キャリーの LSB にまわすことができ, 結局 2octet になるわけです.
４．もっと手前: 4octet 以上のとき: ３と同じで, CSA を使って 3octet を 2octet にするという処理を＊がんばって＊繰り返します.
つまるところ, 「何も考えずに乗算器を作る」のと大差ないんですけどね.

回答No.3

stomachman

正の整数xを与えた時、
r≡x mod 255　(0≦r＜255)
つまり
x=255n+r　(0≦r＜255)
となるrを計算する。
x＜255ならばr=xでおしまいですが、
x≧255の場合にはそうは行かない。

ところで、x mod 256の計算
x=256m+k 　(0≦k＜256)
ならイトモ簡単で、kはxの２進表現の下8桁そのもの。そしてmとはxの下8桁を捨てたもの（つまりxを右に8桁シフトしたもの）。これはお分かりでしょう。
mとkを使うと、
x = 255m+(m+k)
だから
r ≡ (m+k) mod 255
である。そこで
x' = m+k
としたとき、
r≡x' mod 255 (0≦r＜255)
つまり
x'= 255n'+r　(0≦r＜255)
となるrを計算する。
x'<255 なら r=x'でおしまいですが、
x'≧255の場合にはそうは行かない。

あれ？これはどっかで見たぞ？

という訳でまとめますと、

while (x ≧ 255)
　　k = x の下8桁
　　m = xを右に8桁シフトしたもの
　　x = (m+k)
end while
r=x

とやれば割り算なしに高速で計算できます。

お礼

回答ありがとうございました。
わかりやすい説明で助かりました。
条件判断が必要なんですね。
この回答を参考にがんばりたいと思います。

回答No.2

Tacosan

すみません, 前提を教えてもらえませんか?
・どのような計算をするのですか?
・計算の対象となる値はどのような範囲なのですか?