C言語なら俺に聞け 146

2018/04/30(月) 04:47:37.50

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

2018/08/05(日) 08:56:17.59

ここ喧嘩ばっかだから他所行くかーと思ってC++スレ行ったらそこでも喧嘩しててワロタ

2018/08/05(日) 08:57:44.72

一緒にすんな失礼な

　　　発　者　同　　　　　　　　 .　｡_　　 ____　　　　　　　　　　争
　生　同　.じ　　　　 .　　　　/´ 　 (ゝ___)　　　　　　　　　　い
　.し　士　.レ　　　　　　.__／'r-┴<ゝi,,ノ　　ro､　　　　　　は、
　.な　で　.ベ　　　　 ∠ゝ　(ゝ.／/｀　　 ./｀　 }⌒j　　　　　
　.い　し　.ル　　　　　　　} ⌒ ／｀ヽ､_∠l,ノ　・ヽ´
　.! !　か　の　　　　　　 /　　´..:.} ＞､､___,　 .r､ｿ､｀＼
　　　　　　　　　　　　　/　　　..:.:.}　　　/　　　∨　｀￣
　　　　　　　　　　　／　　　..:.:./　　　　　　丶
　　　　　　　　　　 /　＿､　..:.:.:.{　　　 .{.:.:.　　　＼
　　　　　　　　　　{　　　..:Y　　.ゝ､　　 {.:.:.:.:.　　　ヽ
　　　　　　　　　　､　　..:/　丿　.:〉　　 >.- ⌒ 　. 　ヽ
　　　　　　　　　 / {.　..:./　ｿ　..:./　 .(　　　　..:.:.:｀　..:}
　　　　　　　　 ./..:.:}.:.:./ ヘ､ ..:./　　 .＼　..:.:r＿,ノ､.:.:}
　　　　　　　　./..:.:/.:/　　 {.:./　　　　　X.:.:}.}　　 X X
　　　　　　　 /..:.:/ .}.: 　　 }:/ 　　　　　　.Y丶ヽ　　Y.:Y
　　.　＿＿／.:／　{　}　　《.〈､　　　　＿,,__>.:》丶　 Y.:＼
　　／.:.:.:.:.::／　　 !.:.:ゝ　　ゝ.:.￣ヾ　´:.:.:.:.:.:.:.:.:ヾゝ　　＼.:￣＞

2018/08/05(日) 10:50:56.85

というかだ
randとquickselectどっからコピペしてきたのか正直にいいなさい

非の打ちどころなく最適化されたロジック
筋のいい関数分割
的確な規約にのっとった命名
正確な英語

おまえがつくったのbakaとallocとfree_dataだけだろ
関数ごとにあまりにも作成者の知性差がありすぎる

2018/08/05(日) 10:53:47.86

partitionの中はそうでもないか

2018/08/05(日) 10:57:17.82

質問者そっちのけで
議論だけは続きます
いつものパターン

2018/08/05(日) 11:03:06.42

問題は解決してるじゃない

2018/08/05(日) 11:15:46.84

そもそもどれが質問だったかわからない

2018/08/05(日) 11:25:14.55

何を議論しているのかも誰も分からない

2018/08/05(日) 11:25:39.76

https://ideone.com/H6J9g6
ｺﾚで上位3件と
ｺﾚで上位3%の比較ができる

ちなみにｱﾎのｺｰﾄﾞが混じってるせいでWebでは動かない

https://en.wikipedia.org/wiki/Quickselect
ちなみにｺｰﾄﾞはｺﾚみながらちゃんとｵﾚが作ったからな

あとな　quickselect　は見直してたら一箇所ｺｰﾄﾞに誤りがあったわ

動作自体に大きな影響はない
それがなんでかは、それでどう動作がかわわるか、それがどういう修正なのかは
きっとこのｽﾚの知恵遅れたちには分からない

疑似乱数生成器は普通にxorshiftｺﾋﾟって作ったわ
あれならｲﾝﾀｰﾈｯﾂにいるようなどんなﾊﾞｶが書いても同じ結果になるからな
その部分だけはあってるわ

で、あとは、ﾃｽﾄ評価用関数の名前がどうこうしかないﾜｹか
まあｵﾂﾑの程度がよくしれるわ

2018/08/05(日) 11:51:24.52

1個も自分で考えたアルゴリズムが無いっていう
選択も正しくない

2018/08/05(日) 11:54:12.46

ﾊﾝｶｸ君「100件から上位3件のｿｰﾄじゃダメだ!
　　　　100万件から上位3万件を抽出（未ｿｰﾄ）できるｸｲｯｸｾﾚｸﾄがｴﾚｶﾞﾝﾄ！」

全角君「１億件をソートするにはそれじゃダメだろ　ヴォケが！
　　　　『マルチコアの並列ソート』こそがグレイシャス！」

二　倍　角　君　「　ダ　ァ　ホ　が　！　　１　０　０　億　じ　ゃ　！
　　　　　　　　　　量　子　C　P　U　で　超　並　列　じ　ゃ　ー　い　！　！」

今後の展開を想像したらわくわくしてきた
にしても　今日もあっついなぁ……

2018/08/05(日) 11:56:40.45

元は100個だか1000個だかだよ確か

2018/08/05(日) 12:05:44.10

なんかしょうもない争いしてんのな
どんぐりの背比べ

2018/08/05(日) 12:19:17.66

病気の発作みたいなもの
しばらく放置して、本人が落ち着くのを待つ
かまえばかまうほど、病気は進行する

2018/08/05(日) 12:25:21.31

またCPUが熱くなったわ
今回はvmwareで動作してるLinuxで動作させた

↓処理結果
http://fast-uploader.com/file/7088994902722/

　上位3件
　https://i.imgur.com/cBCyXmq.png
　上位3%
　https://i.imgur.com/SxxNkoj.png

もうねｵﾚのｺｰﾄﾞがｴﾚｶﾞﾝﾄすぎて困るわ
ｷﾐﾗとはﾚﾍﾞﾙが違うﾜｹ　ﾚﾍﾞﾙが
ｷﾐﾗとはｽﾃｰｼﾞが違うﾜｹ　ｽﾃｰｼﾞが

分かった？

2018/08/05(日) 12:30:52.32

よほどくやしかったんだろうね

2018/08/05(日) 12:35:47.77

あとな、知恵遅れが自分で新しいｱﾙｺﾞﾘｽﾞﾑを考えるとか
1億年たってもﾑﾘだからな

ｵﾚﾚﾍﾞﾙの人間ぐらいにならないとﾑﾘ

このｽﾚにいるような知恵遅れを遥かに凌駕する先人が
考えたｱﾙｺﾞﾘｽﾞﾑすら使いこなせてない

はっきりいってな低学歴知恵遅れやｸｿﾆｰﾄは
自己評価が高すぎるﾜｹ
低学歴知恵遅れやｸｿﾆｰﾄは自分のｶｽっぷりの自覚がない
まずｺｺが問題なﾜｹ

そんな知恵遅れが新しいｱﾙｺﾞﾘｽﾞﾑとかな逆立ちしてもﾑﾘだからな
知恵遅れや凡人はまず適切なｱﾙｺﾞﾘｽﾞﾑを選択できるようになるのが先だからな

2018/08/05(日) 12:37:41.32

日本ではPGは低学歴底辺しかならない職業だからな
しょうがないという側面もなある

おのずと低学歴底辺の頭悪いのばっかりになる

2018/08/05(日) 12:43:27.32

長文で自己紹介乙

2018/08/05(日) 12:57:32.94

まちがいがあったんだろうか？
相手が間違ってるかもしれないのに知ったげして

2018/08/05(日) 13:07:24.80

いつもいってることだが
ﾚｽしてるﾔﾂが低学歴か
ﾚｽしてるﾔﾂがﾆｰﾄかなんかな
ﾚｽみればすぐに分かることだからな

残念なことにそれをいくら隠そうとしても
隠すことはできない

本人はﾊﾞﾚてないつもりかもしれないが
ﾁｮﾝﾊﾞﾚなﾜｹ

2018/08/05(日) 13:12:35.48

お前の書き込みが病的だからお前が特定されてるだけだろ
ほかのやつの学歴なんか一切わからんわｗ

2018/08/05(日) 13:22:37.54

#include <stdio.h>

int func(int n)
{
if(n==0)
return 0;
if(n==1)
return 1;
return(func(n-2)+func(n-1));

}

int main()
{
printf ("%d",func(4));

return 0;
}

これの出力は３なんだけど

これ、永久的数が増えていく気がするんだけど。。。
どういう考え方で3になるか教えてほしい

2018/08/05(日) 13:28:13.17

4
2, 3
0, 1, 1, 2
0, 1, 1, 0, 1

2018/08/05(日) 13:29:48.92

>>776
足し算の合計としてじゃなく２つのfuncとして返されるってこと？
そしてその連続ってこと？

2018/08/05(日) 13:31:08.57

>>775
フィボナッチだってことは解ってる?
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

func(0) = 0
func(1) = 1
func(2) = func(0) + func(1) = 0 + 1 = 1
func(3) = func(1) + func(2) = 1 + 1 = 2
func(4) = func(2) + func(3) = 1 + 2 = 3

2018/08/05(日) 13:41:13.29

>>778
え、概念はわかった
func(0) = 0
func(1) = 1 ってどこからわかるんだ？
returnではないよね？

2018/08/05(日) 13:43:51.70

return 0;ってはっきり書いてあるやろ

2018/08/05(日) 13:45:55.07

>>780
え、リターンって　定型文というか終わりを意味するだけだと思ってた。

2018/08/05(日) 13:52:07.99

#include <stdio.h>
int func(int n, int stack)
{
++stack;
if(n==0) {
for (int i = 0; i < stack; ++i) printf(" ");
printf("[%d] returned func(%d) -> %d\n", stack, n, 0);
return 0;
}
if(n==1) {
for (int i = 0; i < stack; ++i) printf(" ");
printf("[%d] returned func(%d) -> %d\n", stack, n, 1);
return 1;
}
int i_ret = func(n-2, stack) + func(n-1, stack);
for (int i = 0; i < stack; ++i) printf(" ");
printf("[%d] returned func(%d) + func(%d) -> %d\n", stack, n - 2, n - 1, i_ret);
return(i_ret);
}

int main()
{
printf ("%d",func(4, 0));
return 0;
}

このｽﾚの知恵遅れがどうこういうだけﾑﾀﾞ
ｺﾚ動かして自分で考えればﾊﾞｶでもﾁｮﾝでも分かる

2018/08/05(日) 13:57:48.29

>>781
return は関数を抜けて　呼び出し元に戻り値を返すんだよ

2018/08/05(日) 14:15:22.97

>>781
なぜ、そんなものが存在するのか
つまり、必要なのか
ただブレースを閉じるだけではダメなのか
疑問を持ったことはないのか？

2018/08/05(日) 14:56:39.59

https://ideone.com/lYgehQ

ｺﾚでfuncが再帰による深さ優先探索が行われてる様子も分かるﾊｽﾞ
ｺｺまで分かるならこの部分の課題は終わりのﾊｽﾞだ

2018/08/05(日) 16:39:28.00

ヒープソートの参照のみならオーダー（計算量）はどうなるか。
先着順
当てたらアマギフ

2018/08/05(日) 16:43:08.34

ダニング＝クルーガー効果か。こういうのも既に研究されているんだな。
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.72

低能事件に続き5chでも半角事件が来るのか？

2018/08/06(月) 17:48:10.34

俺も何度かここで質問してるが、ム板にしては答えちゃんと返してくれるスレなんだよ。
ただただ質問者と回答者以外の第三者の介入が必ず発生して荒れ出すだけで・・・ｗ

2018/08/06(月) 20:11:30.49

>>785
なんでindent() のforの++iってなんか意味あるの？

2018/08/06(月) 20:12:03.76

2ch慣れというか5ch慣れしてスルーカパワーが高まった人でないと中々難しいのかも知れんのう

2018/08/06(月) 22:34:10.82

一番上と内部でレベルが合ってるように見えてて実はズレてる気持ち悪さ
中に入れるか呼び出し場所で外に書くかどっちかにしる

2018/08/06(月) 23:08:00.95

あとひどいのがprintしてる"return"の後ろの文字列の示すところが変わってること
固定値返してるところでfunc(n) -> n みたいにさらに下位を呼び出してるみたいにとれる書き方がしてあって
return func(2-2) + func(2-1) -> 1 とか計算内容を書いてるところと一貫性がとれてない

2018/08/06(月) 23:12:24.56

でも計算内容を展開してるだけだからいいっちゃいいのか
うーん

2018/08/06(月) 23:39:21.68

全然ずれてない
ｺｰﾙｽﾀｯｸの深さとぴったり一致してる

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

　https://ideone.com/2vP2kN

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

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

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

知恵遅れは再帰が理解できてないのが、よおく分かったわ

2018/08/06(月) 23:51:48.07

余計紛らわしくなっとるわ！同じレベルで連続でリターンすんなしｗ
関数の戻りと呼び出し先の戻りがごちゃごちゃに

2018/08/07(火) 00:04:14.76

https://ideone.com/2vP2kN

知恵遅れ対応はｺﾚが限界

2018/08/07(火) 00:19:28.13

とてもわかりよいです

2018/08/07(火) 00:21:00.39

フィボナッチごときでよくもまあ話題が続くねえ

2018/08/07(火) 00:22:04.86

一般項の求め方くらい学校で習わなかった？

2018/08/07(火) 12:37:07.91

記憶から消滅

2018/08/07(火) 12:49:11.36

一般項は実数を扱うせいで誤差が出るから論外

2018/08/07(火) 12:50:36.34

誤差www
そりゃアホが作れば誤差が問題になるだろうねえwww

2018/08/07(火) 12:51:27.81

アホは素直に加算を繰り返せば良いよ

2018/08/07(火) 17:18:17.21

あれ？今日は半角にしないんだ。

2018/08/07(火) 19:11:24.43

おれは半角野郎じゃない
半角野郎はアホだから無理

◆QZaw55cn4c (ﾜｯﾁｮｲ 7f60-0Uuo) · 2018/08/07(火) 19:21:21.20

>>802
√5 の係数を整数で持てばいいのでは？
F_n = （φ^n - (-φ)^(-n)) / √5, φ=(1 + √5)/2

2018/08/07(火) 20:18:00.72

富士山麓オウム啼く・・・あれ？怖いなこれ

2018/08/07(火) 22:59:36.12

https://ideone.com/jzecIF

やはり
整数を足すにかぎるわ

2018/08/07(火) 23:08:45.73

IEEEの倍精度（64bit）で15～16桁程度の精度
つまりdouble、>>809の精度が概ねその程度

64bit整数なら19桁はいける

2018/08/07(火) 23:43:22.81

相変わらずアホだね
視野が狭い

2018/08/07(火) 23:47:20.78

ルートとｎ乗求める処理オーダーってどんなんじゃろ

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

じつは全部足し算したほうが早かったりして

2018/08/08(水) 05:09:15.02

重いのはべき乗のほうだね

2018/08/08(水) 07:15:16.24

nが大きい場合の計算オーダー

足し算の繰り返しの場合 : n^2
一般項を普通に計算した場合 : n (log n)^2

2018/08/08(水) 09:01:38.18

足し算の繰り返し：O(n)
一般項：O(1)
じゃないの？

2018/08/08(水) 12:44:41.36

加算、乗算、expなどの計算がO(1)で出来る範囲ならそうだね

2018/08/08(水) 12:50:59.40

>>816
まずはO(1)の定義を調べようか…

2018/08/08(水) 12:52:04.40

お前より詳しいと思うよ

2018/08/08(水) 15:07:25.41

お前のほうが可愛いよ

2018/08/08(水) 16:09:12.75

ありがと

2018/08/08(水) 18:58:28.93

フィボナッチの私の回答

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.97

じゃあ多倍長演算を用いて任意のnに対して正確に求める場合を考える

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

以上より、一般項の式の通りまじめに計算しても
オーダー n (log n)^2 で計算できる

2018/08/08(水) 19:10:00.90

工夫すると、計算オーダーを n log n にすることが出来る

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

この式を用いれば
計算オーダー n log n で正確に n 番目のフィボナッチ数を求めることができる

◆QZaw55cn4c (ﾜｯﾁｮｲ 7f60-0Uuo) · 2018/08/08(水) 19:13:46.21

>>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.51

元は>>775の初心者の質問で
計算オーダーとか全く関係なかったんだけど
半角君があまりに無知な癖に自信過剰なので
つい書いてしまった

2018/08/08(水) 19:34:04.93

>>824
それは固定有効精度の場合

固定有効精度であればオーダーは1で計算出来る
>>821参照

2018/08/08(水) 19:36:02.18

固定精度であれば
四則演算もexpも丸めも全て
値によらず固定時間で計算出来る

2018/08/08(水) 19:41:56.80

てことで、
半角君に３勝ですね

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

全て勝ってしまった

まあ学歴も勝ってると思うので４勝か

2018/08/08(水) 19:42:03.28

>>824
桁数分のnかからんの？

◆QZaw55cn4c (ﾜｯﾁｮｲ 7f60-0Uuo) · 2018/08/08(水) 20:30:18.66

>>829
>>826 の指摘のとおり、固定有効精度だったら >>829 になるようです
>>821 は、ちょっと理解が及びません…

2018/08/08(水) 21:38:16.32

頭悪いバカが半角に勝ったつもりでいる
半角はこのスレでは間違いなく天才
他のやつらがお話にならないぐらい頭悪いからな
典型的な頭悪いやつが半角に勝とうと必死になってる

2018/08/08(水) 23:31:41.87

ここまで一般式も行列もコードなし多倍長も

まだはじまってもいない

2018/08/08(水) 23:37:23.86

ISO C99に準拠して、なおかつある程度開発が盛んなOSSを教えてください。
ソースコードが綺麗なことで有名ならなお嬉しいです。

◆QZaw55cn4c (ﾜｯﾁｮｲ 7f60-0Uuo) · 2018/08/08(水) 23:41:36.55

>>832
多桁長は結構手間、というか C/C++ でやるのは実は大変だと思います、キャリーフラグが使えない…

2018/08/09(木) 08:27:30.86

素直にライブラリを使えば良いよ

加減乗算しか使わないから
速度を求めなければ自作するのも大した手間では無いけど

2018/08/09(木) 08:39:55.95

>>833
勉強のためなのかな
もしそうならFreeBSDのコマンドのソースコードが良いと思う
短いものが多いからおすすめ
Linuxのものと比べると読みやすい

FreeBSDソースコードリポジトリ
https://svnweb.freebsd.org/base/release/11.2.0/
"bin"が名前に含まれるフォルダにコマンドのソースがある

2018/08/09(木) 10:23:18.39

GNUのツールチェインもいいんじゃないか
ストールマンのコードとか見れるよ

2018/08/09(木) 10:24:09.98

>>836
ありがとうございます。
> 勉強のため
その通りです。
プログラム言語自体がほぼ初めてなのですが
やはり教科書や仕様書ばかり見て実際を見ないのでは身に付かない
と思いまして、OSSのソースコードであれば
コーディング規約が守られていたり
優秀なアルゴリズムが使われていたりするかなと予測して
OSSのソースコードリーディングをすることにしました。
ところが私が勉強の対象にしているのはISO/IEC 9899:1999（C99）であるのに対し、
ほとんどの有名なOSSはC89/90に準拠し、その古い制約に縛られていてC99の勉強の妨げになりそうでした。
というわけでC99に準拠した有名なOSSを探しているのです。

**デフォルトの名無しさん** (JP 0Heb-5Ep3) · 2018/08/09(木) 10:43:20.34

C89とC99の差を何も見ずにここに書けるなら別だが、
そうでなければ勉強の妨げにはならんから安心しろ

2018/08/09(木) 10:54:41.59

多倍長ならGMPがあるやん

2018/08/09(木) 12:48:19.15

>>838
musl libc

◆QZaw55cn4c (ﾜｯﾁｮｲ ea60-Qb5F) · 2018/08/09(木) 21:25:05.58

>>832
＞一般式
＞多倍長
https://mevius.5ch.net/test/read.cgi/tech/1434079972/50
遅くて残念

2018/08/09(木) 22:23:11.20

もうつくったんかはええｗ

順次加算とスピード同じくらい？

◆QZaw55cn4c (ﾜｯﾁｮｲ ea60-Qb5F) · 2018/08/09(木) 22:27:53.84

>>843
よくわかりません
多桁長計算に手間取りすぎていて、順次加算だろうが、一般式だろうが、差が出ないのです、私の多桁長計算は亀のように遅いのです…

2018/08/09(木) 23:30:35.12

コードを見てないけど

多倍長は乗算がキモ
オーダーn log nで計算する方法を考えよう
フーリエ変換を使うのが普通

2018/08/09(木) 23:45:29.15

最終的に10進数で表記するのが目的であれば
10進数のまま演算した方が良い
2進10進変換の方がフィボナッチより重い

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

同じく>>823の方法を使う場合
桁数の多い最後の方の計算ほど時間がかかる
最後の方の桁数の多い乗算を減らすのが高速化のにつながる

2018/08/10(金) 01:21:54.58

>>841
ありがとうございます。
そもそもmuslを初めて聞きました（恥ずかしながら）
ちょうど，Linuxシステムも勉強したいと思っていたので，これを読もうかなと思います。

2018/08/10(金) 21:12:30.49

とりあえずこの前ｲﾝｽﾄｰﾙした仮想環境のlinuxにgmplibをｲﾝｽﾄｰﾙした
相変わらず低学歴知恵遅れどもは頭悪いﾃｷﾄｰなことばっかりいってるわ

2018/08/10(金) 23:14:02.99

俺なんかGoogleのAIライブラリのTensolFlowインストールしたぞ！

インストールしたぞ

2018/08/10(金) 23:55:30.59

>>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.68

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.47

コードをアップしようと思ったけど
ideoneだとうまく動かないみたい

2018/08/11(土) 10:03:32.46

乙
じゃ、多倍長使って一般項の公式で算出したケースを晒します

スレチと知りつつ 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分ぐらい
文字列化でかなり時間を食ってます