Как сделать корень в программе

Обновлено: 06.07.2024

Под извлечением корня из какого-либо числа чаще всего подразумевают нахождение решение уравнения x в степени n = value, соответственно для квадратного корня, число n — это два, для кубического — 3. Чаще всего под результатом и числом подразумеваются вещественные числа.

В программировании нахождение корней используется очень часто. Разберемся, как и какими методами можно эффективно извлекать корни из числа. Вначале рассмотрим, какие способы есть в Python, и определим самый эффективный. Потом более подробно разберём, как можно найти не только квадратный корень из числа, но и кубический, и потом корень n степени.

Способы извлечения корня

В языке программирования Python 3 существует три способа извлечения корней:

Использование функции sqrt из стандартной математической библиотеки math.
Операция возведения в степень **
Применение функции pow(x, n)

Чтобы воспользоваться первым способом, необходимо вначале импортировать sqrt из модуля math. Это делается с помощью ключевого слова import: from math import sqrt . При помощи этой функции можно извлекать только квадратный корень из числа. Приведем пример:

Если же нам нужно вычислить в Python корень квадратный из суммы квадратов, то можно воспользоваться функцией hypot из модуля math. Берется сумма квадратов аргументов функции, из нее получается корень. Аргументов у функции два.

Еще одним, чуть более универсальным методом, будет использование возведения в степень. Известно, что для того, чтобы взять корень n из числа, необходимо возвести его в степень 1/n. Соответственно, извлечение квадратного корня из числа 4 будет выглядеть так:

Обратите внимание, что в Python 2 необходимо ставить точку после единицы, иначе произойдет целочисленное деление, и 1/n == 0, а не нужной нам дроби. В Python 3 можно не ставить точку.

Последний метод использует функцию pow(value, n). Эта функция в качестве аргумента value возьмет число, которое необходимо возвести в степень, а второй аргумент будет отвечать за степень числа. Как и в предыдущем методе, необходимо использовать дробь, для того, чтобы получить корень числа.

Какой метод быстрее?

Для того, чтобы определить какой же метод предпочтительнее использовать, напишем программу. Замерять время выполнения будем с помощью метода monotonic библиотеки time.

Как видно, самое быстрое решение — использовать **. На втором месте метод sqrt, а pow — самый медленный. Правда, метод sqrt наиболее нагляден при вычислении в Python квадратных корней.

Таким образом, если критична скорость, то используем **. Если скорость не критична, а важна читаемость кода, то следует использовать sqrt.

Квадратный корень

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

Но можно использовать и трюки с возведением в степень 1/2, что тоже будет приводить к нужному результату.

x = value ** (0.5) или x = pow(value, 0.5) .

Кубический корень

Для извлечения кубического корня в Python 3 метод sqrt не подойдет, поэтому воспользуйтесь возведением в степень 1/3:

x = value ** (1./3) или x=pow(value, 1/3) .

Корень n-степени

Корень n-степени из числа в Python извлекается можно получить двумя способами с помощью возведения в степень 1.0/n:

С помощью оператора **.
Используя функцию pow.

Как было проверено выше, оператор ** быстрее. Поэтому его использовать более целесообразно. Приведем пример вычисления кубических корней в Python 3 с помощью этих двух методов:

Корень отрицательного числа

Рассмотрим, как поведут себя функции, если будем брать корень из отрицательного числа.

Как видим, функция sqrt выдаёт исключение.

Теперь посмотрим, что будет при использовании других методов.

Как видно из результата, оператор ** не выдает исключения и возвращает некорректный результат. Функция pow работает корректно. В результате получаем комплексное число 2j, что является верным.

Вывод

В Python существуют два универсальных способа для извлечения корня из числа. Это возведение в необходимую степень 1/n. Кроме того, можно воспользоваться функцией из математического модуля языка, если необходимо извлечь квадратный корень числа.

Все эти методы имеют свои преимущества и недостатки. Самый наглядный это sqrt, но подходит только для квадратный корней из числа. Остальные методы не такие элегантные, но легко могут извлечь корень нужной степени из числа. Кроме того оператор ** оказался наиболее быстрым при тестировании.

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

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

Например, квадратный корень из 144 равен 12.

Использование метода math.sqrt()

Функция sqrt() – это встроенная функция, которая возвращает квадратный корень из любого числа. Ниже приведены шаги, чтобы найти квадратный корень из числа.

Запустите программу.
Определите любое число, квадратный корень которого нужно найти.
Вызовите функцию sqrt() и передайте значение, которое вы определили на шаге 2, сохраните результат в переменной.
Выведите квадратный корень.
Завершите программу.

Давайте напишем программу на Python.

Давайте создадим программу на Python, которая находит квадратный корень десятичных чисел.

В следующей программе мы прочитали число от пользователя и нашли квадратный корень.

Использование функции math.pow()

Pow() – это встроенная функция, которая используется в Python для возврата степени числа. У него два параметра. Первый параметр определяет число, а второй параметр определяет увеличение мощности до этого числа.

Использование оператора **

Мы также можем использовать оператор экспоненты, чтобы найти квадратный корень из числа. Оператор может применяться между двумя операндами. Например, x ** y. Это означает, что левый операнд возведен в степень правого.

Ниже приведены шаги, чтобы найти квадратный корень из числа.

Шаг 1. Определите функцию и передайте значение в качестве аргумента.
Шаг 2. Если заданное число меньше 0 или отрицательное, оно ничего не возвращает.
Шаг 3. Используйте экспоненциальный знак **, чтобы найти степень числа.
Шаг 4. Возьмите числовое значение у пользователя.
Шаг 5. Вызовите функцию и сохраните ее вывод в переменной.
Шаг 6. Отобразите квадратный корень числа в Python.
Шаг 7. Выход из программы.

Давайте реализуем вышеуказанные шаги.

Как мы видим в приведенном выше примере, сначала мы берем ввод(число) от пользователя, а затем используем оператор степени **, чтобы узнать степень числа. Где 0,5 равно √(символ корня), чтобы увеличить степень данного числа.

Давайте создадим программу Python, которая находит квадратный корень из указанного диапазона, в следующей программе вычисление из всех чисел от 0 до 50.

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

Корень с помощью комбинации клавиш на клавиатуре

Если вам нужно просто поставить знак корень, то это делается достаточно просто. Для этого нужно воспользоваться комбинацией клавиш ALT+251 . Данная комбинация клавиш нажимается следующим образом: сначала зажимаете клавишу ALT на клавиатуре, а потом не отпуская ALT набираете число 251 на дополнительном цифровом блоке (под клавишей Num Lock ).

Нужно отметить, что число 251 нужно набирать именно на дополнительном цифровом блоке, а Num Lock должен быть включен. Иначе комбинация клавиш ALT+251 не сработает.

На картинке вверху показан индикатор сообщающий, что Num Lock включен.

Корень в текстовом редакторе Word

Если все было сделано правильно, то в рамке для формул появится знак корень.

Разделы

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

При программировании микроконтроллеров разработчики иногда сталкиваются с проблемой вычисления квадратного корня. Например, данная операция требуется при выполнении быстрого преобразования Фурье или вычислении среднеквадратического значения сигнала.
В стандартной библиотеке Си – math.h, есть функция для вычисления квадратного корня sqrt(), которой при желании можно воспользоваться. Она работает с числами типа float, обеспечивает высокую точность результата, но требует для своей работы длительного времени. Для микроконтроллера AVR это порядка 3000 циклов тактовой частоты (проверено в компиляторе IAR на разных уровнях оптимизации).
Если к точности вычисления корня не предъявляются высокие требования, можно воспользоваться упрощенным алгоритмом, занимающим меньше места в памяти и выполняющим вычисления в несколько раз быстрее.

Алгоритм выглядит так.

Как мне подсказали умные люди, алгоритм основан на итерационной формуле Герона.

где А – фиксированное положительное число, а X1 – любое положительное число.
Итерационная формула задаёт убывающую (начиная со 2-го элемента) последовательность, которая при любом выборе X1 быстро сходится к квадратному корню из числа А.

Ради интереса я переписал алгоритм в явном виде. Скомпилированный, он ничуть не потерял ни в быстродействии, ни в объеме. Объем даже на пару байтов уменьшился.

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

Код занимает прядка 70 байт и выполняется ~ за 700 циклов. Данные получены в компиляторе IAR AVR при medium оптимизация по скорости.

Точность вычисления данного алгоритма можно оценить по приведенному ниже графику. Синий график построен по значениям, полученным c помощью библиотечной функции sqrt(), красный график по значениям функции root().

В ходе обсуждения моей заметки, те же самые умные люди подсказали еще один алгоритм вычисления квадратного корня.

Related items

Comments

Хотя, я был не прав. По итерационной формуле Герона нужно 8 делений для получения приближенного ответа. В описанном вами методе можно увеличить точность добавив ещё одну итерацию:
x = b/x;
a = x = (x+a)>>1;
Но для AVR, данный алгоритм не оптимальный, т.к. деление выполняется долго. Посмотрите на метод бинарного поиска целочисленного квадратного корня (только умножение и сложение), описан в книге "Алгебраические трюки для программиста". Там ещё описан алгоритм без умножения, только сдвиги, сложения и битовые операции. Можно попробовать адаптировать для AVR его, тогда выигрыш во времени будет значительный.

Да нет, все правильно. В википедии приведена формула Герона.
Xn+1 = (Xn + A/Xn)*1/2
A - число из которого требуется вычислить корень, X1 - любое положительное число.

Если написать код так
Code:
unsigned int root(unsigned int a)
unsigned int x;
x = (a/0x3f + 0x3f)>>1;
x = (a/x + x)>>1;
x = (a/x + x)>>1;
return(x);
>

получаются точно такие же результаты. Как по ответам, так и по скорости исполнения кода. А по объему даже небольшой выигрыш. Зачем надо было так мудрить?

подскажите пожалуйста как проделать это с переменной типа long?

Напишу как делаеться в AVR Studio. Пишеться код - компилим,смотри м сколько занял,добавляем функцию - и смотрим новий размер кода. Разница между новым и старым значение есть размер функции.

Для скорости выполнения. ставим брейкпойнт перед вызовом функции и после,запускаем симуляцию - обнуляем cycle counter,запуска ем симуляцию - и новое значение будеть скоростью выполнения (также можно увидеть сколько время исполняеться функция в мкс или мс).

Для IAR`a . Нужно включить опцию создания листинга программы. Project > Options > C/C++ Compiler > List галочка Output list file. Если включить еще и Assembler mnemonics в lst файле будет ассемблерный код, сгенерированный компилятором из твоей программы. Эта информация полезна для оптимизации сишного кода, конечно, если ты знаешь ассемблер.
Затем запускаешь компиляцию проекта и с левой стороны (в окне отображения структуры проекта) ищешь файлы с расширением *.lst Они будут созданы для каждого программного модуля. В конце этого файла есть табличка со списком функций и значениями занимаемой памяти.

Чтобы прикинуть скорость выполнения какого-нибудь куска кода (обычно функции), я прогоняю этот код в программном симуляторе IAR`a. Включаю опцию Project > Options > Linker > Debug Information . Запускаю компиляцию и отладку с помощью кнопки Debug (Ctrl+D). Устанавливаю брейкпоинты, открываю окно с регистрами микроконтроллер а (меню View > Register) и запускаю код на выполнение по шагам (F11) или непрерывно (f5). В окне регистров в разделе CPU Register есть строка CYCLES. Она отображает число прошедших тактов. По показаниям этого числа можно прикинуть сколько тактов занимает выполнение функции.

То же самое можно делать и в AVR Studio. Там это даже лучше получается, потому что студия моделирует прерывания, а IAR нет.

У меня нет компилятора для AVR под рукой.
Можете проверить функцию:
Code:
unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
if (x >= b)
x = x - b;
y = y | m;
>
m = m >> 2;
>
return y;
>

Сколько занимает и как долго выполняется?

У меня нет компилятора для AVR под рукой.
Можете проверить функцию:
unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
if (x >= b)
x = x - b;
y = y | m;
>
m = m >> 2;
>
return y;
>
Сколько занимает и как долго выполняется?

F = 8 MHz, ATmega8, optimization O0 (none):

размер 14 байт.
скорость 540 циклов - 67.5uS

F = 8 MHz, ATmega8, optimization Os (none):

размер 14 байт.
скорость 2 циклf - 0.25uS

Код которий тестировал:

unsigned int value = 0;

unsigned int isqrt(unsigned int x)
unsigned int m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;

int main(void)
asm("nop");
value = isqrt(4096);
asm("nop");

тоже самое но с типом long
unsigned long isqrt(unsigned long x)
unsigned long m, y, b;
m = 0x4000;
y = 0;
while (m != 0)
b = y | m;
y = y >> 1;
if (x >= b)
x = x - b;
y = y | m;
>
m = m >> 2;
>
return y;
>

Пользовался детским алгоритмом, на мой взгляд достаточно быстр и достаточно компактный. Идея в том что от числа последовательно отнимаются все нечётные числа, и сколько вычитаний удалось сделать, таков и корень числа. Пример, число 49;
1) 49 - 1 = 48
2) 48 - 3 = 45
3) 45 - 5 = 40
4) 40 - 7 = 33
5) 33 - 9 = 24
6) 24 - 11 = 13
7) 13 - 13 = 0

7 циклов, корень числа 49 - 7.

И кстати при работе с МК типа AVR-ки лучше избегать делений, т.к. у AVR ядра нет аппаратного деления, а программное занимает дофига тактов. Другое дело ARM Cortex-M3 и выше, у которых деление выполняется за 2. 12 тактов.

У функции корня есть некоторые свойства симметрии, которые позволяют вычислять ее только на некотором отрезке, а потом решение распространить на всю ось. Например,
sqrt(a*2^16)=2^ 8*sqrt(a).

Удобно в качестве такого отрезка взять значения [2^30-2^31), потому что остальные значения можно свести к нему побитовым сдвигом и при этом не будет происходить потеря точности. Сначала вычисляем первый значащий бит (программно половинным делением или процессорной инструкцией, например на ARM это __clz). Потом сдвигаем входное число на это кличество бит и вычисляем корень, полученное значение сдвигаем обратно на в два раза меньшее количество).
Для вычисления корня на отрезке интерполируем его многочленом Лагранжа (параболой). Например, возьмем в качестве точек многочлена 2^30, 1,5 * 2^30, 2^31. Можно воспользоваться сторонним сервисом, и не возиться с вычислением коэффициентов. У меня получилась такая формула:
-x^2/499100218444523 + x/52370 + 14575
Очевидно, напрямую её использовать нельзя, потому что значения не влазят даже в диапазон целых. Но надо учесть, что нам важны только 16 бит результата, поэтому можно немного схитрить и вынести что-то за скобки.
(-x/9530269590 + 1) * x/52370 + 14575
(-x/145420 + 65536) * (x/65536) / 52370 + 14575
Ну и последнее - заменить деление на умножение. Допустим, у нас в резерве 30 бит числа. Мы хотим поделить некое число x, например, на 543. Вычисляем, в числе 543 есть 10 бит, в х 16 бит.
x / 543 * 2^26 / 2^26
x * (2^26 / 543) / 2^26
x * 123589 / 2^26
Теперь эти знания применяем к своему многочлену.
(-x/2^14 * 7384 / 2^16 + 2^16) * (x/2^16) / 2^16 * 20503 / 2^14 + 14575
Не ручаюсь за правильность коэффициентов, надо внимательно проверить.
Когда писал, не учел одну штуку, число бит может быть нечетным, отрезок надо брать больше.

Естественно, алгоритм будет быстро работать при наличии аппаратного умножения.

Если умножение делается за один такт, можно сделать вычисление корня побитовым подбором. На первой итерации выставляем 16 бит в 1, возводим в квадрат, сравниваем с входным числом. Если больше, сбрасываем бит. Потом с 15 битом повторяем то же самое и т.д. Как в АЦП.

А что за магическое число:
Code: m = 0x4000; ?
Это половина от максимума int ?
А вот 2й вариант работает отлично, спасибо!
Мне нужно считать корни из больших чисел до 250 000 000, поэтому увеличил количество:
Code: x = (a/x + x)>>1;
до 7 и точность приемлима.

Читайте также: