Tw-city.info

IT Новости
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Корень в программировании

Функции Sqrt и Sqr

Функция Sqrt в Паскале вычисляет квадратный корень числа. Синтаксис функции следующий:

function Sqrt(Х : ValReal) : ValReal;

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

Функция Sqr в Паскале вычисляет квадрат числа. Синтаксис функции для разных типов приведён ниже:

Эта функция возвращает результат вычисления квадрата числа, переданного через параметр. То есть Sqr = х * х.

О типе ValReal я рассказывал здесь.

Квадрат числа

Здесь всё крайне просто. Квадрат числа Х равен произведению Х на Х. То есть функция Sqr на первый взгляд кажется бесполезной. Потому что во многих случаях проще написать так:

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

будет написать проще, чем

Х := 5.3456753322 * 5.3456753322

Также возведение в квадрат числа в Паскале сложного выражения тоже будет проще, если использовать функцию Sqr:

X := Sqr(Y + 100 * Z / X)

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

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

Однако использование этих функций всё-таки немного сложновато. Поэтому для вычисления квадратного корня в Паскале имеется специальная функция (потому что квадратный корень приходится вычислять намного чаще, чем, например, корень n-й степени).

Эту функцию вы уже знаете — это функция Sqrt.

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

Итак, квадратный корень из числа А (корень 2-й степени) — это решение уравнения:

То есть квадратный корень из числа А, это число Х, которое при возведении в квадрат даёт число А.

ВАЖНО!
Число А может быть только положительным числом. Извлечение корня из отрицательного числа тоже возможно, но это уже будут комплексные числа.

Как стать программистом 2.0

Эта книга для тех, кто хочет стать программистом. На самом деле хочет, а не просто мечтает. И хочет именно стать программистом с большой буквы, а не просто научиться кулебякать какие-то примитивные программки… Подробнее.

Функции Sqrt и Sqr

Функция Sqrt в Паскале вычисляет квадратный корень числа. Синтаксис функции следующий:

function Sqrt(Х : ValReal) : ValReal;

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

Функция Sqr в Паскале вычисляет квадрат числа. Синтаксис функции для разных типов приведён ниже:

Эта функция возвращает результат вычисления квадрата числа, переданного через параметр. То есть Sqr = х * х.

О типе ValReal я рассказывал здесь.

Квадрат числа

Здесь всё крайне просто. Квадрат числа Х равен произведению Х на Х. То есть функция Sqr на первый взгляд кажется бесполезной. Потому что во многих случаях проще написать так:

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

будет написать проще, чем

Х := 5.3456753322 * 5.3456753322

Также возведение в квадрат числа в Паскале сложного выражения тоже будет проще, если использовать функцию Sqr:

X := Sqr(Y + 100 * Z / X)

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

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

Однако использование этих функций всё-таки немного сложновато. Поэтому для вычисления квадратного корня в Паскале имеется специальная функция (потому что квадратный корень приходится вычислять намного чаще, чем, например, корень n-й степени).

Эту функцию вы уже знаете — это функция Sqrt.

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

Итак, квадратный корень из числа А (корень 2-й степени) — это решение уравнения:

То есть квадратный корень из числа А, это число Х, которое при возведении в квадрат даёт число А.

ВАЖНО!
Число А может быть только положительным числом. Извлечение корня из отрицательного числа тоже возможно, но это уже будут комплексные числа.

Читать еще:  Программирование на си в visual studio

Как стать программистом 2.0

Эта книга для тех, кто хочет стать программистом. На самом деле хочет, а не просто мечтает. И хочет именно стать программистом с большой буквы, а не просто научиться кулебякать какие-то примитивные программки… Подробнее.

Извлечение корней в Python

Под извлечением корня из какого-либо числа чаще всего подразумевают нахождение решение уравнения 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 будет выглядеть так:

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

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

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

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

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

Для извлечения квадратного корня самым наглядным способом, правда не самым быстрым, будет использование 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, но подходит только для квадратный корней из числа. Остальные методы не такие элегантные, но легко могут извлечь корень нужной степени из числа. Кроме того оператор ** оказался наиболее быстрым при тестировании.

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

Корень в программировании

Разделы

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

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

Читать еще:  Язык программирования майкрософт

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

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

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

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

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

Код занимает прядка 70 байт и выполняется

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

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

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

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

80 байтов), — скорость выполнения (

1000 циклов для AVR).

Напишу как делаеться в 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 нет.

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»);

Пользовался детским алгоритмом, на мой взгляд достаточно быстр и достаточно компактный. Идея в том что от числа последовательно отнимаются все нечётные числа, и сколько вычитаний удалось сделать, таков и корень числа. Пример, число 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
Не ручаюсь за правильность коэффициентов, надо внимательно проверить.
Когда писал, не учел одну штуку, число бит может быть нечетным, отрезок надо брать больше.

Читать еще:  Идентификатор в программировании это

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

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

Квадратный корень в программах встречается очень часто, при этом его вычисление достаточно трудоемко. Еще в 1950х годах соответствующая операция была вынесена в специальный математический сопроцессор — центральный процессор отправлял в него запрос и пока выполнялись вычисления он успевал обрабатывать другие важные команды.

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

Вычисление корня через площадь прямоугольника

В древней Греции было разработано множество алгоритмов с хорошей геометрической интерпретацией. Не удивлюсь, если и этот алгоритм придумали греки. На самом деле, подумайте откуда берется квадратный корень? — известно, что у квадрата со стороной A площадь равна S = A*A . Из этого простого соотношения следует, что если вам надо вычислить корень из S — нужно построить такой квадрат, что его площадь будет равна S , а длина стороны квадрата как раз и будет искомым корнем ( a = sqrt(S) ).

Кстати, аналогичные рассуждения возможны для кубического корня (но при этом площадь квадрата нужно заменить объемом куба). Это прекрасная геометрическая интерпретация, но как же найти длину стороны такого квадрата? — итеративно. Возьмем для начала прямоугольник одна из сторон которого имеет длину S , а другая — 1 . Площадь такого прямоугольника совпадает с площадью исходного квадрата, если при этом длины сторон отличаются на величину допустимой погрешности вычислений — то сторона прямоугольника является ответом. Если же стороны различаются слишком сильно — то самый очевидный алгоритм предлагает усреднить одну из сторон ( a ), а вторую вычислить как b = S/a . За счет того, что одна сторона усредняется, разница длин сторон сокращается. Вторая сторона вычисляется так, чтобы площадь прямоугольника не изменялась.

Блок-схема такого алгоритма вычисления корня:

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

Метод половинного деления относится к серии алгоритмов, построенных по принципу «разделяй и властвуй». Он применяется для поиска корней уравнений. Допустим, есть у нас некоторая функция f(x) , известно, что функция монотонна на некотором интервале [a,b] .

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

Тогда, если на концах интервала функция имеет разные знаки — она обязательно пересекает горизонтальную ось, т.е. имеет корень. Если f(a) * f(b) > 0 — значит функция на этом интервале корня не имеет.

Как же найти где именно находится этот корень? — опять же итеративно. Возьмем точку посередине интервала ( x = a + (b-a)/2 ) — по знаку f(x) можно определить где именно находится корень (правее этой точки или левее). Если f(a)*f(x) — то корень находится на интервале [a,x] при этом заменим b на x и повторим процесс. В противном случае корень находится на [x,b] . Вычисления продолжаются до тех пор, пока интервал поиска корня не сузится достаточно сильно, т.е. пока abs(b-a) > Eps .

Причем же тут корень квадратный? — заметьте, что для его вычисления достаточно решить уравнение типа x*x = S , т.е. f(x) = x*x — S = 0 . Начальное значение интервала поиска — [1,S] .

Блок-схема такого алгоритма вычисления корня:

Ссылка на основную публикацию
Adblock
detector