Извлечение корня в си - IT Справочник
Llscompany.ru

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

Извлечение корня в си

Извлечение корня в си

Разделы

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

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

Читать еще:  Лечение microsd карты

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

Функции 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

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

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

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

Функции в языке Си

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

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

Семантика функции определяет способ реализации функции. Обычно представляет собой тело функции.

Определение функции

Каждая функция в языке Си должна быть определена, то есть должны быть указаны:

  • тип возвращаемого значения;
  • имя функции;
  • информация о формальных аргументах;
  • тело функции.

Определение функции имеет следующий синтаксис:

Пример : Функция сложения двух вещественных чисел

В указанном примере возвращаемое значение имеет тип float . В качестве возвращаемого значения в вызывающую функцию передается значение переменной y . Формальными аргументами являются значения переменных x и z .

Если функция не возвращает значения, то тип возвращаемого значения для нее указывается как void . При этом операция return может быть опущена. Если функция не принимает аргументов, в круглых скобках также указывается void .

Различают системные (в составе систем программирования) и собственные функции.

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

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

Разбиение программ на функции дает следующие преимущества:

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

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

Вызов функции

Общий вид вызова функции

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

Возврат в вызывающую функцию

По окончании выполнения вызываемой функции осуществляется возврат значения в точку ее вызова. Это значение присваивается переменной, тип которой должен соответствовать типу возвращаемого значения функции. Функция может передать в вызывающую программу только одно значение. Для передачи возвращаемого значения в вызывающую функцию используется оператор return в одной из форм:

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

Оператор return также завершает выполнение функции и передает управление следующему оператору в вызывающей функции. Оператор return не обязательно должен находиться в конце тела функции.

Функции могут и не возвращать значения, а просто выполнять некоторые вычисления. В этом случае указывается пустой тип возвращаемого значения void , а оператор return может либо отсутствовать, либо не возвращать никакого значения:

Читать еще:  Установить антивирус секьюрити

Пример : Посчитать сумму двух чисел.

В языке Си нельзя определять одну функцию внутри другой.

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

  • тип возвращаемого значения;
  • имя функции;
  • типы формальных аргументов в порядке их следования.

Прототип необходим для того, чтобы компилятор мог осуществить проверку соответствия типов передаваемых фактических аргументов типам формальных аргументов. Имена формальных аргументов в прототипе функции могут отсутствовать.

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

Рекурсивные функции

Функция, которая вызывает сама себя, называется рекурсивной функцией .

Рекурсия — вызов функции из самой функции.

Пример рекурсивной функции — функция вычисления факториала.

Извлечение корня в си

Представленный алгоритм был создан в те бородатые времена, когда производительность x87 оставляла желать лучшего. Но и сейчас, скорость работы этого алгоритма соизмерима со скоростью вычисления с плавающей точкой на PII или MMX. На мой взгляд, материал может быть интересен, как начинающим программистам — пусть учатся писать программы, а не ломать их, и не вирусы, так и опытным — как игра ума., скомпилированный MSVC 5.0, на PII-233×2 дает следующие результаты (Листинг 1):

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

Результат выполнения кода приведенного в примере 1 выглядит так:

В действительности, значение квадратного корня для числа 168 соответствует числу 12.96, что по общепринятым правилам округления ближе к целому числу 13. В данном примере мы видим классический машинный случай округления с отбрасыванием дробной части.

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

Функция, приведенная в примере 2, дает абсолютно правильные значения для всех целых чисел согласно принятым правилам округления. Однако возникает вопрос: возможно ли получение правильных результатов при использовании целочисленных алгоритмов?

Самый известный целочисленный алгоритм для вычисления квадратного корня из числа поражает своей простотой и приведен в примере 3.

Результат работы алгоритма из примера 3 идентичен результату из примера 1 — отбрасывание дробной части. Кроме того, невооруженным глазом виден еще один недостаток данного алгоритма — количество итераций в цикле соответствует значению вычисленного квадратного корня от аргумента L:

Рассматривая задачу вычисления квадратного корня с точки зрения уменьшения величины вычислительных затрат, более привлекателен целочисленный алгоритм, реализующий формулу Ньютона — пример 4.

Количество итераций в цикле для алгоритма из примера 4 приблизительно будет равняться натуральному логарифму от аргумента L:

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

Однако результат работы алгоритма из примера 4 опять тот же — округление до целого числа отбрасыванием дробной части. Анализ кода алгоритма показывает, что наибольшая ошибка при вычислениях накапливается в главной формуле алгоритма и возникает при целочисленном делении на 2 без учета остатка от деления. В примере 5 приведен модифицированный алгоритм вычисления квадратного корня, с учетом вышеупомянутого замечания.

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

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

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

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

Последняя модификация алгоритма (пример 7) вычисляет квадратный корень из числа без ошибок округления на диапазоне [0..10000] в среднем за 3 итерационных цикла. В таблице ниже представлена сводная таблица по вычислительным затратам алгоритма на исследуемом диапазоне. На других диапазонах аргумента количество итераций не бывает больше 6, а в среднем равняется 3. Сравнивая с первоначально достигнутыми результатами, см. таблицу в начале, можно сказать, что достигнуто увеличение производительности как минимум в 2 — 4 раза.

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

Ссылка на основную публикацию
ВсеИнструменты 220 Вольт
Adblock
detector