除算を行わずに剰余を求める方法とは？
- 除算を行わずに剰余を求める方法として、2の累乗を利用する方法があります。
- 具体的な手順は、2の累乗の値を求めて、それを元の数値から減算した後、元の数値の1ビットをマスクして足し合わせることです。
- ただし、いくつかの実装上の誤植があるため、適切な修正が必要です。
- ベストアンサー
除算を行わずに剰余を求めたい
http://www.tensyo.com/urame/date/dayTips.htm#MOD によると、除算を行わずに剰余を求める方法として、 ------------------------------------------------------- 2^N>=b となるNを求める(2^N == 1<<N) B=2^N-b C=2^N-1 while(a>=2*b){ B *(a>>N) + a&C }; 最後に１回 if(a>=b)a-=b ; と計算する ------------------------------------------------------- とありますが、これの実装はおそらく誤植です。 というのも、4行目B *(a>>N) + a&Cは代入操作等をしていないため、 実質何もしていないからです。 そこで、a=B *(a>>N) + a&Cのように変更するなどやってみましたが、 5回に1回ぐらい異なる値が現れます。 このアルゴリズムはどのように変更したらよいでしょうか？ また、他の方法でも結構ですので、教えてください。
- ibm_111
- お礼率70% (44/62)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 商と剰余を同時に求める（Ｃ言語）
Ｃ言語についてですが、 整数の除算を行うときに、商と剰余を同時に求めることは可能なは ずなので、１回の演算で両方知りたいのですが、c = a / b;だと商 だけ、d = a % b;だと剰余だけしか分からないです。 １回の演算で両方得たい場合はどう記述すればいいでしょうか？
- ベストアンサー
- C・C++・C#
- 剰余類の問題
剰余類の問題について解説がなく自分の考え方が正しいのか判断できず困っています。 問題は 3の剰余類をC0,C1,C2とするとき 1. a ∈ C0 , b ∈ C1 のとき a + b はどれに属するか。 2. a ∈ C1 , b ∈ C2 のとき a + b はどれに属するか。 です。 以下自分の解答↓ C0 は整数を 3 で割った時、あまりが 0 になる整数の集合 C1 は整数を 3 で割った時、あまりが 1 になる整数の集合 C2 は整数を 3 で割った時、あまりが 2 になる整数の集合 なので、n を整数とすると、 C0 = { 3n } C1 = { 3n + 1 } C2 = { 3n + 2 } となる。 よって 1のときは a = 3n , b = 3n + 1 とし a + b = (3n) + (3n + 1) = 6n + 1 = 3(2n) + 1 nは整数なので2nも整数である。よってa + b ∈ C1 2のときは a = 3n + 1 , b = 3n + 2 とし a + b = (3n + 1) + (3n + 2) = 6n + 3 = 3(2n + 1) nは整数なので2n + 1も整数である。よってa + b ∈ C0 1 , 2 ともにC1 , C0 に属しているということは正しいのですが、解答にいたるまでの自分の考え方があっているかどうかがわかりません。(特に剰余類について) どなたかご教授よろしく御願いいたします。
- ベストアンサー
- 数学・算数
- テイラーの定理、剰余項について
以前に質問した者です。テイラーの剰余項について [f^(n)(c)/n!](x-a)^n=Σ[k=n,∞]f^(k)(a)/k!](x-a)^k=[f^(n)(a)/n!](x-a)^n+[f^(n+1)(a)/(n+1)!](x-a)^(n+1)+ … つまり、(x-a)のn乗以降の無限項和がaとxの間のcを選べば １つの項「[f^(n)(c)/n!](x-a)^n」 で表せるということは分かりました。 これは、例えはf(x)が6次の関数のとき、f(x)=f(a)+f'(a)(x-a)+｛f''(c)/2!｝(x-a)^2となるcが存在するということですか？ またこのとき、6回微分すると、f(x)は定数になりますが、このとき｛f''''''(c)/6!｝(x-a)^6を剰余項とすると、他のサイトだとc=aとなっていて、これはcがaとxの間にあるということを満たさないのですが、どうせ定数でx=aを代入できないので、綺麗にするために形式上そう書くのでしょうか？
- ベストアンサー
- 数学・算数
- 代数の問題です。
大学の代数でこのような問題がでて きて、わからないので教えてくださ い 。よろしくお願いします。加法群G=Zの部分群H=nZ(n≧1は 自然数)に関する剰余類aHをa+nZと加 法的に表す。 また、a,b∈Zに対し、a-bがnの倍数 のときa≡b(mod n)と表し、aとbはn を法として合同であるという。 これは、a+nZ=b+nZと同値である。 剰余類の集合G/H=Z/nZをZnと表す。 Cn:位数nの巡回群={e,a,a^2,…a^n-1}a ^n=eとする (1)a≡a′(mod n),b≡b′(mod n)な らば、a+b≡a′+b′(mod n)を示せ 。 これより剰余類の集合Znに(a+Z)+(b+Z )=a+b+Zによって 積(この場合は和)が定義されることを 示し、 Znに群の構造が入ることを示せ。(Zn をnによる剰余類群という。) (2)剰余類群Znは巡回群Cnと同型であ ることを示せ
- ベストアンサー
- 数学・算数
- 代数の問題です。
加法群G=Zの部分群H=nZ(n≧1は 自然数)に関する剰余類aHをa+nZと加 法的に表す。 また、a,b∈Zに対し、a-bがnの倍数 のときa≡b(mod n)と表し、aとbはn を法として合同であるという。 これは、a+nZ=b+nZと同値である。 剰余類の集合G/H=Z/nZをZnと表す。 Cn:位数nの巡回群={e,a,a^2,…a^n-1}a ^n=eとする (1)a≡a′(mod n),b≡b′(mod n)な らば、a+b≡a′+b′(mod n)を示せ 。 これより剰余類の集合Znに(a+Z)+(b+Z )=a+b+Zによって 積(この場合は和)が定義されることを 示し、 Znに群の構造が入ることを示せ。(Zn をnによる剰余類群という。) (2)剰余類群Znは巡回群Cnと同型であ ることを示せ
- 締切済み
- 数学・算数
- 剰余の問題について
基本情報技術者試験の問題にて、 pを2以上の整数とする。任意の整数nに対して、 n=kp+m (0 <= m < p) を満たす整数kとmが一意に存在する。このmをnのpによる剰余といい、 n mod pで表す。（-10000）mod 32768に等しくなるものはどれか。 ア -(10000 mod 32768) イ (-22768)mod 32768 ウ 10000 mod 32768 エ 22768 mod 32768 という問題があります。 この問題の解答は「エ」となるのですが、 解き方がどうしても理解することができません。 解説では （-10000）mod 32768と等しいのは 32768+(-10000)=22768から 22768mod32768となる。 と書いてあるのですが、このように解答していく プロセスがさっぱり見えてきません。 この解法の仕方をレクチャーしていただけないでしょうか。
- ベストアンサー
- 情報処理技術者
- 合同式の定義 剰余？ それとも 最小非負剰余？
合同式の定義について、参考書ではあいまいにごまかしてあったので質問させてください 合同式の定義は 整a≡整b (mod 整c） ⇔ 整a=整c×整d＋整e ∧ 整b＝整c×整f＋整e なのでしょうか？ （つまり整eは剰余） それとも 整a≡整b (mod 整c） ⇔ 整a=整c×整d＋整e ∧ 整b＝整c×整f＋整e ∧ 0≦整e＜整c なのでしょうか （つまり整eは最小非負剰余） 参考書ではどちらにもとれる書き方をしてありました
- ベストアンサー
- 数学・算数
- オイラーの定理(整数)
nは自然数、aは整数とする。aとnが互いに素な時、a^{φ(n)}≡1( mod n)が成り立つ。 ここでφ(n)は「n以下の自然数でnと互いに素なものの個数を表す」"オイラーの関数"である。 この定理の例証で、例えばn=45=3^(2)*5のときa=7として考えます。 φ(45)=φ(3^2)*φ(5)となり、φ(3^2)=6、φ(5)=4です。 フェルマーの小定理よりmod 5 で、7^φ(45)={7^φ(5)}^φ(3^2)は {7^φ(5)}≡1 (mod 5)より、7^φ(45)≡1 (mod 5 )・・・(1)になり。 次に7^φ(3^2)≡1(mod 3^2)をしるします。フェルマーの小定理より mod 3 で 7^(3-1)≡1なので7^(3-1)＝3k+1、 7^φ(3^2)={7^(3-1)}^3＝(3k+1)^3=(3k)^3+3C1(3k)^2+3C2(3k)+1 3C1、3C2は３の倍数なので、7^φ(3^2)≡1(mod 3^2)・・・(2)です。 よって、7^φ(45)={7^φ(3^2)}^φ(5)≡1(mod 3^2)となります。 ここからが分からない箇所なのですが、中国の剰余定理から、 (1)かつ(2)⇔7^φ(45)≡■(mod 3^(2)*5)となる■が、1つだけ存在します。と書いてありますが、自分は中国の剰余定理は、m、nを互いに素な自然数とする。 x≡a(mod m)かつ x≡b(mod n)を満たす整数xはmnを法として、ただ1つ存在する。と書いてあることから、割る数が違えば、a,bのように余りもちがう場合に、整数xはmnを法として、ただ1つ存在する。と思っていたのですが、 この例証では、■≡7^φ(45) (mod 5)かつ■≡7^φ(45) (mod 3^2)のような余りが 一緒の場合を同時に満たす■を求めているような気がして、中国の剰余定理があてはまるか不安です。 自分の考えの間違いや、余りが一緒の場合でも中国の剰余定理が使えるかを教えてください。お願いします。 本では、■＝1のとき(1)、(2)が成り立つので、■＝1だとわかります。 よって7^φ(45)≡1(mod 45 )となることがしるされました。としめくくっています。
- ベストアンサー
- 数学・算数
- 剰余を求めるプログラム
初心者です。 aのb乗をcで割った時の余りを求めるプログラムを作りたいのですが、うまく作れません。 また、aのb乗はオーバーフローを起こしてしまう巨大な数です。 「一回一回積を計算してから剰余を求めていく」、や「long long int型を使う」などのヒントがありfor文を使って剰余を求めようとしましたがうまくできませんでした。 wikipediaで冪剰余について調べましたが関数を使わないでやってみるとのことなので関数を使わないで剰余を求めるプログラムを組むのはどうすればいいでしょうか？
- ベストアンサー
- C・C++・C#
- 初級シスアド-チェックディジット
こんにちは、問題でどうしても分からないところがありますのでお助けください。 問題 データの誤りを発見するために、次の方法によって、誤り検出コードを付加することにした。出力データがN2=7、N3=6、N4=2、C=4のとき、N1の値は幾らか。 入力データ ：N1N2N3N4 計算方法 ：C-mod((N1×1+N2×2+N3×3+N4×4),10) ：ここで、mod(x,y)はx/yの剰余 出力データ ：N1N2N3N4C ア 0 イ 2 ウ 4 エ 6 解説 計算方法にそれぞれの値を代入する。 4=mod((N1×1＋7×2+6×3＋2×4),10) 4=mod((N1+40),10) (N1+40)/10の剰余が4という意味である。 したがってN1=4 以上 柏木先生のイメージ＆クレバー方式 初級シスアド P.254より 最後の「したがってN1=4」とありますがなぜ、したがってN1=4になるのかが分かりません。そこまでは理解できます。 よろしくお願い致します。
- ベストアンサー
- 情報処理技術者
お礼
なるほど、ありがとうございます。 明日試してみます。