ESP32平台下大数计算实现直线交点高精度求解方案问询

针对你用放大1e7倍的经纬度整数求解直线交点时遇到的int64_t溢出问题，且ESP32不支持__int128的情况，以下是几种保证精度的可行方案：

方案1：预化简直线方程+分步约分的有理数运算 #

核心思路是先化简直线的一般式系数，再用有理数（分子+分母）表示所有运算，每一步先约分再计算，避免大整数相乘溢出。

步骤1：化简直线方程 #

对于直线的一般式 a1x + b1y + c1 = 0，先计算三个系数的最大公约数（GCD），将系数除以GCD缩小数值：

#include <stdint.h>
#include <stdlib.h>

int64_t gcd(int64_t a, int64_t b) {
    a = llabs(a);
    b = llabs(b);
    while (b != 0) {
        int64_t temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

void reduce_line(int64_t *a, int64_t *b, int64_t *c) {
    int64_t g = gcd(gcd(*a, *b), *c);
    if (g == 0) return;
    *a /= g;
    *b /= g;
    *c /= g;
    // 保证首项系数为正，统一符号
    if (*a < 0) {
        *a *= -1;
        *b *= -1;
        *c *= -1;
    }
}

步骤2：用有理数结构体实现无溢出运算 #

定义有理数结构体，所有运算先约分再计算，避免中间值过大：

typedef struct {
    int64_t num;  // 分子
    int64_t den;  // 分母（始终为正）
} Rational;

// 化简有理数为最简形式
Rational rational_reduce(Rational r) {
    if (r.den == 0) {
        r.num = 0;
        return r;
    }
    int64_t g = gcd(r.num, r.den);
    r.num /= g;
    r.den /= g;
    if (r.den < 0) {
        r.num *= -1;
        r.den *= -1;
    }
    return r;
}

// 有理数乘法：先约分再相乘，避免溢出
Rational rational_mul(Rational a, Rational b) {
    Rational res;
    // 先约分a.num和b.den
    int64_t g1 = gcd(a.num, b.den);
    int64_t num_a = a.num / g1;
    int64_t den_b = b.den / g1;
    // 再约分a.den和b.num
    int64_t g2 = gcd(a.den, b.num);
    int64_t den_a = a.den / g2;
    int64_t num_b = b.num / g2;
    // 此时相乘的数值已最小化
    res.num = num_a * num_b;
    res.den = den_a * den_b;
    return rational_reduce(res);
}

// 有理数减法
Rational rational_sub(Rational a, Rational b) {
    Rational res;
    // 先通分，再计算
    int64_t common_den = a.den * b.den;
    int64_t num_a = a.num * b.den;
    int64_t num_b = b.num * a.den;
    res.num = num_a - num_b;
    res.den = common_den;
    return rational_reduce(res);
}

// 有理数除法（乘以倒数）
Rational rational_div(Rational a, Rational b) {
    Rational inv_b = {b.den, b.num};
    return rational_mul(a, inv_b);
}

步骤3：计算交点 #

将直线系数转为有理数，代入交点公式计算：

// 输入两条直线的一般式系数，返回交点的有理数形式
// 返回的den为0表示直线平行/重合
Rational compute_intersection_x(int64_t a1, int64_t b1, int64_t c1, int64_t a2, int64_t b2, int64_t c2) {
    // 先化简直线
    reduce_line(&a1, &b1, &c1);
    reduce_line(&a2, &b2, &c2);

    Rational a1_r = {a1, 1};
    Rational b1_r = {b1, 1};
    Rational c1_r = {c1, 1};
    Rational a2_r = {a2, 1};
    Rational b2_r = {b2, 1};
    Rational c2_r = {c2, 1};

    // 计算行列式D = a1*b2 - a2*b1
    Rational D_r = rational_sub(rational_mul(a1_r, b2_r), rational_mul(a2_r, b1_r));
    if (D_r.num == 0) {
        return (Rational){0, 0}; // 无交点或重合
    }

    // 计算分子Nx = b2*c1 - b1*c2
    Rational Nx_r = rational_sub(rational_mul(b2_r, c1_r), rational_mul(b1_r, c2_r));

    // 计算x = Nx / D
    return rational_div(Nx_r, D_r);
}

// 同理计算y坐标
Rational compute_intersection_y(int64_t a1, int64_t b1, int64_t c1, int64_t a2, int64_t b2, int64_t c2) {
    reduce_line(&a1, &b1, &c1);
    reduce_line(&a2, &b2, &c2);

    Rational a1_r = {a1, 1};
    Rational b1_r = {b1, 1};
    Rational c1_r = {c1, 1};
    Rational a2_r = {a2, 1};
    Rational b2_r = {b2, 1};
    Rational c2_r = {c2, 1};

    Rational D_r = rational_sub(rational_mul(a1_r, b2_r), rational_mul(a2_r, b1_r));
    if (D_r.num == 0) {
        return (Rational){0, 0};
    }

    Rational Ny_r = rational_sub(rational_mul(a1_r, c2_r), rational_mul(a2_r, c1_r));
    return rational_div(Ny_r, D_r);
}

使用时，将返回的有理数分子除以分母，即可得到放大1e7倍的交点坐标（如需小数，再除以1e7）。

方案2：128位差值的无溢出计算（极端场景） #

如果方案1仍出现溢出，可通过拆分64位整数为高低位，模拟128位运算计算行列式和分子，再通过辗转相除法约分：

核心函数：计算ab - cd的128位结果 #

typedef struct {
    uint64_t high;
    uint64_t low;
} Int128;

// 计算a*b的128位结果
Int128 multiply_64_to_128(int64_t a, int64_t b) {
    uint64_t ua = (uint64_t)a;
    uint64_t ub = (uint64_t)b;
    uint64_t low = ua * ub;
    uint64_t high = (ua >> 32) * (ub >> 32);
    high += (ua >> 32) * (ub & 0xFFFFFFFF) >> 32;
    high += (ub >> 32) * (ua & 0xFFFFFFFF) >> 32;
    high += (low >> 32);
    return (Int128){high, low};
}

// 计算两个128位整数的差值
Int128 subtract_128(Int128 a, Int128 b) {
    Int128 res;
    if (a.low >= b.low) {
        res.low = a.low - b.low;
        res.high = a.high - b.high;
    } else {
        res.low = a.low + (UINT64_MAX - b.low + 1);
        res.high = a.high - b.high - 1;
    }
    return res;
}

128位整数的GCD计算 #

通过辗转相除法实现128位整数的约分，将结果缩小到int64_t可表示的范围，具体实现可参考二进制除法或减法迭代（代码略，需处理128位取模）。

方案选择 #

• 优先选择方案1：实现简单，性能足够，针对经纬度场景的数值大小，预化简+分步约分基本可避免溢出。
• 仅当极端差值场景下才使用方案2：实现复杂，但能处理所有整数溢出情况。

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