How to accurately solve quadratic equations with large integer coefficients (for integers)?

Question

I read the issue about bullseyes in google code jam. (The contest is over, so it's ok to talk about it)

Maria begins with tons of black ink, which she will use to draw rings 1 cm thick (one centimeter). A ring 1 cm thick is the space between two concentric circles whose radii differ by 1 cm.

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

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

According to my calculations on paper, the area of ​​paint to draw a bullseye with n rings, the inner radius r, as a multiple of pi, is 2*n**2 + n*(2*r-1)

So, given t*pi milliliter of paint, the task is to find the greatest n such that f(n,r) <= t .

This morning I decided that with binary search https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bullseye.py

I chose the binary search by the quadratic equation, because I am very careful about floating point inaccuracies - in this problem t and r are integers, such as 10 ** 18). An arithmetic inaccuracy bit me in a previous code jam.

But I'm curious. Can you strengthen the quadratic equation to give the correct answer for equations with large integer coefficients? Can math libraries like Sympy or Numpy offer me?

---

Demonstrating that a quadratic equation gives the wrong answer for large inputs. For example, with r=308436464205151562 and t=1850618785230909388 . The solution of the quadratic equation

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

t. odds

 a = 2 b = 616872928410303123 c = -1850618785230909388 

Python Computation

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

This is the wrong answer! The correct answer (found by binary search) is 3

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

Answer 1

For symbolic precision manipulations, sympy .

If you enter the following:

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

here , you get 3.

[edited after OP comment].

Answer 2

Rounding accuracy killed me on this issue ... but you could save everything with an accuracy of 64 bits and perform a binary search on the obtained quadratic equation. I set out my approach here .

Answer 3

If (t / r^2) > 10000 calculate via sqrt .
If (t / r^2) < 10000 try each n , starting at 0, increasing by 1.

Answer 4

A solution using integer square roots proposed by @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)