プログラミングのお題スレ Part9

1 名前：デフォルトの名無しさん mailto:sage [2016/12/01(木) 16:58:30.97 ID:gTkHDluD.net] プログラミングのお題スレです。 前スレ プログラミングのお題スレ Part8©2ch.net echo.2ch.net/test/read.cgi/tech/1444216746/ 【出題と回答例】 1 名前：デフォルトの名無しさん 　　お題：お題本文 2 名前：デフォルトの名無しさん 　　>>1 使用言語 　　回答本文 【ソースコードが長くなったら】 (オンラインでコードを実行できる) ideone.com/ codepad.org/ compileonline.com/ rextester.com/runcode runnable.com/ code.hackerearth.com/ melpon.org/wandbox https://paiza.io/ 宿題は宿題スレがあるのでそちらへ。 652 名前：デフォルトの名無しさん mailto:sage [2017/11/16(木) 15:03:27.99 ID:/xRbPsNU.net] >>628 可笑しいところ教えて！ 653 名前：デフォルトの名無しさん mailto:sage [2017/11/16(木) 15:46:11.61 ID:9+S8V57k.net] (3^2)^2 = 3^4 ((3^2)^2)^2 = 3^8 だから、3^(2*3) とかやっちゃダメだろ あと、 3×5÷7 = 15÷7 ≠ 2 654 名前：デフォルトの名無しさん mailto:sage [2017/11/16(木) 15:59:11.96 ID:/xRbPsNU.net] >>631 あー、俺がタコでした。 まぁ、前段は表示系の問題だと思うお。 後者は割り算が全部悪い。 浮動小数で比較したくないんだよなぁ。悩ましい。 655 名前：デフォルトの名無しさん mailto:sage [2017/11/16(木) 16:39:35.92 ID:9+S8V57k.net] 有理数クラスを作るのだ 656 名前：デフォルトの名無しさん mailto:sage [2017/11/16(木) 17:43:36.30 ID:/xRbPsNU.net] 有理数の法則がよくわかってないし、デカイ。 ままならんなー。 657 名前：デフォルトの名無しさん mailto:sage [2017/11/16(木) 18:03:35.37 ID:9+S8V57k.net] (a/b) + (c/d) = (ad + bc) / bd (a/b) - (c/d) = (ad - bc) / bd (a/b) * (c/d) = ac / bd (a/b) / (c/d) = ad / bc (a/b) = (c/d) <===> ad = bc 分子 : 整数 分母 : 0以外の整数 658 名前：デフォルトの名無しさん mailto:sage [2017/11/16(木) 21:25:39.77 ID:/xRbPsNU.net] 数学ムズイ。。。 PGも算数で解いてるからな。 659 名前：デフォルトの名無しさん mailto:sage [2017/11/17(金) 00:16:40.63 ID:5DUWZGJy.net] 紙とペ 660 名前：ンで考えてみたところ 0以外の任意の整数なら3,5,7で表わせるから問題として不適なのでは？ [] [ここ壊れてます] 661 名前：デフォルトの名無しさん mailto:sage [2017/11/17(金) 00:20:03.76 ID:M2EFWWXH.net] 17 662 名前：デフォルトの名無しさん [2017/11/17(金) 10:03:52.61 ID:oe8UBfUe.net] >>637 3,5,7は１回までって回数制限があるから 表せる数は限られるよ。 663 名前：デフォルトの名無しさん mailto:sage [2017/11/17(金) 10:44:12.02 ID:a6b9gyRQ.net] 17が出来ない 664 名前：デフォルトの名無しさん mailto:sage [2017/11/17(金) 19:35:00.15 ID:5DUWZGJy.net] ああ、本当だ。17はどうやっても作れないね しかしこれをどうやってコードで計算すんだろう ^2があるから全探査はできないし 自分は「+または-」をいくつ使うかで場合分けして一個一個可能性を消していったんだけれども 665 名前：デフォルトの名無しさん mailto:sage [2017/11/17(金) 20:04:40.56 ID:M2EFWWXH.net] コードはアップしないけど出来たよ 666 名前：デフォルトの名無しさん mailto:sage [2017/11/17(金) 20:07:16.14 ID:M2EFWWXH.net] 独自有理数クラス 演算回数を1回ずつ増やしていって、 出来た値に対応するフラグをセット 667 名前：デフォルトの名無しさん mailto:sage [2017/11/17(金) 20:09:06.68 ID:M2EFWWXH.net] 数値をstd::multisetで保持 演算n回目のmultisetをstd::setで保持 668 名前：デフォルトの名無しさん [2017/11/18(土) 17:51:34.79 ID:6foiYhRZ.net] ABC4D -E3FG ----- 77777 A〜G は、1〜9 の異なる数字。 ただし、3, 4 ではない 669 名前：デフォルトの名無しさん mailto:sage [2017/11/18(土) 17:56:36.72 ID:R4dFDjUs.net] はい、そうですか。 670 名前：デフォルトの名無しさん mailto:sage [2017/11/18(土) 19:08:28.21 ID:8fhXEikQ.net] >>645 Java 2年前の問題と俺の回答 peace.2ch.net/test/read.cgi/tech/1429195275/451 を改造したもの (50-54行目と標準入力) https://ideone.com/2chU62 671 名前：デフォルトの名無しさん mailto:sage [2017/11/18(土) 19:44:36.57 ID:oFg54zrO.net] >>645 Ruby f = ->a, b, c, d, e, f, g{10000*a + 1000*b + 100*c + d - (1000*e + 10*f + g) == 78037} [1, 2, 5, 6, 7, 8, 9].permutation{|a| puts "%d%d%d4%d - %d3%d%d == 77777" % a if f[*a]} #=>87142 - 9365 == 77777 672 名前：デフォルトの名無しさん mailto:sage [2017/11/18(土) 20:40:01.77 ID:6foiYhRZ.net] >>647 何も、そこまで作り込まなくても良いだろw 色々な覆面算に対応するため、汎用的に書いたのか 673 名前：デフォルトの名無しさん [2017/11/19(日) 22:39:02.74 ID:oda4btU4.net] 500, 100, 50, 10, 5, 1円のすべての種類の硬貨を、1枚以上使って、 合計15枚で750円にする時、10円硬貨は何枚になるか？ A〜E の5人のランナーが走った結果、 完走したのは、1着とべべの2人で、残りの3人は、途中で棄権した ここで、完走した2人は、必ず真実を言い、 棄権した3人は、必ず嘘をつくものとする (つまり、事実に対して、真偽値を取る) A: D は棄権した B: A は、べべだった C: E は棄権した D: C は、べべだった E: B は完走した A〜Eがこのように答えた時、1着は誰か？ 674 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 01:25:03.39 ID:Z32/GYkn.net] 先に答えやそれに至る式がわかっててコードに書き直すだけになっちゃうから 数学的に道筋立てて答えが出せるものはあんまりおもしろくないんだよな 675 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 03:34:46.27 ID:GkhyFhEh.net] アルゴリズムとは、数式の完全コピー 最初に、数式を考えて、その数式が間違っていれば、 撃墜モードでは、そこを突かれて撃墜される 結局、数式の証明が大事。 証明に、勘違いが無いかどうか 676 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 11:24:27.08 ID:7i/OQPcC.net] べべってなんぞ？ 677 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 11:38:36.82 ID:OJcNabXy.net] >>653 たぶんこの場合は大阪の方言 678 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 11:45:30.45 ID:7i/OQPcC.net] 俺地方の人間だからわかんない。 679 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 18:24:16.80 ID:Slkhafwt.net] べべって最下位のことじゃないか どべ 680 名前：デフォルトの名無しさん [2017/11/21(火) 23:50:05.58 ID:zUV8sDjk.net] >>645 こんなのどうかな。Kotlin で作った。 https://paiza.io/projects/ObrsYN_Z7G44yy-pOlZh_Q 681 名前：デフォルトの名無しさん [2017/11/23(木) 10:05:44.85 ID:zWeuVerg.net] お題 1から99を表示する お題：1から999を出力する ただし0を含む数は除く 682 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 10:11:40.40 ID:TrZHjzbP.net] >>658 1000.times{|i|p i unless i.to_s[?0]} 683 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 12:15:31.91 ID:6AL/1aep.net] >>658 GNU Smalltalk 1 to: 999 do: [:n | (n asString includes: $0) ifFalse: [n displayNl]] 684 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 12:38:42.26 ID:KUvGqrz8.net] >>658 F# let () = seq { 1..999 } |> Seq.iter (printfn "%d") 685 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 12:40:24.86 ID:KUvGqrz8.net] >>661 すまん、問題よく読んでなかった･･･ 686 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 13:30:23.43 ID:jBvfUrCY.net] >>658 https://ideone.com/unKY2z C++。ほかの言語だと一行で書けるんだけどなぁ。 まぁ過去に比べれば大分短くなったけど。 687 名前：デフォルトの名無しさん [2017/11/23(木) 15:45:02.09 ID:ys+VuKpG.net] >>658 文字も数もその場に合わせて適当に解釈してくれる言語だと楽だね。 perl だとこれでできる。 for(1..999){print"$_\n"unless(/0/)} 688 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 16:16:10.88 ID:JcpJJmmU.net] >>658 @Mathematica nListWithoutZero[n_]:=n// 　Range[1,#]&// 　Map[ToString,#]&// 　StringCases[#,RegularExpression["^(?!.*0).*$"]]&// 　Flatten; In[1] := nListWithoutZero[999] Out[1] = (略) 689 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 16:34:54.15 ID:2sNCCDGP.net] >>658 ダメだお題の意味がわからん 降参 690 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 16:42:00.54 ID:QTAUjuBR.net] >>658 rust https://ideone.com/NFrvi7 fn main() { println!("{:?}", (1..1000).filter(|i| !i.to_string().contains("0")).collect::<Vec<_>>()) } 691 名前：デフォルトの名無しさん [2017/11/23(木) 16:46:25.38 ID:ys+VuKpG.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) } 692 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 17:05:13.53 ID:fGVRHt7J.net] >>658 >>668 同じく数値のままやる場合 https://ideone.com/xySZgM 693 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 17:08:37.18 ID:fGVRHt7J.net] rio2016.2ch.net/test/read.cgi/math/1510671832/722 お題： n^2-1 = m^5 を満たす自然数 n, m は存在するか？ 存在するという人と存在しないという人の両方が存在します 694 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 17:18:38.32 ID:TrZHjzbP.net] >>670 (n, m) = (1, 0) 揚げ足取りはおいておいて、プログラミングで説く問題じゃないよね 695 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 18:35:09.23 ID:zveldNvP.net] >>658 python 今回は必要ないかもだけど桁数増えた場合を考え再帰で https://ideone.com/WC8Ksm 696 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 19:09:48.15 ID:fGVRHt7J.net] >>671 まあ自明な解はさておき、その他は見つからないのが不思議です 697 名前： [] [ここ壊れてます] 698 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 20:21:54.46 ID:/mQ4CZGQ.net] >>673 カタラン予想ですでに存在しないことが証明されているのに何が不思議なのかね 699 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 20:24:10.50 ID:hjkeK8jf.net] >>673 その問題は数学的に解くものではないかな? まあ、コンピュータなら力業でかなりの値を n, m に入れて計算して確認できるけどさ。 700 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 20:56:22.87 ID:fGVRHt7J.net] >>674 カタラン予想というのがあるんですね、ありがとうございます！ https://en.wikipedia.org/wiki/Catalan%27s_conjecture 701 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 21:05:28.66 ID:uF7hi9HH.net] >>658 #!/bin/sh seq 999|grep -v 0 702 名前：668 [2017/11/24(金) 06:21:36.98 ID:8wyGH9pr.net] >>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) } 703 名前：デフォルトの名無しさん mailto:sage [2017/11/24(金) 07:42:25.55 ID:MEHEP0+e.net] 存在するしないをプログラミングで証明するのはお題として良くない 704 名前：デフォルトの名無しさん mailto:sage [2017/11/24(金) 20:42:02.54 ID:G34PGfZh.net] 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 705 名前：デフォルトの名無しさん mailto:sage [2017/11/24(金) 23:31:00.22 ID:r53+zpq0.net] >>680 c++で書いたけど小数第100億位を計算するのに5時間くらいかかりそうorz 706 名前： mailto:sage [2017/11/25(土) 00:04:03.20 ID:ROI3Hzdd.net] >>681 もう初手に届くとは劇速ですね 707 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 06:53:37.62 ID:Uo3oYb2P.net] 無条件でlogって書いたら普通自然対数だろ 708 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 07:01:13.88 ID:Uo3oYb2P.net] ライブラリを使えばほとんど何も書かなくて良いけど どこから書くことを求められてるの？ 709 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 07:03:54.53 ID:Uo3oYb2P.net] >>679 「良くない」じゃなくて「出来ない」でしょ 710 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 07:16:55.64 ID:Uo3oYb2P.net] >>684 と思ったけど、普通に全桁計算したら終わらないな 711 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 07:34:12.57 ID:Uo3oYb2P.net] Σ { 1 / (2^i × i) } を使って10^10項位までを42bitくらいだけ計算すれば出来るかな？ 1/nの周期性を考えないと計算量的に無理？ 10^10が微妙に32bitを越えてるのがイヤだねえ 712 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 08:21:38.07 ID:Uo3oYb2P.net] >>687 ダメだ ざっと計算量を見積もったらとても5時間じゃ終わらない 713 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 13:10:34.24 ID:l6j6CjYT.net] >>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 714 名前：258623241511168180642964355153611979969197632389120000000000 12413915592536072670862289047373375038521486354677760000000000 608281864034267560872252163321295376887552831379210240000000000 30414093201713378043612608166064768844377641568960512000000000000 暇つぶしに書いてみたけど足算掛算割算しかできない 引算は難しすぎるんで諦めた [] [ここ壊れてます] 715 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 16:35:37.76 ID:J1zvm3XW.net] バイナリ法で最適化した結果なんとか1時間あれば10^10位は計算できるようになったがまだ縮められるかな 716 名前： mailto:sage [2017/11/25(土) 16:41:37.19 ID:ROI3Hzdd.net] 備忘メモ rio2016.2ch.net/test/read.cgi/math/1510671832/890 ちゃんとお題にして出題しなおします 717 名前： mailto:sage [2017/11/25(土) 21:49:51.82 ID:ROI3Hzdd.net] >>680 指数関数のマクローリン展開で試してみたのですが、これは収束が遅すぎますね、それに収束半径を超えてるし… なにか収束の早いよい方法はないものか… 718 名前： mailto:sage [2017/11/25(土) 21:54:37.24 ID:ROI3Hzdd.net] >>692 ×指数関数 ○対数関数 719 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 22:58:19.91 ID:yyAYDlfh.net] 対数関数のマクローリン展開？ そりゃ無理だ log 0 が定義されてない 720 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 23:12:41.85 ID:FRsJtlII.net] >>689 CASLで書いたの? ソースコードは? 721 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 23:38:41.06 ID:yyAYDlfh.net] >>680 log 2 = Σ_[i=1, 2, ...] { 1 / (2^i × i) } 冪剰余 でいける気がしてきた しばらく暇がない 時間が空いたら アセンブラ & C++ & OpenMP でやってみる 722 名前：デフォルトの名無しさん [2017/11/26(日) 02:33:02.82 ID:T275kIwU.net] >>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)) 723 名前：デフォルトの名無しさん [2017/11/26(日) 02:34:12.86 ID:T275kIwU.net] >>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)) 724 名前： mailto:sage [2017/11/26(日) 11:18:11.00 ID:rNgJnhxq.net] >>694 いやいや https://ja.wikipedia.org/wiki/%E5%AF%BE%E6%95%B0 log(1-x) = - Σ((1/n)x^n) に x = -1 を機械的に代入しました、収束半径外ですが、この値は正しいらしい。 725 名前：デフォルトの名無しさん [2017/11/26(日) 12:12:20.72 ID:ffy1o2uq.net] お題 ASCIIコード表が載っている� 726 名前：{をあげよ [] [ここ壊れてます] 727 名前：デフォルトの名無しさん mailto:sage [2017/11/26(日) 12:35:31.87 ID:tJzac9f2.net] >>695 うんCASL 全部で1200行かあ ｘｘｘ@ｘｘｘ-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 728 名前：デフォルトの名無しさん mailto:sage [2017/11/26(日) 12:35:43.37 ID:WgExDItE.net] >>699 他だ単に対数って言えば log x のこと これをマクローリン展開は無理 log (1-x) のマクローリン展開ならそう書かないと通じない 収束半径の外じゃなくて、収束半径丁度でしょ 729 名前：デフォルトの名無しさん mailto:sage [2017/11/26(日) 12:49:31.90 ID:WgExDItE.net] -log (1-x) のマクローリン展開に、 x = 1/2 を入れると >>696 になる 730 名前：デフォルトの名無しさん [2017/11/26(日) 13:21:30.43 ID:jiBTwXK4.net] 理解はしてないが、出てきたので貼っとく。 指数対数関数等の超越関数の多倍精度計算 本論文では、 指数対数関数の高精度計算として 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 の方法を超えることを示した。 www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1456-24.pdf 731 名前： mailto:sage [2017/11/26(日) 13:37:36.96 ID:rNgJnhxq.net] >>702 たしかに 収束半径は |x < 1| なのでは？ 732 名前：デフォルトの名無しさん [2017/11/26(日) 13:44:48.59 ID:jiBTwXK4.net] とりあえず理解はできた計算方法として、logxの近似値などをaとおいたとき、 logx = a + log(x/e^a)という変形を用いる方法だ。 aが近似値だと、x≒e^aなので良いらしい。 733 名前：デフォルトの名無しさん mailto:sage [2017/11/26(日) 13:58:53.69 ID:WgExDItE.net] >>705 収束半径は1 収束半径は、収束するエリアと収束しないエリアの境目となる円の半径 収束半径丁度の時は収束する場合もあるししない場合もある 734 名前：デフォルトの名無しさん mailto:sage [2017/11/26(日) 14:20:52.91 ID:WgExDItE.net] >>706 計算する項が少なければ良いわけではなく、 各項の計算時間も重要 735 名前：デフォルトの名無しさん [2017/11/26(日) 15:04:05.33 ID:jiBTwXK4.net] exp(x)は、(exp(x/k))^k (kは2ベキ)、とするといいらしい。 k=2なら、括弧内を計算したやつ同士 736 名前：の掛け算。 [] [ここ壊れてます] 737 名前：695 mailto:sage [2017/11/26(日) 18:33:11.28 ID:XHzckn9a.net] >>701 なるほどありがとう 怖いもの見たさがあった 738 名前： mailto:sage [2017/11/26(日) 20:54:13.61 ID:rNgJnhxq.net] >>689 えへへ、調べさせてもらったよｗ 後半は 42! から 50! までの値だね この範囲なら、多数桁×ワンレジスタの計算で済みますね 多数桁×多数桁を実装すれば思いっきり褒めてあげるよ、えへへ：−） 739 名前：デフォルトの名無しさん mailto:sage [2017/11/26(日) 21:11:54.45 ID:tJzac9f2.net] >>711 ほい xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl bimul.casl 350306543997676425792 153864088327713953064 53899597027434699691252340823058767026688 740 名前： mailto:sage [2017/11/26(日) 21:47:36.23 ID:rNgJnhxq.net] >>712 おお、すごい、gmp で確認したがあってるぞ 私はまだ 10進文字列から多数桁型への変換は実装できていない、また仕事ができてしまったなあ 741 名前：デフォルトの名無しさん mailto:sage [2017/11/26(日) 23:01:31.48 ID:tJzac9f2.net] >>713 gmpで確かめてるのかあ 俺は確認はclispかrubyでやってるよ 10進文字列からの変換は10倍しながら足しこんでいくだけだから そんなに難しくないでしょ 掛算なしでも(n<<3)+(n<<1)でできるし 逆の10進文字列への変換は割算が必要だから実装するの大変だったなあ これができあがるまではメモリを16進ダンプして計算が合ってるか確かめてた 742 名前：デフォルトの名無しさん [2017/11/27(月) 06:49:43.60 ID:qqP20rnw.net] >>696がよさげだな こういうことだろ? Σ(1/n) >> n 小数にもシフトを適用するとして。 和の誤差がかわかれば、どこまで計算したらいいかわかるがどうやるんだ? 743 名前：デフォルトの名無しさん [2017/11/27(月) 07:17:24.36 ID:qqP20rnw.net] 誤差しらべたら、テイラー展開は平均値の定理一般化だったか 数値計算とテイラー展開 ある区間において,関数 f(x)がn 回微分可能であるとし,定数aはこの区間に含まれるものとする.x もこの区間内に含まれるとき, math-lab.main.jp/taylor07a.jpg をみたすa とx の間の実数c (a <c <x または x <c <a)が存在する math-lab.main.jp/taylor7.html 744 名前：デフォルトの名無しさん [2017/11/27(月) 07:40:30.25 ID:qqP20rnw.net] 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以下か。ふたたびシフト使用。 745 名前：デフォルトの名無しさん [2017/11/27(月) 07:44:14.48 ID:qqP20rnw.net] まとめると、 log2 - (Σ(1/k) >> k) < (1/n) >> n 　(級数はn-1までの和) 746 名前：デフォルトの名無しさん [2017/11/27(月) 08:54:49.81 ID:qqP20rnw.net] どこか間違えてる　次数か? 747 名前：デフォルトの名無しさん [2017/11/27(月) 08:59:59.63 ID:qqP20rnw.net] いやあってるか。 A(k) = (1/k)>>kと置くと、 log2 - ΣA(k) < A(n) (級数はn-1までの和)　で ΣA(k)　(n+1以上の和) < A(n) が成立するのか。 748 名前：デフォルトの名無しさん [2017/11/27(月) 10:11:23.24 ID:qqP20rnw.net] やはり、どこか間違ってるな。 上のとおりだと、log2 - ΣA(k)　(級数はn-1までの和)は、 A(n) を含むので、A(n)より小さいはずがない。 749 名前： mailto:sage [2017/11/27(月) 23:07:50.22 ID:b0u4s5jJ.net] >>701 ＞ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして何が何だか分からなくなるよ 対象のコード書いてるときの「感覚」をハードディスクかどこかに貯めておいて、 必要に応じてまた脳みそに搭載できるようにならないものか… そのマシン語の一行一行にも、もともとはなんらかの意味的構造があったのに、それが消えてしまうなんて損失以外のなにものでもないよね 750 名前：デフォルトの名無しさん mailto:sage [2017/11/27(月) 23:36:53.65 ID:bwTh4Bk9.net] >>680 >>696の方法で作ってみました n=10^10の時に48.3秒くらいです 751 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 13:09:45.40 ID:IU/PYwM1.net] >>723 はHaswell (4770) 3.4GHz固定での結果で Skylake (6700K) 定格だと38.4秒でした ちゃんとCPUも進化してるんですね 752 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 13:17:18.48 ID:IU/PYwM1.net] >>681 >>690 C++だとどうやって計算してるかが非常に気になります 32bitを越える値同士の乗算(結果が64bitを越える)部分 アセンブラだと 64bit x 64bit ===> 128bit 128bit / 64bit ===> 64bit 等があるのでそれを使っちゃってますが

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef