Javaだとlongのビット幅とか浮動小数点のフォーマットが決まっているので、可搬性が高い。 static float Q_rsqrt(float number) { final float threehalfs = 1.5F; float x2 = number * 0.5F, y = number; long i = Float.floatToIntBits(y); i = 0x5f3759df - (i >> 1); y = Float.intBitsToFloat((int)i); y = y * (threehalfs - (x2 * y * y)); y = y * (threehalfs - (x2 * y * y)); return y; }
![x^x^4=64 [English Subtitles]](http://i.ytimg.com/vi/QeAr5NXGfi0/mqdefault.jpg)
![x^x^4=64 [English Subtitles]](/img/tr.png)
![[FINAL] AtCoder Beginner Contest 373 [English Subtitles]](http://i.ytimg.com/vi/qXmLBNBKBDA/mqdefault.jpg)
![21 Weird Ways to Say Hello, World! 1,000,000 Times [English Subtitles]](/img/n.gif)
最後の「忘れろ」が趣深い
平方根はlogにすると計算しやすくて、一方floatのlogを取ってlog(1+x)のマクローリン展開による近似を適用すると上手いこと元の数のlongが現れて、さらにニュートン法で精度を高くしてるのか
もうこれ書いた人機械語話せる数学者やろ
このプログラムを書いた人も起源は知らずに使っていて、本当の元はどっかの大学の数学者だったはずです。その論文は有名になりませんでしたがゲームのような誤差があまり気にならないプログラムでは有用で、ソフトウェア会社で代々受け継がれていたとかだった気がします。
@@collectedby8655 やっぱ数学者って神だわ
logの底は2なのでマクローリン展開とかではないんじゃないかな
@@Anonymous-qx6xp 底の変換でも結局log(e,2)の定数で割ってるだけだし、割となんとかなりそう
@@Anonymous-qx6xp
確かにと思って調べてみたら
0< x=m/2^23
16億くらいの定数のところに書いてある
“// what the fuck?”がおもろい
//なんこれ？
@@可児風我コメントであることを示す記号
@@Asakoto1849 いやまて、what the fuckを日本語訳しただけにも見える。。。
@@inti-lime61 そうでしたか…
想像より数倍変態的なコードだった
floatの仕様の中身に手つっこんで裏技にしてるなんて…
Inverse square rootで検索したらWiki立ってるのかよこのアルゴリズム……
気の狂った遺物マジで大好き
数学と機械計算をグチャグチャにしていいとこどりしたコード好きだ
今まで見た高速逆平方根の説明で一番分かりやすかったです。
意外と解析？されていたんですね。
ゆっくり解説の中で、1番簡潔でわかりやすい動画だと思う
この話知った時、このチャンネルで解説してくれないかなあと思ったので助かります
高速逆平方根の解説他でも見たけど難しかったけど、
えびまラボさんの解説は無駄がない非常に簡潔だし、とてもわかり易かったです！
むしろえびまラボさんでも８分かかるくらいの難しい話ってことか
そのWTFな逆平方根関数気になってました！
プログラミングの勉強になりました！(ならない)
解説ありがとうございます！
変態ということだけ知ってたけど、ちゃんとした理屈があるってことに感動した。
分子動力学の多重極子展開などで3次元座標にある２点間距離の逆乗を高速に求めたい時につかってました
lapacあたりにも実装があった気がする
あと数列の加速法とか補間あたりの分野も標本の数を変えずに予測精度を上げれんの？というワクワク感ありますよね。
Inverse Square Rootだ！だいすきです！
5:13
知ってるだろうがでふふってなりました。
マジックナンバー！
ちょっと前にショート動画で見たやつだ
floatの中身がそのまま使えるなんてよく気付いたよなぁ...
ポインタでキャストする理由は普通にキャストすると整数と小数の内部表現に合わせてキャストされますが、
(1->1.0のように)
ポインタでキャストすることで内部のbitそのままに型を変換できるからですね。
ポインタでのキャストはstrict aliasing ruleに反するので未定義動作ですね。
ちゃんと実装するのであれば、C言語ならunionが使えます。
C++の場合はunionでの変換も未定義動作なので、C++17以前はmemcpy、それ以降はstd::bit_castが使えます (コンパイラの最適化により実際にコピーは行われません)
@@とっぽ-x8g 僕に言われても困りますが💦
動画のソースコードにもコメントでevil floating point bit level hackingって書いてありますね。
@@とっぽ-x8g std::bit_castの存在知らんかったから助かる……
memcpy使って処理したら処理速度落ちるし、reinterpret_cast使ったら未定義動作だし……で妥協して無理やりキャストしてたのでマジで助かる
memcpyはバイト単位の操作だからたぶん遅くなる。
もちろん32bitアラインされたポインタ専用のmemcpyを作ればいいけどそれはもうC++じゃない
とかなんとかいってるけどそういうことを分かったうえで無理してて
しかも役に立ってるのがこの話のミソ
普通は無理してもほとんど効果なくてバグるだけだから「忘れろ」
なるほどlogを取ることで√の操作を1/2倍に置き換えることができるのか
肝心のlogの操作は浮動小数点数の表記をそのまま整数として読めばできるから時間を短縮できると
こういう、floatとかの「仕様」を利用した変態コードは、別環境に移植したときに(つまり仕様が変わったときに)正しく動作しなくなる可能性があるので、手放しで真似するのはやめましょう。
組み込みプログラミングとかで「別環境への移植」が考えられない場合や、
IEEEなどの規格を厳密に守られていることが保証されている環境間の移植しかありえない場合などは使えるので、そういったことを事前に検討してから使いましょう。
数学あるある証明を丁寧に解説してくれれば理解は出来るけど思い付くわけないだろシリーズ
記録って偉大だよね
後世の化学者は常に「強くてニューゲーム」できる
記録を読むだけで寿命尽きちゃう定期
ちょうど1/√x+1/√y
超絶わかりやすい～！
rsqrt 命令と掛け算命令さえあれば、rsqrt(x) × x で sqrt(x) の代わりになったり、rsqrt(x) の2乗で1/x が求められたりと、2命令だけで sqrt も div も実現できてお得（sqrt も div も本来とても複雑な回路）
1+m/2^23が0以上1未満だから、e=floor(log2(y))+127、m/2^23=y*2^(127-e)-1で、i/2^23=e+m/2^23を具体的にyで表すことができる。Excelか何かでグラフを作ってみるとlog2(y)+Cを区分的に直線で表した関数になるのがよくわかる
このアルゴリズムホント好き
ほんとこれ天才
コメントの
what the fuck?
が好きすぎる
これが何に使われてるのかをちゃんと説明してくれるの地味にありがたい、照明の処理に使われているけど詳しいことは省くって言うだけで終わらせることもできるだろうに…
3:48「意外と複雑じゃなかった」
ワイ「…？」
キモすぎと気持ち良いが同時に来る
近似ってセンスやなあ
Javaだとlongのビット幅とか浮動小数点のフォーマットが決まっているので、可搬性が高い。
static float Q_rsqrt(float number) {
final float threehalfs = 1.5F;
float x2 = number * 0.5F, y = number;
long i = Float.floatToIntBits(y);
i = 0x5f3759df - (i >> 1);
y = Float.intBitsToFloat((int)i);
y = y * (threehalfs - (x2 * y * y));
y = y * (threehalfs - (x2 * y * y));
return y;
}
3:23 これ、初めて知ったときちょっと感動したのを思い出した。
ニュートン法は収束が早いってどっかで聞いたことがあるけどほんとに速いんだなあ
これは気持ちいい……
1/√xで思い出したんですが、グラフィック系のシェーダープログラミングだと、rand関数がないので色々工夫して代用しているらしいです。それに関連してメルセンヌツイスターとかXORシフトあたりの乱数生成の解説も聞いてみたいです！ここ最近WGSLでパストレーサーを実装しようとしてるんですが、有名なfract-sinの擬似乱数だと周期性が気になるので他のアルゴリズムも知りたいと思ってます。
このcastはstrict aliasing ruleに反し、未定義動作となるため、正しく動作する保証がないことには注意する必要がありますね。Cではunionを使うのが正しいですね。
これの応用で立方根を求める手法もありますよね。
確かに変態コードなんだけど、ここまでするならもっと開き直って、入射光に大～小5段階くらいのパラメータを割り振って、その大小関係を反射光にも反映、でいい気がする・・・
flootをlogの近似でlongに救出してニュートン法で帳尻合わせ、数値解析の演習でやりましたねえ
もしかして数値計算やる人も、実はそんなに気にしていない・・・・・・？
実際今のCPU命令に√計算あるんでもう忘れて良いやつ
中身はもしかして同じようなことしてるのかな？
マイコンとか組み込み系では使えそう。
@@resistan-y1hこれ
対数だと計算が楽
昔はコンピューターさんも計算尺を使っていたんですね
7行テトリスについて解説して欲しいです！
リクエストありがとうございます！お約束はできませんが、年内に出そうとしてみます。
そ、そうか……！ 指数の情報が直接メモリに書かれているのだから、logを求めるのは容易……！なんてエレガントなんだ
αとかいう定数について考えるのはやめておきます
これが天才か
正規表現の微分について解説してほしいです！
天才は居る
感動するが､実務でこんなコードを書いてはいけない｡
誰もメンテできなくて休日どころか退職後も呼び出される可能性がある｡
&yのアドレスがfloatポインタ型だから、それをlongポインタ型にキャストした上で間接参照することで、yの中身自体もfloatからlongにキャストできるってことか？
精度の比較だけじゃなくて，実際の計算速度の比較も気になる
今のコンピュータでやってもあんまり効果は感じられないと思う。
当時の掛け算割り算のコストがバカ高いコンピュータだからこそ価値がある感じのコード。
弥生土器とかを見てロマンに浸ってる感じ。
この動画は
「昔は穴の中で火を焚べてたから縦長で重心低いんだなぁ」
って紹介してる感じ。現代は平たいコンロで十分。
@ なるほど！
longのビット数って実行環境によって変わらなかったっけ…（32か64になることがほとんどだったと思いますが…）
そうですね、uint32_tを使うのが最適だと思います。
floatと整数型のキャストも未定義動作なので、実際にはmemcpyなどを使う必要がありますね
そもそもこのコード自体32bit時代の話で独自命令も乏しかったらしいし、現代じゃ最初のチルノの書き方が何周も回って速くて確実なんだっけ？
x2 = number*0.5F;
ってあるけど、ビットハック使って
long temp;
temp = *(long*)&number;
temp -= 0x800000;
x2 = *(float*)&temp;
にすれば速くなるかな
解説されればまぁ分かる（分からん）のだけどこれをゼロから思いつくのは無理
思考ルートが分からん
ある文字(二進数の組み合わせ）で表現された数字のlogをとったらその文字そのものが含まれてて、マジックナンバーはその残り物ってこと？
変態すぎる
昔のプログラミングはこんな考え方がてんこ盛りだったよね。懐かしい。
むずかしい…
floatってどこから指数なのかどこで調べるの？
区切りが決まってる
C/C++におけるfloatは実装定義なので、残念ながら一般的な方法はありません。
ただし、ほとんどの処理系ではfloatはIEEE754に従っているので、それを仮定すればよいです。
C23/C++23以降であれば、それぞれIEEE754に従うことが規定されている _Float32, std::float32_t がありますが、そこまで気にする必要はないです
IEEEと呼ばれる「ルール」がある。
このコードが初めてのCでしたはーと❤
面白い
longって符号付き64bitでは？？？
03:35 の「ケチだね」、ふふってなる
詳しくは分からんけど、すげぇってことは分かった.
よく気がつくなぁ...
高速逆平方根アルゴリズム
高速逆平方根！
世の中のエンジニアってこれをぱっと理解できるのか 土方には無理だなやっぱ
高速逆平方根きもちよすぎだろ！
こんなのよく気づくなあ
日本語のはずなのに99.8%くらいわかんねぇ…
半分くらいはC言語やけどもな
きm...(褒め言葉)
マジックナンバーは誤差吸収で
真の技術結晶はマジックナンバー書いてある行のyの計算だったってこと？
中田敦彦のモノマネしながらコレ解説する奴好き
「結果が分かりやすいし⑨で」
ぶっちゃけここのチルノは賢い……
なるほどわからん
なに言ってるかわからん笑笑
進数は人間が読むための数値の書式の話であり、量とは関係ない。ビットは2進数に様相が似ているだけで、2進数ではない。変数には値があり、そこにはビットで表現されており、進数は関係ない。コンピューターの値が2進数と言うひどい嘘があって、ただの数学の話なんだなぁと思った。