C言語なら俺に聞け 146

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾜｯﾁｮｲ 839f-AnMQ)
垢版 |
2018/04/30(月) 04:47:37.50ID:XX4FB8lc0
C言語の話題のみ取り扱います C++の話題はC++スレへ
質問には最低限の情報(ソース/コンパイラ/OS)を付ける
数行で収まらないソースは以下を適当に使ってURLを晒す
https://paiza.io/
https://ideone.com/
http://codepad.org/

C11
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf

C99
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
http://kikakurui.com/x3/X3010-2003-01.html

C FAQ 日本語訳
http://www.kouno.jp/home/c_faq/

JPCERT C コーディングスタンダード
https://www.jpcert.or.jp/sc-rules/

前
C言語なら俺に聞け 144
https://mevius.5ch.net/test/read.cgi/tech/1514025223/

次スレを立てる時は本文の1行目に以下を追加して下さい
!extend:on:vvvvv:1000:512
-
※前スレ
C言語なら俺に聞け 145
http://mevius.5ch.net/test/read.cgi/tech/1519046038/
VIPQ2_EXTDAT: default:vvvvv:1000:512:----: EXT was configured
786デフォルトの名無しさん (ﾗｸｯﾍﾟ MM47-YMl7)
垢版 |
2018/08/05(日) 16:39:28.00ID:HLNQqKaSM
ヒープソートの参照のみならオーダー（計算量）はどうなるか。
先着順
当てたらアマギフ
787デフォルトの名無しさん (ﾜｯﾁｮｲ a39f-Xflc)
垢版 |
2018/08/05(日) 16:43:08.34ID:cdvogGHQ0
ダニング＝クルーガー効果か。こういうのも既に研究されているんだな。
https://ja.wikipedia.org/wiki/%E3%83%80%E3%83%8B%E3%83%B3%E3%82%B0%EF%BC%9D%E3%82%AF%E3%83%AB%E3%83%BC%E3%82%AC%E3%83%BC%E5%8A%B9%E6%9E%9C
2018/08/06(月) 01:43:03.72ID:DWW9arOl0
低能事件に続き5chでも半角事件が来るのか？
2018/08/06(月) 17:48:10.34ID:ODvV2Pda0
俺も何度かここで質問してるが、ム板にしては答えちゃんと返してくれるスレなんだよ。
ただただ質問者と回答者以外の第三者の介入が必ず発生して荒れ出すだけで・・・ｗ
2018/08/06(月) 20:11:30.49ID:Nuh0gMtFM
>>785
なんでindent() のforの++iってなんか意味あるの？
791デフォルトの名無しさん (ｱｳｱｳｶｰ Sa07-iFcb)
垢版 |
2018/08/06(月) 20:12:03.76ID:PKEcOyRea
2ch慣れというか5ch慣れしてスルーカパワーが高まった人でないと中々難しいのかも知れんのう
2018/08/06(月) 22:34:10.82ID:d11E19u/0
一番上と内部でレベルが合ってるように見えてて実はズレてる気持ち悪さ
中に入れるか呼び出し場所で外に書くかどっちかにしる
2018/08/06(月) 23:08:00.95ID:d11E19u/0
あとひどいのがprintしてる"return"の後ろの文字列の示すところが変わってること
固定値返してるところでfunc(n) -> n みたいにさらに下位を呼び出してるみたいにとれる書き方がしてあって
return func(2-2) + func(2-1) -> 1 とか計算内容を書いてるところと一貫性がとれてない
2018/08/06(月) 23:12:24.56ID:d11E19u/0
でも計算内容を展開してるだけだからいいっちゃいいのか
うーん
795デフォルトの名無しさん (ﾜｯﾁｮｲ cf80-gYkF)
垢版 |
2018/08/06(月) 23:39:21.68ID:9v3Lf9b90
全然ずれてない
ｺｰﾙｽﾀｯｸの深さとぴったり一致してる

ｵﾂﾑが足りない知恵遅れのために
さらにﾑﾀﾞな補助出力をつけてやったぞ（AとB）

　https://ideone.com/2vP2kN

ここまでくると
ﾒｸﾗやﾂﾝﾎﾞを誘導するのに近い。。。

　↓この課題は、最終的には、ｺﾚにおちつくことになる
　　（なんでかは、nを増やせばきっと知恵遅れでも分かるとは思ってたからな）
　https://ideone.com/eaJEjX

補助出力がないとなにやってるのかすら分からないﾒｸﾗやﾂﾝﾎﾞでは
ｺﾚがなにやってるかもきっと理解できないわ
u_l、u_r、u_yしかないからな

知恵遅れは再帰が理解できてないのが、よおく分かったわ
2018/08/06(月) 23:51:48.07ID:d11E19u/0
余計紛らわしくなっとるわ！同じレベルで連続でリターンすんなしｗ
関数の戻りと呼び出し先の戻りがごちゃごちゃに
797デフォルトの名無しさん (ﾜｯﾁｮｲ cf80-gYkF)
垢版 |
2018/08/07(火) 00:04:14.76ID:5k05bDr80
https://ideone.com/2vP2kN

知恵遅れ対応はｺﾚが限界
2018/08/07(火) 00:19:28.13ID:bqsBgWbb0
とてもわかりよいです
2018/08/07(火) 00:21:00.39ID:JmB8aria0
フィボナッチごときでよくもまあ話題が続くねえ
2018/08/07(火) 00:22:04.86ID:JmB8aria0
一般項の求め方くらい学校で習わなかった？
801デフォルトの名無しさん (ｱｳｱｳｶｰ Sa07-iFcb)
垢版 |
2018/08/07(火) 12:37:07.91ID:r/NXRNz/a
記憶から消滅
2018/08/07(火) 12:49:11.36ID:sFIHfBH10
一般項は実数を扱うせいで誤差が出るから論外
2018/08/07(火) 12:50:36.34ID:1Vrs+If4d
誤差www
そりゃアホが作れば誤差が問題になるだろうねえwww
2018/08/07(火) 12:51:27.81ID:1Vrs+If4d
アホは素直に加算を繰り返せば良いよ
805デフォルトの名無しさん (ｱｳｱｳｶｰ Sa07-iFcb)
垢版 |
2018/08/07(火) 17:18:17.21ID:r/NXRNz/a
あれ？今日は半角にしないんだ。
2018/08/07(火) 19:11:24.43ID:PQcYGo+5d
おれは半角野郎じゃない
半角野郎はアホだから無理
2018/08/07(火) 19:21:21.20ID:4JY7xbU70
>>802
√5 の係数を整数で持てばいいのでは？
F_n = （φ^n - (-φ)^(-n)) / √5, φ=(1 + √5)/2
2018/08/07(火) 20:18:00.72ID:8+yE0dxd0
富士山麓オウム啼く・・・あれ？怖いなこれ
809デフォルトの名無しさん (ﾜｯﾁｮｲ cf80-gYkF)
垢版 |
2018/08/07(火) 22:59:36.12ID:5k05bDr80
https://ideone.com/jzecIF

やはり
整数を足すにかぎるわ
810デフォルトの名無しさん (ﾜｯﾁｮｲ cf80-gYkF)
垢版 |
2018/08/07(火) 23:08:45.73ID:5k05bDr80
IEEEの倍精度（64bit）で15〜16桁程度の精度
つまりdouble、>>809の精度が概ねその程度

64bit整数なら19桁はいける
2018/08/07(火) 23:43:22.81ID:JmB8aria0
相変わらずアホだね
視野が狭い
2018/08/07(火) 23:47:20.78ID:oCoNsgzD0
ルートとｎ乗求める処理オーダーってどんなんじゃろ

６４bitまでならルート使ったほうが早いだろうけど
結局桁数が大きくなったらルートとってｎ乗してって結構処理重そう

じつは全部足し算したほうが早かったりして
2018/08/08(水) 05:09:15.02ID:d90b/R1Y0
重いのはべき乗のほうだね
2018/08/08(水) 07:15:16.24ID:UEEWq45u0
nが大きい場合の計算オーダー

足し算の繰り返しの場合 : n^2
一般項を普通に計算した場合 : n (log n)^2
2018/08/08(水) 09:01:38.18ID:IJcCYJpk0
足し算の繰り返し：O(n)
一般項：O(1)
じゃないの？
2018/08/08(水) 12:44:41.36ID:DBa81iRmd
加算、乗算、expなどの計算がO(1)で出来る範囲ならそうだね
2018/08/08(水) 12:50:59.40ID:CvCa/3U5M
>>816
まずはO(1)の定義を調べようか…
2018/08/08(水) 12:52:04.40ID:DBa81iRmd
お前より詳しいと思うよ
2018/08/08(水) 15:07:25.41ID:FOgunlIR0
お前のほうが可愛いよ
2018/08/08(水) 16:09:12.75ID:H7dQbZh7d
ありがと
2018/08/08(水) 18:58:28.93ID:UEEWq45u0
フィボナッチの私の回答

nが比較的小さな数までである場合、テーブルを持つのが最速であることは間違いない

じゃあテーブルを持たない場合、

固定有効精度であれば、以下で求めるのが計算量のオーダーが1
(int)(exp(.4812118250596034475*n-.8047189562170501873)+0.5)

floatやdoubleではなく、4倍精度や100倍精度であってもオーダーは1
上の2個の定数は事前に計算しておけばいいし、
毎回計算してもnとは無関係
nが非常に小さい数でなければ単純に加算するよりは上記の方が速いでしょう
floatやdoubleであれば1行で済みます
2018/08/08(水) 19:03:59.97ID:UEEWq45u0
じゃあ多倍長演算を用いて任意のnに対して正確に求める場合を考える

以下は基礎知識
n番目のフィボナッチ数の桁数はnに比例する
乗算の計算オーダーは、桁数をnとすると n log(n)
ルートの計算オーダーは n log(n)
n乗は、オーダーlog(n)回の乗算で求まる

以上より、一般項の式の通りまじめに計算しても
オーダー n (log n)^2 で計算できる
2018/08/08(水) 19:10:00.90ID:UEEWq45u0
工夫すると、計算オーダーを n log n にすることが出来る

行列の形でフィボナッチ数列の漸化式を記述すると
|0 1|^n |0|
|1 1| . . |1|
でn番目とn+1番目のフィボナッチ数が求まることがわかる

この式を用いれば
計算オーダー n log n で正確に n 番目のフィボナッチ数を求めることができる
2018/08/08(水) 19:13:46.21ID:35SEMuEM0
>>810,812,814
漸化式 f(n+2)=f(n+1)+f(n) から一般のf(n) を求めるオーダーはΟ(n)
一般式 >>807 から求めるオーダーはΟ(log n)
だと思う
https://mevius.5ch.net/test/read.cgi/tech/1434079972/49
c を定数として、c^n を求めるにはΟ(log n) でいける
2018/08/08(水) 19:30:35.51ID:xXLtNtIVd
元は>>775の初心者の質問で
計算オーダーとか全く関係なかったんだけど
半角君があまりに無知な癖に自信過剰なので
つい書いてしまった
2018/08/08(水) 19:34:04.93ID:xXLtNtIVd
>>824
それは固定有効精度の場合

固定有効精度であればオーダーは1で計算出来る
>>821参照
2018/08/08(水) 19:36:02.18ID:xXLtNtIVd
固定精度であれば
四則演算もexpも丸めも全て
値によらず固定時間で計算出来る
2018/08/08(水) 19:41:56.80ID:xXLtNtIVd
てことで、
半角君に３勝ですね

コーディング
アルゴリズム
数学

全て勝ってしまった

まあ学歴も勝ってると思うので４勝か
2018/08/08(水) 19:42:03.28ID:bSSLrH090
>>824
桁数分のnかからんの？
2018/08/08(水) 20:30:18.66ID:35SEMuEM0
>>829
>>826 の指摘のとおり、固定有効精度だったら >>829 になるようです
>>821 は、ちょっと理解が及びません…
2018/08/08(水) 21:38:16.32ID:Iprz26WCK
頭悪いバカが半角に勝ったつもりでいる
半角はこのスレでは間違いなく天才
他のやつらがお話にならないぐらい頭悪いからな
典型的な頭悪いやつが半角に勝とうと必死になってる
2018/08/08(水) 23:31:41.87ID:bSSLrH090
ここまで一般式も行列もコードなし多倍長も

まだはじまってもいない
2018/08/08(水) 23:37:23.86ID:85EJM9li0
ISO C99に準拠して、なおかつある程度開発が盛んなOSSを教えてください。
ソースコードが綺麗なことで有名ならなお嬉しいです。
2018/08/08(水) 23:41:36.55ID:35SEMuEM0
>>832
多桁長は結構手間、というか C/C++ でやるのは実は大変だと思います、キャリーフラグが使えない…
2018/08/09(木) 08:27:30.86ID:RmtKVlli0
素直にライブラリを使えば良いよ

加減乗算しか使わないから
速度を求めなければ自作するのも大した手間では無いけど
2018/08/09(木) 08:39:55.95ID:+YHL5mth0
>>833
勉強のためなのかな
もしそうならFreeBSDのコマンドのソースコードが良いと思う
短いものが多いからおすすめ
Linuxのものと比べると読みやすい

FreeBSDソースコードリポジトリ
https://svnweb.freebsd.org/base/release/11.2.0/
"bin"が名前に含まれるフォルダにコマンドのソースがある
2018/08/09(木) 10:23:18.39ID:vVjcL3xq0
GNUのツールチェインもいいんじゃないか
ストールマンのコードとか見れるよ
2018/08/09(木) 10:24:09.98ID:FWE3MOHN0
>>836
ありがとうございます。
> 勉強のため
その通りです。
プログラム言語自体がほぼ初めてなのですが
やはり教科書や仕様書ばかり見て 実際を見ないのでは身に付かない
と思いまして、OSSのソースコードであれば
コーディング規約が守られていたり
優秀なアルゴリズムが使われていたりするかなと予測して
OSSのソースコードリーディングをすることにしました。
ところが私が勉強の対象にしているのはISO/IEC 9899:1999（C99）であるのに対し、
ほとんどの有名なOSSはC89/90に準拠し、その古い制約に縛られていてC99の勉強の妨げになりそうでした。
というわけでC99に準拠した有名なOSSを探しているのです。
2018/08/09(木) 10:43:20.34ID:fhYwVVV8H
C89とC99の差を何も見ずにここに書けるなら別だが、
そうでなければ勉強の妨げにはならんから安心しろ
2018/08/09(木) 10:54:41.59ID:wz655HRh0
多倍長ならGMPがあるやん
2018/08/09(木) 12:48:19.15ID:9ZSWxBpXM
>>838
musl libc
2018/08/09(木) 21:25:05.58ID:rS9AJYq60
>>832
＞一般式
＞多倍長
https://mevius.5ch.net/test/read.cgi/tech/1434079972/50
遅くて残念
2018/08/09(木) 22:23:11.20ID:MlnftC8O0
もうつくったんかはええｗ

順次加算とスピード同じくらい？
2018/08/09(木) 22:27:53.84ID:rS9AJYq60
>>843
よくわかりません
多桁長計算に手間取りすぎていて、順次加算だろうが、一般式だろうが、差が出ないのです、私の多桁長計算は亀のように遅いのです…
2018/08/09(木) 23:30:35.12ID:8Br7DHMpd
コードを見てないけど

多倍長は乗算がキモ
オーダーn log nで計算する方法を考えよう
フーリエ変換を使うのが普通
2018/08/09(木) 23:45:29.15ID:8Br7DHMpd
最終的に10進数で表記するのが目的であれば
10進数のまま演算した方が良い
2進10進変換の方がフィボナッチより重い

>>823の方法を使う場合
多倍長ライブラリの乗算を使うより
フーリエ変換のライブラリを使う方が速い
それは式の関係上多倍長乗算を使うと
同じ事を複数回行うために無駄が多いから

同じく>>823の方法を使う場合
桁数の多い最後の方の計算ほど時間がかかる
最後の方の桁数の多い乗算を減らすのが高速化のにつながる
2018/08/10(金) 01:21:54.58ID:r84RRSaO0
>>841
ありがとうございます。
そもそもmuslを初めて聞きました（恥ずかしながら）
ちょうど，Linuxシステムも勉強したいと思っていたので，これを読もうかなと思います。
848デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/10(金) 21:12:30.49ID:Ao+gKXlH0
とりあえずこの前ｲﾝｽﾄｰﾙした仮想環境のlinuxにgmplibをｲﾝｽﾄｰﾙした
相変わらず低学歴知恵遅れどもは頭悪いﾃｷﾄｰなことばっかりいってるわ
2018/08/10(金) 23:14:02.99ID:z8f8fUe70
俺なんかGoogleのAIライブラリのTensolFlowインストールしたぞ！

インストールしたぞ
2018/08/10(金) 23:55:30.59ID:Jbhl98S70
>>823の方針でフィボナッチ数を計算するコードを書いてみました
F(1億) が10.5秒
F(10億) が137.1秒
Cで450行くらいのコード
計算時間より秀丸エディタで結果を開く方が時間がかかってました

F(10) : time = 0.000013 / err = 0.000000
F(100) : time = 0.000017 / err = 0.000000
F(1000) : time = 0.000021 / err = 0.000000
F(10000) : time = 0.000111 / err = 0.000000
F(100000) : time = 0.001233 / err = 0.000001
F(1000000) : time = 0.019993 / err = 0.000004
F(10000000) : time = 0.251717 / err = 0.000019
F(100000000) : time = 10.507523 / err = 0.000076
F(1000000000) : time = 137.143945 / err = 0.000305
2018/08/11(土) 00:06:54.68ID:N9ICkOCi0
10000進数多倍長
超単純なFFT
演算は乗算と加算のみ
誤差の感じから100000進数でも大丈夫そうですね

計算式は基本以下を多倍長にしただけ
多少の無駄は除いてますが

----
uint64_t f(uint64_t n){
n++;
uint64_t a = 1;
uint64_t b = 0;
uint64_t t;
for (int i = 0 ; i < 64 ; i++){
t = b * b;
b = 2 * a * b + t;
a = a * a + t;
if (n & 0x8000000000000000){
t = b;
b = a + b;
a = t;
}
n += n;
}
return a;
}
2018/08/11(土) 00:16:27.47ID:N9ICkOCi0
コードをアップしようと思ったけど
ideoneだとうまく動かないみたい
2018/08/11(土) 10:03:32.46ID:ONHM6Q8h0
乙
じゃ、多倍長使って一般項の公式で算出したケースを晒します

スレチと知りつつ C++ で　boost/multiprecision バックエンドは gmp
https://wandbox.org/permlink/QqxaauQeHTjJRrYX

# fib(0) .. fib(1000) + fib(10億)
real 0m0.004s
user 0m0.004s
sys 0m0.000s

ま、そりゃ速いですわな……
科学的表記で出力すると速いけど　整数表記しようとするとfib(10億)で2分ぐらい
文字列化でかなり時間を食ってます
2018/08/11(土) 10:40:58.88ID:y6G1YdWMd
正確に全桁計算してその時間？
じゃないよね？
2018/08/11(土) 10:44:26.74ID:y6G1YdWMd
有効精度何桁で計算した場合の時間？
2018/08/11(土) 10:50:42.30ID:y6G1YdWMd
有効数字が少ない時は>>821の式の方が速いよ
2018/08/11(土) 11:00:32.72ID:vW2Ha+vq0
>>821　は桁数が非常に大きくなるとどうなるか、よくわからないんですよ、ちょっと試してみますね
2018/08/11(土) 11:02:48.70ID:y6G1YdWMd
2個の定数は求めたい有効精度+αの精度で求めておけばOK
2018/08/11(土) 11:04:23.75ID:y6G1YdWMd
>>853の式の、
nに依存せずに計算できる所だけ先に計算しただけなので
2018/08/11(土) 11:11:54.17ID:y6G1YdWMd
expの計算の内部ではlog 2を使うし
2進10進変換にはlog_10 (2)を使うので
doubleより高精度で求めるなら
この辺も先に計算しておくことになるでしょう

>>850ははじめから10進での計算なので
10進文字列に変換するのは一瞬
2018/08/11(土) 11:13:07.14ID:y6G1YdWMd
書き忘れましたが
>>850は10進数で全桁正確に求めた場合の時間です
2018/08/11(土) 11:19:04.68ID:ONHM6Q8h0
>>855
>>853は仮数部のビット数を任意長に指定してあるから無限精度ですね
出力で桁落ちしてますが　正確に全桁計算してるはずです
2018/08/11(土) 11:22:04.43ID:y6G1YdWMd
>>862
どこで有効桁数を指定してます？
無理数の数値計算なので指定しないと低精度で計算しそうですが
2018/08/11(土) 11:25:21.63ID:y6G1YdWMd
f(10億)の下位100桁はいくつになります？
私は今出先で私の結果は夜貼ります
2018/08/11(土) 11:29:35.08ID:ONHM6Q8h0
>>863
https://www.boost.org/doc/libs/1_68_0/libs/multiprecision/doc/html/boost_multiprecision/tut/floats/gmp_float.html
gmp_floatが　number<gmp_float<0>> の typedef なので
"variable precision by setting the template argument to zero"で無限精度指定になってると理解してます
正確に出力させると桁が膨大で検証しにくくてしょうがないな……　これ
866デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/11(土) 11:39:50.69ID:17qcRus/0
とりあえずかわいそうなぐらい頭悪いﾔﾂしかいないのは分かった

一旦、多倍長演算向けに3つの方法を評価する
ちなみにgmpの関数にﾌｨﾎﾞﾅｯﾁの関数がついてる
きっとこの速度にすら届かないと考えられる（まだ動かしてない）

↓多倍長演算使ってない3つの方法の簡単なｺｰﾄﾞがｺﾚ
https://ideone.com/vhpLPV
※　ｵﾏｹでｱﾎが書いたｺｰﾄﾞ(>>851)も入ってる
※　ｵﾚの適切なありがたい注釈がついてる

1.ひたすら足し算

2.一般項
　多倍長演算をするまえに適切な精度を設定しないといけない
　どれぐらいの精度にすればいいかがまだ未解決　※ とりあえず2回計算することでいけるような気がしないでもない

3.再帰階乗演算
　https://www.ics.uci.edu/~eppstein/161/960109.html
　探した中でｺｲﾂが一番いい感じがする
　> This is a recursive algorithm, so as usual we get a recurrence relation defining time,
　> just by writing down the time spent in a call to matpow (O(1)) plus the time in each recursive call
　> (only one recursive call, with argument n/2). So the recurrence is
　> time(n) = O(1) + time(n / 2)
2018/08/11(土) 11:48:25.12ID:y6G1YdWMd
>>864
手計算だと下位3桁は875
合ってます？
2018/08/11(土) 11:52:02.92ID:y6G1YdWMd
>>865
√5を無限精度で求めるなんて不可能ですよ
2018/08/11(土) 11:55:08.80ID:y6G1YdWMd
>>866
>>851はそこのリンクのAlgorithm 5の無駄を省いたものですよ
2018/08/11(土) 11:58:25.35ID:y6G1YdWMd
桁数は>>821で瞬時に出ますね
>>850もまず桁数を求めて必要なメモリを確保してから計算してます
871デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/11(土) 12:00:16.70ID:17qcRus/0
↓ｱﾙｺﾞﾘｽﾞﾑ5でｵﾚのｻﾝﾌﾟﾙではちゃんと動いてるからな
https://ideone.com/vhpLPV

↓ｵﾏｴのは動かしても適切な結果にならない
https://ideone.com/vhpLPV

ｵﾏｴのはお話にならないぐらいﾍﾟｹ
↓ﾍﾟｹの理由もちゃんとｺﾒﾝﾄに書いてある
https://ideone.com/vhpLPV
2018/08/11(土) 12:04:23.64ID:y6G1YdWMd
劣化コピーしたらそりゃ正しく動かないよ
nは64bitにしないと
2018/08/11(土) 12:06:06.40ID:ONHM6Q8h0
>>868
あー、そりゃそうですね…

>>867
968 ずれてますね
874デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/11(土) 12:06:47.07ID:17qcRus/0
ｵﾏｴは基本的にｵﾂﾑに問題がある
病院へいったほうがいい
2018/08/11(土) 12:07:58.68ID:y6G1YdWMd
nが32bitなら0x80000000にしないと

多倍長で動かすためのテストコードだから
桁数が小さい時の計算回数は全く無視
ループが進んでからやっと演算がはじまる
876デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/11(土) 12:09:49.79ID:17qcRus/0
64回しかﾙｰﾌﾟしてない

　Σ n
　n→64

はいくつになる
2018/08/11(土) 12:14:07.21ID:y6G1YdWMd
n <<= 1;
って書いてあげた方がよかったかな
どうせコンパイラが足し算に直すだろうし
878デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/11(土) 16:36:24.18ID:17qcRus/0
1.と3.は簡単にできた
https://ideone.com/cmAQzO

gmplibのﾌｨﾎﾞﾅｯﾁは n=10,000,000 を
0.7秒ぐらいで処理できる
ｵﾚが作ったのは4秒ぐらいかかる

m,10000000,4.008508,3.989280
g,10000000,0.724954,0.717120

全然かなわない
少しやってみて面倒そうだから後回しにしてた一般項やってみるか
2018/08/11(土) 18:32:01.22ID:y6G1YdWMd
>>853
同じライブラリを使って>>851のアルゴリズムで計算すると速いかもしれません
a, b, t だけ多倍長にすればいいです
2018/08/11(土) 18:34:26.69ID:y6G1YdWMd
ループの最後の64回目は
aだけを計算すればいいので
かなり省略出来ます
881デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/11(土) 19:41:53.58ID:17qcRus/0
https://ideone.com/2by35t

精度評価用のﾛｸﾞ取得処理

32bit版GMPの仮数部は初期値が64bitで32bitずつ増えていく模様
ちなみに64bit精度で一瞬で求まるﾌｨﾎﾞﾅｯﾁ数のｻｲｽﾞ（bit）予測値はほぼ誤差なし
※ 9999件まで確認したが誤差は発生してない
※ 保険で、1dword(32bit - 最小単位) 分、余分に足しとけば、この予測値で間違いがおきることはまずないと考えられる

ﾌｨﾎﾞﾅｯﾁ数のｻｲｽﾞ（bit）予測値から必要な精度が予測できる
※ 9999件まで確認したが
※ ﾌｨﾎﾞﾅｯﾁ数のｻｲｽﾞ（bit）の1dword(32bit - 最小単位) 分より大きい誤差は発生してない

↓ｺﾚがその結果
http://fast-uploader.com/file/7089539563485/
http://fast-uploader.com/file/7089539604357/

数学的に証明したわけではないが、きっとｺﾚで間違いなくいける
つまり予測値に64bit足しとけば間違いがおきることはない
882デフォルトの名無しさん (ﾜｯﾁｮｲ de80-oNxq)
垢版 |
2018/08/11(土) 19:44:24.09ID:17qcRus/0
で、>>881の結果に基づいて
一般項で処理するｺｰﾄﾞを書いた

　https://ideone.com/QKTrLi
　一般項で処理

やってみたが
一般項で処理なんかするとともかく遅い

6,942,482 bitsの一般項の計算で
お話にならないぐらいものすごい時間がかかる

calculation 6942482bits
f,10000000,35.082393,34.855636
g,10000000,0.722054,0.720584

つまり、結論としてﾌｨﾎﾞﾅｯﾁ数を求めるなら
GMPに用意されてる関数を使うのが一番

再帰階乗演算使う方がはるかにﾏｼ
一般項で求めるのはｳﾝｺ
2018/08/11(土) 19:56:34.45ID:vW2Ha+vq0
>>882
gmp の生Cインターフェースを叩くとは、勇気がありますね
私は、C++ インターフェース gmp_class でやることはあっても gmp を C インターフェースで叩くことはありません
あれは、あとから見てなにがなんだかわからなくなってしまう…

a + b√5, a, b ∈Z で表される数は、それ同士を足しても掛けても、その結果はやはり a + b√5 の形になるのだから（そして結果は整数になることがわかっているのだったらなおさら）、
√5 を開かずにその係数を有理数の範囲で計算するようにすれば(>>807)、ずいぶんと違うと思います >>824, >>842
2018/08/11(土) 21:43:12.30ID:N9ICkOCi0
F(1千万)の計算時間
gmp_fib_uiは0.72秒
私のは0.25秒

私が適当に作ったヤツの方が勝っちゃいましたね

コードは以下
https://ideone.com/hklTK1
2018/08/11(土) 21:47:29.90ID:vW2Ha+vq0
>>884
＞F(1000000000) = 0
となっていますが、ちゃんと動いているのでしょうか？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況