ขนาดวิดีโอ: 1280 X 720853 X 480640 X 360
แสดงแผงควบคุมโปรแกรมเล่น
เล่นอัตโนมัติ
เล่นใหม่
平方根は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->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使ったら未定義動作だし……で妥協して無理やりキャストしてたのでマジで助かる
Inverse Square Rootだ！だいすきです！5:13 知ってるだろうがでふふってなりました。
分子動力学の多重極子展開などで3次元座標にある２点間距離の逆乗を高速に求めたい時につかってましたlapacあたりにも実装があった気がするあと数列の加速法とか補間あたりの分野も標本の数を変えずに予測精度を上げれんの？というワクワク感ありますよね。
変態ということだけ知ってたけど、ちゃんとした理屈があるってことに感動した。
rsqrt 命令と掛け算命令さえあれば、rsqrt(x) × x で sqrt(x) の代わりになったり、rsqrt(x) の2乗で1/x が求められたりと、2命令だけで sqrt も div も実現できてお得（sqrt も div も本来とても複雑な回路）
高速逆平方根の解説他でも見たけど難しかったけど、えびまラボさんの解説は無駄がない非常に簡潔だし、とてもわかり易かったです！むしろえびまラボさんでも８分かかるくらいの難しい話ってことか
なるほどlogを取ることで√の操作を1/2倍に置き換えることができるのか肝心のlogの操作は浮動小数点数の表記をそのまま整数として読めばできるから時間を短縮できると
そのWTFな逆平方根関数気になってました！プログラミングの勉強になりました！(ならない)解説ありがとうございます！
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を区分的に直線で表した関数になるのがよくわかる
マジックナンバー！ちょっと前にショート動画で見たやつだfloatの中身がそのまま使えるなんてよく気付いたよなぁ...
コメントのwhat the fuck?が好きすぎる
ちょうど1/√x+1/√y
超絶わかりやすい～！
実際今のCPU命令に√計算あるんでもう忘れて良いやつ
中身はもしかして同じようなことしてるのかな？
マイコンとか組み込み系では使えそう。
@@resistan-y1hこれ
1/√xで思い出したんですが、グラフィック系のシェーダープログラミングだと、rand関数がないので色々工夫して代用しているらしいです。それに関連してメルセンヌツイスターとかXORシフトあたりの乱数生成の解説も聞いてみたいです！ここ最近WGSLでパストレーサーを実装しようとしてるんですが、有名なfract-sinの擬似乱数だと周期性が気になるので他のアルゴリズムも知りたいと思ってます。
このアルゴリズムホント好き
ニュートン法は収束が早いってどっかで聞いたことがあるけどほんとに速いんだなあ
3:23 これ、初めて知ったときちょっと感動したのを思い出した。
ほんとこれ天才
03:35 の「ケチだね」、ふふってなる
C言語にはunionというものがあってだな
確かにすごいが、今はやってはいけない事に分類されるんだろうな。組み込みなど非力なマシンで高速化しようとしたらメモリ使うか、タイミング変えるか、何かをやめる位しかない。メモリ12kと言われて回路図見たら8kしかアクセスできず、アセンブラを削りまくった日々がよみがえる。
flootをlogの近似でlongに救出してニュートン法で帳尻合わせ、数値解析の演習でやりましたねえもしかして数値計算やる人も、実はそんなに気にしていない・・・・・・？
キモすぎと気持ち良いが同時に来る
これの応用で立方根を求める手法もありますよね。
数学あるある証明を丁寧に解説してくれれば理解は出来るけど思い付くわけないだろシリーズ
解説されればまぁ分かる（分からん）のだけどこれをゼロから思いつくのは無理思考ルートが分からん
近似ってセンスやなあ
&yのアドレスがfloatポインタ型だから、それをlongポインタ型にキャストした上で間接参照することで、yの中身自体もfloatからlongにキャストできるってことか？
対数だと計算が楽昔はコンピューターさんも計算尺を使っていたんですね
こういう、floatとかの「仕様」を利用した変態コードは、別環境に移植したときに(つまり仕様が変わったときに)正しく動作しなくなる可能性があるので、手放しで真似するのはやめましょう。組み込みプログラミングとかで「別環境への移植」が考えられない場合や、IEEEなどの規格を厳密に守られていることが保証されている環境間の移植しかありえない場合などは使えるので、そういったことを事前に検討してから使いましょう。
7行テトリスについて解説して欲しいです！
リクエストありがとうございます！お約束はできませんが、年内に出そうとしてみます。
正規表現の微分について解説してほしいです！
これは気持ちいい……
ある文字(二進数の組み合わせ）で表現された数字のlogをとったらその文字そのものが含まれてて、マジックナンバーはその残り物ってこと？
longのビット数って実行環境によって変わらなかったっけ…（32か64になることがほとんどだったと思いますが…）
そうですね、uint32_tを使うのが最適だと思います。floatと整数型のキャストも未定義動作なので、実際にはmemcpyなどを使う必要がありますね
そもそもこのコード自体32bit時代の話で独自命令も乏しかったらしいし、現代じゃ最初のチルノの書き方が何周も回って速くて確実なんだっけ？
「結果が分かりやすいし⑨で」
ぶっちゃけここのチルノは賢い……
精度の比較だけじゃなくて，実際の計算速度の比較も気になる
今のコンピュータでやってもあんまり効果は感じられないと思う。当時の掛け算割り算のコストがバカ高いコンピュータだからこそ価値がある感じのコード。弥生土器とかを見てロマンに浸ってる感じ。この動画は「昔は穴の中で火を焚べてたから縦長で重心低いんだなぁ」って紹介してる感じ。現代は平たいコンロで十分。
@ なるほど！
世の中のエンジニアってこれをぱっと理解できるのか 土方には無理だなやっぱ
詳しくは分からんけど、すげぇってことは分かった.よく気がつくなぁ...
面白い
floatってどこから指数なのかどこで調べるの？
区切りが決まってる
C/C++におけるfloatは実装定義なので、残念ながら一般的な方法はありません。ただし、ほとんどの処理系ではfloatはIEEE754に従っているので、それを仮定すればよいです。C23/C++23以降であれば、それぞれIEEE754に従うことが規定されている _Float32, std::float32_t がありますが、そこまで気にする必要はないです
IEEEと呼ばれる「ルール」がある。
高速逆平方根！
日本語のはずなのに99.8%くらいわかんねぇ…
半分くらいはC言語やけどもな
高速逆平方根アルゴリズム
むずかしい…
はぇ〜すっごい実用的…
マジックナンバーは誤差吸収で真の技術結晶はマジックナンバー書いてある行のyの計算だったってこと？
こんなのよく気づくなあ
なるほどわからん
![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)
![Can You Measure 3000√2-4211 Minutes with a 1-Minute and √2-Minute Hourglass? [English Subtitles]](/img/tr.png)
![Which is Bigger: Fukasetsu Fukasetsuten or Graham's Number? [English Subtitles]](http://i.ytimg.com/vi/3wurgrmYGiw/mqdefault.jpg)
平方根は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->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使ったら未定義動作だし……で妥協して無理やりキャストしてたのでマジで助かる
Inverse Square Rootだ！だいすきです！
5:13
知ってるだろうがでふふってなりました。
分子動力学の多重極子展開などで3次元座標にある２点間距離の逆乗を高速に求めたい時につかってました
lapacあたりにも実装があった気がする
あと数列の加速法とか補間あたりの分野も標本の数を変えずに予測精度を上げれんの？というワクワク感ありますよね。
変態ということだけ知ってたけど、ちゃんとした理屈があるってことに感動した。
rsqrt 命令と掛け算命令さえあれば、rsqrt(x) × x で sqrt(x) の代わりになったり、rsqrt(x) の2乗で1/x が求められたりと、2命令だけで sqrt も div も実現できてお得（sqrt も div も本来とても複雑な回路）
高速逆平方根の解説他でも見たけど難しかったけど、
えびまラボさんの解説は無駄がない非常に簡潔だし、とてもわかり易かったです！
むしろえびまラボさんでも８分かかるくらいの難しい話ってことか
なるほどlogを取ることで√の操作を1/2倍に置き換えることができるのか
肝心のlogの操作は浮動小数点数の表記をそのまま整数として読めばできるから時間を短縮できると
そのWTFな逆平方根関数気になってました！
プログラミングの勉強になりました！(ならない)
解説ありがとうございます！
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を区分的に直線で表した関数になるのがよくわかる
マジックナンバー！
ちょっと前にショート動画で見たやつだ
floatの中身がそのまま使えるなんてよく気付いたよなぁ...
コメントの
what the fuck?
が好きすぎる
ちょうど1/√x+1/√y
超絶わかりやすい～！
実際今のCPU命令に√計算あるんでもう忘れて良いやつ
中身はもしかして同じようなことしてるのかな？
マイコンとか組み込み系では使えそう。
@@resistan-y1hこれ
1/√xで思い出したんですが、グラフィック系のシェーダープログラミングだと、rand関数がないので色々工夫して代用しているらしいです。それに関連してメルセンヌツイスターとかXORシフトあたりの乱数生成の解説も聞いてみたいです！ここ最近WGSLでパストレーサーを実装しようとしてるんですが、有名なfract-sinの擬似乱数だと周期性が気になるので他のアルゴリズムも知りたいと思ってます。
このアルゴリズムホント好き
ニュートン法は収束が早いってどっかで聞いたことがあるけどほんとに速いんだなあ
3:23 これ、初めて知ったときちょっと感動したのを思い出した。
ほんとこれ天才
03:35 の「ケチだね」、ふふってなる
C言語にはunionというものがあってだな
確かにすごいが、今はやってはいけない事に分類されるんだろうな。組み込みなど非力なマシンで高速化しようとしたらメモリ使うか、タイミング変えるか、何かをやめる位しかない。メモリ12kと言われて回路図見たら8kしかアクセスできず、アセンブラを削りまくった日々がよみがえる。
flootをlogの近似でlongに救出してニュートン法で帳尻合わせ、数値解析の演習でやりましたねえ
もしかして数値計算やる人も、実はそんなに気にしていない・・・・・・？
キモすぎと気持ち良いが同時に来る
これの応用で立方根を求める手法もありますよね。
数学あるある証明を丁寧に解説してくれれば理解は出来るけど思い付くわけないだろシリーズ
解説されればまぁ分かる（分からん）のだけどこれをゼロから思いつくのは無理
思考ルートが分からん
近似ってセンスやなあ
&yのアドレスがfloatポインタ型だから、それをlongポインタ型にキャストした上で間接参照することで、yの中身自体もfloatからlongにキャストできるってことか？
対数だと計算が楽
昔はコンピューターさんも計算尺を使っていたんですね
こういう、floatとかの「仕様」を利用した変態コードは、別環境に移植したときに(つまり仕様が変わったときに)正しく動作しなくなる可能性があるので、手放しで真似するのはやめましょう。
組み込みプログラミングとかで「別環境への移植」が考えられない場合や、
IEEEなどの規格を厳密に守られていることが保証されている環境間の移植しかありえない場合などは使えるので、そういったことを事前に検討してから使いましょう。
7行テトリスについて解説して欲しいです！
リクエストありがとうございます！お約束はできませんが、年内に出そうとしてみます。
正規表現の微分について解説してほしいです！
これは気持ちいい……
ある文字(二進数の組み合わせ）で表現された数字のlogをとったらその文字そのものが含まれてて、マジックナンバーはその残り物ってこと？
longのビット数って実行環境によって変わらなかったっけ…（32か64になることがほとんどだったと思いますが…）
そうですね、uint32_tを使うのが最適だと思います。
floatと整数型のキャストも未定義動作なので、実際にはmemcpyなどを使う必要がありますね
そもそもこのコード自体32bit時代の話で独自命令も乏しかったらしいし、現代じゃ最初のチルノの書き方が何周も回って速くて確実なんだっけ？
「結果が分かりやすいし⑨で」
ぶっちゃけここのチルノは賢い……
精度の比較だけじゃなくて，実際の計算速度の比較も気になる
今のコンピュータでやってもあんまり効果は感じられないと思う。
当時の掛け算割り算のコストがバカ高いコンピュータだからこそ価値がある感じのコード。
弥生土器とかを見てロマンに浸ってる感じ。
この動画は
「昔は穴の中で火を焚べてたから縦長で重心低いんだなぁ」
って紹介してる感じ。現代は平たいコンロで十分。
@ なるほど！
世の中のエンジニアってこれをぱっと理解できるのか 土方には無理だなやっぱ
詳しくは分からんけど、すげぇってことは分かった.
よく気がつくなぁ...
面白い
floatってどこから指数なのかどこで調べるの？
区切りが決まってる
C/C++におけるfloatは実装定義なので、残念ながら一般的な方法はありません。
ただし、ほとんどの処理系ではfloatはIEEE754に従っているので、それを仮定すればよいです。
C23/C++23以降であれば、それぞれIEEE754に従うことが規定されている _Float32, std::float32_t がありますが、そこまで気にする必要はないです
IEEEと呼ばれる「ルール」がある。
高速逆平方根！
日本語のはずなのに99.8%くらいわかんねぇ…
半分くらいはC言語やけどもな
高速逆平方根アルゴリズム
むずかしい…
はぇ〜すっごい実用的…
マジックナンバーは誤差吸収で
真の技術結晶はマジックナンバー書いてある行のyの計算だったってこと？
こんなのよく気づくなあ
なるほどわからん