プログラミングのお題スレです。
前スレ
プログラミングのお題スレ Part8©2ch.net
http://echo.2ch.net/test/read.cgi/tech/1444216746/
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
http://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
http://runnable.com/
http://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/
宿題は宿題スレがあるのでそちらへ。
探検
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
2016/12/01(木) 16:58:30.97ID:gTkHDluD
685デフォルトの名無しさん
2017/11/25(土) 07:03:54.53ID:Uo3oYb2P >>679
「良くない」じゃなくて「出来ない」でしょ
「良くない」じゃなくて「出来ない」でしょ
686デフォルトの名無しさん
2017/11/25(土) 07:16:55.64ID:Uo3oYb2P >>684
と思ったけど、普通に全桁計算したら終わらないな
と思ったけど、普通に全桁計算したら終わらないな
687デフォルトの名無しさん
2017/11/25(土) 07:34:12.57ID:Uo3oYb2P Σ { 1 / (2^i × i) }
を使って10^10項位までを42bitくらいだけ計算すれば出来るかな？
1/nの周期性を考えないと計算量的に無理？
10^10が微妙に32bitを越えてるのがイヤだねえ
を使って10^10項位までを42bitくらいだけ計算すれば出来るかな？
1/nの周期性を考えないと計算量的に無理？
10^10が微妙に32bitを越えてるのがイヤだねえ
688デフォルトの名無しさん
2017/11/25(土) 08:21:38.07ID:Uo3oYb2P689デフォルトの名無しさん
2017/11/25(土) 13:10:34.24ID:l6j6CjYT >>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
暇つぶしに書いてみたけど足算掛算割算しかできない
引算は難しすぎるんで諦めた
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
暇つぶしに書いてみたけど足算掛算割算しかできない
引算は難しすぎるんで諦めた
690デフォルトの名無しさん
2017/11/25(土) 16:35:37.76ID:J1zvm3XW バイナリ法で最適化した結果なんとか1時間あれば10^10位は計算できるようになったがまだ縮められるかな
694デフォルトの名無しさん
2017/11/25(土) 22:58:19.91ID:yyAYDlfh 対数関数のマクローリン展開？
そりゃ無理だ
log 0 が定義されてない
そりゃ無理だ
log 0 が定義されてない
695デフォルトの名無しさん
2017/11/25(土) 23:12:41.85ID:FRsJtlII696デフォルトの名無しさん
2017/11/25(土) 23:38:41.06ID:yyAYDlfh >>680
log 2 = Σ_[i=1, 2, ...] { 1 / (2^i × i) }
冪剰余
でいける気がしてきた
しばらく暇がない
時間が空いたら
アセンブラ & C++ & OpenMP
でやってみる
log 2 = Σ_[i=1, 2, ...] { 1 / (2^i × i) }
冪剰余
でいける気がしてきた
しばらく暇がない
時間が空いたら
アセンブラ & C++ & OpenMP
でやってみる
697デフォルトの名無しさん
2017/11/26(日) 02:33:02.82ID:T275kIwU >>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))
(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))
698デフォルトの名無しさん
2017/11/26(日) 02:34:12.86ID:T275kIwU >>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))
(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 を機械的に代入しました、収束半径外ですが、この値は正しいらしい。
いやいや
https://ja.wikipedia.org/wiki/%E5%AF%BE%E6%95%B0
log(1-x) = - Σ((1/n)x^n) に x = -1 を機械的に代入しました、収束半径外ですが、この値は正しいらしい。
700デフォルトの名無しさん
2017/11/26(日) 12:12:20.72ID:ffy1o2uq お題
ASCIIコード表が載っている本をあげよ
ASCIIコード表が載っている本をあげよ
701デフォルトの名無しさん
2017/11/26(日) 12:35:31.87ID:tJzac9f2 >>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
うん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
702デフォルトの名無しさん
2017/11/26(日) 12:35:43.37ID:WgExDItE703デフォルトの名無しさん
2017/11/26(日) 12:49:31.90ID:WgExDItE704デフォルトの名無しさん
2017/11/26(日) 13:21:30.43ID:jiBTwXK4 理解はしてないが、出てきたので貼っとく。
指数対数関数等の超越関数の多倍精度計算
本論文では、 指数対数関数の高精度計算として 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
指数対数関数等の超越関数の多倍精度計算
本論文では、 指数対数関数の高精度計算として 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
706デフォルトの名無しさん
2017/11/26(日) 13:44:48.59ID:jiBTwXK4 とりあえず理解はできた計算方法として、logxの近似値などをaとおいたとき、
logx = a + log(x/e^a)という変形を用いる方法だ。
aが近似値だと、x≒e^aなので良いらしい。
logx = a + log(x/e^a)という変形を用いる方法だ。
aが近似値だと、x≒e^aなので良いらしい。
707デフォルトの名無しさん
2017/11/26(日) 13:58:53.69ID:WgExDItE708デフォルトの名無しさん
2017/11/26(日) 14:20:52.91ID:WgExDItE709デフォルトの名無しさん
2017/11/26(日) 15:04:05.33ID:jiBTwXK4 exp(x)は、(exp(x/k))^k (kは2ベキ)、とするといいらしい。
k=2なら、括弧内を計算したやつ同士の掛け算。
k=2なら、括弧内を計算したやつ同士の掛け算。
>>689
えへへ、調べさせてもらったよｗ
後半は 42! から 50! までの値だね
この範囲なら、多数桁×ワンレジスタの計算で済みますね
多数桁×多数桁を実装すれば思いっきり褒めてあげるよ、えへへ：−）
えへへ、調べさせてもらったよｗ
後半は 42! から 50! までの値だね
この範囲なら、多数桁×ワンレジスタの計算で済みますね
多数桁×多数桁を実装すれば思いっきり褒めてあげるよ、えへへ：−）
712デフォルトの名無しさん
2017/11/26(日) 21:11:54.45ID:tJzac9f2 >>711
ほい
xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl bimul.casl
350306543997676425792
153864088327713953064
53899597027434699691252340823058767026688
ほい
xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl bimul.casl
350306543997676425792
153864088327713953064
53899597027434699691252340823058767026688
714デフォルトの名無しさん
2017/11/26(日) 23:01:31.48ID:tJzac9f2 >>713
gmpで確かめてるのかあ
俺は確認はclispかrubyでやってるよ
10進文字列からの変換は10倍しながら足しこんでいくだけだから
そんなに難しくないでしょ
掛算なしでも(n<<3)+(n<<1)でできるし
逆の10進文字列への変換は割算が必要だから実装するの大変だったなあ
これができあがるまではメモリを16進ダンプして計算が合ってるか確かめてた
gmpで確かめてるのかあ
俺は確認はclispかrubyでやってるよ
10進文字列からの変換は10倍しながら足しこんでいくだけだから
そんなに難しくないでしょ
掛算なしでも(n<<3)+(n<<1)でできるし
逆の10進文字列への変換は割算が必要だから実装するの大変だったなあ
これができあがるまではメモリを16進ダンプして計算が合ってるか確かめてた
715デフォルトの名無しさん
2017/11/27(月) 06:49:43.60ID:qqP20rnw716デフォルトの名無しさん
2017/11/27(月) 07:17:24.36ID:qqP20rnw 誤差しらべたら、テイラー展開は平均値の定理一般化だったか
数値計算とテイラー展開
ある区間において,関数 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
数値計算とテイラー展開
ある区間において,関数 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
717デフォルトの名無しさん
2017/11/27(月) 07:40:30.25ID:qqP20rnw 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以下か。ふたたびシフト使用。
-log(1-x)では、1/n * (x/(1+c))^n か。
x=1/2で考えると、この項をなるべく大きくするならc=0で、誤差は(1/n) >> n以下か。ふたたびシフト使用。
718デフォルトの名無しさん
2017/11/27(月) 07:44:14.48ID:qqP20rnw まとめると、
log2 - (Σ(1/k) >> k) < (1/n) >> n (級数はn-1までの和)
log2 - (Σ(1/k) >> k) < (1/n) >> n (級数はn-1までの和)
719デフォルトの名無しさん
2017/11/27(月) 08:54:49.81ID:qqP20rnw どこか間違えてる 次数か?
720デフォルトの名無しさん
2017/11/27(月) 08:59:59.63ID:qqP20rnw いやあってるか。
A(k) = (1/k)>>kと置くと、
log2 - ΣA(k) < A(n) (級数はn-1までの和) で
ΣA(k) (n+1以上の和) < A(n) が成立するのか。
A(k) = (1/k)>>kと置くと、
log2 - ΣA(k) < A(n) (級数はn-1までの和) で
ΣA(k) (n+1以上の和) < A(n) が成立するのか。
721デフォルトの名無しさん
2017/11/27(月) 10:11:23.24ID:qqP20rnw やはり、どこか間違ってるな。
上のとおりだと、log2 - ΣA(k) (級数はn-1までの和)は、
A(n) を含むので、A(n)より小さいはずがない。
上のとおりだと、log2 - ΣA(k) (級数はn-1までの和)は、
A(n) を含むので、A(n)より小さいはずがない。
>>701
＞ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして何が何だか分からなくなるよ
対象のコード書いてるときの「感覚」をハードディスクかどこかに貯めておいて、
必要に応じてまた脳みそに搭載できるようにならないものか…
そのマシン語の一行一行にも、もともとはなんらかの意味的構造があったのに、それが消えてしまうなんて損失以外のなにものでもないよね
＞ソースはこういうのが延々続いててずっと眺めてるとゲシュタルト崩壊起こして何が何だか分からなくなるよ
対象のコード書いてるときの「感覚」をハードディスクかどこかに貯めておいて、
必要に応じてまた脳みそに搭載できるようにならないものか…
そのマシン語の一行一行にも、もともとはなんらかの意味的構造があったのに、それが消えてしまうなんて損失以外のなにものでもないよね
723デフォルトの名無しさん
2017/11/27(月) 23:36:53.65ID:bwTh4Bk9724デフォルトの名無しさん
2017/11/28(火) 13:09:45.40ID:IU/PYwM1725デフォルトの名無しさん
2017/11/28(火) 13:17:18.48ID:IU/PYwM1726デフォルトの名無しさん
2017/11/28(火) 13:20:30.03ID:IU/PYwM1 冪剰余を求めるのに
(a * b) % c
みたいなのがたくさん出てきませんか？
aもbもcも32bitの範囲を微妙に越えてて
(a * b) % c
みたいなのがたくさん出てきませんか？
aもbもcも32bitの範囲を微妙に越えてて
727デフォルトの名無しさん
2017/11/28(火) 14:44:32.26ID:jzUFRHpN 誤差部分の間違いが判った。これでよさげだ。
ただし誤差評価を荒くやってはダメそうだが。一番最後の行のところ。
誤差項ありのマクローリン展開は、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
ただし誤差評価を荒くやってはダメそうだが。一番最後の行のところ。
誤差項ありのマクローリン展開は、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
728デフォルトの名無しさん
2017/11/28(火) 19:45:30.22ID:jzUFRHpN これが収束速いようだ。
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))
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))
729デフォルトの名無しさん
2017/11/28(火) 22:18:22.38ID:7WoPw74F >>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 だから速く計算できるのだ
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 だから速く計算できるのだ
730デフォルトの名無しさん
2017/11/28(火) 22:20:46.48ID:7WoPw74F731デフォルトの名無しさん
2017/11/28(火) 22:47:09.33ID:7WoPw74F >>724
Haswellで33.96秒に縮まりました
シングルスレッドだと182.54秒で5.3倍
HTTが効くということは、
まだ多少改善の余地がありそう
一番内側のループは
vmulpd
vmulpd
vroundpd
vfmsub213pd
vfmsub132pd
vsubpd
なんと浮動小数点で計算してます
Haswellで33.96秒に縮まりました
シングルスレッドだと182.54秒で5.3倍
HTTが効くということは、
まだ多少改善の余地がありそう
一番内側のループは
vmulpd
vmulpd
vroundpd
vfmsub213pd
vfmsub132pd
vsubpd
なんと浮動小数点で計算してます
732デフォルトの名無しさん
2017/11/28(火) 22:53:54.93ID:7WoPw74F n=10000000000の時は
0000010101 でした
出題者さま、合ってます？
また、たまたまですが
n=10000000004では
0101010101
n=10000000005では
1010101010
になります
0000010101 でした
出題者さま、合ってます？
また、たまたまですが
n=10000000004では
0101010101
n=10000000005では
1010101010
になります
733デフォルトの名無しさん
2017/11/28(火) 23:30:15.70ID:9HoDrqB3 一番内側のループのコード
http://fast-uploader.com/file/7067434368942/
PORT5がガラ空きで、処理のほとんどがPORT0,PORT1
こんなんでもHTTが効く
やっぱり浮動小数点はレイテンシがデカい
AVX512になれば
レジスタの数が倍になるので
8パラにしてレイテンシを隠蔽出来るんだけど
もちろんレジスタ長が倍になる方が大きい
http://fast-uploader.com/file/7067434368942/
PORT5がガラ空きで、処理のほとんどがPORT0,PORT1
こんなんでもHTTが効く
やっぱり浮動小数点はレイテンシがデカい
AVX512になれば
レジスタの数が倍になるので
8パラにしてレイテンシを隠蔽出来るんだけど
もちろんレジスタ長が倍になる方が大きい
734デフォルトの名無しさん
2017/11/29(水) 13:17:33.09ID:mHyZby47735デフォルトの名無しさん
2017/11/29(水) 13:34:57.75ID:8/kTvoZy 2 = (81/80)^3 * (25/24)^5 * (16/15)^7
3 と 5 の指数の合計が0になる組み合わせを検索すれば良い
3 と 5 の指数の合計が0になる組み合わせを検索すれば良い
736デフォルトの名無しさん
2017/11/29(水) 13:37:30.83ID:8/kTvoZy737デフォルトの名無しさん
2017/11/29(水) 13:42:05.17ID:mHyZby47 >>728はそういうことか。みつけたやつのコピペで、そのとき考慮はしてなかった。
738デフォルトの名無しさん
2017/11/29(水) 13:45:31.51ID:mHyZby47 指数も固定でなくていいはずで、
16/15よりかはたとえば1001/1000のほうが1に近いからそういうのはいくらでも見つけられるのかとおもった。
16/15よりかはたとえば1001/1000のほうが1に近いからそういうのはいくらでも見つけられるのかとおもった。
739デフォルトの名無しさん
2017/11/29(水) 14:44:26.09ID:8/kTvoZy 分母分子の素因数の数と同じ項数が必要
例えば素因数が 2, 3, 5, 7 の4種類の場合、
1個差もしくは2個差のペアを4個探す
例えば
126/125
225/224
2401/2400
4375/4374
これらを適当に掛け算して2^nになるようにすると
項が4個の式がみつかる
例えば素因数が 2, 3, 5, 7 の4種類の場合、
1個差もしくは2個差のペアを4個探す
例えば
126/125
225/224
2401/2400
4375/4374
これらを適当に掛け算して2^nになるようにすると
項が4個の式がみつかる
740デフォルトの名無しさん
2017/11/30(木) 00:31:43.08ID:H4qIjcIH 分母、分子とも 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)
以下が一番計算する項の数が少ないようです
log(2) = 72*log(126/125)+27*log(225/224)-19*log(2401/2400)+31*log(4375/4374)
741デフォルトの名無しさん
2017/11/30(木) 05:07:54.11ID:fMs2N0Mh >>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
その数値を検索すると、音楽のコンマというのが出てくる。関係あったり理論があったりするのか。
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
742デフォルトの名無しさん
2017/11/30(木) 05:28:17.43ID:fMs2N0Mh 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
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
743デフォルトの名無しさん
2017/11/30(木) 11:02:35.16ID:fMs2N0Mh log2のほうは、分子・分母の素因数分解が似通ってないと成立しないってことで、
音楽のほうは小さい素数に限定して一個差ペアを求めたと理解。
log2のほうは、共通の素数で大きいやつを最初に固定すれば考えれば、よさげかと。
音楽のほうは小さい素数に限定して一個差ペアを求めたと理解。
log2のほうは、共通の素数で大きいやつを最初に固定すれば考えれば、よさげかと。
744片山博文MZ ◆T6xkBnTXz7B0
2017/11/30(木) 12:12:48.85ID:NsMGt5if お題。横x[cm]、縦y[cm]の長方形のステンレスの１枚の板がある。この板からm枚の複数の長方形の部材を切り出す。
部材のサイズは配列で与えられる。
部材のサイズ(縦×横)はそれぞれだいたい決まっているが、1cm程度変わってもよい。
ただし、部材の縦または横が変わるとそれぞれ一点減点となる。
すべての部材を切り出すことができれば、減点がなるべく少ない方法の切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順になるべくたくさん部材を切り出せ。
部材のサイズは配列で与えられる。
部材のサイズ(縦×横)はそれぞれだいたい決まっているが、1cm程度変わってもよい。
ただし、部材の縦または横が変わるとそれぞれ一点減点となる。
すべての部材を切り出すことができれば、減点がなるべく少ない方法の切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順になるべくたくさん部材を切り出せ。
745片山博文MZ ◆T6xkBnTXz7B0
2017/11/30(木) 12:19:33.84ID:NsMGt5if テストデータ。
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}
}
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}
}
746片山博文MZ ◆T6xkBnTXz7B0
2017/11/30(木) 12:28:07.36ID:NsMGt5if 部材の縦と横は入れ替わってもよい。
可能ならば、切り出し方法をSVG形式で出力せよ。
可能ならば、切り出し方法をSVG形式で出力せよ。
747片山博文MZ ◆T6xkBnTXz7B0
2017/11/30(木) 12:51:59.04ID:NsMGt5if 切り出し方法は、
切り出す部材のx座標、y座標、幅、高さ
のリストとして出力せよ。
切り出す部材のx座標、y座標、幅、高さ
のリストとして出力せよ。
748片山博文MZ ◆T6xkBnTXz7B0
2017/11/30(木) 12:56:57.25ID:NsMGt5if 切り出しに余裕があるときは、なるべくx座標の大きい方、y座標の大きい方を残すようにせよ。
749デフォルトの名無しさん
2017/11/30(木) 13:08:21.37ID:tkxPMdZc 斜めもOK？
750デフォルトの名無しさん
2017/11/30(木) 13:08:55.87ID:tkxPMdZc 人間用のパズルで、斜めにしないと解けないのとかありそう
751デフォルトの名無しさん
2017/11/30(木) 14:23:24.17ID:SHLZLl2M 問題文の条件が“だいたい”“なるべく”なんて
あいまい表現だらけ
これでプログラミングの問題かよ
あいまい表現だらけ
これでプログラミングの問題かよ
752片山博文MZ ◆T6xkBnTXz7B0
2017/11/30(木) 16:18:01.24ID:NsMGt5if 斜めは考えなくてもよい。
訂正。
すべての部材を切り出すことができれば、減点が最小である切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順に切り出せる部材の面積が最大になるよう部材を切り出せ。
切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。
訂正。
すべての部材を切り出すことができれば、減点が最小である切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順に切り出せる部材の面積が最大になるよう部材を切り出せ。
切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。
753680
2017/11/30(木) 17:10:37.24ID:8ZVWPbH7754デフォルトの名無しさん
2017/11/30(木) 17:26:52.63ID:r8WkgLop 普通に多倍長で計算したら計算量的に終わらないですよね？
n=314159265を求めるのに
冪剰余は使ってますよね？
おそらく私も同じような方法と思います
FMA3命令とOpenMPで高速化してるだけで
n=314159265を求めるのに
冪剰余は使ってますよね？
おそらく私も同じような方法と思います
FMA3命令とOpenMPで高速化してるだけで
755デフォルトの名無しさん
2017/11/30(木) 22:49:50.18ID:TklDiPhy 愚直という言い方は良く割りませんでしたね
仰る通り冪剰余は用います
仰る通り冪剰余は用います
756片山博文MZ ◆T6xkBnTXz7B0
2017/12/01(金) 14:26:32.50ID:fw1UFg83 再出題。横cx[cm]、縦cy[cm]の長方形または正方形のステンレスの１枚の板がある。この板から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}
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}
757デフォルトの名無しさん
2017/12/01(金) 17:01:28.13ID:BqJQPTjH 頭の悪そうな文章だな
正方形⊂長方形
ステンレスの板の座標上の位置指定が無い
余裕がある場合の条件の意味が曖昧
正方形⊂長方形
ステンレスの板の座標上の位置指定が無い
余裕がある場合の条件の意味が曖昧
758片山博文MZ ◆T6xkBnTXz7B0
2017/12/01(金) 18:41:36.20ID:fw1UFg83 ステンレスの板の左上座標は原点にあるものとする。
切り出しは、可能な限り、座標の小さい方を優先する(「余裕」の意味)。
切り出しは、可能な限り、座標の小さい方を優先する(「余裕」の意味)。
759デフォルトの名無しさん
2017/12/01(金) 20:32:10.86ID:9YSaSAW0760片山博文MZ ◆T6xkBnTXz7B0
2017/12/01(金) 20:41:14.79ID:fw1UFg83 全ての部材の上辺と左辺が別の部材の辺、もしくは、元の板の端に接していること。
このような条件のをすべて見つけること。
このような条件のをすべて見つけること。
761片山博文MZ ◆T6xkBnTXz7B0
2017/12/01(金) 20:43:57.24ID:fw1UFg83 なんか、工学関係でこのような問題があるらしいが、まだ解決策があるかどうかわからん。これが解ければ、実用化待ったなし。
762デフォルトの名無しさん
2017/12/01(金) 21:15:23.73ID:9YSaSAW0 お題じゃなくて依頼かよ
763デフォルトの名無しさん
2017/12/01(金) 21:19:54.38ID:9YSaSAW0 実用性なら
切りやすさとか余り素材の形状とか
そういうのが重要だろうに
問題として中途半端過ぎる
切りやすさとか余り素材の形状とか
そういうのが重要だろうに
問題として中途半端過ぎる
764デフォルトの名無しさん
2017/12/01(金) 21:20:21.36ID:qVeescqP また片山博文MZ が乞食をやってるのか
765デフォルトの名無しさん
2017/12/01(金) 21:23:07.33ID:9YSaSAW0 普通に考えて、NP問題だろう
766デフォルトの名無しさん
2017/12/01(金) 21:48:16.44ID:8H4JUlF5 なにやら揉めてますね
そろそろうんざりなので次のお題どうぞ
そろそろうんざりなので次のお題どうぞ
767デフォルトの名無しさん
2017/12/01(金) 23:36:29.58ID:N1IVcYDB スポーツスケジューリング問題。
768デフォルトの名無しさん
2017/12/03(日) 02:47:12.16ID:QazTjKaA お題ってこういうのでもいいのかな
a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
このように10個の整数を要素に持つ配列がある（整数の値は不定）
b = エントリーポイント
c = 移動する数量
d = 移動する距離
を与えることにより、配列の要素を移動させるプログラムを作りなさい
ただし配列の右端の要素を一つ移動させると、配列の左端に移動するものとする
例
a = 3, b = 1, c = 5, a = 0124567839
b = 1, c = 3, d = 1, a = 0412356789
b = 7, c = 1, d = 5, a = 1273456890
b = 0, c = 8, d = 1, a = 8012345679
b = 4, c = 5, d = 4, a = 6783901245
b = 9, c = 5, d = 4, a = 5679012384
b = 7, c = 3, d = 1, a = 9123456078
a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
このように10個の整数を要素に持つ配列がある（整数の値は不定）
b = エントリーポイント
c = 移動する数量
d = 移動する距離
を与えることにより、配列の要素を移動させるプログラムを作りなさい
ただし配列の右端の要素を一つ移動させると、配列の左端に移動するものとする
例
a = 3, b = 1, c = 5, a = 0124567839
b = 1, c = 3, d = 1, a = 0412356789
b = 7, c = 1, d = 5, a = 1273456890
b = 0, c = 8, d = 1, a = 8012345679
b = 4, c = 5, d = 4, a = 6783901245
b = 9, c = 5, d = 4, a = 5679012384
b = 7, c = 3, d = 1, a = 9123456078
769デフォルトの名無しさん
2017/12/03(日) 02:49:08.83ID:QazTjKaA770デフォルトの名無しさん
2017/12/03(日) 09:00:27.20ID:ucQfMVKf771デフォルトの名無しさん
2017/12/03(日) 09:04:48.71ID:b0AFqm0g772デフォルトの名無しさん
2017/12/03(日) 10:14:55.69ID:ZeeZWfzn773デフォルトの名無しさん
2017/12/03(日) 12:12:41.56ID:jbLAlLAh >>768
b + c が10を超えることはありますか？
b + c が10を超えることはありますか？
774デフォルトの名無しさん
2017/12/03(日) 12:55:22.10ID:sC6phLBS >>773訂正
b,c,dが10を越えることはありますか？
b,c,dが10を越えることはありますか？
775デフォルトの名無しさん
2017/12/03(日) 13:05:23.73ID:b0AFqm0g >>771はb,c,dが任意の自然数でも大丈夫なようにしておいた
776デフォルトの名無しさん
2017/12/03(日) 13:08:19.92ID:QazTjKaA みなさんプログラム作るの早いですね
>>774
一応a、b、cの条件は、このようになると思います。
0 <= a <= 9
0 <= b <= 8
0 <= c <= 10 - b - 1
bとcは0では意味がないので、こっちのほうがいいのかな
0 <= a <= 9
1 <= b <= 8
1 <= c <= 10 - b - 1
>>774
一応a、b、cの条件は、このようになると思います。
0 <= a <= 9
0 <= b <= 8
0 <= c <= 10 - b - 1
bとcは0では意味がないので、こっちのほうがいいのかな
0 <= a <= 9
1 <= b <= 8
1 <= c <= 10 - b - 1
777デフォルトの名無しさん
2017/12/03(日) 13:12:58.80ID:QazTjKaA778デフォルトの名無しさん
2017/12/03(日) 13:34:35.32ID:QazTjKaA779デフォルトの名無しさん
2017/12/03(日) 17:47:25.64ID:Gq7SJlPX Linked list 使うと楽そうな感じするな
780デフォルトの名無しさん
2017/12/03(日) 18:26:21.27ID:QazTjKaA >>770,771
せっかくなのでこのテストデータを作って検証してみましたが、全部合っていました、さすがですね
それにしても他人のプログラムって動かすことはできても、理解するのは困難ですね
>>772
Mathematicaは残念ながら持っていないので検証できませんでした
b = 8 c = 6 d = 2 a = 8901236745
b = 4 c = 3 d = 2 a = 0123784569
b = 4 c = 5 d = 2 a = 8123904567
b = 2 c = 5 d = 2 a = 0178234569
b = 0 c = 5 d = 3 a = 5670123489
b = 9 c = 3 d = 4 a = 3459016782
b = 5 c = 1 d = 7 a = 1253467890
b = 4 c = 6 d = 2 a = 8923014567
b = 6 c = 7 d = 2 a = 8901253467
b = 7 c = 5 d = 4 a = 5789016234
b = 4 c = 2 d = 2 a = 0123674589
b = 6 c = 4 d = 5 a = 4678950123
b = 7 c = 4 d = 4 a = 4789056123
b = 4 c = 5 d = 4 a = 6783901245
b = 8 c = 1 d = 5 a = 1238456790
b = 0 c = 2 d = 6 a = 2345670189
b = 3 c = 7 d = 1 a = 9120345678
b = 9 c = 4 d = 2 a = 4901256783
b = 8 c = 3 d = 6 a = 3456890712
b = 2 c = 5 d = 3 a = 0178923456
せっかくなのでこのテストデータを作って検証してみましたが、全部合っていました、さすがですね
それにしても他人のプログラムって動かすことはできても、理解するのは困難ですね
>>772
Mathematicaは残念ながら持っていないので検証できませんでした
b = 8 c = 6 d = 2 a = 8901236745
b = 4 c = 3 d = 2 a = 0123784569
b = 4 c = 5 d = 2 a = 8123904567
b = 2 c = 5 d = 2 a = 0178234569
b = 0 c = 5 d = 3 a = 5670123489
b = 9 c = 3 d = 4 a = 3459016782
b = 5 c = 1 d = 7 a = 1253467890
b = 4 c = 6 d = 2 a = 8923014567
b = 6 c = 7 d = 2 a = 8901253467
b = 7 c = 5 d = 4 a = 5789016234
b = 4 c = 2 d = 2 a = 0123674589
b = 6 c = 4 d = 5 a = 4678950123
b = 7 c = 4 d = 4 a = 4789056123
b = 4 c = 5 d = 4 a = 6783901245
b = 8 c = 1 d = 5 a = 1238456790
b = 0 c = 2 d = 6 a = 2345670189
b = 3 c = 7 d = 1 a = 9120345678
b = 9 c = 4 d = 2 a = 4901256783
b = 8 c = 3 d = 6 a = 3456890712
b = 2 c = 5 d = 3 a = 0178923456
781デフォルトの名無しさん
2017/12/03(日) 20:16:05.68ID:hV+xPFYR782デフォルトの名無しさん
2017/12/03(日) 20:37:58.61ID:ucQfMVKf783デフォルトの名無しさん
2017/12/03(日) 20:51:48.60ID:ucQfMVKf784デフォルトの名無しさん
2017/12/03(日) 23:00:23.32ID:QazTjKaA■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 「脅迫だ」国分太一に同情論 音声データ削除要求など日テレの対応を疑問視する声ネットに噴出「それこそコンプラ違反では」 [muffin★]
- 中国と対話で良い関係つくるのが責任と首相 ★4 [少考さん★]
- 【国際法を無視】日本での「中華人民共和国に台湾問題を論じる資格なし」との声に 中国外交部が厳しく反論… [BFU★]
- 生クリームだけの真っ白なクリスマスケーキ 大手メーカーが販売、その理由は…フルーツなしで価格は半額以下に ★3 [おっさん友の会★]
- 首相答弁「スパイ防止法、外国代理人登録法、ロビー活動公開法などについて速やかに法案を策定する」 [１ゲットロボ★]
- 〈シカが泣いている…〉奈良が“観光崩壊”危機…外国人観光客は44.5万人、宿泊客単価は3万1千円 [１ゲットロボ★]
- 【実況】博衣こよりのえちえちSSholox4周年切り抜き鑑賞🧪★3
- 【高市大悲報】ホタテの国内価格高騰してしまうwwwwwwwww [616817505]
- 【正論】高市さん「原因は野党のしつこい質問。従来の答弁の繰り返しは国会を空転させると考えた」立憲岡田、議員辞職不可避か [519511584]
- 【悲報】野田佳彦、高市さんの『存立危機事態』答弁を撤回 [519511584]
- ヤンジャン新人漫画大賞、入賞作品のAI絵疑惑で大荒れ😄😄😄 高市早苗要素あり [175344491]
- 【毎日調査】衆院選議席数、自民28維新6立憲86国民21公明19参政138共産48れいわ56保守18社民19みらい26 [369521721]