网上无意中看到的居说很神的平方根倒数快速算法

wzda_gundam · 发表于 2020-2-15 17:19:40

最精简的1/sqrt()函数：

float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}

另外还有个
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}

jayzah · 发表于 2020-2-15 17:21:47

早就有了，以前还用过了

arm · 发表于 2020-2-15 19:34:25

没看明白

brother_yan · 发表于 2020-2-15 19:56:19

卡马克算法

DevLabs · 发表于 2020-2-15 20:39:34

雷神之锤

brother_yan · 发表于 2020-2-15 21:14:29

arm 发表于 2020-2-15 19:34
没看明白

网上有解释，主要知识点是IEEE754及牛顿迭代

qtechzdh · 发表于 2020-2-15 22:21:00

我以为是口算？。。。

motoedy · 发表于 2020-2-15 22:30:50

0x5f3759df，Quake-III Arena (雷神之锤3)代码里的的魔数。
原始代码里的备注是// what the fuck?

gallle · 发表于 2020-2-16 11:26:50

不管了，先收藏，

cht-rtos · 发表于 2020-2-16 12:06:59

牛逼的程序猿，数学肯定差不了，

strongbaby · 发表于 2020-2-16 12:11:55

没看明白，先收藏

amazing030 · 发表于 2020-2-16 12:42:00

很早就有贴了好像国外有人不信邪挨个测试有个相似的数更准

javenreal · 发表于 2020-2-16 12:50:49

有意思，一楼两段代码里的常数不同：0x5f375a86 VS 0x5f3759df

onev · 发表于 2020-2-16 13:04:26

这个是很著名的一个算法，搞过姿态解算的一般都知道这个算法，可以看看这里 https://en.wikipedia.org/wiki/Fast_inverse_square_root

LM1876 · 发表于 2020-2-16 13:28:38

先收藏

lb0857 · 发表于 2020-2-16 13:55:00

算法，程序灵魂

johncoop · 发表于 2020-2-16 14:35:51

以前坛里就有

lxk52000 · 发表于 2020-2-16 15:36:06

motoedy 发表于 2020-2-15 22:30
0x5f3759df，Quake-III Arena (雷神之锤3)代码里的的魔数。
原始代码里的备注是// what the fuck? {:titte ...

哈哈哈哈~~~~what the fuck

luzj05 · 发表于 2020-2-16 15:46:59

先收藏，

not_at_all · 发表于 2020-2-16 16:49:33

早就知道了。但是用这个算法开平方需要求倒数，效率还是低了一点。开平方还有一个更直接的快速算法。

modbus · 发表于 2020-2-16 17:00:52

这个好像精度不高

t3486784401 · 发表于 2020-2-16 17:03:49

大致猜测下原理：目标是求 x^(-1/2)，牛顿迭代需要有个接近结果的起始数，然后 fuck 那一行里的 >>1 最大作用是把float里二进制指数减半，这样量级就就近 ^(1/2) 处理了

liwei_jlu · 发表于 2020-2-16 17:05:19

详细原理这里有个介绍视频
「骚代码是怎样炼成的」解剖快速平方根倒数算法
https://www.bilibili.com/video/av52050885/

356053261 · 发表于 2020-2-16 17:11:24

年前才刚用过

Mr.D · 发表于 2020-2-16 21:02:08

0x5f3759df 是卡马克选择的值

0x5f375a86是一个教授暴力求解的

这有详细介绍：https://blog.csdn.net/zyex1108/article/details/53540824

rube · 发表于 2020-2-16 22:55:37

mark。。。

rainbow · 发表于 2020-2-17 05:17:25

看标题我以为是楼主学会口算了呢。

lhaoyue · 发表于 2020-2-17 08:55:51

平方根倒数快速算法

异客 · 发表于 2020-2-17 08:57:45

学习一下，看看呢

cdl35 · 发表于 2020-2-17 08:59:38

学习一下，不错，简洁

huangqi412 · 发表于 2020-2-17 10:20:41

https://www.amobbs.com/forum.php ... 5851&highlight=开方 https://www.amobbs.com/forum.php ... 1525&highlight=开方 https://www.amobbs.com/forum.php ... 6598&highlight=开方

xyz543 · 发表于 2020-2-17 10:34:36

【转】神一样的算法，一个数开平方并取倒，0x5f3759df

1399866558 · 发表于 2020-2-17 20:21:34

马克一下。

AlexYzhov · 发表于 2020-2-18 15:43:55

本帖最后由 AlexYzhov 于 2020-2-18 15:45 编辑

快是快，但是要注意数值范围。一些数值范围里这算法的精度跌的很厉害。实用时可以会在快速近似的基础上，再跑几轮迭代

XA144F · 发表于 2020-2-18 16:20:08

64位的常数是0x5fe6ec85e7de30da，谁能试一下?

simplorer · 发表于 2020-2-21 09:22:52

卡马克的神来之笔，这哥们就是程序员楷模。

zhongsandaoren · 发表于 2020-2-21 09:58:56

马克，开平方

ddplys · 发表于 2020-2-21 10:26:59

测试过在32位系统中有优势，在64位系统中已经没有优势了。

jdw924 · 发表于 2020-2-21 10:48:37

我看标题还以为是口算平方根的倒数

yxy633 · 发表于 2020-3-1 08:20:56

开平方倒数

dpzc1234 · 发表于 2020-3-1 08:57:48

谢谢分享

sml009 · 发表于 2020-3-1 21:31:03

学习

qwe2231695 · 发表于 2020-3-13 10:07:00

再倒一次就是快速开方算法

yunhuisong · 发表于 2020-3-13 10:46:37

让我想起来高中时的一个物理老师，当时是个马上要退休的女教师，给我们在黑板上演示过一次徒手开方

nikoli1990 · 发表于 2020-3-13 11:20:01

这个确实牛逼，当初看到，也是一句"What the fuck!"

网上无意中看到的居说很神的平方根倒数快速算法

阿莫论坛20周年了！感谢大家的支持与爱护！！

本帖子中包含更多资源