如何将循环转为常数时间计算？能否预计算x、d移除while(1)循环？

1. 把while(1)循环改成常数时间计算 #

先拆解这个循环的逻辑：初始x=0、d=1-2*r，每次循环先x++，再给d加上4*x-2，直到d>0时调用initialFunction并退出。我们可以通过数学推导直接算出满足条件的x和d，不用一次次迭代。

推导过程 #

• 初始状态：x₀=0，d₀=1-2r
• 当x增加到k时，d的总变化量是从i=1到i=k的4i-2之和，计算这个求和：

  Σ(4i-2) = 4*(k(k+1)/2) - 2k = 2k(k+1) - 2k = 2k²
  

• 此时d的表达式为：d(k) = 1-2r + 2k²

我们要找最小的正整数k（也就是最终的x），让d(k) > 0：

1-2r + 2k² > 0 → k² > r - 0.5 → k > √(r - 0.5)

因为r是整数，r-0.5是半整数，所以√(r-0.5)不可能是整数，直接取大于这个值的最小整数就是x，也就是：
x = (int)sqrt(r - 0.5) + 1

对应的d直接代入公式：d = 1 - 2*r + 2*x*x

2. 不用while(1)，直接预计算x和d调用initialFunction #

完全可以跳过while(1)循环，直接用上面的公式算出x和d。不过要注意浮点运算的精度问题，比如大数值r时，sqrt可能有误差，所以可以加个验证步骤确保x是正确的最小值。

替换后的示例代码 #

void function( int xc, int yc, int r, int color ){
    int x, y = r;
    int d;

    // 计算满足条件的最小x
    double sqrt_val = sqrt(r - 0.5);
    x = (int)sqrt_val + 1;
    // 验证并修正x，避免浮点精度误差
    while( (long long)x*x <= r - 0.5 ) {
        x++;
    }
    while( (long long)(x-1)*(x-1) > r - 0.5 ) {
        x--;
    }

    // 计算对应的d
    d = 1 - 2*r + 2*x*x;

    // 直接调用initialFunction，无需循环
    initialFunction(x, y, d);

    // 后续循环保持不变
    while( x>=y ){
        x++;
        d += 4*x-2;
        if( d>0 ){
            // some code
        }
    }
}

注意点 #

• 用long long计算x*x是为了避免整数溢出，当r较大时，x的平方可能超出int的范围。
• 验证步骤是兜底用的，大部分情况下直接(int)sqrt(r-0.5)+1就能得到正确的x，但极端情况（比如r刚好让sqrt结果接近整数）可以确保正确性。

内容的提问来源于stack exchange，提问作者Dobijasek