Làm thế nào để giải quyết chính xác phương trình bậc hai với hệ số nguyên lớn (trên số nguyên)?

Question

Tôi đọc số a problem about bullseyes trong Google Code Jam. (Cuộc thi là hơn bây giờ, do đó, nó không quan trọng để nói về nó)

Maria bắt đầu với ml t sơn đen, mà cô sẽ sử dụng để vẽ vòng tròn dày 1cm (một centimet). Một vòng dày 1cm là khoảng cách giữa hai vòng tròn đồng tâm có bán kính khác nhau 1cm.

Maria vẽ vòng màu đen đầu tiên quanh vòng tròn bán kính màu trắng r cm.

Diện tích đĩa có bán kính 1cm là π cm2. Cần một mililít sơn để che phủ diện tích π cm2. Số vòng đen tối đa mà Maria có thể vẽ là bao nhiêu?

Theo tính toán của tôi trên giấy, diện tích sơn để vẽ một Bullseye với nhẫn n, bán kính bên trong r, như một bội số của pi là 2*n**2 + n*(2*r-1)

Vì vậy, cho t*pi millitres của sơn vấn đề là tìm n lớn nhất sao cho f(n,r) <= t.

Sáng nay tôi giải quyết rằng với tìm kiếm nhị phân https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bullseye.py

tôi đã chọn tìm kiếm nhị phân trên các phương trình bậc hai vì tôi rất cảnh giác với dấu chấm động không chính xác - trong vấn đề này t và r là các số nguyên lớn như 10 ** 18). Số học không chính xác bit tôi trong một Jam mã trước đó.

Nhưng tôi rất tò mò. Bạn có thể đưa lên phương trình bậc hai để đưa ra câu trả lời đúng cho phương trình với hệ số nguyên lớn không? Các thư viện toán học như Sympy hay Numpy có gì để cung cấp cho tôi không?

---

Trình diễn phương trình bậc hai cho câu trả lời sai cho các đầu vào lớn. Ví dụ: với r=308436464205151562 và t=1850618785230909388. Phương trình bậc hai để giải quyết là

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

ie. các hệ số là

a = 2 
b = 616872928410303123 
c = -1850618785230909388 

Computing bằng Python

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

Đây là câu trả lời sai! Câu trả lời đúng (được tìm thấy bởi tìm kiếm nhị phân) là 3

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

Answer 1

Đối với các thao tác chính xác tượng trưng, ​​có sympy.

Nếu bạn dán như sau:

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

here, bạn sẽ có được 3.

[Sửa sau bình luận OP].

Answer 2

Nếu (t/r^2) > 10000 tính qua sqrt.
Nếu (t/r^2) < 10000 thử mọi n bắt đầu từ 0 tăng 1.

Answer 3

Giải pháp sử dụng rễ nguyên vuông theo đề nghị của @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

Độ chính xác roundoff giết tôi về vấn đề này ... nhưng bạn có thể giữ mọi thứ ở độ chính xác số nguyên 64 bit và thực hiện tìm kiếm nhị phân trên phương trình bậc hai kết quả. Tôi vạch ra cách tiếp cận của tôi here.