プチコン 非公式コミュニティ
トピック
こういち
◆ou0jbJnEJ0Kb
2025/3/22 13:37
2025/3/22 13:37
質問
p進数とは何ですか
以前、mkIIでAKS素数判定法を実装しようとして諦めた(そのときはオイラーのトーシェント関数が分からなかったとかだと思います)んですけど、再度実装しようと調べたら、オイラーのトーシェント関数以前にp進数(p-ary numbersではなくp-adic numbers)上でニュートン法を使う必要があると知りました。
p進数について検索して、なんとなく理解は出来ましたが、
p進数をコンピュータ上でどう表現するのか
p進数を扱うことでどう嬉しいのか
p進数上で高速フーリエ変換が出来るらしいけど、利点はあるのか
というのが分かりません
何か情報を持っている方は居ませんか
p進数について検索して、なんとなく理解は出来ましたが、
p進数をコンピュータ上でどう表現するのか
p進数を扱うことでどう嬉しいのか
p進数上で高速フーリエ変換が出来るらしいけど、利点はあるのか
というのが分かりません
何か情報を持っている方は居ませんか
コメント
こういち
2025/3/22 13:41
◆ou0jbJnEJ0Kb
https://qiita.com:443/qnighy/items/ba7e6cb6e321972bebf2#%E6%95%B4%E6%95%B0%E3%81%AB%E3%82%88%E3%82%8B%E8%BF%91%E4%BC%BC%E8%A8%88%E7%AE%97
AKSに使うのはこれですね。
後で読むとして、SQRのROUNDは多倍長には使えないので、これを使うしかなさそう。
近似とあるので、無理数を誤差なしで表現できるとかではないんでしょうか。(無理数を誤差なしで表現できると嬉しい。Sinc()は無理数なので)
AKSに使うのはこれですね。
後で読むとして、SQRのROUNDは多倍長には使えないので、これを使うしかなさそう。
近似とあるので、無理数を誤差なしで表現できるとかではないんでしょうか。(無理数を誤差なしで表現できると嬉しい。Sinc()は無理数なので)
Soybeanman
2025/4/19 16:33
◆SDLkyXUP6WqK
有限長や循環小数のp進数は定義から有理数の有限回の足し算で表せるので無理数を誤差なく表せるということはないです。(p自体を無理数と見なすのであれば話は変わる)
また、pが2の累乗の場合は元々2進数を扱っていることもあり、効率的にコンピュータ上で表現できるはずです。(2、8、16進数はデフォルトで対応している言語も多い)
しかし、そうでない場合はメモリ効率や速度を犠牲にして表現するか(配列を用意し、仮数部を配列の要素で1桁ずつ表すなど)、内部的には2進数として扱い見た目上はp進数にする(print関数で表示する際に変換する)やり方で行うことになるはずです。
また、pが2の累乗の場合は元々2進数を扱っていることもあり、効率的にコンピュータ上で表現できるはずです。(2、8、16進数はデフォルトで対応している言語も多い)
しかし、そうでない場合はメモリ効率や速度を犠牲にして表現するか(配列を用意し、仮数部を配列の要素で1桁ずつ表すなど)、内部的には2進数として扱い見た目上はp進数にする(print関数で表示する際に変換する)やり方で行うことになるはずです。
Soybeanman
2025/4/19 16:47
◆SDLkyXUP6WqK
FFTについては仰る通り、3進数や5進数用に最適化されたバタフライ演算のような手法があると聞きますが、2進数を扱うコンピュータ上で実装しても処理時間やメモリ効率は2進数でのバタフライ演算と同等か、それ以下になると思われます。(FFTを提供しているパッケージ、ライブラリ等でそのような実装を使っている話は聞いたことがないです)
p進数を扱うことで嬉しいことについてはいろいろあると思いますが、pのn乗で割った余りが分かりやすい(下n桁を見ればよい)のがすぐ思いつくところですね。
p進数を扱うことで嬉しいことについてはいろいろあると思いますが、pのn乗で割った余りが分かりやすい(下n桁を見ればよい)のがすぐ思いつくところですね。
こういち
1日前
◆ou0jbJnEJ0Kb
いくつかの無理数自体を有限の桁数で表現できるのかな…と思ったんですけど、そうではない感じなんですかね？
いや、3^(1/3)を2進数で表してる画像が流れてきて無理数を表現できないかと思ったんですけど、よく見たらこれも無限に続きそうですね。
https://twitter.com:443/fmathsecond/status/1886069803510903153
p進数、剰余はおろか除算もよく分かってない(除算が定義されているかどうかすら知らない)ので、剰余が分かりやすいってのはピンと来てないですね。乗算も怪レい。
いや、3^(1/3)を2進数で表してる画像が流れてきて無理数を表現できないかと思ったんですけど、よく見たらこれも無限に続きそうですね。
https://twitter.com:443/fmathsecond/status/1886069803510903153
p進数、剰余はおろか除算もよく分かってない(除算が定義されているかどうかすら知らない)ので、剰余が分かりやすいってのはピンと来てないですね。乗算も怪レい。
こういち
1日前
◆ou0jbJnEJ0Kb
そんなわけで、調べてみます。
https://blog.miraikan.jst.go.jp/articles/20190315post-339.html
例えば、2の平方根は7進数で表現できるっぽくて、それは無限桁が必要？
実数の
1.41421356…
と何が違うんだろう？
循環小数…と言って良いのかな…で表せるってこと？
https://blog.miraikan.jst.go.jp/articles/20190315post-339.html
例えば、2の平方根は7進数で表現できるっぽくて、それは無限桁が必要？
実数の
1.41421356…
と何が違うんだろう？
循環小数…と言って良いのかな…で表せるってこと？
Soybeanman
1日前
◆SDLkyXUP6WqK
2つ目の記事中の
√2 = ...421216213, ...245450454
は無限長必要な数であることは間違いないですが、循環小数ではないですね。
仮に循環小数であれば、循環部分はどんなp進数でも等比級数の和として表され循環していない部分は有限長の小数なので、この値は分子分母共に整数の分数、つまり有理数となります。
しかし、√2は無理数なので仮定が誤りとわかり、先ほどの表現は循環小数ではないということになります。
√2 = ...421216213, ...245450454
は無限長必要な数であることは間違いないですが、循環小数ではないですね。
仮に循環小数であれば、循環部分はどんなp進数でも等比級数の和として表され循環していない部分は有限長の小数なので、この値は分子分母共に整数の分数、つまり有理数となります。
しかし、√2は無理数なので仮定が誤りとわかり、先ほどの表現は循環小数ではないということになります。
Soybeanman
1日前
◆SDLkyXUP6WqK
>剰余が分かりやすいってのはピンと来てない
例えば、15(10進数)を7で割った余りは1です。この状態では分かりにくいですが、この15を7進数にすると21(7進数)となります。するとどうでしょう。ちょうど1桁目が余りと一致しています。
別の例も見てみます。421(10進数)を8で割った余りは5です。この状態では分かりにくいですが、この421を2進数にすると110100101(2進数)となります。8は2^3なので、n=3となり下3桁を見ると101となっています。これは10進数に直すと5のため、確かに余りと一致しています。8進数に直すと645(8進数)で、こちらはn=1なので1桁目を見ると確かに余りと一致しています。
こんな感じに分かりやすいです。
例えば、15(10進数)を7で割った余りは1です。この状態では分かりにくいですが、この15を7進数にすると21(7進数)となります。するとどうでしょう。ちょうど1桁目が余りと一致しています。
別の例も見てみます。421(10進数)を8で割った余りは5です。この状態では分かりにくいですが、この421を2進数にすると110100101(2進数)となります。8は2^3なので、n=3となり下3桁を見ると101となっています。これは10進数に直すと5のため、確かに余りと一致しています。8進数に直すと645(8進数)で、こちらはn=1なので1桁目を見ると確かに余りと一致しています。
こんな感じに分かりやすいです。
こういち
1日前
◆ou0jbJnEJ0Kb
-1も2進数で無限桁必要だっけ…
…11111
奇しくも2の補数と同じ形。いや、導出方法を考えれば当然か。
https://ja.wikipedia.org/wiki/P%E9%80%B2%E6%95%B0#%E7%95%A5%E5%BC%8F%E3%81%AE%E8%A7%A3%E8%AA%AC
p進数で四則演算も存在するっぽくて、任意のpについて負数の概念も存在するらしい。
2進数の実家感よ…
有限桁の小数範囲で必ず逆数が存在する…らしい(整数範囲が有限桁とは言ってない)
というより、逆数が必ず存在するためにp(素数)なのか…(これはmod pと似てる)
…11111
奇しくも2の補数と同じ形。いや、導出方法を考えれば当然か。
https://ja.wikipedia.org/wiki/P%E9%80%B2%E6%95%B0#%E7%95%A5%E5%BC%8F%E3%81%AE%E8%A7%A3%E8%AA%AC
p進数で四則演算も存在するっぽくて、任意のpについて負数の概念も存在するらしい。
2進数の実家感よ…
有限桁の小数範囲で必ず逆数が存在する…らしい(整数範囲が有限桁とは言ってない)
というより、逆数が必ず存在するためにp(素数)なのか…(これはmod pと似てる)
こういち
1日前
◆ou0jbJnEJ0Kb
逆数を実際に計算してみる。
&b11(3)の逆数は
…010101011
らしい
3倍するには元の数に1桁右シフトした数を足せば良い
…010101011+
…101010110=
…000000001
本当だ。
プログラムで計算してみる。
プログラムの場合、上位のビットを切り捨てれば良い。
OPTION DEFINT
VAR A#=&b010101010101011
VAR B#=3
PRINT FORMAT$("%d*%d=%d",A#,B#,A#*B#AND 32767)
やってることはmod 32768上でのモジュラ逆数と同じ。
https://keisan.casio.jp/exec/system/1589337561
&b11(3)の逆数は
…010101011
らしい
3倍するには元の数に1桁右シフトした数を足せば良い
…010101011+
…101010110=
…000000001
本当だ。
プログラムで計算してみる。
プログラムの場合、上位のビットを切り捨てれば良い。
OPTION DEFINT
VAR A#=&b010101010101011
VAR B#=3
PRINT FORMAT$("%d*%d=%d",A#,B#,A#*B#AND 32767)
やってることはmod 32768上でのモジュラ逆数と同じ。
https://keisan.casio.jp/exec/system/1589337561
こういち
23時間前 ネタバレ
◆ou0jbJnEJ0Kb
こういち
23時間前
◆ou0jbJnEJ0Kb
mod 32768だと偶数の逆数は存在しないんだけど、その場合は小数点を使えば良いのか。
例えば、&b10(2)の逆数は普通に0.1
つまり、&b110(6)の逆数は2の逆数と3の逆数を掛けたものなので
…101010101010101.1
OPTION DEFINT
VAR A#=21845.5
VAR B#=6
PRINT FORMAT$("%f*%d=%d",A#,B#,ROUND(A#*B#)AND 32767)
なかなか面白い。
無理数を誤差なしで表現できる気がしてきた。
正直、(整数)/(2^n)を誤差なしで表現できて離散フーリエ変換が定義できる時点で十分期待できる。(ガウシアンフィルタは(整数)/(2^n)の形なので)
モジュラ逆数は拡張ユークリッドの互除法というアルゴリズムで求まるので、頑張れば2進数上の逆数を求めるプログラムを書けそう。
例えば、&b10(2)の逆数は普通に0.1
つまり、&b110(6)の逆数は2の逆数と3の逆数を掛けたものなので
…101010101010101.1
OPTION DEFINT
VAR A#=21845.5
VAR B#=6
PRINT FORMAT$("%f*%d=%d",A#,B#,ROUND(A#*B#)AND 32767)
なかなか面白い。
無理数を誤差なしで表現できる気がしてきた。
正直、(整数)/(2^n)を誤差なしで表現できて離散フーリエ変換が定義できる時点で十分期待できる。(ガウシアンフィルタは(整数)/(2^n)の形なので)
モジュラ逆数は拡張ユークリッドの互除法というアルゴリズムで求まるので、頑張れば2進数上の逆数を求めるプログラムを書けそう。
こういち
23時間前
◆ou0jbJnEJ0Kb
3^(1/3)を計算してみる。(もちろん実数では無理数)
https://twitter.com:443/fmathsecond/status/1886069803510903153
OPTION DEFINT
VAR A#=379
PRINT FORMAT$("%d*%d*%d=%d",A#,A#,A#,A#*A#*A#AND 1023);
言われて見ればmod 1024上での3の3乗根なんだけど、合成数mod上でn乗根を計算したことないので新鮮(実はフィボナッチ数を計算するためにmod p上で5の平方根を計算しようとしたことはあるけど、計算方法が分からなくて挫折したことがある)
とりあえず、2進数についてはある程度理解できたし、当初の疑問も解決しそうです。
印象としては、剰余環(mod n)と有限小数のハイブリットって感じですね。なんで今まで知らなかったんだろう…
https://twitter.com:443/fmathsecond/status/1886069803510903153
OPTION DEFINT
VAR A#=379
PRINT FORMAT$("%d*%d*%d=%d",A#,A#,A#,A#*A#*A#AND 1023);
言われて見ればmod 1024上での3の3乗根なんだけど、合成数mod上でn乗根を計算したことないので新鮮(実はフィボナッチ数を計算するためにmod p上で5の平方根を計算しようとしたことはあるけど、計算方法が分からなくて挫折したことがある)
とりあえず、2進数についてはある程度理解できたし、当初の疑問も解決しそうです。
印象としては、剰余環(mod n)と有限小数のハイブリットって感じですね。なんで今まで知らなかったんだろう…
こういち
23時間前 ネタバレ
◆ou0jbJnEJ0Kb
Soybeanman
23時間前
◆SDLkyXUP6WqK
>p進数上で剰余という演算を定義できるのか
床関数(小数部分を除く関数)を[x]として、x mod pを以下のように定義できると思います。
x mod p=x - p・[x/p]
xやpが整数でない実数の場合でも上手く拡張できていると思います。
床関数(小数部分を除く関数)を[x]として、x mod pを以下のように定義できると思います。
x mod p=x - p・[x/p]
xやpが整数でない実数の場合でも上手く拡張できていると思います。
Soybeanman
23時間前
◆SDLkyXUP6WqK
>あぁ…今更ながら、Soybeanmanさんが言ってるそれはd-ary(binaryなど)の方な気がします。
ああ、トピックの最初にp-adicって書いてましたね……大変失礼しました。
そちらの方には詳しくないのでちょっとわからないです……
ああ、トピックの最初にp-adicって書いてましたね……大変失礼しました。
そちらの方には詳しくないのでちょっとわからないです……
こういち
23時間前
◆ou0jbJnEJ0Kb
まぁ名前ややこしいので無理もないですね。
ボクも最初AKS実装しようとしたとき、p-aryと思って気にしてなかったので…
しかし、p進数、普通に生きていれば触れることすらない概念なのでどういう書籍で勉強すればいいのか分からないですね。
ボクも最初AKS実装しようとしたとき、p-aryと思って気にしてなかったので…
しかし、p進数、普通に生きていれば触れることすらない概念なのでどういう書籍で勉強すればいいのか分からないですね。
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります