由于专业课需要，学了两个学期的数论，最后直到学完了也对群论没什么直观感, 最近在写信息论课设的时候遇到了C语言下的浮点数精度问题, 然后找到了一些数论中群论的应用,也就是本篇要讲的,满足某种情况的有理浮点数, 甚至是无理数运算(有额外限制)都可以使用这种方法进行算法优化
正文
首先我需要默认读者有模运算基础, 如果没有, 请不要忽略这一部分
首先我们都知道普通的实数域下的加法如何计算, 这里就不搞一遍加法的精确定义了; 然后减法是加相反数, 实数域下求相反数比较简单, 只需要加一个负号, 我们后面会讲如何定义一个相反数运算
接下来我们需要定义一套新的加减乘除四则运算, 这套运算在数学上可证明是在某些情况下 与实数域上的, 我们平常使用的四则运算完全等价的, 要求如下:
- 我们需要找到一个足够大的质数p, 已知我们求解的问题的结果一定小于这个足够大的质数, 在一般情形下,大于1024的质数就可以胜任很多环境的工作了
- 我们运算的结果已知是整数, 但是运算过程中会参杂入浮点数, 比如计算斐波那契数列, 通项公式中参杂大量分数运算, 但是结果一定为整数
- 计算式子中可以包含根号, 但是根号下的内容只能有一种, 因为在我们新定义的乘法中,
\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(这个是精髓)
主要关注最后一行, 我们居然可以让一个分数等价映射为整数
从数学上可以证明, 只要我们的计算式满足上面说的三点, 我们的计算结果就一定是正确的
下面来点例子
参考资料
https://www.bilibili.com/video/BV1EM41117Dv
Comments NOTHING