C言語なら俺に聞け 146
レス数が950を超えています。1000を超えると書き込みができなくなります。
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;
} コードをアップしようと思ったけど
ideoneだとうまく動かないみたい 乙
じゃ、多倍長使って一般項の公式で算出したケースを晒します
スレチと知りつつ 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分ぐらい
文字列化でかなり時間を食ってます >>821 は桁数が非常に大きくなるとどうなるか、よくわからないんですよ、ちょっと試してみますね 2個の定数は求めたい有効精度+αの精度で求めておけばOK >>853の式の、
nに依存せずに計算できる所だけ先に計算しただけなので expの計算の内部ではlog 2を使うし
2進10進変換にはlog_10 (2)を使うので
doubleより高精度で求めるなら
この辺も先に計算しておくことになるでしょう
>>850ははじめから10進での計算なので
10進文字列に変換するのは一瞬 書き忘れましたが
>>850は10進数で全桁正確に求めた場合の時間です >>855
>>853は仮数部のビット数を任意長に指定してあるから無限精度ですね
出力で桁落ちしてますが 正確に全桁計算してるはずです >>862
どこで有効桁数を指定してます？
無理数の数値計算なので指定しないと低精度で計算しそうですが f(10億)の下位100桁はいくつになります？
私は今出先で私の結果は夜貼ります >>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"で無限精度指定になってると理解してます
正確に出力させると桁が膨大で検証しにくくてしょうがないな…… これ とりあえずかわいそうなぐらい頭悪いﾔﾂしかいないのは分かった
一旦、多倍長演算向けに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) >>864
手計算だと下位3桁は875
合ってます？ >>865
√5を無限精度で求めるなんて不可能ですよ >>866
>>851はそこのリンクのAlgorithm 5の無駄を省いたものですよ 桁数は>>821で瞬時に出ますね
>>850もまず桁数を求めて必要なメモリを確保してから計算してます ↓ｱﾙｺﾞﾘｽﾞﾑ5でｵﾚのｻﾝﾌﾟﾙではちゃんと動いてるからな
https://ideone.com/vhpLPV
↓ｵﾏｴのは動かしても適切な結果にならない
https://ideone.com/vhpLPV
ｵﾏｴのはお話にならないぐらいﾍﾟｹ
↓ﾍﾟｹの理由もちゃんとｺﾒﾝﾄに書いてある
https://ideone.com/vhpLPV 劣化コピーしたらそりゃ正しく動かないよ
nは64bitにしないと >>868
あー、そりゃそうですね…
>>867
968 ずれてますね ｵﾏｴは基本的にｵﾂﾑに問題がある
病院へいったほうがいい nが32bitなら0x80000000にしないと
多倍長で動かすためのテストコードだから
桁数が小さい時の計算回数は全く無視
ループが進んでからやっと演算がはじまる 64回しかﾙｰﾌﾟしてない
Σ n
n→64
はいくつになる n <<= 1;
って書いてあげた方がよかったかな
どうせコンパイラが足し算に直すだろうし 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
全然かなわない
少しやってみて面倒そうだから後回しにしてた一般項やってみるか >>853
同じライブラリを使って>>851のアルゴリズムで計算すると速いかもしれません
a, b, t だけ多倍長にすればいいです ループの最後の64回目は
aだけを計算すればいいので
かなり省略出来ます 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足しとけば間違いがおきることはない で、>>881の結果に基づいて
一般項で処理するｺｰﾄﾞを書いた
https://ideone.com/QKTrLi
一般項で処理
やってみたが
一般項で処理なんかするとともかく遅い
6,942,482 bitsの一般項の計算で
お話にならないぐらいものすごい時間がかかる
calculation 6942482bits
f,10000000,35.082393,34.855636
g,10000000,0.722054,0.720584
つまり、結論としてﾌｨﾎﾞﾅｯﾁ数を求めるなら
GMPに用意されてる関数を使うのが一番
再帰階乗演算使う方がはるかにﾏｼ
一般項で求めるのはｳﾝｺ >>882
gmp の生Cインターフェースを叩くとは、勇気がありますね
私は、C++ インターフェース gmp_class でやることはあっても gmp を C インターフェースで叩くことはありません
あれは、あとから見てなにがなんだかわからなくなってしまう…
a + b√5, a, b ∈Z で表される数は、それ同士を足しても掛けても、その結果はやはり a + b√5 の形になるのだから（そして結果は整数になることがわかっているのだったらなおさら）、
√5 を開かずにその係数を有理数の範囲で計算するようにすれば(>>807)、ずいぶんと違うと思います >>824, >>842 F(1千万)の計算時間
gmp_fib_uiは0.72秒
私のは0.25秒
私が適当に作ったヤツの方が勝っちゃいましたね
コードは以下
https://ideone.com/hklTK1 >>884
＞F(1000000000) = 0
となっていますが、ちゃんと動いているのでしょうか？ ローカル環境では動いてますが、
>>852に書いた通りideoneだと動きません floatとdoubleの値の範囲を教えてください。
-0.000034 < float < 0.000034
-0.00000000016 < ｌong < 0.0000000016
みたいな感じで教えてください＞＜ >>886
ライブラリがないとかならエラーになるし
そんなことってあるん？
何が原因だ >>886
私も手元で確かめました、確かにこれは爆速ですね…私の古いPCでもf(1000万)までならば一瞬で答えが出ます。 C言語でゲームがアクションゲームが作りたくてプログラミングはじめた
実際にプログラミングって楽しいと感じてる
でも入門書通りソートアルゴリズムを勉強してて、基本交換法やら基本選択法は楽にフローチャートもコードも書けたのに、そのあとにやった クイックソートとか単純挿入法では面白いぐらい苦戦した（どっちももうできるようになったけど）
これって、俺のアルゴリズムを考える能力が乏しいってことなのかな
それともはじめはみんなこんなもの？ 再帰とポインタで躓くと昔から伝わっている
特に再帰は禅でもやって悟りを得ないと理解できない だれでも最初は赤ちゃん歩き。私も最初はじゃんけんのプログラミングが全くできなかった。 >>884のバグを修正しました
https://ideone.com/4a3zE8
F(1千万)のideoneでの計算時間は0.31s n log nより遅いように見えるのは
サイズが大きいとキャッシュから外れるため
フーリエ変換はメモリのランダムアクセスが頻発するので
キャッシュに入るかどうかで大きく時間が変わる
適当に並び変えながら変換することで
キャッシュヒット率を上げたり
メインメモリに収まりきらない巨大サイズをHDDを使いながら変換することも出来るのだが、
今回はシンプルさ重視の為見送り
世の中にある高速FFTライブラリに差し替えれば
もっと高速化する >>887
環境依存
float, double がそれぞれIEEE754のbinary32とbinary64準拠の場合はおおよそ
-3.4028234663852885981*10^38 ≦ float ≦ 3.4028234663852885981*10^38
-1.7976931348623157081*10^308 ≦ double ≦ 1.7976931348623157081*10^308
正確には以下の範囲
float : ±(2^24-1)*2^104
double : ±(2^53-1)*2^971
これに追加して±∞, NaN などがある
組み込みなどではdoubleも32bitであることも多い C言語スレだから ^ は排他的論理和の意味で使うべきでしたかね
-340282346638528859811704183484516925440 ≦ binary32 ≦ 340282346638528859811704183484516925440
-1797693134862315708145274237317043567980705675258449965989174768
0315726078002853876058955863276687817154045895351438246423432132
6889464182768467546703537516986049910576551282076245490090389328
9440758685084551339423045832369032229481658085593321233482747978
26204144723168738177180919299881250404026184124858368
≦ binary64 ≦
1797693134862315708145274237317043567980705675258449965989174768
0315726078002853876058955863276687817154045895351438246423432132
6889464182768467546703537516986049910576551282076245490090389328
9440758685084551339423045832369032229481658085593321233482747978
26204144723168738177180919299881250404026184124858368 >>888
単純なバグでした
size_t が64bit前提の部分があったのと、
非常に恥ずかしいですが以下のような動作不定なコードがありました
a->data[i++] = b->data[i] + carry;
私のローカル環境だとたまたま動いていたようです
intが16bitだとまだヤバそうですが、
16bit環境で動かすことはないと思うので気にしないことにします >>896
ありがとうございました
例えば、986.0033っていう数字は
floatではないのでしょうか？ >>899
986.0033 はdoubleのリテラル
986.0033f はfloatのリテラル >>898
ideoneだと100万ちょっと下でRuntimeErrorで途中でとまってるぽいね 蛇とJSとアセンブラ少しかじったんだけどCの効率的な勉強法ある？
主に蛇のチューニングと、これから勉強する予定なんだけど組み込み用マイコンのプログラムを書くために使う
小型のドローンもどきにのせたマイコンに、学習済みパターンをのせて動作制御したい アセンブラをかじったのならCの習得は速そう
組み込みマイコンはどんなやつ？ 聞いといて申し訳ないんだけど全然知らないんだよね門外漢で
シンプリンク？とか言うやつでいいかなと思ってるけど、種類により出来ること出来ないことも分からない 文法をざっくり本とかで覚えたらあとは実践
高速化なら具体例を提示すれば私がアドバイスしますよ
高速化する場合はクリティカルポイントを絞ってから
時間がかからない所は高速化せずにそのままにしておくこと
アルゴリズムや式など、
上位の改良の方が高速化に寄与しやすいので
まずは上の方から考えること
下を高速化することで上が見にくくなって上の改良を妨げるようじゃ本末転倒なので >>901
出力データが大きすぎて途中で切られたのかと思ったけど
エラーになってます？ >>907
なるほど
心にとどめておきます
C入門でおすすめの本とかサイトとかある？
JSには教科書探しに大分苦労させられたので アルゴリズムなど分からないですが、プログラムが出来るようになりますか？ >>909
苦しんで覚えるC言語
https://9cguide.appspot.com
書籍版：ISBN 978-4798030142
>>911の本は古い記法だったはずだから初学者向けではないと思う 古い記法ってこれか？
main(argc, argv)
char **argv;
{
int i 0;
while (i < argc) printf("%s ", argv[i =+ 1]);
return (0);
} >>911
K&Rって言えよ。余計わかりにくい。
>>909
K&Rは「既にプログラミングできる人がCの文法を覚える用」だから、本当に最小セットしか乗ってない。
ただ、それでいい人＝上級者からは絶賛されてる。彼らにとってはいわゆる入門書は冗長すぎるから。
十分にPythonと『アセンブラ』を使え、文法だけ知ればいけるのなら、K&Rはすごくいい。
PythonやJS等の上級言語しか使ったことなく、ポインタって何？なら、
殆どの人はポインタで躓くので、K&Rだけではかなり厳しいと思う。
アセンブラのインデックスレジスタがポインタそのものなのだが、ピンと来るか？
ピンと来るなら、まずK&R買って、だめなら入門書でいいと思う。
意味不明だと思うのなら、最初から入門書を買え。 >>914
> 文法だけ知ればいけるのなら、K&Rはすごくいい。
アホなの？ ありがとう
とりあえず苦Cは確定で、メインとしてK&R 使えるか本屋で見てくる
正直上級者どころか初心者を脱したかどうかレベルだから合わないかもだが
数学でチューリングマシンがーって机上の勉強やってたからかアセンブラはすんなりいった
行けそうだったらK&R使ってみる
てことで本屋行ってくる チューリングマシンは数学板の巨大数スレッドで
よく話題にあがるので
ご教授しに来ていただけるとうれしいです >>916
> 数学でチューリングマシンがーって机上の勉強やってたからかアセンブラはすんなりいった
これって理論畑から行くとチューリングマシンがプログラミングより先に来るんか？
正直、それが何の役に立つのかはよく分からんが… コンピューター言語で記述出来る事の限界がわかる
実際のコーディング技術はあまり関係ないと思う 全ての命令に、次に実行する命令のアドレスを指定出来るようなCPUがあるが
これはちょっと近いか >>919
それって自然言語に対してって事？
なら逆にチューリングマシンの範囲を超える事象って何？
単純に言えば、それは未来永劫今の構造のCPUでは無理ってことになるはずだが、
そんな分野があるのか？ プログラムの停止判定とか
乱数生成とか
非常に増加量の大きな関数とか >>883
a, bを漸化式の形にして
それを行列表記にすると
|0.5 2.5|^n
|0.5 0.5|
これを基底変換して最適化すると
結局>>823 >>851になりました
まあ当たり前と言えば当たり前なんですが Java屋なんですけど自己啓発のために学生時代以来のCを夏休みに勉強しようと思ってます
開発環境のオススメを教えてください
自分が思いつくところでは…
・Vimとgcc
・VScode
・eclipse
こんな所ですが皆さんどうされてますか？
MacもWindowsも両方手元にはあります 開発環境なんて何でもいいから
さっさと勉強しなさい >>926
組み込みとかで特定のコンパイラ使うとかならVSCodeでいいと思うが、そうでないなら普通にVisual Studioでいいと思う IDEが無い時代の開発を体験してみるという修行をしたいのならテキストエディタとコマンドラインだけでやる
これは啓発効果が高い 俺は未だにターミナルとエディター
これ以上の快適さを知らないし知るつもりもない 別にいいんじゃね？
ターミナル最高だからお前らも使え！
とか言わなきゃ Vimと言いたいところだが最近はもっぱらVSCodeばかり 俺は超初心者時代をTurbo Cで、
中級以後はviとccでおぼえた
ただし常に他の環境も色々使ってみてた VisualStudioで良いとか口が裂けても言えねぇよ
MSVCはこのご時世ですらpure CはC89だぞ？
初心者で知らないならともかくこういうスレでVSをCの環境として勧める奴何者だよ gccもclangもインテルコンパイラーもc99さえ100%準拠してないだろ
何でmsvcだけ槍玉あげてんの？ C89/90から覚えれば良い
あとはおまけ
Cが使われるのなんて今時組み込みくらいだ
組み込み用コンパイラだといまだC89/90が多い いろんなコンパイラ、いろんな環境を使って見るのも良い
8bit、RAM64バイトみたいなチープな環境とか いや、組込開発環境なんてgccばっかりだからC99が標準だよ。
まあ妙に保守的なひとがいて古い文法を強制するんだけど… そういやLinuxとかのCUIでTurboCみたいな環境ってあるのかな？
あると外部からsshでログインしている時に使えて良いのだが。 >>940
年寄りぶったガキが「古い環境でもコンパイル可能なコード」にこだわってるせいでどんどんコードが汚くなるのよ。
>>941
emacsじゃだめってことなんだろうねえ。
webベースのIDEでいろいろあるんだろうけど、決定版があったら知りたいわ >>942
細かい表記とかよりももっと大きな事を気にした方がいいぞ >>942
emacsねえ。あれは複雑過ぎて今更覚える気になれない。
まああれが多機能過ぎるせいで他が伸びなかったって感じはするなあ。 >>943
大きいことって、15年前の環境でコンパイルできることだろ？ vimでエディットして :make でビルド、
エラーや警告は quickfix 機能でシラミ潰し。
強く薦める気はないし、他の人に使い方を教えるほどの技量はないけど、
個人的にはこの組み合わせが便利だわ。
errorformat オプションを設定すれば、どんなコンパイラや変換ツールでも
ソースファイルのエラー箇所を呼び出してくれるからね。 C99じゃないと困ることなんてそんなにないしな。わざわざC++と互換性ないコード書くメリットもない。 C89だとforの初期化のときに新しく変数を宣言できないじゃん コンパイラは案件による、それだけ
C99を使う案件でC89がどうたらぬかすのはただのアホ
逆もまたしかり そういう意味じゃたしかに、C99規格に入れられたいくつかの機能は便利だ。
なので訂正する↓
msvcがC99準拠じゃないからといって困ることなんてそんなにないしな。 レス数が950を超えています。1000を超えると書き込みができなくなります。
