Remkomplekty.ru

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

Корень в си шарп

Консольное приложение вычисление квадратного корня на С#

Это консольное приложение которое производит вычисление квадратного корня через дискриминант.

Эта прога написанна в муках, по этому не судите строго.

Я только начал изучать прекрасный язык программирования С#.

Хотя раньше писал только на Vb . Но надо двигаться вперед.

Console.WriteLine(«X1 = , X2 = <1>«, x1, x2);

Что ты хотел сказать этим коментарием?

Console.WriteLine(«X1 = , X2 = <1>«, x1, x2);

Console.WriteLine(«X1 = , X2 = <1>«, x1, x2);

Не «вычисление квадратного корня», а «вычисление корней квадратного уравнения», е-мае!

Прежде чем писать свои мысли надо разбираться в этом. И запомни от перемены мест слагаемых сумма не меняется. Квадратное уравнение — уравнение вида ax2 + bx + c = 0, где a ≠0. Переменная х называется корнем квадратного уравнения. Думай прежде чем написать что нибуть. А еще лучше учи математику.

Met 🙂
1) ты доказал именно то, про что я и написал.
2) я учусь в университете на математическом, можешь мне не указывать 🙂

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

Ну а если совсем по правилам то Решения квадратного уравнения через дискриминант.

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

ты мне прям настроение с утра поднял, спасибо)

Это тебе спасибо. Повесилил от души. Продолжай в таком духе. Теперь я знаю к кому обратиться по поводу слов в тексте.

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

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

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

И да, черт возьми, я вернулся!

Ну вот еще один прыщик проклюнулся. Кулхацкер ты молодец давай жги. Я же еще раз говорю что дурная голова рукам покоя не дает.

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

Мет-мет, большей оригинальности я и не ожидал.

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

Met, есть ли в твоей жизни хоть что-нибудь, в чем ты не сомневаешься?)

Да-да. Я молокосос на правильном пути.

Чувствую я, что сие плавно в срач перерастет.

Ничего, главврач следит, санитары на стреме.

за вами с мобильника следить еле успеваю)

Слезь с мобильника. Работа есть.

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

Лайс, я где-нибудь, хоть в одной из своих статеек сказал, что она шедевр?

Хотя, не будем срач разводить.

Нда, весело тут у вас.

А чего нет никакой защиты от дурака. А если я буквы введу, или вместо точки запятую? Или ноль забью в переменную ‘a’ и начнется деление на ноль?
Кроме Console.WriteLine(«X1 = X2 = <1>«, x1, x2);(показали вывод нескольких аргументов строки вывода)
и Console.ForegroundColor = ConsoleColor.DarkCyan; (консольные разукрашки) стоит обратить внимание только на Math.Sqrt(D).
Но если это и есть цели урока, то тема НЕ раскрыта.
Ни ConsoleColor, ни WriteLine, ни Math.

Klinsman, Тут статьи не профессионалы пишут, а те кто ещё новички в программировании, если у вас есть хорошие знания по программированию, то можете написать несколько хороший статей!

Корень в си шарп


Приложение «Калькулятор» На первом занятии мы уже создавали простое приложение. Создадим ещё одно, назовём его Lesson2, и рассмотрим некоторые свойства формы и визуальных элементов. При этом мы будем создавать приложение «калькулятор». Итак, сначала присвоим форме заголовок «Калькулятор» (не путать с именем формы). Заголовок задаётся свойством Text. Панель свойств находится в правой части экрана.

Покрасим форму, например, в темно-синий цвет. Для этого найдём в редакторе свойств строку BackColor и выпадающем списке выберем нужный цвет.

Мы будем делать немного нетрадиционный калькулятор, в отличие, например от Windows калькулятора. Он будет иметь отдельные строки для ввода аргументов, знака математического действия и результата вычислений.
Поставим на форму четыре текстовых поля textBox1 . textBox4 сверху вниз.

Напротив каждого текстового поля поставим метки Label и в свойстве Text меток введём надписи, показанные на рисунке. Цвет надписей меток можно изменить свойством ForeColor.
Добавим кнопку и создадим событие на нажатие кнопки «Вычислить». Событие можно создать двойным щелчком на выделенной кнопке или, на панели свойств и событий, переключиться на раздел события (Properties) и выбрать событие Click.

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

private void button1_Click(object sender, EventArgs e)
<
double x, y, z;
string znak = «»;
x = Convert.ToDouble(textBox1.Text);
y = Convert.ToDouble(textBox3.Text);
z = 0;
znak = textBox2.Text;
if (znak == «+») z = x + y; else
if (znak == «-«) z = x — y; else
if (znak == «/») z = x / y; else
if (znak == «*») z = x * y; else
textBox4.Text = Convert.ToString(z);
>


Объявление переменных и способы записи выражений. Рассмотрим подробно все строки написанные в функции обработчика события.
Строка double x, y, z; — объявляет три переменные x, y и z (x и y — для вводимых значений и z для хранения результата вычислений) типа double. Тип double выбран с тем расчётом, что калькулятор должен уметь вычислять максимально большие числа.
При объявлении переменных любого типа им присваивается имя. Имя переменной должно начинаться с латинской буквы за которой могут следовать числа, например x256. Переменная может быть словом, например означающем назначение переменной input_x, out_y. Несколько переменных одного типа записываются через запятую. Выражение объявления переменных завершается точкой с запятой. При объявлении имени переменной и последующему её вызову в программе, регистр символов имеет значение. Так переменные Input_x и input_x являются независимыми, то есть это не одна переменная, а две.

Следующая строка программы string znak = «»; объявляет переменную znak (для хранения знака математической операции) типа string — строка и сразу этой переменной присваивается начальное значение — пустая строка.
Строка x = Convert.ToDouble(textBox1.Text); преобразует первую числовую строку введённую пользователем в textBox1 в число и присваивает это число переменной x. Аналогичное назначение следующей строки — преобразование и присваивание числа переменной y.
В строке z = 0; присваиваем начальное значение переменной z. В языке C# принято инициализировать переменные до обращения к ним из программы. Если не написать эту строку то компилятор (компилятор — программа преобразующая текст программы в цифровой код понятный для ЭВМ) выдаст предупреждающее сообщение, но программа всё равно будет работоспособна.
Строкой znak = textBox2.Text; мы получаем символ знака оперции введённый пользователем в textBox2 и присваиваем его переменной znak.
Далее, нам нужно проверить какой знак операции ввёл пользователь. Строка if (znak == «+») z = x + y; определяет ввёл ли пользователь знак +. Прочитать эту строку можно так: Если (if) переменная знак (znak) равна символу «+» то результат вычисления будет z = x + y. В скобках выражения записана проверка истинности выражения.
Для проверки истинности выражений в операторе if следует использовать следующие знаки сравнения:
== проверка равенства
!= проверка неравенства
больше
= больше или равно
Следующие три строки:
if (znak == «-«) z = x — y; else
if (znak == «/») z = x / y; else
if (znak == «*») z = x * y; else
выполняют проверку на ввод остальных математических знаков и, соответственно, производят вычисления. Слово else в конце каждой строки означает «иначе», то есть, если условие не выполнено, то иначе нужно проверить следующее условие.
И, наконец, строка textBox4.Text = Convert.ToString(z); выводит полученное значение z в textBox4. В связи с тем, что переменная z числового типа, а вывести в textBox4 мы можем только строковый тип, то нужно преобразовать число в строку функцией Convert.ToString.
Калькулятор готов, можно проверить его работоспособность нажав клавишу F5.

Читать еще:  Сортировка методом шелла паскаль

Примечание — при вводе чисел с плавающей запятой, в Windows принято вводить разделитель запятую, а не точку, как это принято в DOS.


Логические операции. Известно, что при делении на 0 возникает ошибка. Попробуем исключить такую ошибку, если пользователь введёт знаменателем 0. Доработаем строку определяющую ввод знака деления:

В этой строке мы написали: если знак равен наклонной черте ((znak == «/») и && второй аргумент (знаменатель) равен 0 (y == 0) то выводится сообщение об ошибке MessageBox.Show(«Ошибка! Деление на 0»); иначе else можно вычислить результат деления z = x / y;. Из этой строки видно, что сложные логические выражения записываются в скобках. В сложных логических конструкциях следует использовать следующие операторы:
&& — логическое «И»
|| — логическое «ИЛИ»

Введя изменения, посмотрим, как работает программа в такой ситуации.


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

Математические операторы C#

Математические операторы C#

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

Основные математические операторы

Основными математическими операторами в языке программирования C# являются:

  • Сложение (+)
  • Вычитание (-)
  • Умножение (*)
  • Деление (/)
  • Остаток от деления (%)

Рассмотрим пример простейшего приложения:

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

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

Так же стоит упомянуть операцию остатка от деления, про которую многие забывают. В других языках она часто записывается как mod. Она означает, что результатом будет число, оставшееся неподеленным при целочисленном делении. Для примера 5 % 2 = 1, это означает, что было выполнено целочисленное деление ближайшего меньшего подходящего числа — 4. А результатом является разница этого числа и исходного 5 — 4 = 1.

Операторы инкремента

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

  • Увеличение значения переменной на 1 (++)
  • Уменьшение значения на 1 (—)
  • Увеличение значения переменной на заданное значение (+=)
  • Уменьшение переменной на заданное значение (-=)
  • Умножение переменной на значение (*=)
  • Деление переменной на значение (/=)

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

Или другой пример, когда если мы хотим умножить текущее значение переменной на 4, то это можно записать так:

Префиксная и постфиксная запись инкремента

Обратите внимание, что существуют две формы записи:

  • Префиксная — когда оператор инкремента ставится перед именем переменной (++i)
  • Постфиксная — когда оператор инкремента ставится после имени переменной (i++)
Читать еще:  Площадь окружности паскаль

В большинстве случаев разницы нет, но в некоторых специфических случаях разница существует. Рассмотрим пример кода:

Как вы видите, результат переменных n и m отличаются. Это связано с тем, что при постфиксной записи сначала выполнилось присвоение значения переменной i (0) в переменную n (0), а после этого было выполнено увеличение значение переменной i на единицу (1). При префиксной записи, сначала выполнилось увеличение значения переменной j (1), а после этого присвоение переменной m (1).

Сложение (конкатенация) строк

Если со сложением чисел все достаточно просто, то как будет вести себя язык C# при попытке сложения, вычитания, умножения и деления строк? На самом деле все достаточно просто, для строк доступна только одна операция это сложение, а если быть точнее конкатенация. Конкатенация — это операция склеивания двух строк в одну новую стоку, содержащую обе исходные подстроки. Рассмотрим пример:

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

Приоритет выполнения операторов

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

Математические операторы C# — Заключение

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

Кроме того, рекомендую прочитать статью Установка .NET Framework 3.5. Исправление ошибок 0x800F081F и 0x800F0906. А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.

Функции в Си-шарп. Оператор return

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

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

До этого, мы весь код писали в функции main. Функция main является главной функцией приложения и точкой входа программы. Любая функция в Си-шарп может быть объявлена только в рамках класса, так как C# — полностью объектно-ориентированный язык программирования (ООП). Объявление пользовательской функции внутри другой функции (например main) недопустимо. Объявление функции имеет следующую структуру:

[модификатор доступа] [тип возвращаемого значения] [имя функции] ([аргументы])

Модификатор доступа (области видимости) может быть public, private, protected, internal, но пока будем везде использовать public.

Между модификатором и типом может стоять ключевое слово static, что означает, что функция будет статичной. Скажу только, что из статичной функции можно вызывать другие функции, если они тоже статичные. Главная функция main – всегда static, поэтому все функции в этом уроке мы будем объявлять также статичными.

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

Желательно называть функции так, чтобы имя отражало суть функции. Используйте глаголы или словосочетания с глаголами. Примеры: GetAge(), Sort(), SetVisibility().

Аргументы – это те данные, которые необходимы для выполнения функции. Аргументы записываются в формате [тип] [идентификатор]. Если аргументов несколько, они отделяются запятой. Аргументы могут отсутствовать.

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

Перейдем к практике.

Пример функции, которая не возвращает значение

Напишем простую функцию, которая будет заменять в массиве строк указанное имя на другое. Данная функция будет принимать три аргумента: массив строк, имя, которое необходимо заменить и новое имя. Так как функция не будет возвращать значение, указываем тип void перед именем функции.

public static void ReplaceName(string[] names, string name, string newName)
<
for (int i=0; i max)
max = array[i];
>
return max;
>

Логика функции проста. Создаем переменную max, в которую записываем первый элемент массива. Дальше в цикле сравниваем каждый элемент со значением в max, если элемент больше, чем max, то записываем в max этот элемент. В конце функции используем оператор return, чтобы вернуть наш результат.

Оператор return должен быть обязательно в функции, которая возвращает значение.

Используем нашу функцию:

class Program
<
public static int GetMax(int[] array)
<
int max = array[0];
for (int i = 1; i max)
max = array[i];
>
return max;
>
static void Main(string[] args)
<
int[] numbers = < 3, 32, 16, 27, 55, 43, 2, 34 >;
int max;
max = GetMax(numbers); //вызов такой функции можно использовать при присваивании значения
Console.WriteLine(GetMax(numbers)); // вызов функции также можно использовать как аргумент при вызове другой функции. WriteLine() – тоже функция.
Console.ReadKey();
>
>

Оператор return

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

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

public static void replacesign (int[] numbers, int number)
<
for (int i=0; i c? c : b) > a)? a : min;
>

class Program
<
public static int getmin (int[] numbers)
<
int min = numbers[0];
for (int i=1; i 2) <
for (int i=2; i

Корень в си шарп

Разделы

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

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

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

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