数学@ふたば
[ホーム]

[掲示板に戻る]
レス送信モード
おなまえ
E-mail
題  名
コメント
添付File []
削除キー(記事の削除用。英数字で8文字以内)

画像ファイル名:1617467817641.jpg-(23463 B)
23463 B無題Name名無し21/04/04(日)01:36:57No.115032+ 10月16日頃消えます
プログラミングと数学
数学の問題をプログラミングで解くも良し
プログラミングにまつわる数学の話をしても良し
なにか作ってもよし
そんな適当なスレがあれば良いなと思ったので立てました
このスレは古いので、もうすぐ消えます。
削除された記事が7件あります.見る
1無題Name名無し 21/04/04(日)01:45:59No.115033+
最近写像12相をプログラムで実装する記事を読んだんだけど、高校の数学で学ぶような組み合わせ論って絶対プログラミングと平行で学んだほうが理解しやすいよなと思った
どう漸化式を立てるか=どうリストを消費するかを考えるセンスが身につくと思う
https://crypto.stanford.edu/~blynn/haskell/count.html
2無題Name名無し 21/04/04(日)22:47:06No.115037+
写像12相というのは初めて聞いた

最初はユークリッドの互除法あたりを書いてみるのがおすすめ
3無題Name名無し 21/04/04(日)23:56:58No.115038+
gcd a 0 = a
gcd a b = gcd b (a `mod` b)
Haskellだと数学の定義通りだね
世界最古のアルゴリズムと言われるだけあってシンプル
4無題Name名無し 21/04/04(日)23:58:57No.115039+
数学の問題をプログラミングで解くというとproject eulerとか競技プログラミングになるんだろうか
5無題Name名無し 21/04/05(月)06:21:08No.115040+
RSA暗号を破壊するとの論文が発表される(も「ほぼ誤報」とみられる)
https://idle.srad.jp/story/21/03/04/210213/

まとめ
https://twitter.com/a4lg/status/1367427805827321858
6無題Name名無し 21/04/05(月)19:46:24No.115042+
modを使って良いんなら筆算による四則演算も
アルゴリズムとして書けるからそっちのが古い
希ガス
7無題Name名無し 21/04/05(月)23:36:23No.115043+
>RSA暗号を破壊するとの論文が発表される(も「ほぼ誤報」とみられる)
量子コンピュータが普及するまでは今の暗号技術には頑張って欲しいね
8無題Name名無し 21/04/06(火)06:41:50No.115045+
言語を指定しないところを見ると
アルゴリズムだな
9無題Name名無し 21/04/09(金)02:06:37No.115047+
書き込みをした人によって削除されました
10無題Name名無し 21/04/09(金)02:08:21No.115048+
動的計画法(DP)を使いこなせるようになりたい
11無題Name名無し 21/04/09(金)14:33:12No.115049+
    1617946392875.png-(86102 B)
86102 B
>動的計画法(DP)を使いこなせるようになりたい
Wikipediaの図が分からせる気無さすぎる
https://ja.wikipedia.org/wiki/ベルマン方程式
12無題Name名無し 21/04/09(金)17:42:29No.115050+
アルゴリズムイントロダクションという教科書に動的計画アルゴリズムの設計方法が載ってたので引用してみる
>動的計画アルゴリズムは以下の4つの段階を経て開発される.
>1. 最適解の構造を特徴づける.
>2. 最適解の値を再帰的に定義する.
>3. (多くの場合にはボトムアップ方式で)最適解の値を計算する.
>4. 計算された情報から1つの最適解を構成する.
13無題Name名無し 21/04/09(金)18:00:25No.115051+
1はちゃんと部分構造最適性があるかチェックしてokだったら2で漸化式として問題を定義
3でメモ化を使って最適解の値を出す(漸化式を解く)プログラムを書く
4はオプション
14無題Name名無し 21/04/13(火)00:24:30No.115056+
計算量って難しいよね
O(n^2)だけどnが小さいからまいっかと思ったら
結局nが大きくなる可能性もでてきたり
15無題Name名無し 21/04/13(火)21:44:11No.115057+
書き込みをした人によって削除されました
16無題Name名無し 21/04/13(火)21:44:31No.115058+
クイックセレクトと組み合わせたクイックソートは
最悪計算量がO(n*log(n))や
O(n^2)にならず、O(n*log(n))や

オーダー上は……
17無題Name名無し 21/04/14(水)18:59:26No.115060+
計算量はループの個数数えたり再帰のグラフを描いたりしておおざっぱに見積もれることも多いけど厳密に出そうとすると漸化式ちゃんと解かなきゃいけないから面倒ね
そういえばマスター定理とかいう強そうな名前の定理があった気がする
18無題Name名無し 21/04/24(土)22:30:51No.115111+
書き込みをした人によって削除されました
19無題Name名無し 21/04/24(土)22:31:28No.115112+
>掛け算も割り算も O(N log(N)) でできてしまいました!
https://qiita.com/square1001/items/1aa12e04934b6e749962

おおおおおおおおおおおおおお……!
20無題Name名無し 21/04/26(月)00:57:22No.115116+
FFTって一種のチートだと思う
21無題Name名無し 21/04/27(火)19:55:17No.115121+
いやFFTまでしてしまったら積が和になるからむしろ普通
22無題Name名無し 21/05/02(日)08:55:27No.115137+
書き込みをした人によって削除されました
23無題Name名無し 21/05/02(日)09:08:13No.115138+
ミラー–ラビン素数判定法で2^60の直近上位の素数を10個列挙してみた、
1152921504606847009
1152921504606847067
1152921504606847081
1152921504606847123
1152921504606847127
1152921504606847189
1152921504606847201
1152921504606847229
1152921504606847253
1152921504606847291

本当に素数かどうかはどうやって確認したらいいんじゃorz
24無題Name名無し 21/05/02(日)22:02:37No.115143+
AKS素数判定法はどうでしょうか
25無題Name名無し 21/05/03(月)00:28:44No.115144+
AKSはオーダーは多項式だけど実用上はかなり遅かったはず
26無題Name名無し 21/05/03(月)00:37:57No.115145+
普通にやると手元のノートPCで5分ぐらいかかるな
まあ元も子もないけど素数の一覧表見るのが一番早いよね
27無題Name名無し 21/05/08(土)18:49:15No.115158+
RSA-100以降のRSA Challenge は全部
数体篩法 (Number Field Sieve Method)
やんけ
https://qiita.com/izutetsuya/items/ff0347d26d1699ae3a94
28無題Name名無し 21/05/08(土)20:16:50No.115159そうだねx1
wolfram alphaが尋常じゃない速度で素数判定してくるけどどういうアルゴリズムなんだろ
予め計算してある値を検索してるだけなのかリアルタイムに判定してるのか
https://www.wolframalpha.com/input/?i=1152921504606847009&lang=ja
29無題Name名無し 21/05/09(日)19:45:05No.115163+
書き込みをした人によって削除されました
30無題Name名無し 21/05/09(日)19:54:09No.115164+
>wolfram alphaが尋常じゃない速度で素数判定してくるけどどういうアルゴリズムなんだろ
WolframAlphaは知らんけどブラウザはミラーラビン素数判定法やAKS素数判定法などを組み合わせて素数を生成している
というのもブラウザはHTTPS(TLS)は暗号化のためにRSAやDSAを用いるから巨大な素数が必要になるんだな
PCやスマホでHTTPSのサイトに訪れる度に内部では巨大な素数を生成しているということだ

https://security.stackexchange.com/questions/176394/how-does-openssl-generate-a-big-prime-number-so-fast
31無題Name名無し 21/05/09(日)20:00:00No.115165+
五次元は、今までの言い方で言うと、次元の数が5である空間です。
五次元は四次元よりさらに次元が増えた空間ですが、その説明の仕方には、人によってさまざまな違いがあります。そのうち比較的簡単なものが、「五次元=無数の時間軸が存在する世界」というものです。この場合の時間軸とは、異なる時間の流れということで、一般的には「パラレルワールド」などという言葉で知られています。
つまり、私たちが暮らす世界とは別の世界がいくつも広がる空間というのが、分かりやすい五次元の理解になります。

ただ、やはり私たち人間にとっては知覚が不能であり、観測して存在を確かめることはできません。あくまで理論上の空間となっています。
32無題Name名無し 21/05/09(日)21:44:22No.115166+
別に
5次元までなら5-2=3次元なので
3次元(どうせ3軸似たり寄ったり)のうちの2軸を残りの1軸に射影でもすれば
観測して存在を確かめることはできませんことにはならない

知覚できるかどうかは5次元目の中身による
そもそも能動的に5次元目の座標を能動的に選べない、とか
残り4次元(射影したら2次元)のコピーが延々続いているなら確かに知覚できないが
そうでなければそうでない
33無題Name名無し 21/05/11(火)00:59:56No.115168+
>WolframAlphaは知らんけどブラウザはミラーラビン素数判定法やAKS素数判定法などを組み合わせて素数を生成している
AKSは遅いしミラー=ラビンは低確率でミスっちゃわない?
wolframalphaでは直には採用してない気がする
34無題Name名無し 21/05/12(水)22:21:07No.115171+
書き込みをした人によって削除されました
35無題Name名無し 21/05/12(水)22:27:16No.115172そうだねx1
>No.115159
公式ドキュメントに内部実装について書いてあるよ
色々なアルゴリズムを組み合わせているっぽいね
https://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#5107
36無題Name名無し 21/05/12(水)23:37:18No.115173+
    1620830238984.jpg-(78720 B)
78720 B
ありがとう
どうやらFactorIntegerって関数みたいね
素数判定と言うより普通に素因数分解してあの速度なのスゴイ
>FactorIntegerは小さな素数を試験的に除算してみる方法とポラード(Pollard) ,ポラード・ロー,楕円曲線および二次ふるい法を交互に試す.
37なーNameなー 21/07/22(木)20:23:54No.115589+
なー

- GazouBBS + futaba-