在进行浮点运算时,计算结果的准确性是一个重要的考量。区间算术提供了一种方法来评估和保证计算的准确性。它通过将单个浮点数替换为包含该值的数值范围来实现这一点。例如,使用米制卷尺测量一个3米乘4米的房间可能会得到精确到0.5厘米的结果,这可以表示为[2.995, 3.005]乘以[3.995, 4.005]。区间算术的任何操作都以一种保持这种属性的方式执行。例如,区间的加法([a_inf, a_sup], [b_inf, b_sup])将得到[a_inf + b_inf, a_sup + b_sup]。
区间算术的基本思想是对每个操作执行两次——一次在“舍入到负无穷大”(RD)模式下,一次在“舍入到正无穷大”(RU)模式下。虽然这种方法保证有效,但它有以下缺点:每次操作都需要三次改变舍入模式——到RU,到RD,然后回到默认模式(通常是“舍入到最近”或RN)。在大多数现代处理器上,这些切换非常昂贵。例如,在最新的Intel处理器上,读取SSE舍入模式是昂贵的,而设置它是一个序列化操作!
对于某些操作,一种有效的方法是利用RD(a) == -RU(-a)的事实。为了做到这一点,将区间存储为[-a, b]而不是[a, b]。很明显,加法/减法可以直接使用RU执行,而乘法和除法可能需要一些额外的符号位翻转。这种方法的优点是:每次操作只需要两次舍入模式切换;允许使用SIMD指令进行加法/减法。然而,它不能普遍使用。例如,sqrt(-a) == NaN,而不是-sqrt(a)。
区间算术的问题归结为选择问题。给定一个无限精确的结果A作为其中一个界限,如果要计算区间的下界,需要向下舍入,或者如果要计算区间的上界,需要向上舍入。发现这个信息是可用的。此外,为了使这个工作,需要使用“舍入到最近”模式。
给定两个浮点数a和b,可以按照以下方式计算精确变换:
TwoSum() - (a, b)被转换为(s,e),使得s = RN(a + b)和e = a + b - s
s = RN(a + b)
a' = RN(s - b)
b' = RN(s - a')
da = RN(a - a')
db = RN(b - b')
e = RN(da + db)
TwoSum()算法需要6次浮点运算。
TwoProd - (a, b)被转换为(p, e),使得p = RN(a * b)和e = a * b - p
Split(x, n)需要C = 2^n + 1,其中n = (mantissa的位数 + 1)/2
t1 = RN(C * x)
t2 = RN(x - t1)
xh = RN(t1 + t2)
xl = RN(x - xh)
TwoProd(x, y)
(xh, xl) = Split(x, s)
(yh, yl) = Split(y, s)
p = RN(x * y)
t1 = RN(-p + RN(xh * yh))
t2 = RN(t1 + RN(xh * yl))
t3 = RN(t2 + RN(xl * yh))
e = RN(t3 + RN(xl * yl))
TwoProd()算法需要17次浮点运算。
如果e是负数,那么RN(a + b) == RU(a + b),RD(a + b) == prev(s)。如果e是正数,那么RN(a + b) == RD(a + b),RU(a + b) == succ(s)。TwoProd()也有类似的论证。
TwoSum()和TwoProd()过程足以执行区间加法/减法和乘法。如果存在fma()操作(在IEEE 754-2008下是强制性的),可以计算以下函数:
TwoProdFMA(a, b)
p = RN(a * b)
e = fma(a, b, -p)
TwoProdFMA()算法执行TwoProd(),但只需要2次浮点运算,而不是17次。
Division() - q = RN(a / b); r = -fma(q, b, -a)
Reciprocal() - q = RN(1.0 / b); r = -fma(q, b, -1.0)
Sqrt() - q = RN(sqrt(a)); r = -fma(q, q, -a)
如果r是负数,那么结果 = RN(A) == RU(A),RD(A) == prev(result)。如果r是正数,那么结果 = RN(A) == RD(A),RU(A) == succ(result)。
注意:prev(x)和succ(x)由IEEE Std 754要求,并且在C++ 2011中作为std::nextafter()实现。如果硬件中没有fma()操作,可以使用TwoProd()和TwoSum()操作在软件中模拟。这需要总共35次浮点运算——17次用于TwoProd(),18次用于所需的3次TwoSum()操作。
测试了以下C++实现的区间算术:
“基本”区间算术——根据需要设置RU、RD和默认舍入模式
“RU”区间算术——将[a, b]存储为[-a, b],消除了在许多情况下将舍入模式设置为RD的要求。
“舍入到最近”区间算术——实现了本文中定义的算法。
在所有情况下,如果可用且有用,都使用了SIMD指令。
测试涉及1亿次操作,使用随机操作数,如下所示:
加法
乘法
除法(分母的区间不包括0.0)
平方sqr(x) = (x*x)
平方根
hypot(x, y) = sqrt(sqr(x), sqr(y))。
选择hypot()函数是因为它包括加法(可以通过RU方法优化),平方(也可以通过RU方法优化),以及平方根(只能通过“舍入到最近”方法优化)。它也可以很容易地用简单的C++代码计算。
代码使用Visual Studio 2013在x64 Release模式下编译,使用/fp:strict编译器选项。注意,如果需要获得准确的结果,使用这个选项是必要的。
在Intel Core i7 2670QM处理器上的测试结果(以每次操作的纳秒数表示)如下:
操作 | 基本 | RU | 舍入到最近 |
---|---|---|---|
加法 | 104 | 79 | 25 |
乘法 | 230 | 194 | 61 |
除法 | 280 | 217 | 94 |
平方 | 238 | 185 | 42 |
平方根 | 139 | 83 | 44 |
hypot() | 804 | 702 | 173 |
注意:时间是在减去循环开销和生成随机输入所需的时间后给出的。与最新的Intel处理器不同,这个2670QM处理器没有硬件中的fma(),并且必须在软件中模拟它。这显著降低了“舍入到最近”方法在乘法、除法、平方和平方根操作中的优势。
使用舍入到最近模式的区间算术库是可行的,并且在当前流行的硬件上——比定向舍入方法快3倍以上。
目前正在开发一个区间数学包,它将包括IEEE-1788标准为区间算术所需的大部分前向函数。
IEEE Std 754-2008
IEEE Std 1788-2015
《浮点数运算手册》,Jean-Michel Muller等人,Birkhäuser