• ベストアンサー

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を実現しますか？ よろしく、お願いします。

質問者が選んだベストアンサー

  • ベストアンサー
noname#47894
noname#47894
回答No.1

mod255　の計算結果は、本来、255より小さな値になるのではないでしょうか？ 511（111111111）の場合、ただ255　を引くだけだと 111111111-100000000+1＝100000000 となってしまうので、 もう一度同じ計算をして、 100000000-100000000+1=000000001　とすればよいのでは？ 右から9桁（より左も含めて）が、0になるまで、繰り返すように処理しないと、255より小さくならないと思われます。 終了判定をどうするかが、ポイントでしょうか。

tinpun-kanpun
質問者

お礼

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

その他の回答 (3)

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.4

#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 にするという処理を＊がんばって＊繰り返します. つまるところ, 「何も考えずに乗算器を作る」のと大差ないんですけどね.

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.3

正の整数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 とやれば割り算なしに高速で計算できます。

tinpun-kanpun
質問者

お礼

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

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

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

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ＭＯＤ２５（２５を法とする剰余）の計算

    エクセルでＭＯＤ２５（２５を法とする剰余）の計算をします。 （記号）３∧ｎで３のｎ乗をあらわすものとする。 （したいこと）ｍｏｄ（３、25），３∧２=9、３∧３=２７、―――、３∧２０、―――、３∧２４に対して、 ｍｏｄ（３、25）～ｍｏｄ（３∧２４、25）までの値を求めたいのですが、～ｍｏｄ（３∧２0、25）以降の値がおおきすぎてエラーとなります。どうすればいいのでしょうか。

  • Javascriptで算術演算子を作っているのですがわかりません・・・

    あの、JavaScriptの課題で、算術演算子つくり、加算、減算、乗算、除算、整数の除算の商と余りが求めれるように、a bにそれぞれ数値を代入して計算開始というのを作りました。それで、数値以外のたとえば、アルファベットなどを代入した場合、それは数値ではありません、数値を代入してくださいというような数値の入力を促すようになるようにしたいのですが、エラーばかりでます。どのようにソースを打ったら良いのかさっぱりわかりません。教えてください！！よろしくおねがいします。

  • このたし算を子供に簡単に計算できるよう説明したい

    ５４０＋５５０＋５６０……＋１０６０＝？？？？？　という問題です。 ５４０から１０刻みの数字を、１０６０まで足した合計はいくつでしょう？という問題の解き方、考え方を、小学生（乗算、除算、加算。減算できます）でもわかるように説明したいです。 インド式（？）のように、なるほど！とわかやりやすい説明の仕方はありませんでしょうか？ 各数字を並べた時、端同士を足せば１６００になり、その数をペアの数だけかければ計算しやすいかなと思ったのですが、どうすれば、より早く分かりやすく計算できる説明ができるでしょうか？

  • modの計算方法について

    下記ホームページで紹介されているmodの計算方法について教えてください。 http://c4t.jp/introduction/cryptography/cryptography04.html (1)「素数」を法とする世界では、Xn mod 素数＝X という、元の数字と答え（X）が共に同じとなる「n」の値を「素数」から計算することができます。というのがありますが、例をあげて説明していただけないでしょうか？ (2)RSA暗号の概要で暗号分456はどのように計算するのでしょうか？ よろしくお願いします。

  • 基本情報技術者過去問

    1)負数を2の補数で表す8ビットの数値がある。この値を10進数で表現すると-100である。この値を符号なしの数値として解釈すると、10進数で幾らか？ ア）28 イ）100 ウ）156 エ）228 2) 多くのコンピュータが、演算回路を簡単にするために補数を用いている理由はどれですか。 ア）加算を減算で処理できる イ）減算を加算で処理できる ウ）乗算を加算の組み合わせで処理できる エ）除算を減算の組み合わせで処理できる

  • 電卓における「乗算器の回路」と「2進法・10進法間の変換」

    電卓のしくみを調べています。 以下のことはわかりました。 A.計算には2進法を利用している（引き算には2の補数を利用している） B.全加算器、乗算器などをAND回路、OR回路などをつかって実現している そこで2点知りたいことがでてきました。 1.乗算器の計算のしくみは、 http://www-lab.ee.uec.ac.jp/text/arithmetic/serial.html をみてなんとなくわかったのですが、AND回路、OR回路などをつかった具体的な回路がいまいちイメージできません。 乗算器の回路を図で表し、詳しく解説したサイトがあれば教えてください。 2.電卓では入力と出力が10進法ですが、具体的な計算は2進法でやっているということはわかりました。しかし、入力した10進法を2進法に直す回路や、計算結果の2進法を10進法として出力する回路がわかりません。 その回路を図で表し、詳しく説明したサイトがあれば教えてください。 もしそういったサイトがない場合は、これらを解説した書籍を紹介していただければありがたいです。 よろしくお願いします。

  • 四則演算についてです

    四則演算の除算法についてですが ｛23/6｝を２進数で求めたいです。 但し、被除数は６ビット、除数は４ビットという条件付き。 23=(0 10111)2 6=(0 110)2 ２の補数を用いて-6=(1 010)2 減算結果が正の場合、商として１をたて 減算結果が負の場合、商として０を立てるのですが 010111 +)1010　　　　商 --------- 111111　…０ +) 1010 --------- 1010011　…０ +) 1010 --------- 1101　…０ +) 1010 --------- 10111 となってしまい商と余りがうまく出ません！ 間違ってるところ教えてください！

  • 浮動小数点をXの倍数（整数）に丸める方法

    浮動小数点数Fを、Fにより近いX（整数）の倍数（整数）に丸める方法を教えてください。 自分なりにコード化しましたが、イマイチ美しくないです^^; もっとスッキリした方法があれば教えてください。 よろしくお願いします。 ※Fは正の浮動小数点数に限定します。 long L, mod ; L = (long)F ; //キャストして小数点以下を切り捨てて整数化 mod = L%X ; //Xで除算して余りを求める if ( mod ==0 ) { //既にXの倍数なので何もしない ; } else if ( mod <= X/2 ) { //余りがX/2より等しいか小さい時 L -= mod ;　//余りを減算する } else { //mod > X/2の時 L += X-mod ; //Xに満たない分を加算 }

  • これがプログラミングなのかもわからないのですが…

    さっぱりわからないので詳しく説明してもらいたい所なのですが、きっと理解できないと思うので…簡単に(1)(2)について述べてもらえると嬉しいです。 （１）計算機における割り込みの用途と通常のサブルーチン・コールとの違い （２）プログラムを再配置可能なものに変換する上で、CPU,アセンブラなどで用いられている工夫について 　あと、右シフトだと除算で、左シフトだと乗算ですよね。じゃあ回転をするときって、何がもとめられるんですか？ 　困っているのでどうかよろしくおねがいします。

  • なぜ？コンパイルできないのでしょうか？

    タイトルのとおりなんですが、よろしくお願いします。 (-人-) public class Calc1 { public static void main (String[] args) { System.out.println("加算の結果は"+(3+2)+"です。"); 　　　　System.out.println("減算の結果は"+(5-8)+"です。"); System.out.println("乗算の結果は"+(3*4)+"です。"); System.out.println("除算の結果は"+(7/3)+"です。");　 } }

    • ベストアンサー
    • Java

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する