Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 61
Если дискриминант равен 0, то у уравнения 2 корня, но одинаковых. Будем учить хорошему=)
Эх… а нам в школе в десятом классе не рассказывали о комплексных числах
А почему коэффициенты int? Чтобы дискриминант влез в long long и не заморачиваться с длинной арифметикой?
А почему коэффициенты целочисленные? Почему не вещественные. Там ведь такой простор для ошибок. Сравнение с нулем, потеря точности при вычислении дискриминанта и т.д.
А почему коэффициенты целочисленные? Почему не вещественные. Там ведь такой простор для ошибок. Сравнение с нулем, потеря точности при вычислении дискриминанта и т.д.
По следам Итхеппенса?
Здесь специально для не читавших ITHappens поясню, что речь идёт об истории http://ithappens.ru/story/10776 на ITHappens.
Ох, помню тоже писал подобное…
Только на скриптовом языке для AVZ, когда на virusinfo проходил обучение :)
Только на скриптовом языке для AVZ, когда на virusinfo проходил обучение :)
Сегодня преподу как раз сдавал лабу, там в одном месте надо было решить квадратное уравнение с комплексными корнями. Решил в Wolfram Mathematica, показал ему. Он спрашивает: «А вы вручную считать умеете? А то большинство ваших коллег уже забыли, как такое на листике считать». Стало обидно за даржаву — написал ему решение на листочке :)
А вы квадратный корень в столбик считать умеете? :D Студенты очень удивились, когда я показал, как это делается…
Я по мотивам этого пытаюсь в уме научиться извлекать, но дальше трёх значащих цифр не идёт особо.
В уме лучше работает просто метод Ньютона: меньше информации приходится запоминать одновременно (только исходное число и текущее приближение корня), соответственно, меньше опасность ошибиться (и больше шансов ошибку исправить). С одной стороны, получается дольше, каждый раз приходится возводить в квадрат заново, с другой — можно получить больше дополнительных цифр. Тем более, что дальше пяти цифр результата пройти сложно :)
Честно признаюсь: в школе умел, но сейчас уже забыл )
Для этого есть логарифмическая линейка.
На ней даже три знака получить трудно — максимум, два с половиной. А от студентов требовалась тысяча — вот они и интересовались, как её лучше посчитать. Без использования чужой длинной арифметики.
Так для этого и калькулятор подойдёт, причём любой.
Вот я вроде старше вас лет на десяток, но никто никогда не учил меня пользоваться логарифмической линейкой… Я о ней читал и даже на бумаге рисовал (был у меня бзик рисовать на бумаге программы для различных средств ВТ), но логарифмы считал либо на электронном калькуляторе, либо по таблицам синусов и косинусов. В любом случае результатом были десятичные дроби ограниченной разряда этак до четвертого после запятой точности.
Я линейкой пользоваться сам учился. Было очень интересно, и на физике помогало. А калькулятора тогда у нас не было.
А мне логарифмическая линейка случайно в руки попалась (дома лежала где-то), вместе с книжкой где полностью описывались правила всяких действий на ней, вплоть до самых продвинутых. Хотя особой нужды в этом не было, но пользоваться ей научился =) Основные действия и сейчас помню. Вот таблицы различных функций уже, можно сказать, не застал (младше вас почти на 20 лет).
Нас учили в школе, как и таблицам и всем возможным столбикам, класс математический был. Калькулятором на математиках пользоваться не поощрялось.
Но с линейкой я гораздо раньше познакомился, дед научил. И еще многому другому.
Но с линейкой я гораздо раньше познакомился, дед научил. И еще многому другому.
Вариант с целочисленными коэффициентами значительно проще. Я думаю, что написать корректную программу для нахождения вещественных корней квадратного уравнения с вещественными коэффициентами сможет менее 1% программистов. Если считать, что программа, рашающая такую простую задачу, должна давать ответ с полной доступной точностью.
Что вы имеете в виду под полной доступной точностью? Я даже с ограниченной стандартными типами точностью не знаю как подойти к вводу (хотя бы) вещественных чисел — как минимум это калькулятор (с функциями, пределами и интегралами) нужно писать, но далеко не уверен, что это покроет все множество иррациональных чисел. Вы же не рассматриваете в рамках такой простой задачи вещественные коэффициенты только как рациональные и пару-тройку популярных иррациональных констант?
Если числа вводятся как десятичные дроби, то проще всего работать с ними как с десятично-рациональными и написать небольшую длинную арифметику (или использовать существующую). А вот если это числа double, возникшие в программе (что более вероятно), то становится интересно: как проверить условие b^2>=4*a*c для 53-битных чисел? Я бы, наверное, представил каждое вещественное число в виде суммы чисел, в которых только по 24 ненулевых бита, написал для них аккуратную операцию нормализации такой суммы, после чего арифметика (без деления) работала бы без потерь точности. А после того, как у нас есть дискриминант, можно вернуться в double, найти больший по модулю корень, а меньший посчитать по теореме Виета (как c/a/x1). Непросто, но если про программу известно, что ей нужно работать вблизи вырожденных случаев, то такое может понадобиться.
Если вводятся как десятичные (небесконечные) или рациональные дроби, то если разрешно учетверить разрядность большего знаменателя, ничего особо сложного не вижу — обычные школьные правила сравнения дробей и библиотека длинной арифметики (без деления, да). А вот нормализация (как вынос множителей из под радикала, так и сокращение дробей) могут вызвать задержки ощутимые даже для одноразового расчета.
нормализация (как вынос множителей из под радикала, так и сокращение дробей) могут вызвать задержки ощутимые даже для одноразового расчета
Это же разве задержки? Вот Вы сравните на досуге время работы стандартной функции hypot() и прямого вычисления по соответствующей формуле. Будете неприятно удивлены. А дело в том, что hypot() полностью реализует специальную вещественную магию (tm) и обеспечивает максимальное количество верных разрядов в ответе.
Вынос множителя из-под радикала (при решении в алгебраических числах) — это действительно задержка. Так же, как и работа с десятичными числами без перевода их в double.
А гипотенузу уже обсуждали. Правда, проверить скорость и точность разных подходов так никто и не взялся.
А гипотенузу уже обсуждали. Правда, проверить скорость и точность разных подходов так никто и не взялся.
Да, это я читал. Корректно проверить точность довольно хлопотно, поскольку там основные отличия между полноценной hypot() и версией с простым делением на максимум проявляются (насколько я помню свои старые эксперименты) для денормализованных чисел. А оценки скорости хорошо известны всем, кто занимается численными приложениями — версия с делением на максимум примерно вдвое, а полноценный hypot() примерно на порядок медленнее бесхитростной реализации (кстати, в обсуждении по ссылке примерно такие же оценки тоже назывались). Именно это я имел в виду, когда сказал «Это же разве задержки?» — по сравнению с hypot() вынос множителя изменяет производительность не очень сильно (коэффициент 2 против 10-15).
Максимальное не обеспечивает. Я проверял лет 10 назад. Обусловлено было тем, что, грубо говоря, что корень из 4/9 никак не считался как 2/3… Числа были не равны. Поэтому я вспомнил программирование для КР580ВМ80А и реализовал свою арифметику…
Ну, Вы наверно сами понимаете, что «проверял лет 10 назад» — это вообще ни о чем не говорит. Какой компилятор? Какие библиотеки? Корректно ли проверяли? Кроме того, один знак последнего двоичного разряда — это в общем случае теоретический минимум погрешности для чисел с плавающей точкой. Так что даже точный смысл Ваших слов остался неясным.
Какой компилятор? PHP ни разу не был компилятором. Библиотек никаких, кроме стандартной и собственной.
Я проверял числа не с плавающей точкой, использовал целочисленную рациональную арифметику на уровне, кажется, 4-го класса (по исчислению СССР).
Я проверял числа не с плавающей точкой, использовал целочисленную рациональную арифметику на уровне, кажется, 4-го класса (по исчислению СССР).
Вы в исходном сообщении где-то между строк написали про то, что тестировали в PHP? Или в исходном посте что-то говорилось про PHP? Или все на свете пишут на PHP? И вообще, я подозреваю, что в PHP результат будет зависеть от того, каким компилятором и с какой libc был собран сам этот интерпретатор.
Тогда какую ценность имеет вот это Ваше высказывание:
если речь шла о свойствах именно функции hypot() из libc?
Я проверял числа не с плавающей точкой, использовал целочисленную рациональную арифметику
Тогда какую ценность имеет вот это Ваше высказывание:
Максимальное не обеспечивает.
если речь шла о свойствах именно функции hypot() из libc?
Имеется в виду, конечно, машинная вещественная арифметика. Под полной точностью понимают максимальное возможное количество верных двоичных разрядов. Например, в случае кратных корней, ожидаемое количество верных двоичных разрядов будет вдвое меньше общего количества разрядов в вещественном числе (вывод, кажущийся неожиданным, если просто смотреть на формулы). На самом деле корректная программа решения квадратного уравнения оказывается довольно сложной и ее написание практически недоступно среднему программисту без специальной подготовки.
Например, в случае кратных корней, ожидаемое количество верных двоичных разрядов будет вдвое меньше общего количества разрядов в вещественном числе
Это зависит от интерпретации исходных данных — считаем ли мы, что исходные коэффициенты заданы с точностью плюс-минус младший бит, и мы имеем право выдать решение любого уравнения с коэффициентами в этих пределах — или мы должны считать, что коэффициенты — именно такие двоично-рациональные числа, и от нас ожидают решения именно этого уравнения, с максимально возможной точностью? Конечно, первая постановка встречается намного чаще. Но и вторая имеет право на существование.
Это зависит от интерпретации исходных данных — считаем ли мы, что исходные коэффициенты заданы с точностью плюс-минус младший бит, и мы имеем право выдать решение любого уравнения с коэффициентами в этих пределах — или мы должны считать, что коэффициенты — именно такие двоично-рациональные числа, и от нас ожидают решения именно этого уравнения, с максимально возможной точностью? Конечно, первая постановка встречается намного чаще. Но и вторая имеет право на существование.
1) решение квадратного уравнения вида ax2+bx+c=0 с целочисленными коэффициентами.
При a = 0 уравнение не квадратное. Так что либо говорим, что решаем уравнение (без слова квадратное), либо не выпендриваемся добавляя исключительные случаи.
2) Программа должна всегда выдавать результат.
Опять таки, программа выдаёт результат. Причём, даже правильный.
Зачем пытаться усложнить себе жизнь, если этого не было в задании?
При a = 0 уравнение не квадратное. Так что либо говорим, что решаем уравнение (без слова квадратное), либо не выпендриваемся добавляя исключительные случаи.
2) Программа должна всегда выдавать результат.
Опять таки, программа выдаёт результат. Причём, даже правильный.
Зачем пытаться усложнить себе жизнь, если этого не было в задании?
Задание «написать программу решения квадратного уравнения» каждый понимает в меру своей испорченности образованности и эрудиции. И три разных человека могут счесть одну и ту же программу как неработающей («комплексные корни есть, а пишет, что корней нет»), так и работающей как надо, а равно как «мою задачу выполняет, но столько лишнего». Просто такое задание не техническое.
1) Напоминаю, в определении в учебнике написано:
Здесь этого условия в задании нет, так что этот случай тоже рассматривается.
2) Программа и вначале выдавала результат, но не тот, который был нужен.
Уравнение вида ax2+bx+c=0, где a≠0.
Здесь этого условия в задании нет, так что этот случай тоже рассматривается.
2) Программа и вначале выдавала результат, но не тот, который был нужен.
Это моя любимая задача! Она отлично показывает как надо подходить к анализу формулировки задачи заказчиком и как все неоднозначно в этом плане.
Я эту задачу всегда первой давал студентам, когда начинал рассказывать про проектирование новой системы и первичный анализ требований заказчика. Большинство студентов ее решают как описано в самом первом варианте, а задумываться начинают только после наводящих вопросов про комплексные числа, вырожденные случаи и т.д.
Я эту задачу всегда первой давал студентам, когда начинал рассказывать про проектирование новой системы и первичный анализ требований заказчика. Большинство студентов ее решают как описано в самом первом варианте, а задумываться начинают только после наводящих вопросов про комплексные числа, вырожденные случаи и т.д.
Что-то я не понял.
Без преобразования b к long long мы начнём получать неверный результат уже начиная с b=50000 (даже чуть раньше). Если преобразуем — то на числах, близких к границе int, получим переполнение, когда 4*a*c окажется больше 2^63. Я в этом месте написал
По идее, сравнение дискриминанта с нулём будет работать всегда корректно, даже когда double для этого бы не хватило. Но вот с выводом в алгебраическом виде возникает проблема: при нечётных b дискриминант может выйти за пределы 2^64 и тут уж без длинной арифметики не обойтись.
Кстати, как устроен класс radical? Он должен выносить полный квадрат за пределы корня (иначе пятёрку не поставят — sqrt(18) не понравится ни одному учителю). Удалось ли там обойтись без полного разложения 19-значных чисел на множители?
long long discriminant = b*b - 4*a*c;
Без преобразования b к long long мы начнём получать неверный результат уже начиная с b=50000 (даже чуть раньше). Если преобразуем — то на числах, близких к границе int, получим переполнение, когда 4*a*c окажется больше 2^63. Я в этом месте написал
__int64 ac=(__int64)a*c;
__int64 b2=(__int64)b*b;
__int64 D=b2/4-ac;
if(b%2==0 && D==0) printf("One root: %lg\n",-(double)b/2.0/a);
else{
if(D<0) printf("No roots\n");
else{
double v=sqrt((double)D+(b%2==0 ? 0 : 0.25));
printf("Two roots: %lg and %lg\n",(-b/2.0-v)/a,(-b/2.0+v)/a);
}
}
По идее, сравнение дискриминанта с нулём будет работать всегда корректно, даже когда double для этого бы не хватило. Но вот с выводом в алгебраическом виде возникает проблема: при нечётных b дискриминант может выйти за пределы 2^64 и тут уж без длинной арифметики не обойтись.
Кстати, как устроен класс radical? Он должен выносить полный квадрат за пределы корня (иначе пятёрку не поставят — sqrt(18) не понравится ни одному учителю). Удалось ли там обойтись без полного разложения 19-значных чисел на множители?
Полное там не нужно, сложность тупого перебора не sqrt(N), а sqrt(sqrt(N)).
Насчёт дискриминанта — не знал, по наивности решил, что такого будет достаточно.
Да, radical выносит за пределы без разложения, в общем-то, но в не слишком оптимальном цикле (для оптимального стоило заиметь массив простых чисел:
Вот и корень из 18, например:
Да, radical выносит за пределы без разложения, в общем-то, но в не слишком оптимальном цикле (для оптимального стоило заиметь массив простых чисел:
int radical::getPerfectSquare()
{
long long a = abs(radicand);
int square = 1;
int maxDiv = floor(sqrt(a)); // делители, большие корня из подкоренного выражения, нас не интересуют: их всегда будет меньше двух
for (int i = 2; i <= maxDiv; i++)
{
while (a % (i*i) == 0)
{
a /= i*i;
square *= i;
}
maxDiv = floor(sqrt(a));
}
return square;
}
Вот и корень из 18, например:
1 0 -18
D != 0; 2 корня:
x1 = 3┐/2
x2 = - 3┐/2
Мой первый курсовик в техническом вузе: аналитическое решение всех видов квадратных и биквадратных уравнений с учётом комплексных корней — сделан за вечер:
Честно говоря, не вижу здесь ничего особенно сложного. Может, поясните, в чём «фишка»? Какие были подводные камни? На чём написано?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Квадратное уравнение? Да раз плюнуть!