Wie genau lösen wir quadratische Gleichungen mit großen ganzzahligen Koeffizienten (über ganze Zahlen)?

Question

Ich lese a problem about bullseyes in Google Code Jam. (Der Wettbewerb ist vorbei, also ist es in Ordnung, darüber zu sprechen)

Maria beginnt mit t Millilitern schwarzer Farbe, die sie verwenden werden Ringe mit einer Dicke von 1 cm ziehen (ein Zentimeter). Ein Ring mit einer Dicke von 1 cm ist der Abstand zwischen zwei konzentrischen Kreisen, deren Radien sich um 1 cm unterscheiden.

Maria zeichnet den ersten schwarzen Ring um einen weißen Kreis mit Radius r cm.

Die Fläche einer Scheibe mit Radius 1 cm ist π cm2. Ein Milliliter Farbe wird benötigt, um die Fläche π cm2 zu bedecken. Wie viele schwarze Ringe kann Maria maximal zeichnen?

Nach meinen Berechnungen auf dem Papier, die Fläche der Farbe, die ein Bullseye mit n Ringen, Innenradius r zu ziehen, als ein Vielfaches von PI ist 2*n**2 + n*(2*r-1)

So t*pi millitres von Farbe ist das Problem gegeben ist, zu finden, die größte n wie f(n,r) <= t.

An diesem Morgen löste ich, dass mit binärer Suche https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bullseye.py

Ich binäre Suche über die quadratische Gleichung entschieden, weil ich sehr vorsichtig mit der Ungenauigkeit Gleitkomma bin - in diesem Problem t und r ganze Zahlen sind, so groß wie 10 ** 18). Arithmetische Ungenauigkeit hat mich in einem früheren Code Jam gebissen.

Aber ich bin neugierig. Können Sie die quadratische Gleichung stützen, um die richtige Antwort für Gleichungen mit großen ganzzahligen Koeffizienten zu geben? Haben Mathematikbibliotheken wie Sympy oder Numpy mir etwas zu bieten?

---

Demonstration, dass quadratische Gleichung falsche Antwort für große Eingaben gibt. Zum Beispiel mit r=308436464205151562 und t=1850618785230909388. Die zu lösende quadratische Gleichung ist

dh. die Koeffizienten

a = 2 
b = 616872928410303123 
c = -1850618785230909388 

Computing in Python

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

Dies ist die falsche Antwort ist! Die richtige Antwort (gefunden durch binäre Suche) ist 3

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

Answer 1

Für symbolische exakte Manipulationen gibt es sympy.

Wenn Sie fügen die folgenden:

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

here, Sie bekommen 3.

[folgende OP Kommentar edited].

Answer 2

Wenn (t/r^2) > 10000 berechnen über sqrt.
Wenn (t/r^2) < 10000 versuchen jedes n von 0 beginnend von 1.

Answer 3

Lösung zu erhöhen, indem @Vaughn mit ganzzahligen Quadratwurzeln vorgeschlagen als

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

Die Abrundungs ​​Präzision getötet mich auf dieses Problem ... aber man konnte halten alles mit 64-Bit-Integer-Genauigkeit und eine binäre Suche nach der resultierenden quadratischen Gleichung. Ich skizzierte meine Vorgehensweise here.