Как точно решить квадратичные уравнения с большими целыми коэффициентами (по целым числам)?

Я прочитал a problem about bullseyes в Google Code Jam. (Конкурс завершен сейчас, так что это нормально, чтобы говорить об этом)Как точно решить квадратичные уравнения с большими целыми коэффициентами (по целым числам)?

Марии начинается с т миллилитров черной краски, которую она будет использовать, чтобы рисовать кольца толщиной 1 см (один сантиметр). Кольцо толщиной 1 см представляет собой пространство между двумя концентрическими кругами, радиусы которых отличаются на 1 см.

Мария рисует первое черное кольцо вокруг белого круга радиуса r см.

Площадь диска с радиусом 1 см составляет π см2. Для покрытия площади π см2 требуется один миллилитр краски. Каково максимальное количество черных колец, которые Мария может нарисовать?

По моим подсчетам на бумаге, площадь краски, чтобы нарисовать яблочко с п кольцом, внутренним радиусом, а кратно пи является 2*n**2 + n*(2*r-1)

Поэтому, учитывая t*pi millitres краски проблемы найти наибольшее n такое, что f(n,r) <= t.

Этим утром я решил, что с двоичным поиском https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bullseye.py

Я выбрал бинарный поиск по квадратному уравнению, потому что я очень настороженно относится к точке неточностей плавающей - в этой задаче т и р являются целыми числами, как большие, как 10 ** 18). Арифметическая неточность укусила меня в предыдущем коду.

Но мне любопытно. Можете ли вы укрепить квадратичное уравнение, чтобы дать правильный ответ для уравнений с большими целыми коэффициентами? Могут ли библиотеки математики, такие как Sympy или Numpy, что-нибудь предложить?

Демонстрация того, что квадратичное уравнение дает неправильный ответ для больших входов. Например, с r=308436464205151562 и t=1850618785230909388. Квадратичное уравнение для решения -

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

ie. коэффициенты

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

источник

2013-04-27 Colonel Panic

Разве вы не просто используете квадратичное уравнение? –

В предыдущей ошибке кода я был укушен ошибкой точности с плавающей точкой http://stackoverflow.com/q/15978781/284795 –

У вас не должно возникнуть проблемы с использованием math.sqrt для целого числа, которое мало. –

Для символических точных манипуляций, есть sympy.

Если вставить следующее:

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

here, вы получаете 3.

[редактировал следующий О.П. комментарий].

источник

2013-04-27 14:15:38 Haile

Больше, чем 3.0? 'int (max (solve (a * x ** 2 + b * x + c, x)))' возвращает 3, что является правильным ответом. Благодаря! Аккумулятор REPL –

Если (t/r^2) > 10000 вычислить по sqrt.
Если (t/r^2) < 10000 попробовать каждый n начиная с 0 увеличивается на 1.

источник

2013-04-27 14:22:21

решения с использованием целочисленного квадратных корней, как предложено @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)

источник

2013-04-27 17:15:17

округления точность убила меня на этой проблеме ... но вы можете сохранить все с точностью до 64 бит и выполнять двоичный поиск по полученному квадратичному уравнению. Я изложил свой подход here.

источник

2013-04-27 19:28:11 tbischel

Как точно решить квадратичные уравнения с большими целыми коэффициентами (по целым числам)?

ответ

Смежные вопросы