python - 如何精确求解具有大整数系数（超过整数）的二次方程？

Question

我在 Google Code Jam 中读到了一个关于靶心的问题。（比赛已经结束了，可以聊聊了）

玛丽亚从 t 毫升黑色颜料开始，她将用它来绘制厚度为 1 厘米（一厘米）的戒指。厚度为 1 厘米的环是两个半径相差 1 厘米的同心圆之间的空间。

Maria 在半径为 r cm 的白色圆圈周围画出第一个黑色环。

半径为 1cm 的圆盘面积为 π cm2。覆盖面积 π cm2 需要一毫升油漆。玛丽亚最多可以画出多少个黑环？

根据我在纸上的计算，绘制一个带有 n 个环、内半径为 r 的靶心的油漆面积是 pi 的倍数2*n**2 + n*(2*r-1)

所以给定t*pi油漆的毫升数，问题是找到最大的 n 使得f(n,r) <= t。

今天早上我用二分搜索解决了这个问题https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bu​​llseye.py

我选择二分搜索而不是二次方程，因为我非常担心浮点不精确——在这个问题中，t 和 r 是 10**18 大的整数）。在之前的 Code Jam 中，算术的不精确让我感到厌烦。

但我很好奇。你能支持二次方程以给出具有大整数系数的方程的正确答案吗？像 Sympy 或 Numpy 这样的数学库有什么可以提供给我的吗？

---

证明二次方程对大输入给出错误的答案。例如，使用r=308436464205151562和t=1850618785230909388。要求解的二次方程是

2*n**2 + 616872928410303123*n -1850618785230909388 <= 0

IE。系数是

a = 2
b = 616872928410303123
c = -1850618785230909388

用 Python 计算

    > int((-b + math.sqrt(b**2 - 4*a*c)) / (2*a))
    0

这是错误的答案！正确答案（通过二分搜索找到）是 3

>>> n = 3
>>> 2*n**2 + 616872928410303123*n -1850618785230909388 <= 0
True

Answer 1

对于符号精确操作，有sympy。

如果您粘贴以下内容：

a, b, c = 2, 616872928410303123, -1850618785230909388
x = Symbol('x')
int(max(solve(a*x**2 + b*x + c, x)))

在这里，你得到 3。

[在 OP 评论之后编辑]。

Answer 2

舍入精度在这个问题上杀死了我......但是您可以将所有内容保持在 64 位整数精度，并对得到的二次方程进行二进制搜索。我在这里概述了我的方法。

Answer 3

使用@Vaughn 建议的整数平方根的解决方案

def solve2(r,t):
    """Maximum number of black rings that Maria can draw, with inner radius r, given pi*t of paint. Solve using quadratic equation"""
    import gmpy
    from gmpy import mpz

    a = 2
    b = 2*r - 1
    c = -t

    x = (-b + mpz(b**2 - 4*a*c).sqrt()) // (2*a) 
    return int(x)

Answer 4

如果(t / r^2) > 10000通过 计算sqrt。
如果(t / r^2) < 10000尝试n从 0 开始每次增加 1。