Только целочисленным может быть корень квадратного уравнения

10.5. НАХОЖДЕНИЕ РАЦИОНАЛЬНЫХ КОРНЕЙ МНОГОЧЛЕНА С ЦЕЛЫМИ КОЭФФИЦИЕНТАМИ

Умножим обе части равенства (1) на (q ≠ 0). Получаем

В равенстве (2) все слагаемые, кроме последнего, делятся на р. Поэтому

Но когда мы записываем рациональное число в виде p/q, то эта дробь счи­тается несократимой, то есть р и q не имеют общих делителей. Произве­дение a₀q n может делиться на р (если р и q — взаимно простые числа) только тогда, когда a₀ делится на р. Таким образом, р — делитель свобод­ного члена a₀.

Аналогично все слагаемые равенства (2), кроме первого, делятся на q. Тогда

Отметим два следствия из этой теоремы. Если взять q = 1, то корнем многочлена будет целое число р — делитель a₀. Таким образом, имеет место:

Следствие 1. Любой целый корень многочлена с целыми коэффи­циентами является делителем его свободного члена.

Если в заданном многочлене f (х) коэффициент а_n = 1, то делителями а_n могут быть только числа ±1, то есть q =±1, и имеет место:

Следствие 2. Если коэффициент при старшем члене уравнения с целыми коэффициентами равен 1, то все рациональные корни этого уравнения (если они существуют) — целые числа.

Задача 1 Найдите рациональные корни многочлена 2х 3 – х 2 + 12х – 6.

Пусть несократимая дробь p/q является корнем многочлена. Тогда р не­обходимо искать среди делителей свободного члена, то есть среди чисел ±1, ±2, ±3, ±6, а q — среди делителей старшего коэффициента: ±1, ±2.

Таким образом, рациональные корни многочлена необходимо искать сре­ди чисел ±1/2, ±1, +±3/2, ±2, ±3, ±6. Проверять, является ли данное число корнем многочлена, целесообразно с помощью схемы Горнера. При x = 1/2 имеем следующую таблицу.

Кроме того, по схеме Горнера мож­но записать, что

Многочлен 2х 2 + 12 не имеет действительных корней (а тем более рацио­нальных), поэтому заданный многочлен имеет единственный рациональ­ный корень x =1/2.

Задача 2 Разложите многочлен Р (х) = 2х 4 + 3х 3 – 2х 2 – х – 2 на множители.

Ищем целые корни многочлена среди делителей свободного члена: ±1, ±2. Подходит 1. Делим Р (х) на х – 1 с помощью схемы Горнера.

Тогда Р (х) = (х – 1)(2х3 + 5х 2 + 3х + 2). Ищем целые корни кубического многочлена 2х 3 + 5х 2 + 3х + 2 среди делителей его свободного члена: ±1, ±2. Подходит (–2). Делим на х + 2

Квадратный трехчлен 2х 2 + х +1 не имеет действительных корней и на линейные множители не расклады­вается.

Ответ: Р (х) = (х – 1)(х + 2)(2х 2 + х +1).

Отметим, что во множестве действительных чисел не всегда можно найти все корни многочлена (например, квадратный трехчлен х 2 + х + 1 не имеет действительных корней). Таким образом, многочлен n-й степени не всегда можно разложить на линейные множители. В курсах высшей алгебры дока­зывается, что многочлен нечетной степени всегда можно разложить на ли­нейные и квадратные множители, а многочлен четной степени представить в виде произведения квадратных трехчленов.

Например, многочлен четвертой степени раскладывается в произведение двух квадратных трехчленов. Для нахождения коэффициентов этого раз­ложения иногда можно применить метод неопределенных коэффициентов.

Задача 3 Разложите на множители многочлен х 4 + х 3 + 3х 2 + х + 6.

Попытка найти рациональные корни ничего не дает: многочлен не имеет рациональных (целых) корней.

Попытаемся разложить этот многочлен в произведение двух квадратных трехчленов. Поскольку старший коэффициент многочлена равен 1, то и у квадратных трехчленов возьмем старшие коэффициенты равными 1. То есть будем искать разложение нашего многочлена в виде:

где а, b, с и d — неопределенные (пока что) коэффициенты. Многочлены, стоящие в левой и правой частях этого равенства, тождественно равны, поэтому и коэффициенты при одинаковых степенях х у них равны. Рас­кроем скобки в правой части равенства и приравняем соответствующие коэффициенты. Это удобно записать так:

Попытка решить эту систему методом подстановки приводит к уравне­нию 4-й степени, поэтому попробуем решить систему (4) в целых числах. Из последнего равенства системы (4) получаем, что b и d могут быть толь­ко делителями числа 6. Все возможные варианты запишем в таблицу.

Коэффициенты b и d в равенстве (3) равноправны, поэтому мы не рас­сматриваем случаи b = 6 и d = 1 или b = –6 и d = –1 и т. д.

Для каждой пары значений b и d из третьего равенства системы (4) най­дем ас = 3 – (b + d), а из второго равенства имеем а + с = 1.

Зная а + с и ас, по теореме, обратной теореме Виета, находим а и с как корни квадратного уравнения. Найденные таким образом значения а, b, с, d подставим в четвертое равенство системы (4) bс + ad = 1, чтобы выбрать те числа, которые являются решениями системы (4). Удобно эти рассуждения оформить в виде таблицы:

Как видим, системе (4) удовлетворяет набор целых чисел а = –1, b = 2, с = 2, d = 3. Тогда равенство (3) имеет вид

Поскольку квадратные трехчлены х 2 – х + 2 и х 2 + 2х + 3 не имеют не только рациональных, но и действительных корней, то равенство (5) дает окончательный ответ.

Упражнения

1. Найдите целые корни многочлена:

1. Найдите рациональные корни уравнения:

1. Разложите многочлен на множители:

1. Найдите действительные корни уравнения:

5*. Разложите многочлен на множители методом неопределенных коэффи­циентов:

6*. Разложите многочлен на множители, заранее записав его с помощью ме­тода неопределенных коэффициентов в виде (х 2 + bх + с) 2 – (mх + n) 2 : :

Вычисление целочисленного квадратного корня

Возникла нужда проверить, является ли целое число квадратом, и если да, то вычислить корень. Причем хочется сделать это в целочисленной арифметике. Понятно, что можно реализовать метод Ньютона в целых числах, но он требует деления на каждом шаге. А нельзя ли по другому? Найти квадратный корень по модулю степени двойки, и проверить, а не будет ли он обычным квадратным корнем.

Можно ограничиться нечетными числами: для четного числа, если количество нулевых младших разрядов нечетно, то корня нет, а если четно, то можно сдвинуть число вправо, посчитать корень от нечетного, и сдвинуть обратно влево на половину от первоначального количества нулевых бит.

Для нечетного N и 2 k , k > 3, если N ≡ 1 mod 8, то есть 4 разных корня по модулю 2 k , а иначе корней нет. Нам нужен наименьший из этих четырех корней x. При этом другие три корня это 2 k — x, 2 k-1 + x и 2 k — 2 k-1 — x

Хочется что-то подобное вычислению обратного по модулю 2 k — удваивая количество верных бит за итерацию.

Пусть у нас уже есть корень x₀ из N по модулю 2 k : N — x₀ 2 = 2 k a
И мы хотим найти x₁ = x₀ + 2 k-1 y, такое чтобы в N — x₁ 2 было больше младших нулевых бит.
N — (x₀ + 2 k-1 y) 2 = 2 k a — 2 k x₀ * y — 2 2k-2 y 2
Поделим на 2 k : a — x₀ * y — 2 k-2 y 2
И приравняем к 0 по модулю 2 k-2 : y = a * x₀ -1 mod 2 k-2
Получилии x₁ = x₀ + 2 k-1 a * (x₀ -1 mod 2 k-2 )
И окончательно x₁ = x₀ + (N — x₀ 2 )/2 * (x₀ -1 mod 2 k-2 )

Из k бит на следующей итерации получится 2(k-1) бит. Параллельно считаем на каждой итерации обратное к корню.

Добавив пару итераций, получим корень из uint_64

Целочисленный квадратный корень в python

есть ли целочисленный квадратный корень где-нибудь в python или в стандартных библиотеках? Я хочу, чтобы он был точным (т. е. возвращал целое число) и лаял, если нет решения.

в тот момент я свернул свой собственный наивный:

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

11 ответов

метод Ньютона отлично работает на целых числах:

Это возвращает наибольшее целое число x для чего x * x не превышает n. Если вы хотите проверить, является ли результат именно квадратным корнем, просто выполните умножение, чтобы проверить, если n является идеальным квадратом.

Я обсуждаю этот алгоритм и три других алгоритма вычисления квадратных корней, at мой блог.

извините за очень поздний ответ, я просто наткнулся на эту страницу. В случае, если кто-то посещает эту страницу в будущем, модуль python gmpy2 предназначен для работы с очень большими входами и включает в себя, среди прочего, целочисленную функцию квадратного корня.

конечно, все будет иметь тег «mpz», но mpz совместимы с int:

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

алгоритм квадратного корня длинной руки

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

поскольку этот алгоритм работает с числами цифра за цифрой, он дает точные результаты для сколь угодно больших совершенных квадратов, а для несовершенных квадратов может производить столько цифр точности (справа от десятичного знака), сколько требуется.

есть две хорошие рецензии на «доктора математики» сайт, объясняющие алгоритм:

и вот реализация в Python:

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

Я не уверен, как это сравнивается с алгоритмом «метода целочисленного Ньютона». Я подозреваю, что метод Ньютона быстрее, поскольку он в принципе может генерировать несколько битов решения за одну итерацию, в то время как алгоритм» длинной руки » генерирует ровно один бит решения за итерацию.

вот очень простая реализация:

это просто двоичный поиск. Инициализируйте значение m чтобы быть наибольшей мощностью 2, которая не превышает квадратный корень, затем проверьте, можно ли установить каждый меньший бит, сохраняя результат не больше квадратного корня. (Проверяйте биты по одному, в порядке убывания.)

для достаточно больших значений n (скажем, около 10**6000 или 20000 биты), это, кажется, быть:

• быстрее, чем реализация метода Ньютона описано user448810.
• гораздо, гораздо медленнее, чем gmpy2 встроенный метод в мой другой ответ.
• сопоставимо с, но несколько медленнее, чем длинный квадратный корень описано nibot.

все эти подходы успешно работают на входах такого размера, но на моей машине эта функция занимает около 1,5 секунд, в то время как @Nibot занимает около 0,9 секунд, @user448810 занимает около 19 секунд, а встроенный метод gmpy2 занимает менее миллисекунды(!). Пример:

эта функция может быть легко обобщена, хотя это не так приятно, потому что у меня нет столь же точного начального предположения для m :

однако обратите внимание, что gmpy2 также i_root метод.

на самом деле этот метод может быть адаптирован и применен к любому (неотрицательная, возрастающая) функция f чтобы определить » целое число, обратное f «. Однако, чтобы выбрать эффективное начальное значение m вы все еще хотите знать что-то о f .

Edit: спасибо @Greggo за указание на то, что i_sqrt функция может быть переписана, чтобы избежать использования каких-либо умножения. это дает впечатляющий прирост производительности!

отметим, что по конструкции k ый бит m is не установлено, поэтому побитовое-или может использоваться для реализации добавления (m . В конечном счете у меня (2*m*(2**k) + 2**(2*k)) написано как (((m , так что это три смены и один побитовый-или (с последующим вычитанием, чтобы получить new_diff ). Может, есть еще более эффективный способ сделать это? Несмотря на это, это намного лучше, чем умножение m*m ! Сравните с приведенным выше: