学习
实践
活动
专区
工具
TVP
写文章

贪心算法快速平方根倒数算法中的“魔术数字”【含matlab源代码】

快速平方根倒数算法(Fast InvSqrt)是一种快速计算平方根的倒数的算法,常用于向量标准化运算,在光照渲染中有重要应用。 一、快速平方根倒数算法简介及实现 1.1 算法简介 在计算平方根的倒数时,传统的计算方法是先计算a的平方根sqrt(a),再计算它的倒数1/sqrt(a)。 而快速平方根倒数算法则将输入的32位浮点数a作为一个整数i,用“魔术数字”0x5f3759df减去i右移一位的值产生近似的估值y,再使用牛顿迭代法迭代一次,就得到了相当精度的计算结果。 下图为你展示了使用快速平方根倒数法计算4.0的-0.5次方的过程。 随机选取几个数,以上文所得的R* = 1597385922为“魔术数字”,用快速平方根倒数算法计算,结果如下: 可见使用该“魔术数字”的计算精度较高。

43130
  • 广告
    关闭

    热门业务场景教学

    个人网站、项目部署、开发环境、游戏服务器、图床、渲染训练等免费搭建教程,多款云服务器20元起。

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法学习笔记(二):平方根倒数速算法

    序 这是一个神奇的算法! 一、介绍 起源于一篇《改变计算技术的伟大算法》文章,知道这个算法,然后google一下,维基讲的还不错,本文权当自己理清下思路。 所以弄清算法关键障碍是:在计算机中是如何表示浮点数和整数的、整数运算又怎能算出浮点数的平方根倒数的近似值、0x5f3759df怎么来的。 如果用上图的浮点数字节序列来表示整数,那么 ,即 .平方根倒数函数仅能处理正数,所以符号位均为0。 “现在不仅该算法的原作者不明,人们也仍无法明确当初选择这个“魔术数字”的方法。 平方根倒数速算法的神奇之处在于:1、充分利用了浮点数和整数在计算机中的表示,然后以两次转换表示和一次整数运算替换复杂的浮点数计算,最后通过牛顿法加强精度;2、R的取值。

    19220

    【小Y学算法】⚡️每日LeetCode打卡⚡️——21.x 的平方根

    ---- 前言 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧 今天是力扣算法题持续打卡第21天! ---- 原题样例 实现int sqrt(int x)函数。 计算并返回 x 的平方根,其中 x 是非负整数。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。 ---- C#方法:二分查找 思路解析 根据题意我们知道,最终目的就是返回 x 的平方根 我们可以直接调用Sqrt方法找到平方根,但是这就不是算法的本意啦~ 所以可以使用二分法来解决这个问题 二分查找的下界为 文章采用 C#和 Java 两种编程语言进行解题 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们 那今天的算法题分享到此结束啦,明天再见!

    13030

    算法浅谈——快速筛出topK的快速选择算法

    今天我们一起来看一个可以更快实现选择的快速选择算法。 思维推导 在公布答案之前,我想先带着大家试着推导一下解法。这其实才是算法能力的精髓,即是应用已知能力解决未知问题的能力。 我们目前比较熟悉的分治算法好像只有归并排序和快速排序这两个,我们可以试着把这两个算法往这个问题上套。归并排序核心思路是每次将数组一分为二,然后通过这两个数组归并的过程找到我们想要的解法。 算法原理 我们来仔细分析一下,一次快速排序的调整之后,我们可以确定标杆的位置,这样一来就有三种情况。第一种,它所在的位置刚好是K,说明它前面的这一段数组就是答案,直接返回即可。 我们当前的快速选择算法和快排算法几乎如出一辙,整个的思路是一样的,也就是说,在数组是逆序的情况下同样会遇到复杂度升级的问题。不过好在这个问题并不是不可解的,我们下面就来分析一下关于这种情况的优化。 如果你读过《算法导论》的话,一定会找到其中好几个人的名字。该算法可以找到一个比较合适的标杆,用来在快排和快速选择的时候切分数组。

    46110

    关注

    腾讯云开发者公众号
    10元无门槛代金券
    洞察腾讯核心技术
    剖析业界实践案例
    腾讯云开发者公众号二维码

    相关产品

    • 人脸融合

      人脸融合

      腾讯云神图·人脸融合通过快速精准地定位人脸关键点,将用户上传的照片与特定形象进行面部层面融合,使生成的图片同时具备用户与特定形象的外貌特征,支持单脸、多脸、选脸融合,满足不同的营销活动需求……

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券