プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
>>658 Kotlin で文字列変換してやる場合 fun main(args: Array<String>) { for (i in 1..999) if (! i.toString().contains('0', false)) println(i) } 数値のままやる場合 fun main(args: Array<String>) { for (i in 1..999) if (i % 10 != 0 && (i < 10 || i / 10 % 10 != 0) && (i < 100 || i / 100 % 10 != 0)) println(i) } http://rio2016.2ch.net/test/read.cgi/math/1510671832/722 お題: n^2-1 = m^5 を満たす自然数 n, m は存在するか? 存在するという人と存在しないという人の両方が存在します >>670 (n, m) = (1, 0) 揚げ足取りはおいておいて、プログラミングで説く問題じゃないよね >>658 python 今回は必要ないかもだけど桁数増えた場合を考え再帰で https://ideone.com/WC8Ksm >>671 まあ自明な解はさておき、その他は見つからないのが不思議です >>673 カタラン予想ですでに存在しないことが証明されているのに何が不思議なのかね >>673 その問題は数学的に解くものではないかな? まあ、コンピュータなら力業でかなりの値を n, m に入れて計算して確認できるけどさ。 >>658 #!/bin/sh seq 999|grep -v 0 >>658 Kotlin数値判定版。こんな風にも書けるなと後で気づいた。 fun f(n: Int): Boolean { var m = n; while (m != 0) { if (m % 10 == 0) return false m = m / 10 } return true } fun main(args: Array<String>) { (1..999).filter(::f).forEach(::println) } 存在するしないをプログラミングで証明するのはお題として良くない log 2 を2進数表記した時の小数点第 n 位から n + 9 位までを求めよ. (1 ≦ n ≦ 10^10) cf. log 2 = 0.10110001... *Sample input* 1 11 10000 31415926 314159265 *Sample output* 1011000101 1100100001 0010110110 1001010110 0111101001 >>680 c++で書いたけど小数第100億位を計算するのに5時間くらいかかりそうorz ライブラリを使えばほとんど何も書かなくて良いけど どこから書くことを求められてるの? >>679 「良くない」じゃなくて「出来ない」でしょ >>684 と思ったけど、普通に全桁計算したら終わらないな Σ { 1 / (2^i × i) } を使って10^10項位までを42bitくらいだけ計算すれば出来るかな? 1/nの周期性を考えないと計算量的に無理? 10^10が微妙に32bitを越えてるのがイヤだねえ >>687 ダメだ ざっと計算量を見積もったらとても5時間じゃ終わらない >>375 xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl fact.casl 1 1 2 6 24 120 720 5040 40320 362880 途 中 省 略 1405006117752879898543142606244511569936384000000000 60415263063373835637355132068513997507264512000000000 2658271574788448768043625811014615890319638528000000000 119622220865480194561963161495657715064383733760000000000 5502622159812088949850305428800254892961651752960000000000 258623241511168180642964355153611979969197632389120000000000 12413915592536072670862289047373375038521486354677760000000000 608281864034267560872252163321295376887552831379210240000000000 30414093201713378043612608166064768844377641568960512000000000000 暇つぶしに書いてみたけど足算掛算割算しかできない 引算は難しすぎるんで諦めた バイナリ法で最適化した結果なんとか1時間あれば10^10位は計算できるようになったがまだ縮められるかな >>680 指数関数のマクローリン展開で試してみたのですが、これは収束が遅すぎますね、それに収束半径を超えてるし… なにか収束の早いよい方法はないものか… 対数関数のマクローリン展開? そりゃ無理だ log 0 が定義されてない >>689 CASLで書いたの? ソースコードは? >>680 log 2 = Σ_[i=1, 2, ...] { 1 / (2^i × i) } 冪剰余 でいける気がしてきた しばらく暇がない 時間が空いたら アセンブラ & C++ & OpenMP でやってみる >>650 (setq aaa '(1 5 10 50 100 500)) (setq ddd 750) (setq jjj 15) (defun bbb (ccc iii) (if (= iii 0) ccc (let (eee) (dolist (fff ccc) (dolist (ggg aaa) (when (<= (+ (apply #'+ fff) ggg) ddd) (push (cons ggg fff) eee)))) (bbb (remove-duplicates (mapcar (lambda (x) (sort (copy-seq x) #'<)) eee) :test 'equal) (1- iii))))) (let* ((kkk (bbb '((0)) jjj)) (lll (mapcar (lambda (x) (remove 0 x)) kkk))) (remove-if-not (lambda (x) (and (= (apply #'+ x) ddd) (= (length x) jjj) (= (length (remove-duplicates x)) (length aaa)) )) lll)) ((1 1 1 1 1 5 5 5 10 10 10 50 50 100 500)) >>650 (setq aaa '(A B C D E)) (defun fff (ddd) (if (null (cdar ddd)) ddd (let (eee) (dolist (jjj ddd) (let ((bbb (car jjj)) (ccc (cdr jjj))) (setq eee (append (mapcar (lambda (x) (cons (cons x bbb) (remove x ccc))) ccc) eee)))) (fff eee)))) (defun iii (kkk) (if (< kkk 2) #'identity #'not)) (let* ((ggg (fff (list (cons nil aaa)))) (hhh (mapcar (lambda (x) (car x)) ggg))) (remove-if-not (lambda (x) (and (funcall (iii (position 'A x)) (> (position 'D x) 1)) (funcall (iii (position 'B x)) (= (position 'A x) 1)) (funcall (iii (position 'C x)) (> (position 'E x) 1)) (funcall (iii (position 'D x)) (= (position 'C x) 1)) (funcall (iii (position 'E x)) (< (position 'B x) 2)))) hhh)) ((D C B E A) (D C E B A) (D C A E B) (D C E A B) (D C A B E) (D C B A E)) >>694 いやいや https://ja.wikipedia.org/wiki/%E5%AF%BE%E6%95%B0 log(1-x) = - Σ((1/n)x^n) に x = -1 を機械的に代入しました、収束半径外ですが、この値は正しいらしい。 >>695 うんCASL 全部で1200行かあ xxx@xxx-VirtualBox:~/casl$ wc -l stdlib.casl bigint.casl fact.casl 274 stdlib.casl 851 bigint.casl 76 fact.casl 1201 合計 ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして 何が何だか分からなくなるよ ld gr5,0,gr1 ld gr6,1,gr1 lad gr4,4,gr1 addl gr4,gr0 st gr4,0,gr1 st gr6,1,gr1 ld gr4,=1 st gr4,2,gr1 st gr0,3,gr1 ld gr6,gr1 ld gr1,0,gr1 st gr5,0,gr1 st gr6,1,gr1 xor gr4,gr4 st gr4,2,gr1 lad gr2,-4,gr2 subl gr2,gr0 st gr2,3,gr1 ld gr0,gr3 >>699 他だ単に対数って言えば log x のこと これをマクローリン展開は無理 log (1-x) のマクローリン展開ならそう書かないと通じない 収束半径の外じゃなくて、収束半径丁度でしょ -log (1-x) のマクローリン展開に、 x = 1/2 を入れると >>696 になる 理解はしてないが、出てきたので貼っとく。 指数対数関数等の超越関数の多倍精度計算 本論文では、 指数対数関数の高精度計算として Taylor 展開に BSA 法を使って高速化する方法提案する。 約 1000 桁以下の精度の計算では、 Taylor 展開を使った計算が Sasaki and Kanada[5] によって、様々な計算 法を比較して最も高速であることが示されているので、 計算時間が問題となるのは、 1000 桁以上の精度の 計算である。 ここで提案した Taylor 展開に BSA 法を適用して高速化した方法と Sasaki and Kanda によっ て提案された方法を 1000 桁を超えた精度で比較し、 その高速性を示した。 211 階乗計算例 10000! の計算を行う。 この計算では、 BSA 法を使うだけでなく、 1600 桁以上の数値に対しては FFT を利用して乗算を行っている。 計算方法 計算時間(msec) BSA 47 従来の方法 3578 このほか、 三角関数、逆三角関数、双曲線関数など簡単な規則で各項の係数が表現でき、 多くの関数がこの 行列の乗算形式に変形できます。Taylor 展開の係数が簡単な規則で表現できない $\tan x$ が例外的に表現できないだけである。 3 まとめ 指数関数や対数関数の Taylor 展開に BSA 法を適用することによって、 BSA を使わない従来の方法に比べ40 %程度の高速化ができた。 対数関数に対しては、 5000 桁程度の精度で最も高速な計算方法として知られた Sasaki and Kanada の方法を超えることを示した。 http://www.kurims.kyoto-u.ac.jp/ ~kyodo/kokyuroku/contents/pdf/1456-24.pdf >>702 たしかに 収束半径は |x < 1| なのでは? とりあえず理解はできた計算方法として、logxの近似値などをaとおいたとき、 logx = a + log(x/e^a)という変形を用いる方法だ。 aが近似値だと、x≒e^aなので良いらしい。 >>705 収束半径は1 収束半径は、収束するエリアと収束しないエリアの境目となる円の半径 収束半径丁度の時は収束する場合もあるししない場合もある >>706 計算する項が少なければ良いわけではなく、 各項の計算時間も重要 exp(x)は、(exp(x/k))^k (kは2ベキ)、とするといいらしい。 k=2なら、括弧内を計算したやつ同士の掛け算。 >>701 なるほどありがとう 怖いもの見たさがあった >>689 えへへ、調べさせてもらったよw 後半は 42! から 50! までの値だね この範囲なら、多数桁×ワンレジスタの計算で済みますね 多数桁×多数桁を実装すれば思いっきり褒めてあげるよ、えへへ:−) >>711 ほい xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl bimul.casl 350306543997676425792 153864088327713953064 53899597027434699691252340823058767026688 >>712 おお、すごい、gmp で確認したがあってるぞ 私はまだ 10進文字列から多数桁型への変換は実装できていない、また仕事ができてしまったなあ >>713 gmpで確かめてるのかあ 俺は確認はclispかrubyでやってるよ 10進文字列からの変換は10倍しながら足しこんでいくだけだから そんなに難しくないでしょ 掛算なしでも(n<<3)+(n<<1)でできるし 逆の10進文字列への変換は割算が必要だから実装するの大変だったなあ これができあがるまではメモリを16進ダンプして計算が合ってるか確かめてた >>696 がよさげだな こういうことだろ? Σ(1/n) >> n 小数にもシフトを適用するとして。 和の誤差がかわかれば、どこまで計算したらいいかわかるがどうやるんだ? 誤差しらべたら、テイラー展開は平均値の定理一般化だったか 数値計算とテイラー展開 ある区間において,関数 f(x)がn 回微分可能であるとし,定数aはこの区間に含まれるものとする.x もこの区間内に含まれるとき, http://math-lab.main.jp/taylor07a.jpg をみたすa とx の間の実数c (a <c <x または x <c <a)が存在する http://math-lab.main.jp/taylor7.html log(1+x)の誤差項、剰余項は、(-1)^(n-1)/n * (x/(1+c))^n らしいので、 -log(1-x)では、1/n * (x/(1+c))^n か。 x=1/2で考えると、この項をなるべく大きくするならc=0で、誤差は(1/n) >> n以下か。ふたたびシフト使用。 まとめると、 log2 - (Σ(1/k) >> k) < (1/n) >> n (級数はn-1までの和) いやあってるか。 A(k) = (1/k)>>kと置くと、 log2 - ΣA(k) < A(n) (級数はn-1までの和) で ΣA(k) (n+1以上の和) < A(n) が成立するのか。 やはり、どこか間違ってるな。 上のとおりだと、log2 - ΣA(k) (級数はn-1までの和)は、 A(n) を含むので、A(n)より小さいはずがない。 >>701 >ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして何が何だか分からなくなるよ 対象のコード書いてるときの「感覚」をハードディスクかどこかに貯めておいて、 必要に応じてまた脳みそに搭載できるようにならないものか… そのマシン語の一行一行にも、もともとはなんらかの意味的構造があったのに、それが消えてしまうなんて損失以外のなにものでもないよね >>680 >>696 の方法で作ってみました n=10^10の時に48.3秒くらいです >>723 はHaswell (4770) 3.4GHz固定での結果で Skylake (6700K) 定格だと38.4秒でした ちゃんとCPUも進化してるんですね >>681 >>690 C++だとどうやって計算してるかが非常に気になります 32bitを越える値同士の乗算(結果が64bitを越える)部分 アセンブラだと 64bit x 64bit ===> 128bit 128bit / 64bit ===> 64bit 等があるのでそれを使っちゃってますが 冪剰余を求めるのに (a * b) % c みたいなのがたくさん出てきませんか? aもbもcも32bitの範囲を微妙に越えてて 誤差部分の間違いが判った。これでよさげだ。 ただし誤差評価を荒くやってはダメそうだが。一番最後の行のところ。 誤差項ありのマクローリン展開は、0<=c<=xが存在して f(x) = Σ x^k * f(k)(0)/k! (kは0からn-1まで) + x^n * f(n)(c)/n! f(x) = -log(1-x)のn次導関数は、(n-1)!/(1-x)^n。 このときマクローリン展開は誤差項は x^n / (n*(1-c)^n) x=1/2ならば、c=1/2のとき最大で、1/n これが収束速いようだ。 log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15) log((x+1)/(x-1)) = log((1+1/x)/(1-1/x)) = 2 Σ 1/((2n+1)*x^(2n+1)) >>728 1/log(2) ≒ 3.32 1/2log(161)+1/2log(49)+1/2log(31) ≒ 0.85 なので、計算に必要な項数は1/4程度 でも、1つの項の計算には時間がかかる log(1-x)のマクローリン展開に0.5を入れた物は 分母が i * 2^i だから速く計算できるのだ >>727 残りの項を等比数列と見なせば 簡単に誤差の上限が出ます >>724 Haswellで33.96秒に縮まりました シングルスレッドだと182.54秒で5.3倍 HTTが効くということは、 まだ多少改善の余地がありそう 一番内側のループは vmulpd vmulpd vroundpd vfmsub213pd vfmsub132pd vsubpd なんと浮動小数点で計算してます n=10000000000の時は 0000010101 でした 出題者さま、合ってます? また、たまたまですが n=10000000004では 0101010101 n=10000000005では 1010101010 になります 一番内側のループのコード http://fast-uploader.com/file/7067434368942/ PORT5がガラ空きで、処理のほとんどがPORT0,PORT1 こんなんでもHTTが効く やっぱり浮動小数点はレイテンシがデカい AVX512になれば レジスタの数が倍になるので 8パラにしてレイテンシを隠蔽出来るんだけど もちろんレジスタ長が倍になる方が大きい >>728 は後半部分が間違ってるか。log((x+1)/x) = log(1+1/x) の展開を用いるのが正解で。 log(・)の中身を1に近づけた方が収束が早くなるが、 こういった分解 log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15)はどうみつけるのか。 これは数値が(x+1)/x の形だけど、(x+1)/(x-1)の分解もあるのか。こっちだと計算するベキ項が一つ飛ばしにできる。>>728 のように。 2 = (81/80)^3 * (25/24)^5 * (16/15)^7 3 と 5 の指数の合計が0になる組み合わせを検索すれば良い log(81/80) = log(162/160) = log((161+1)/(161-1)) わかってて書いてるんだと思ったが >>729 のlogの中身はこの値 >>728 はそういうことか。みつけたやつのコピペで、そのとき考慮はしてなかった。 指数も固定でなくていいはずで、 16/15よりかはたとえば1001/1000のほうが1に近いからそういうのはいくらでも見つけられるのかとおもった。 分母分子の素因数の数と同じ項数が必要 例えば素因数が 2, 3, 5, 7 の4種類の場合、 1個差もしくは2個差のペアを4個探す 例えば 126/125 225/224 2401/2400 4375/4374 これらを適当に掛け算して2^nになるようにすると 項が4個の式がみつかる 分母、分子とも 2, 3, 5, 7, 11, 13, 17 のみしか素因数を持たない形の場合、 以下が一番計算する項の数が少ないようです log(2) = 72*log(126/125)+27*log(225/224)-19*log(2401/2400)+31*log(4375/4374) >>740 その数値を検索すると、音楽のコンマというのが出てくる。関係あったり理論があったりするのか。 A.D. Fokker: Unison Vectors and Periodicity Blocks http://www.huygens-fokker.org/docs/fokkerpb.html List of 7-prime limit accidentals - The?Sagittal?forum http://forum.sagittal.org/viewtopic.php?f=6& ;t=252 log(2)とは無関係で、単に一個差のやつで適当な素因数分解できるやつに名前がついてるだけ? An Investigation into the Extraction of Melodic and Harmonic Features from Digital Audio unit interval name 4375/4374 Ragisma 2401/2400 Breedsma 225/224 Septimal Kleisma 145/144 Difference between 29:16 and 9:5 126/125 Small Septimal Semicomma 121/120 Undecimal Seconds Comma 81/80 Syntonic Comma http://scholar.sun.ac.za/handle/10019.1/100826 log2のほうは、分子・分母の素因数分解が似通ってないと成立しないってことで、 音楽のほうは小さい素数に限定して一個差ペアを求めたと理解。 log2のほうは、共通の素数で大きいやつを最初に固定すれば考えれば、よさげかと。 お題。横x[cm]、縦y[cm]の長方形のステンレスの1枚の板がある。この板からm枚の複数の長方形の部材を切り出す。 部材のサイズは配列で与えられる。 部材のサイズ(縦×横)はそれぞれだいたい決まっているが、1cm程度変わってもよい。 ただし、部材の縦または横が変わるとそれぞれ一点減点となる。 すべての部材を切り出すことができれば、減点がなるべく少ない方法の切り出し方法を出力せよ。 すべての部材を切り出すことができなければ、面積が広い順になるべくたくさん部材を切り出せ。 テストデータ。 x=10, y=10, { {5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5} } x=5, y=12 { {2, 5}, {3, 3}, {2,9}, {3, 2}, {4,3} } 部材の縦と横は入れ替わってもよい。 可能ならば、切り出し方法をSVG形式で出力せよ。 切り出し方法は、 切り出す部材のx座標、y座標、幅、高さ のリストとして出力せよ。 切り出しに余裕があるときは、なるべくx座標の大きい方、y座標の大きい方を残すようにせよ。 人間用のパズルで、斜めにしないと解けないのとかありそう 問題文の条件が“だいたい”“なるべく”なんて あいまい表現だらけ これでプログラミングの問題かよ 斜めは考えなくてもよい。 訂正。 すべての部材を切り出すことができれば、減点が最小である切り出し方法を出力せよ。 すべての部材を切り出すことができなければ、面積が広い順に切り出せる部材の面積が最大になるよう部材を切り出せ。 切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。 >>732 そこにある3つとも正解です 当初は L = Σ1/(k*2^k) として 2^n * L の小数部分を愚直に求める方法を想定していました 普通に多倍長で計算したら計算量的に終わらないですよね? n=314159265を求めるのに 冪剰余は使ってますよね? おそらく私も同じような方法と思います FMA3命令とOpenMPで高速化してるだけで 愚直という言い方は良く割りませんでしたね 仰る通り冪剰余は用います 再出題。横cx[cm]、縦cy[cm]の長方形または正方形のステンレスの1枚の板がある。この板からm枚の複数の長方形または正方形の部材を切り出す。 m枚の部材のサイズは(縦, 横)の配列で与えられる。 すべての部材を切り出すことができれば、切り出し方法を出力せよ。切り出しが不可能ならば「impossible」と出力せよ。 切り出し方法は、 (部材インデックス、部材の一番左のx座標、部材の一番上のy座標、幅、高さ) のリストとして出力せよ。斜めの方向の切り出しは考えなくてもよい。 切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。ただし、x軸は右の向き、y軸は下向きとする。 テストデータ。 cx=10, cy=10, m=5, {5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5} cx=5, cy=12, m=5, {2, 5}, {3, 3}, {2, 8}, {3, 2}, {4, 3} 頭の悪そうな文章だな 正方形⊂長方形 ステンレスの板の座標上の位置指定が無い 余裕がある場合の条件の意味が曖昧 ステンレスの板の左上座標は原点にあるものとする。 切り出しは、可能な限り、座標の小さい方を優先する(「余裕」の意味)。 >>758 相変わらず曖昧な表現 全ての長方形の上辺と左辺がどこかに接していれば良いのか? そうじゃないのか? このような条件のを1個だけ見つければ良いのか すべて見つけるのか 全ての部材の上辺と左辺が別の部材の辺、もしくは、元の板の端に接していること。 このような条件のをすべて見つけること。 なんか、工学関係でこのような問題があるらしいが、まだ解決策があるかどうかわからん。これが解ければ、実用化待ったなし。 実用性なら 切りやすさとか余り素材の形状とか そういうのが重要だろうに 問題として中途半端過ぎる なにやら揉めてますね そろそろうんざりなので次のお題どうぞ ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる