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; }
![How Many Packs Are Needed on Average to Collect All Cards in PTCGP? [English Subtitles]](http://i.ytimg.com/vi/euC280eesGM/mqdefault.jpg)
![How Many Packs Are Needed on Average to Collect All Cards in PTCGP? [English Subtitles]](/img/tr.png)
![Can You Measure 3000√2-4211 Minutes with a 1-Minute and √2-Minute Hourglass? [English Subtitles]](http://i.ytimg.com/vi/jNHJ3z6L5AQ/mqdefault.jpg)
![21 Weird Ways to Say Hello, World! 1,000,000 Times [English Subtitles]](http://i.ytimg.com/vi/OHOTGcQmndQ/mqdefault.jpg)
最後の「忘れろ」が趣深い
平方根はlogにすると計算しやすくて、一方floatのlogを取ってlog(1+x)のマクローリン展開による近似を適用すると上手いこと元の数のlongが現れて、さらにニュートン法で精度を高くしてるのか
もうこれ書いた人機械語話せる数学者やろ
このプログラムを書いた人も起源は知らずに使っていて、本当の元はどっかの大学の数学者だったはずです。その論文は有名になりませんでしたがゲームのような誤差があまり気にならないプログラムでは有用で、ソフトウェア会社で代々受け継がれていたとかだった気がします。
@@collectedby8655 やっぱ数学者って神だわ
logの底は2なのでマクローリン展開とかではないんじゃないかな
@@Anonymous-qx6xp 底の変換でも結局log(e,2)の定数で割ってるだけだし、割となんとかなりそう
@@Anonymous-qx6xp
確かにと思って調べてみたら
0< x=m/2^23
想像より数倍変態的なコードだった
floatの仕様の中身に手つっこんで裏技にしてるなんて…
Inverse square rootで検索したらWiki立ってるのかよこのアルゴリズム……
気の狂った遺物マジで大好き
16億くらいの定数のところに書いてある
“// what the fuck?”がおもろい
//なんこれ？
@@可児風我コメントであることを示す記号
@@Asakoto1849 いやまて、what the fuckを日本語訳しただけにも見える。。。
@@inti-lime61 そうでしたか…
今まで見た高速逆平方根の説明で一番分かりやすかったです。
意外と解析？されていたんですね。
ゆっくり解説の中で、1番簡潔でわかりやすい動画だと思う
そのWTFな逆平方根関数気になってました！
プログラミングの勉強になりました！(ならない)
解説ありがとうございます！
高速逆平方根の解説他でも見たけど難しかったけど、
えびまラボさんの解説は無駄がない非常に簡潔だし、とてもわかり易かったです！
むしろえびまラボさんでも８分かかるくらいの難しい話ってことか
この話知った時、このチャンネルで解説してくれないかなあと思ったので助かります
変態ということだけ知ってたけど、ちゃんとした理屈があるってことに感動した。
数学あるある証明を丁寧に解説してくれれば理解は出来るけど思い付くわけないだろシリーズ
記録って偉大だよね
後世の化学者は常に「強くてニューゲーム」できる
記録を読むだけで寿命尽きちゃう定期
分子動力学の多重極子展開などで3次元座標にある２点間距離の逆乗を高速に求めたい時につかってました
lapacあたりにも実装があった気がする
あと数列の加速法とか補間あたりの分野も標本の数を変えずに予測精度を上げれんの？というワクワク感ありますよね。
ポインタでキャストする理由は普通にキャストすると整数と小数の内部表現に合わせてキャストされますが、
(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++じゃない
とかなんとかいってるけどそういうことを分かったうえで無理してて
しかも役に立ってるのがこの話のミソ
普通は無理してもほとんど効果なくてバグるだけだから「忘れろ」
Inverse Square Rootだ！だいすきです！
5:13
知ってるだろうがでふふってなりました。
なるほどlogを取ることで√の操作を1/2倍に置き換えることができるのか
肝心のlogの操作は浮動小数点数の表記をそのまま整数として読めばできるから時間を短縮できると
rsqrt 命令と掛け算命令さえあれば、rsqrt(x) × x で sqrt(x) の代わりになったり、rsqrt(x) の2乗で1/x が求められたりと、2命令だけで sqrt も div も実現できてお得（sqrt も div も本来とても複雑な回路）
これが何に使われてるのかをちゃんと説明してくれるの地味にありがたい、照明の処理に使われているけど詳しいことは省くって言うだけで終わらせることもできるだろうに…
マジックナンバー！
ちょっと前にショート動画で見たやつだ
floatの中身がそのまま使えるなんてよく気付いたよなぁ...
ちょうど1/√x+1/√y
4:04 「改めてコードを見てみよう」
なんでも鑑定団の、作者に関する前知識解説のあとの「改めて今回の依頼品を見てみよう」ってセリフを唐突に思い出した
超絶わかりやすい～！
ほんとこれ天才
このアルゴリズムホント好き
コメントの
what the fuck?
が好きすぎる
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を区分的に直線で表した関数になるのがよくわかる
ニュートン法は収束が早いってどっかで聞いたことがあるけどほんとに速いんだなあ
キモすぎと気持ち良いが同時に来る
これは気持ちいい……
このcastはstrict aliasing ruleに反し、未定義動作となるため、正しく動作する保証がないことには注意する必要がありますね。Cではunionを使うのが正しいですね。
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;
}
最初に真ん中のマジックナンバーを見た時は複利計算の72の法則みたいな話かと思ったけど
実際はもっとだいぶ変態な話だった……
3:23 これ、初めて知ったときちょっと感動したのを思い出した。
こういう、floatとかの「仕様」を利用した変態コードは、別環境に移植したときに(つまり仕様が変わったときに)正しく動作しなくなる可能性があるので、手放しで真似するのはやめましょう。
組み込みプログラミングとかで「別環境への移植」が考えられない場合や、
IEEEなどの規格を厳密に守られていることが保証されている環境間の移植しかありえない場合などは使えるので、そういったことを事前に検討してから使いましょう。
flootをlogの近似でlongに救出してニュートン法で帳尻合わせ、数値解析の演習でやりましたねえ
もしかして数値計算やる人も、実はそんなに気にしていない・・・・・・？
そ、そうか……！ 指数の情報が直接メモリに書かれているのだから、logを求めるのは容易……！なんてエレガントなんだ
αとかいう定数について考えるのはやめておきます
これの応用で立方根を求める手法もありますよね。
7行テトリスについて解説して欲しいです！
リクエストありがとうございます！お約束はできませんが、年内に出そうとしてみます。
対数だと計算が楽
昔はコンピューターさんも計算尺を使っていたんですね
これが天才か
天才は居る
実際今のCPU命令に√計算あるんでもう忘れて良いやつ
中身はもしかして同じようなことしてるのかな？
マイコンとか組み込み系では使えそう。
@@resistan-y1hこれ
もっと言うと「3D対応グラフィックボード」という存在が少し後に登場するんだよね
平方根命令なら昔から普通にあったよ？ 平方根じゃなくて逆平方根(それも超速い)なのが重要なんだよ(ベクトル正規化を乗算で済ます事ができる)。
尤もIntel系もARM系も今のアプリケーション向け命令セットなら高速逆平方根近似をSIMDで持ってるけれどね。けれどそれら自体が、このアルゴリズムがHW設計者にとっても重要だった事の証なんだよ。
ラマヌジャン的な変態味を感じる
1/√xで思い出したんですが、グラフィック系のシェーダープログラミングだと、rand関数がないので色々工夫して代用しているらしいです。それに関連してメルセンヌツイスターとかXORシフトあたりの乱数生成の解説も聞いてみたいです！ここ最近WGSLでパストレーサーを実装しようとしてるんですが、有名なfract-sinの擬似乱数だと周期性が気になるので他のアルゴリズムも知りたいと思ってます。
@@匿名匿名-p9m シェーダー言語だと乱数無いんだ…ナルホド、確かにパストレースにはキツい。
LuxRender(LuxCoreRender)やblenderのCyclesパストレーサーのコードとか参考になるかも。
解説されればまぁ分かる（分からん）のだけどこれをゼロから思いつくのは無理
思考ルートが分からん
高速逆平方根アルゴリズム
I still remember the original video of Nemean.
「floatの中身はlog」って言われたらよく分からんけど説あるって思うわ
&yのアドレスがfloatポインタ型だから、それをlongポインタ型にキャストした上で間接参照することで、yの中身自体もfloatからlongにキャストできるってことか？
昔のプログラミングはこんな考え方がてんこ盛りだったよね。懐かしい。
むずかしい…
ある文字(二進数の組み合わせ）で表現された数字のlogをとったらその文字そのものが含まれてて、マジックナンバーはその残り物ってこと？
正規表現の微分について解説してほしいです！
longのビット数って実行環境によって変わらなかったっけ…（32か64になることがほとんどだったと思いますが…）
そうですね、uint32_tを使うのが最適だと思います。
floatと整数型のキャストも未定義動作なので、実際にはmemcpyなどを使う必要がありますね
そもそもこのコード自体32bit時代の話で独自命令も乏しかったらしいし、現代じゃ最初のチルノの書き方が何周も回って速くて確実なんだっけ？
マジックナンバーは誤差吸収で
真の技術結晶はマジックナンバー書いてある行のyの計算だったってこと？
x2 = number*0.5F;
ってあるけど、ビットハック使って
long temp;
temp = *(long*)&number;
temp -= 0x800000;
x2 = *(float*)&temp;
にすれば速くなるかな
精度の比較だけじゃなくて，実際の計算速度の比較も気になる
今のコンピュータでやってもあんまり効果は感じられないと思う。
当時の掛け算割り算のコストがバカ高いコンピュータだからこそ価値がある感じのコード。
弥生土器とかを見てロマンに浸ってる感じ。
この動画は
「昔は穴の中で火を焚べてたから縦長で重心低いんだなぁ」
って紹介してる感じ。現代は平たいコンロで十分。
@ なるほど！
正に当時これを知ってすぐ430FX+258KB外付けL2プラットフォームでPentiun133MHz(P54C後期版)搭載PCのWindowsNT4.0環境でボーランドC/C++コンパイラーを用い三次元ベクトル正規化の実用性能と精度をテスト、確か2.25倍以上の速度を記録。
Quake3のメインプラットフォームとなるP6系ならL2直接アクセス可能なので更に高速になると予測。PentiunⅡ400MHzで仮に2.5倍高速ならば1GHz品と同等の性能を叩き出せる。これは圧巻だと思った。
英語版Wikipediaには、このQ3高速逆平方根近似のトピックが在り、今では更に精度の高い定数(16進数マジックナンバー部)が提示されており、倍精度実装での定数や、C/C++可搬性を考慮したコード実装法、このアルゴリズムの辿った歴史まで記述されているので、深く探求したい方、より高精度な結果が必要な応用や組み込み分野など広く応用したい方などは必見。
当時これを知ってすぐ430FXプラットフォーム外付けL2キャッシュ256KBのPentiun133MHz品(P54C後期版)でベクトル正規化に於ける実用性能と精度をテスト、…確か2.25倍のパフォーマンスを記録。
Quake3のメインプラットフォームだったP6系ならL2に直接アクセス可能なので、より高速化されると予測できる。仮に2.5倍高速化されたなら極めて重いベクトル正規化部分(当時のGeForceでもOpenGLに渡す前にCPUで計算しておかなければならないので極めて重要)にてPentiunⅡ400MHz品で1GHz品に匹敵する性能を叩き出せる事になり、これには圧倒された。
なお英語版Wikipediaには、このQ3高速逆平方根のトピックが在り、アルゴリズムの辿った歴史やメカニズム解説だけでなく、その後の研究により得られた、より精度に優れる定数(16進数マジックナンバー)、更に倍精度実装ケースでの最適な定数、可搬性を考慮したC/C++コード実装などまで記述されており、より高精度な結果が要求される応用や組み込み分野、FPGA実装実現など深く探求される方なら極めて参考になりますよ。
なおQuake3は圧倒的にレスポンスが素晴らしいスポーツ系FPSの大傑作で、世界トップクラスプレイヤーの対戦動画は多数ありますが、もう凄すぎ神がかっている人達のそれは圧倒的と云うか異常な世界。リアル系FPSから入って未見な方は是非一度チェックしてみることお薦め！
当時これを知ってすぐ430FXプラットフォーム外付けL2キャッシュ256KBのPentiun133MHz品(P54C後期版)でベクトル正規化に於ける実用性能と精度をテスト、…確か2.25倍のパフォーマンスを記録。
Quake3のメインプラットフォームだったP6系ならL2に直接アクセス可能なので、より高速化されると予測できる。仮に2.5倍高速化されたなら極めて重いベクトル正規化部分(当時のGeForceでもOpenGLに渡す前にCPUで計算しておかなければならないので極めて重要)にてPentiunⅡ400MHz品で1GHz品に匹敵する性能を叩き出せる事になり、これには圧倒された。
なお英語版Wikipediaには、このQ3高速逆平方根のトピックが在り、アルゴリズムの辿った歴史やメカニズム解説だけでなく、その後の研究により得られた、より精度に優れる定数(16進数マジックナンバー)、更に倍精度実装ケースでの最適な定数、可搬性を考慮したC/C++コード実装などまで記述されており、より高精度な結果が要求される応用や組み込み分野、FPGA実装実現など深く探求される方なら極めて参考になりますよ。
なおQuake3は圧倒的にレスポンスが素晴らしいスポーツ系FPSの大傑作で、世界トップクラスプレイヤーの対戦動画は多数ありますが、もう凄すぎ神がかっている人達のそれは圧倒的と云うか異常な世界。リアル系FPSから入って未見な方は是非一度チェックしてみることお薦め！
面白い
変態すぎる
longの数値例の3つ目を見逃さない
191919って一体…？(すっとぼけ)
詳しくは分からんけど、すげぇってことは分かった.
よく気がつくなぁ...
こんなのよく気づくなあ
このコードが初めてのCでしたはーと❤
感動するが､実務でこんなコードを書いてはいけない｡
誰もメンテできなくて休日どころか退職後も呼び出される可能性がある｡
この時代は発売したらそれっきりだから関係ないんよ
世の中のエンジニアってこれをぱっと理解できるのか 土方には無理だなやっぱ
「結果が分かりやすいし⑨で」
ぶっちゃけここのチルノは賢い……
ラマヌジャンみたいなコードや...
03:35 の「ケチだね」、ふふってなる
日本語のはずなのに99.8%くらいわかんねぇ…
半分くらいはC言語やけどもな
凄くマニアックなやり方！でも計算速度はめちゃくちゃ速そう。
コンピューターが貧弱な時代の方が、色々 創意工夫があったんですね。
コメントをしっかり書いといてあげないと、後の時代の人は分からないと思う。
高速逆平方根きもちよすぎだろ！
高速逆平方根！
floatってどこから指数なのかどこで調べるの？
区切りが決まってる
C/C++におけるfloatは実装定義なので、残念ながら一般的な方法はありません。
ただし、ほとんどの処理系ではfloatはIEEE754に従っているので、それを仮定すればよいです。
C23/C++23以降であれば、それぞれIEEE754に従うことが規定されている _Float32, std::float32_t がありますが、そこまで気にする必要はないです
IEEEと呼ばれる「ルール」がある。
中田敦彦のモノマネしながらコレ解説する奴好き
確かに変態コードなんだけど、ここまでするならもっと開き直って、入射光に大～小5段階くらいのパラメータを割り振って、その大小関係を反射光にも反映、でいい気がする・・・
コードは考えつくのは大変だけど考えついたら米粒1個以下のコストで使える
むしろ閃きをここまでする？で終わらせないのがプログラミングの凄いところなんよね
きm...(褒め言葉)
Fワードサムネに使わんほうがええで
◯で隠しときー
なるほどわからん
longって符号付き64bitでは？？？
Cの場合、各型の厳密なサイズは決まっておらず、long型も環境によっては32bitだったり64bitだったりします
逆に64bitが確実に欲しいならlong longかと
なに言ってるかわからん笑笑
進数は人間が読むための数値の書式の話であり、量とは関係ない。ビットは2進数に様相が似ているだけで、2進数ではない。変数には値があり、そこにはビットで表現されており、進数は関係ない。コンピューターの値が2進数と言うひどい嘘があって、ただの数学の話なんだなぁと思った。