Jak dokładnie rozwiązać równania kwadratowe o dużych współczynnikach całkowitych (w liczbach całkowitych)?

Question

Czytam a problem about bullseyes w Google Code Jam. (Konkurs się skończył, więc jest w porządku, aby o tym mówić)

Maria rozpoczyna się t mililitrów czarną farbą, która będzie używała wyciągnąć pierścienie 1cm grubości (jeden centymetr). Pierścień o grubości 1 cm to przestrzeń między dwoma współśrodkowymi okręgami, których promienie różnią się o 1 cm.

Maria rysuje pierwszy czarny pierścień wokół białego okręgu o promieniu r cm.

Obszar dysku o promieniu 1 cm to π cm2. Do pokrycia powierzchni π cm2 wymagane jest 1 mililitr farby. Jaka jest maksymalna liczba czarnych pierścieni, które Maria może narysować?

Według moich obliczeń na papierze, powierzchnia farby narysować dziesiątkę zn pierścienie, wewnętrzny promień r, jako wielokrotność PI 2*n**2 + n*(2*r-1)

Więc podane t*pi millitres farby problemem jest znalezienie największy n taki, że f(n,r) <= t.

Dziś rano rozwiązany, że przy wyszukiwaniu binarnym https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bullseye.py

Wybrałem przeszukiwanie binarne nad równania kwadratowego, bo jestem bardzo ostrożny zmiennoprzecinkowej nieścisłości - w ten problem t i R są liczbami całkowitymi wielkie jak 10 ** 18). Niedokładność arytmetyczna ugryzła mnie w poprzednim Zakleszczeniu kodu.

Ale jestem ciekawy. Czy możesz wzmocnić równanie kwadratowe, aby dać poprawną odpowiedź dla równań o dużych współczynnikach całkowitych? Czy biblioteki matematyczne takie jak Sympy czy Numpy mają coś do zaoferowania?

---

Demonstracja, że ​​równanie kwadratowe daje błędną odpowiedź dla dużych wejść. Na przykład z r=308436464205151562 i t=1850618785230909388. Równanie kwadratowe do rozwiązania to:

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

tj. współczynniki są

a = 2 
b = 616872928410303123 
c = -1850618785230909388 

Computing w Pythonie

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

To zła odpowiedź! Prawidłowa odpowiedź (znaleziona za pomocą wyszukiwania binarnego) to 3

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

Answer 1

Aby uzyskać symboliczne dokładne manipulacje, istnieje sympy.

Jeśli wklej następujący:

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

here, masz 3.

[edytowane po OP komentarz].

Answer 2

Jeśli (t/r^2) > 10000 obliczyć za pomocą .
Jeśli (t/r^2) < 10000 spróbować każdy n zaczynając od 0 zwiększenie o 1.

Answer 3

rozwiązanie wykorzystujące korzenie całkowitą kwadratowych jak sugeruje @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

zaokrąglenia precyzja zabił mi na ten problem ... ale można zachować wszystko przy 64-bitowej dokładności całkowitej i wykonaj wyszukiwanie binarne na wynikowym równaniu kwadratowym. Przedstawiłem moje podejście: here.