请解释 Goldberg 91 中的定理 7
Please explain theorem 7 in Goldberg 91
定理7
当β=2时，若m、n为整数且|m| < 2^(p - 1) 且 n 具有特殊形式 n = 2^i + 2^j，则 (m n) n = m，前提是浮点运算精确舍入。
如果我 post 把整个证明放在这里，它会很长、难读而且难看。所以请点击右边的link，按ctrl + F，找到Theorem 7。在那里！ Goldberg91
好吧，我不得不说，至少从我自己的角度来看，定理7的证明太奇怪了，虽然作者声称它巧妙。
我只能理解的是m has at most 1 bit right of the binary point。是的，我知道，但为什么 so n*qbar will round to m 结果呢？我也无法理解所谓的 "halfway case" 以及该行之后的几乎所有内容。
欢迎任何帮助，提前致谢。
编辑：
有趣的是，下面的第一条评论一口气解决了我所有的问题，第二条评论建议我缩小我的 post。
没错。要求一个人解释整个证明是不人道的。所以现在我的问题变成了：
为什么the initial unscaled m's low-order bit was 0（在公式9下面的段落中找到）？最高有效数字不应该是零而不是最低有效数字吗？这与 'Big-endian' 或 'Little-endian' 有关系吗？
首先，让我们将 n 缩放 2。n 应该大于或等于 2^p - 1，并且小于 2^p。 n 将由 n' 捐赠。缩放不会有任何区别。修改的是指数，因为数字是二进制的，我们只需要关注尾数。
接下来，m被缩放，产生m'，所以q' = m'/n'，小于1和大于1 /2（其实我觉得应该有1/2 < q' ≤ 1）。像这样缩放是可能的，因为上限恰好是下限的两倍，并且 β = 2.
正如我们所见，2^p - 1 ≤ n' < 2^p 和 1/2 < q' < 1，而 m' = q' * n'。因为q'和n'都是正数，所以m'的最大值是n' 和 q''s maximums, that is 2^p * 1 = 2^p. Similarly, the minimum of m' 是 2^p - 1 * 1/2 = 2^p - 2.
现在 2^p - 2 < m' < 2^p，我们可以说 p - 2 < log2(m') < p，所以二进制小数点右边的位数将是 p-1（当 log2(m') 是p-2 和 p-1 之间）或 p（当 log2(m') 大于或等于 p-1 时）。因此，m' 在二进制小数点右边最多有一位。
正如Mark Dickinson所说，结果，m'和下一个precision-p float up/down之间的差异至少是1/2 .因此，要显示一个数量将四舍五入到 m'，足以显示它在 m'.[=54= 的 1/4 以内]
除此之外，“中途情况”，即该数量恰好是 m' 的 1/4 的情况，值得单独讨论：由于初始未缩放 m had |m| < 2*p - 1，它至少在二进制小数点右边有一位，原因同上。 m是一个整数，所以小数点右边的所有数字都是零。当然，由于这个原因，它的 low-order 位为 0。因为缩放对尾数/尾数没有影响，所以 m' 的 low-order 位也是 0.
因此，使用舍入到偶数，原作者通过写道“在本文的其余部分，将使用舍入到偶数”来采用。上面（可以再用ctrl + F找），m' + 1/4 （二进制为 0.01）将四舍五入为 m'，因为 0 是偶数。
即若q̄ = m n，证明定理需要证明
|n' * q̄ - m'| ≤ 1/4.
更新 1
q'是一个有理数，并且q' < 1，所以我们可以假设q' = 0.q1 q2... 在二进制中，其中 qi，其中 i= 1,2,3... 是包含 0 或 1 的单个数字。令 q̂ = 0.q1 q2 ... qp 1。注意，这个标记是“q-hat”，而不是“q-bar”，它是我刚刚引入的新变量。
现在，如果我们将 q̂ 左移 p + 1 位，我们将得到一个整数，即 q1 q2 ... qp 1，因为所有位都在二进制小数点的左边。以后我会用N捐出这个整数。结果，|q̂ - q'| = |N / 2^(p + 1) - m' / n'|.
N的lower-bit为1，所以我们知道N = 1 + (qp * 2^1 + qp-1 * 2^2 + ... + q1 * 2^p)。显然，N是奇数。本来，n = 2^i + 2^j。由于缩放数字只是将其乘以或除以 2，因此 n' 仍然是两个 2 的指数之和。令它们为 n' = 2^i' + 2^j'。为方便起见，假设 i' ≥ j'.
2^p - 1 ≤ n' < 2^p，所以2^p - 1 ≤ 2^i' + 2^j' < 2^p。结果i'占n'的比例较高，必须是p-1。要使 n'小于2^p，j'不能等于i'。为了可读性，让 k = j'，所以 k ≤ p - 2. 因此，
。 （将所有 n 替换为 n'，将 m 替换为 m'）
我建议你用一些草稿纸自己验证这个公式。
更新 2
看看分子|(2^(p - 1 - k) + 1) * N - 2^(p + 1 - k) * m'|。正如我们已经证明的，k ≤ p - 2，所以p - 1 - k ≥ 1，确保2^(p - 1 - k)和2^(p + 1 - k)是偶数。 (2^(p - 1 - k) + 1)和N都是奇数，所以(2^(p - 1 - k) + 1) * N是奇数，而2^(p + 1 - k) * m'是偶数，奇数不能等于偶数。因此，(2^(p - 1 - k) + 1) * N - 2^(p + 1 - k) * m' 是一个 non-zero 整数。它的绝对值，即分子，因此保证等于或大于1。因此，
|q̂ - q'| ≥ 1 / (n' * 2^(p + 1 - k)).
q' < 1，以及 q̄ < 1，所以 q' * q̄ < 1。结果(m' * q') * q̄ < m'，即n' * q̄ < m。因此，
|n' * q̄ - m'|
= m' - n' * q̄
= n' * (q' - q̄)
/* 由于q̄只有p的精度，所以会是0.q1 q2 ... qp。所以q̄ = q̂ - 2^(- p - 1)。 */
= n' * {q' - [q̂ - 2^(- p - 1)]}
= n' * [q' - q̂ + 2^(- p - 1)]
/* 假设 q' < q̂。不讨论 q > q̂ 的情况。 */
= n' * [- |q' - q̂| + 2^(- p - 1)]
/* 自 |q̂ - q'| ≥ 1 / (n' * 2^(p + 1 - k))、- |q̂ - q'| ≤ - 1 / (n' * 2^(p + 1 - k))。所以 */
≤ n' * {- 1 / [n' * 2^(p + 1 - k)] + 2^(- p - 1)}
= n' * {2^(- p - 1) - 1 / [n' * 2^(p+ 1 - k)]}
/* 我们知道n' = 2^i' + 2^j' = 2^(p - 1) + 2^k */
= [2^(p - 1) + 2^k] * {2^(- p - 1) - 1 / {[2^(p - 1) + 2^k] * 2^( p + 1 - k)}}
/* 等式变得越来越难读。为简洁起见，省略了无关紧要的代数步骤。 */
= 2^-2 + 2^(- p - 1 + k) - 1 / 2^(p + 1 - k)
= 1/4
至此，|n' * q̄ - m'| ≤ 1/4已经成立。如上所述，这就证明了定理。
Q.E.D.
仍然存在的问题：
为什么“案例 q > q̂ 是相似的”？我认为没有那个减号，事情会完全不同！
定理7
当β=2时，若m、n为整数且|m| < 2^(p - 1) 且 n 具有特殊形式 n = 2^i + 2^j，则 (m
如果我 post 把整个证明放在这里，它会很长、难读而且难看。所以请点击右边的link，按ctrl + F，找到Theorem 7。在那里！ Goldberg91
好吧，我不得不说，至少从我自己的角度来看，定理7的证明太奇怪了，虽然作者声称它巧妙。
我只能理解的是m has at most 1 bit right of the binary point。是的，我知道，但为什么 so n*qbar will round to m 结果呢？我也无法理解所谓的 "halfway case" 以及该行之后的几乎所有内容。
欢迎任何帮助，提前致谢。
编辑：
有趣的是，下面的第一条评论一口气解决了我所有的问题，第二条评论建议我缩小我的 post。
没错。要求一个人解释整个证明是不人道的。所以现在我的问题变成了：
为什么the initial unscaled m's low-order bit was 0（在公式9下面的段落中找到）？最高有效数字不应该是零而不是最低有效数字吗？这与 'Big-endian' 或 'Little-endian' 有关系吗？
首先，让我们将 n 缩放 2。n 应该大于或等于 2^p - 1，并且小于 2^p。 n 将由 n' 捐赠。缩放不会有任何区别。修改的是指数，因为数字是二进制的，我们只需要关注尾数。
接下来，m被缩放，产生m'，所以q' = m'/n'，小于1和大于1 /2（其实我觉得应该有1/2 < q' ≤ 1）。像这样缩放是可能的，因为上限恰好是下限的两倍，并且 β = 2.
正如我们所见，2^p - 1 ≤ n' < 2^p 和 1/2 < q' < 1，而 m' = q' * n'。因为q'和n'都是正数，所以m'的最大值是n' 和 q''s maximums, that is 2^p * 1 = 2^p. Similarly, the minimum of m' 是 2^p - 1 * 1/2 = 2^p - 2.
现在 2^p - 2 < m' < 2^p，我们可以说 p - 2 < log2(m') < p，所以二进制小数点右边的位数将是 p-1（当 log2(m') 是p-2 和 p-1 之间）或 p（当 log2(m') 大于或等于 p-1 时）。因此，m' 在二进制小数点右边最多有一位。
正如Mark Dickinson所说，结果，m'和下一个precision-p float up/down之间的差异至少是1/2 .因此，要显示一个数量将四舍五入到 m'，足以显示它在 m'.[=54= 的 1/4 以内]
除此之外，“中途情况”，即该数量恰好是 m' 的 1/4 的情况，值得单独讨论：由于初始未缩放 m had |m| < 2*p - 1，它至少在二进制小数点右边有一位，原因同上。 m是一个整数，所以小数点右边的所有数字都是零。当然，由于这个原因，它的 low-order 位为 0。因为缩放对尾数/尾数没有影响，所以 m' 的 low-order 位也是 0.
因此，使用舍入到偶数，原作者通过写道“在本文的其余部分，将使用舍入到偶数”来采用。上面（可以再用ctrl + F找），m' + 1/4 （二进制为 0.01）将四舍五入为 m'，因为 0 是偶数。
即若q̄ = m
|n' * q̄ - m'| ≤ 1/4.
更新 1
q'是一个有理数，并且q' < 1，所以我们可以假设q' = 0.q1 q2... 在二进制中，其中 qi，其中 i= 1,2,3... 是包含 0 或 1 的单个数字。令 q̂ = 0.q1 q2 ... qp 1。注意，这个标记是“q-hat”，而不是“q-bar”，它是我刚刚引入的新变量。
现在，如果我们将 q̂ 左移 p + 1 位，我们将得到一个整数，即 q1 q2 ... qp 1，因为所有位都在二进制小数点的左边。以后我会用N捐出这个整数。结果，|q̂ - q'| = |N / 2^(p + 1) - m' / n'|.
N的lower-bit为1，所以我们知道N = 1 + (qp * 2^1 + qp-1 * 2^2 + ... + q1 * 2^p)。显然，N是奇数。本来，n = 2^i + 2^j。由于缩放数字只是将其乘以或除以 2，因此 n' 仍然是两个 2 的指数之和。令它们为 n' = 2^i' + 2^j'。为方便起见，假设 i' ≥ j'.
2^p - 1 ≤ n' < 2^p，所以2^p - 1 ≤ 2^i' + 2^j' < 2^p。结果i'占n'的比例较高，必须是p-1。要使 n'小于2^p，j'不能等于i'。为了可读性，让 k = j'，所以 k ≤ p - 2. 因此，
我建议你用一些草稿纸自己验证这个公式。
更新 2
看看分子|(2^(p - 1 - k) + 1) * N - 2^(p + 1 - k) * m'|。正如我们已经证明的，k ≤ p - 2，所以p - 1 - k ≥ 1，确保2^(p - 1 - k)和2^(p + 1 - k)是偶数。 (2^(p - 1 - k) + 1)和N都是奇数，所以(2^(p - 1 - k) + 1) * N是奇数，而2^(p + 1 - k) * m'是偶数，奇数不能等于偶数。因此，(2^(p - 1 - k) + 1) * N - 2^(p + 1 - k) * m' 是一个 non-zero 整数。它的绝对值，即分子，因此保证等于或大于1。因此，
|q̂ - q'| ≥ 1 / (n' * 2^(p + 1 - k)).
q' < 1，以及 q̄ < 1，所以 q' * q̄ < 1。结果(m' * q') * q̄ < m'，即n' * q̄ < m。因此，
|n' * q̄ - m'|
= m' - n' * q̄
= n' * (q' - q̄)
/* 由于q̄只有p的精度，所以会是0.q1 q2 ... qp。所以q̄ = q̂ - 2^(- p - 1)。 */
= n' * {q' - [q̂ - 2^(- p - 1)]}
= n' * [q' - q̂ + 2^(- p - 1)]
/* 假设 q' < q̂。不讨论 q > q̂ 的情况。 */
= n' * [- |q' - q̂| + 2^(- p - 1)]
/* 自 |q̂ - q'| ≥ 1 / (n' * 2^(p + 1 - k))、- |q̂ - q'| ≤ - 1 / (n' * 2^(p + 1 - k))。所以 */
≤ n' * {- 1 / [n' * 2^(p + 1 - k)] + 2^(- p - 1)}
= n' * {2^(- p - 1) - 1 / [n' * 2^(p+ 1 - k)]}
/* 我们知道n' = 2^i' + 2^j' = 2^(p - 1) + 2^k */
= [2^(p - 1) + 2^k] * {2^(- p - 1) - 1 / {[2^(p - 1) + 2^k] * 2^( p + 1 - k)}}
/* 等式变得越来越难读。为简洁起见，省略了无关紧要的代数步骤。 */
= 2^-2 + 2^(- p - 1 + k) - 1 / 2^(p + 1 - k)
= 1/4
至此，|n' * q̄ - m'| ≤ 1/4已经成立。如上所述，这就证明了定理。
Q.E.D.
仍然存在的问题：
为什么“案例 q > q̂ 是相似的”？我认为没有那个减号，事情会完全不同！