x的快速整数解（x-1）/ 2 = C [英] Fast integer solution of x(x-1)/2 = c

问题描述

给定一个非负整数 C ，我需要一个高效的算法来找到最大的整数 X ，使得

Given a non-negative integer c, I need an efficient algorithm to find the largest integer x such that

x*(x-1)/2 <= c

等价，我需要一个高效，可靠准确的算法来计算：

Equivalently, I need an efficient and reliably accurate algorithm to compute:

x = floor((1 + sqrt(1 + 8*c))/2)        (1)

为了defineteness我标记了这个问题C ++，所以答案应该是用该语言编写的函数。你可以假设 C 是一个无符号32位整型。

For the sake of defineteness I tagged this question C++, so the answer should be a function written in that language. You can assume that c is an unsigned 32 bit int.

另外，如果你能证明（1）（或同等前pression涉及浮点运算）总是给出正确的结果，这是一个有效的答案也一样，因为在现代的处理器浮点可以更快比整数算法。

Also, if you can prove that (1) (or an equivalent expression involving floating-point arithmetic) always gives the right result, that's a valid answer too, since floating-point on modern processors can be faster than integer algorithms.

推荐答案

如果你愿意承担IEEE一倍正确舍入的所有操作，包括平方根，那么你写的EX pression（加铸加倍）给出了所有输入了正确的答案。

If you're willing to assume IEEE doubles with correct rounding for all operations including square root, then the expression that you wrote (plus a cast to double) gives the right answer on all inputs.

下面是一个非正式的证据。由于 C 是一个32位无符号整数转换为浮点型有53位有效数字， 1 + 8 *（双） ç是精确的，而的sqrt（1 + 8 *（双）C）是正确舍入。 1 +开方（1 + 8 *（双）C）是精确到在一个超低功耗，自上学期小于 2 **（ （32 + 3）/ 2）= 2 ** 17.5 意味着单位在后者任期的最后一位小于 1 ，因而（1 +开方（1 + 8 *（双）C））/ 2 是精确到在一个超低功耗，因为除以 2 是精确的。

Here's an informal proof. Since c is a 32-bit unsigned integer being converted to a floating-point type with a 53-bit significand, 1 + 8*(double)c is exact, and sqrt(1 + 8*(double)c) is correctly rounded. 1 + sqrt(1 + 8*(double)c) is accurate to within one ulp, since the last term being less than 2**((32 + 3)/2) = 2**17.5 implies that the unit in the last place of the latter term is less than 1, and thus (1 + sqrt(1 + 8*(double)c))/2 is accurate to within one ulp, since division by 2 is exact.

最后一块业务是地板。问题的情况下这里的时候（1 +开方（1 + 8 *（双）C））/ 2 被四舍五入到整数。出现这种情况，当且仅当的sqrt（...）向上舍入为奇数。由于开方参数是一个整数，在最坏的情况下看起来像的sqrt（Z ** 2 - 1）的正奇数以Z ，我们势必

The last piece of business is the floor. The problem cases here are when (1 + sqrt(1 + 8*(double)c))/2 is rounded up to an integer. This happens if and only if sqrt(...) rounds up to an odd integer. Since the argument of sqrt is an integer, the worst cases look like sqrt(z**2 - 1) for positive odd integers z, and we bound

z - sqrt(z**2 - 1) = z * (1 - sqrt(1 - 1/z**2)) >= 1/(2*z)

由泰勒展开。由于以Z 小于 2 ** 17.5 ，将差距缩小到最接近的整数至少 1 / ** 18.5 的幅度小于结果 2 ** 17.5 ，这意味着，这个错误不能从正确的舍入结果开方。

by Taylor expansion. Since z is less than 2**17.5, the gap to the nearest integer is at least 1/2**18.5 on a result of magnitude less than 2**17.5, which means that this error cannot result from a correctly rounded sqrt.

采用Yakk的简化，我们可以写

Adopting Yakk's simplification, we can write

(uint32_t)(0.5 + sqrt(0.25 + 2.0*c))

无需进一步检查。

without further checking.

这篇关于x的快速整数解（x-1）/ 2 = C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！