- ふらっと C#,C♯,C＃（初心者用） Part145
473 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 13:27:02.99 ID:GoK8IDZc0 - 以下のプログラムについて質問お願いいたします。
--- 以下プログラム ---
public static int TwoAdicValuation(ulong x)
=> TwoAdicValuationTable[(x & ~x + 1) % 67];
static readonly int[] TwoAdicValuationTable
= InitializeTwoAdicValuationTable();
static int[] InitializeTwoAdicValuationTable() {
var table = new int[67];
table[0] = -1;
for (var i = 0; i < 64; i++) {
table[(1UL << i) % 67] = i;
}
return table;
}
--- 以上プログラム ---
上記の TwoAdicValuation メソッドは、
・引数 x がゼロのときは -1 を返す
・それ以外の場合、引数 x が 2 で割れる回数を返す
という動作をするようです。
例えば TwoAdicValuation(2*3*5) は 1,
TwoAdicValuation(2*2*2*17) は 3,
TwoAdicValuation(19) は 0,
TwoAdicValuation(0) は -1 を返します。
しかしプログラムを読んでみても、
何がどうなってそのような動作になっているのかどうしても理解できません。
何かお分かりになることがあれば
どんなことでも構いませんので教えていただけないでしょうか。
どうぞよろしくお願いいたします。
|
- ふらっと C#,C♯,C＃（初心者用） Part145
478 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 15:11:25.53 ID:GoK8IDZc0 - >>474-477
ありがとうございます。
色々と実験してみた結果、
x & ~x + 1 が、x と 2で割れる回数が同じ、
1UL << i の形の値になることがわかりました。
ただ、どうして x & ~x + 1 と 1UL << i が
結びつくのかまだ理解できておらず、
67 で割った余りを計算する理由も分かっていないので
引き続き考えてみようと思います。
もし他にもヒントがあれば教えていただけると嬉しいです。
よろしくお願いいたします。
|
- ふらっと C#,C♯,C＃（初心者用） Part145
486 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 18:04:22.31 ID:GoK8IDZc0 - >>479
ありがとうございます。
Ruby を扱う技術が私には無いので
アイディアだけお借りして C# に翻訳してみたところ、
期待通りに動作いたしました。
ちなみに、他の方から実行速度に関するご指摘があったので
オリジナルと比較してみたところ、私の書いたコードでは
オリジナルよりも 250 倍程度時間がかかってしまうようでした。
とはいえ読みやすさは良いプログラムの重要な条件なので、
場面に応じて使い分けるのが良さそうですね。
|
- ふらっと C#,C♯,C＃（初心者用） Part145
487 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 18:04:48.09 ID:GoK8IDZc0 - >>481-482
大変わかりやすいご説明どうもありがとうございます。
>>481
> xとx&(~x +1)の関係を理解するには一旦byteで考えてビット演算を図にして考えてみる
>>482
> x & ~x + 1 は、最下位の1のビットだけ残す計算
いただいたアドバイスを元に↓のような実験をしてみて理解できたと思います。
00101100 (44)
11010011 (~44)
11010100 (~44 + 1)
00000100 (44 & ~44 + 1)
>>481
tableの中身を理解するにはi, table[i], 1UL <<1, (1UL<<1 %67)を0~64の範囲で逐次出力してみる
>>482
> 67で割った余りを求める理由は、2^t を67で割った場合
> tが0〜63の範囲ならユニークな値になる
なるほど！実験してみて、確かにそうなっていることがわかりました。
40 人のクラスの中で同じ誕生日のペアがいる確率は 90% 近いと
聞いたことがあるので、なんだか不思議な感じがします。
>>481
> 64と67の関係は、16と19, 32と37でも同じ結果が得られそう
すごく興味深いです。私も実験してみたところ、
1 と 2、2 と 3、4 と 5、8 と 11 という感じになったのですがあってますか？
また、「16と19, 32と37」というのをさらっと書いてくださっていますが、
これは実際に調べてくださったのですか？
それとも、きちんと数学を勉強していればすぐに分かることなのでしょうか。。。
|
- ふらっと C#,C♯,C＃（初心者用） Part145
488 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 18:05:15.79 ID:GoK8IDZc0 - >>485
> ところでまさかこれ課題じゃねーよな？
学校の課題というわけではないのですが、
本来は自力で解くべきものだと思います（汗）
ごめんなさい。。。。
|
- ふらっと C#,C♯,C＃（初心者用） Part145
494 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 20:51:12.72 ID:GoK8IDZc0 - >>492
> ついになる数はそのビット数の次の素数
レスありがとうございます。
私も最初そのように考えたのですが、
16 の対が 17 ではなく 19 なので
そういうわけではないようなのです。
ちなみに 16 の対が 19 になるというのは
>>481 さんが書いてくださっており、
私のほうでも改めて確認しているので、
間違いではないと思います。
|
- ふらっと C#,C♯,C＃（初心者用） Part145
496 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 22:38:41.75 ID:GoK8IDZc0 - >>495
レスありがとうございます。
フェルマーの小定理について調べてみました。
フェルマーの小定理から分かることとして、p が奇数の素数のとき、
(2^0)%p と (2^(p-1))%p はともに 1 になるようです。
つまり >>482 さんの言葉をお借りするなら、
奇数の素数 p がビット数 n 以下のとき
t が 0〜(n-1) の範囲で変化すると (2^t)%p がユニークにならないため、
ビット数 n の対としてn 以下の奇数の素数は不適切ということになります。
ただ、フェルマーの小定理は p > n のときに (2^t)%p がユニークになることを
保証するものではありませんし、そもそも奇数の素数じゃなくても
ビット数 n の対としてn 以下の数が適切でないのは当たり前な気がするので、
フェルマーの小定理から直ちに欲しい情報が得られるというわけではないようです。
とはいえ、関連しそうな分野が分かっただけでも大きな前進ですので、
もう少し詳しく調べてみようと思います。どうもありがとうございました。
|
- ふらっと C#,C♯,C＃（初心者用） Part145
503 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 9fb9-vPHs)[sage]：2019/11/08(金) 23:28:43.13 ID:GoK8IDZc0 - >>497
レスありがとうございます。
いろいろなビット数 n の対になる数を調べてみると、
必ずしも素数になるとは限らないものの、
調べた範囲では全て p^k（p は素数、k は自然数）の形になっていました。
で、教えていただいたガロア体というのは要素の個数 p^k の集合ということで
ビンゴかと思ったのですが、
どうやら私が考えているのは p^k を法とする剰余環というものらしく、
k = 1 で無い限りガロア体とは本質的に異なるもののようです。
しかし色々と調べれば調べるほどこのあたりの分野から答えが見つかりそうだと
思えてきたので、もう少し頑張ってみようと思います。どうもありがとうございます。
|