为什么浮点数的整数表示提供对数的分段线性近似?

问题描述 投票:0回答:0

如果您正在阅读有关 1990 年代图形发展的新闻,您可能已经关注了 Jim Blinn 在 IEEE Computer Graphics & Applications 中的专栏,“Jim Blinn 的角落”。在 1997 年的夏天,您应该将问题打开到一个名为“Floating-Point Tricks”的专栏。所有技巧都基于 Blinn 从微软的两位老手 Steve Gabriel 和 Gideon Yuval 那里传授的以下知识:

"如果只处理正数,浮点数的位模式,解释为整数,给出对数函数的分段线性逼近"

我的问题是,是什么引起了这个特性的浮点数?

适用的地方

这个特性并不是 IEEE 754 浮点数所独有的,尽管它在 Quake III Arena 的快速平方根反比中最著名地被利用了,它使用了standard

float
。然而,它将以抽象格式工作,如 Knuth 的
MIX
教学格式,或与其他格式一起使用,包括以下示例。

据我所知,学术出版社首次记录了这种关系,John Mitchell 的 1961 年Computer Multiplication and Division Using Binary Logarithms 演示了抽象二进制对数系统的方法。 William Kahan 在 1961 年或 1962 年左右在 IBM 7090 上实现了类似的方案。我们也知道,部分原因是 Noah Hellman 的硕士论文,Mitchell-Based Approximate Operations on Floating-Point Numbers,它也在 UNIX 中实现为从 1974 年到 1980 年代中期为 BSD 4.3 创建 libm 的系统平方根。大约在同一时间,Kahan 和他的研究生 K-C Ng 使用这种方法产生了但没有发表一个“神奇”的平方根,该方法旨在对

floats
而非
doubles
进行运算,它将减半并作为 32 位部分进行运算(请参阅相关的 stackoverflow 问题)。

但是,它不适用于所有浮点格式。 DEC 的VAX 浮点格式 交错符号、指数和小数部分(它分成两部分)所以它不会这样做。

我没有问的

我不关心(对于这个问题)工程师是如何了解这种关系的,或者它是在哪里被利用的(参见 FISR)。我想知道它为什么存在。我问过哪些与主题相关的历史问题可以在逆向计算堆栈交换中找到:C 中索引浮点位的早期示例类型双关语和 C 标准/编译器

我也不是在问如何去做,尽管一个好的答案可能包括一个带有一些代码的说明性示例。但是,您应该先看看 codegolf 上这个惊人的 FISR 问题,看看一些非常有趣的问题。

一个很好的答案

一个糟糕的答案可能是“任何有计算尺的工作工程师都会理解这种关系”,尽管我可以想象一个好的答案可能会求助于计算尺。另一个糟糕的答案可能是“因为 Knuth 这么说”,而一个很好的答案可能包括这种情绪,解释取决于 TAOCP 第 2 卷第 4.2.4 节(我没有页码,我有 O'Reilly 的页码令人厌恶,在印刷版第一版中为第 240-247 页)。

一个好的答案应该清楚地理解这种关系的性质及其产生的原因。尽管我可以预见到一些挑战,但证明这种关系必须如此的证据会很有趣。

我为什么要问

我正在写快速逆平方根的历史,相关信息收集于0x5f37642f.com。作为历史学家,调查这个问题的一部分意味着向社区提出这样的问题。我自己没有足够的专业知识来提炼其中的大部分内容,因为我不是数学家或计算机科学家。

FISR 基本上包含三个有趣的部分:对数近似、“魔法”常数和牛顿法。在这三者之间,当人们写 FISR 时,他们写的是魔法常数,然后是牛顿法,然后花费 very 很少时间谈论近似值。我从更广泛的“文献”中得到这种近似值广为人知但不清楚的感觉。我从答案中学到的东西将帮助我理解它。

一个很好的答案将在这项工作的论文或演讲的致谢中注明。

我也在问,因为来吧,还没有人问过这个问题,我们已经在这里多久了?

stackoverflow上的相关问答

math floating-point logarithm approximation
© www.soinside.com 2019 - 2024. All rights reserved.