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

Question

我读了a problem about bullseyes在谷歌代码挑战赛中。 (现在比赛结束了，聊聊也无妨)

Maria starts with t millilitres of black paint, which she will use to draw rings of thickness 1cm (one centimetre). A ring of thickness 1cm is the space between two concentric circles whose radii differ by 1cm.

Maria draws the first black ring around a white circle of radius r cm.

The area of a disk with radius 1cm is π cm2. One millilitre of paint is required to cover area π cm2. What is the maximum number of black rings that Maria can draw?

根据我在纸上的计算，画一个有 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/bullseye.py

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

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

---

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

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

即。系数是

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)))

here , 你得到 3.

[根据 OP 评论进行编辑]。