如何在计算机底层将一部分浮点数运算,转换为等价的整数运算,从而大幅提高计算效率?

发布于 2022-12-29  49 次阅读


由于专业课需要,学了两个学期的数论,最后直到学完了也对群论没什么直观感, 最近在写信息论课设的时候遇到了C语言下的浮点数精度问题, 然后找到了一些数论中群论的应用,也就是本篇要讲的,满足某种情况的有理浮点数, 甚至是无理数运算(有额外限制)都可以使用这种方法进行算法优化

正文

​ 首先我需要默认读者有模运算基础, 如果没有, 请不要忽略这一部分

​ 首先我们都知道普通的实数域下的加法如何计算, 这里就不搞一遍加法的精确定义了; 然后减法是加相反数, 实数域下求相反数比较简单, 只需要加一个负号, 我们后面会讲如何定义一个相反数运算

接下来我们需要定义一套新的加减乘除四则运算, 这套运算在数学上可证明是在某些情况下 与实数域上的, 我们平常使用的四则运算完全等价的, 要求如下:

  1. 我们需要找到一个足够大的质数p, 已知我们求解的问题的结果一定小于这个足够大的质数, 在一般情形下,大于1024的质数就可以胜任很多环境的工作了
  2. 我们运算的结果已知是整数, 但是运算过程中会参杂入浮点数, 比如计算斐波那契数列, 通项公式中参杂大量分数运算, 但是结果一定为整数
  3. 计算式子中可以包含根号, 但是根号下的内容只能有一种, 因为在我们新定义的乘法中,

\sqrt{a}\sqrt{b}\neq\sqrt{ab}

这里以一个简单例子来构建我们新的四则运算体系

首先我们选取一个质数p=11

然后我们定义新加法, 新乘法

a\oplus b = a+b\mod 11
a\otimes b = a\times b\mod 11

定义相反数运算

-a = 11-a \mod 11

定义除法运算前, 需要先定义负一次方运算

负一次方运算又叫做 求逆元, 这个过程是有更简单的公式做到的, 但是我们这边采用暴力法

设 a^{-1}=r
若a\otimes r=1 (\mod11)

也就是说,在模11这个环里面, 有0-10总共十个数字, 找到一个数字与a进行O乘, 结果为1的数字, 就是a的逆元, 简称a的逆

比如3和4在模11环中互为逆元, 因为3*4 = 12 模11余1

定义除法为O乘逆元

所以有以下例子

6+7=13
\
6\oplus7=2
\
6\times7=42
\
6\otimes7=9
\
-6=-6
\
\ominus6=5
\
3^{-1}=\frac{1}{3}
\
3^{\ominus1}=4
\
7\div10=\frac{7}{10}
\
7\div10= 7\otimes10^{\ominus1}=7\times10=4(这个是精髓)

主要关注最后一行, 我们居然可以让一个分数等价映射为整数

从数学上可以证明, 只要我们的计算式满足上面说的三点, 我们的计算结果就一定是正确的

下面来点例子

image-20221229161224000

参考资料

https://www.bilibili.com/video/BV1EM41117Dv