Easyelectronics.ru

Электроника для всех
Текущее время: 23 сен 2020, 08:22

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/5шт. два слоя. $5/5шт. четыре слоя
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 05 авг 2016, 13:22 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
судя по приведённому листингу это ничего не поменяет


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 05 авг 2016, 13:55 
Старожил

Зарегистрирован: 07 фев 2011, 21:00
Сообщения: 510
Откуда: Ханты-Мансийск
Студентам в качестве задания на лабораторную даю (см. вложение) по дисциплине языки низкого уровня.


Вложения:
вычисление кв.корня.docx [16.08 Кб]
Скачиваний: 325
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 09 авг 2016, 13:59 
Старожил

Зарегистрирован: 02 июл 2010, 23:41
Сообщения: 465
SOVA писал(а):
У себя я не считал такты, а смотрел осциллографом время выполнения программы. На STM8 получилось 2,5мс.


Не ясно, как при 606 тактах программы получилось такое большое время - 2,5 мсек? Неужели у STM так плохо?
У меня в разделе Valhalla в теме Алгоритм Билдер (описания, без программ) от 26 марта 2016 г. есть пример логарифма для AVR. Программа вычисляет логарифм с гарантированной точностью 0,5 процента во всем диапазоне. Число тактов – 1025, время выполнения – 256 мксек при частоте кварца 4 МГц – почти в 10 раз быстрее.
Расчет в программе основан на линейной аппроксимации.
Думаю, эту программу можно использовать и для расчета квадратного корня, она, скорее всего, не меняется. Изменятся только численные значения массивов разбиения точек координаты Х и коэффициентов альфа и бета аппроксимирующей прямой.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 09 авг 2016, 14:48 
Старожил
Аватара пользователя

Зарегистрирован: 30 янв 2014, 18:09
Сообщения: 647
Откуда: Киев
600-700 тактов при 16 МГц будет примерно 43 мкс. Может, забыл время выполнения, год назад было дело, здесь даже темы не осталось. Наверное, это было время вычисления первоначального варианта.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 13 авг 2016, 09:11 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
Есть вот такой любопытный вариант над плавающей точкой. По сути это таже формула гирона, но с выбором начальной точки алгоритма на основе флоатовской битовой магии. (По сути, если большая точность не важна, то можно вообще ограничиться манипуляцией над битами во float представлении числа).

Код:
float lib_sqrtapprox(float x)
{
  int32_t i;

  /* Floats + bit manipulation = +inf fun! */

  i = *((int32_t *) & x);
  i = 0x1fc00000 + (i >> 1);
  x = *((float *)&i);

  return x;
}

double sqrt(double x)
{
  long double y, y1;

  if (x < 0.0)
    {
      set_errno(EDOM);
      return NAN;
    }

  if (isnan(x))
    {
      return NAN;
    }

  if (isinf(x))
    {
      return INFINITY;
    }

  if (x == 0.0)
    {
      return 0.0;
    }

  /* Guess square root (using bit manipulation) */

  y = lib_sqrtapprox(x);

  /* Perform four iterations of approximation.  This number (4) is
   * definitely optimal
   */

  y = 0.5 * (y + x / y);
  y = 0.5 * (y + x / y);
  y = 0.5 * (y + x / y);
  y = 0.5 * (y + x / y);

  /* If guess was terribe (out of range of float).  Repeat approximation
   * until convergence.
   */

  if (y * y < x - 1.0 || y * y > x + 1.0)
    {
      y1 = -1.0;
      while (y != y1)
        {
          y1 = y;
          y = 0.5 * (y + x / y);
        }
    }

  return y;
}


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 13 авг 2016, 09:19 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
И, кстати, зачастую нужен не квадратный корень, а обратный квадратный корень.

https://ru.wikipedia.org/wiki/%D0%91%D1 ... 0%BD%D1%8C


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 13 авг 2016, 09:26 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
SOVA

А не получится оптимизировать ваш алгоритм так, чтобы корректно выполнялось округление результата?
Допустим, корень из пятнадцати получается 3, хотя реальный результат ближе к 4.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 13 авг 2016, 16:47 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 757
Откуда: GMT+6
Mirmik писал(а):
Есть вот такой любопытный вариант над плавающей точкой. По сути это таже формула гирона, но с выбором начальной точки алгоритма на основе флоатовской битовой магии. (По сути, если большая точность не важна, то можно вообще ограничиться манипуляцией над битами во float представлении числа).
Код:
Микроконтроллер - это вам не x86, он с плавающей точкой ой как не быстро работает.

Mirmik писал(а):
SOVA
А не получится оптимизировать ваш алгоритм так, чтобы корректно выполнялось округление результата?
Допустим, корень из пятнадцати получается 3, хотя реальный результат ближе к 4.
Да без проблем, перед возвратом из функции ставим if(y < x) ++y;
Хотя, смотря что понимать под "корректно", например стандарт IEEE754 не выполняет даже x86 процессор https://youtu.be/K5Y4-4SKaSA?t=12m
Show Код



_pv
А у вашего бинарного поиска переполнение в строке uint16_t y = (y0 + y1) >> 1;, из за чего в диапазоне 0x3FFF0001-0xFFFFFFFF возвращается всегда 0x7FFF.

SOVA
Спасибо за идею изменения начального значения m.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 13 авг 2016, 22:46 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
Я не совсем согласен про плавающую точку. Я специально устраивал тесты над плавающей арифметикой на восьмибитных аврках. Так вот плавающая арифметика показала себя.... Совсем чуть чуть хуже, чем 32битная целочисленная.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 14 авг 2016, 12:01 
Старожил
Аватара пользователя

Зарегистрирован: 30 янв 2014, 18:09
Сообщения: 647
Откуда: Киев
Kelvin писал(а):
SOVA
Спасибо за идею изменения начального значения m.

Пожалуйста, но это не моя идея.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 15 авг 2016, 11:03 
Старожил

Зарегистрирован: 21 янв 2015, 16:19
Сообщения: 617
SOVA, спасибо. Забрал в библиотеку.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 16 авг 2016, 01:37 
Старожил

Зарегистрирован: 02 июл 2010, 23:41
Сообщения: 465
SOVA, а какая точность расчета корня и какой диапазон аргумента?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 16 авг 2016, 01:44 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 757
Откуда: GMT+6
Alexandr_1
Точность - 0 знаков после запятой, я приводил способ округления.
Диапазон входных значений = диапазону значений типа аргумента.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 13:40 
Заглядывает иногда

Зарегистрирован: 28 мар 2013, 11:01
Сообщения: 86
Алгоритмы с циклами довольно медленные. Если есть быстрый умножитель, то гораздо быстрее будет метод ньютона (Ньютона-Рафсона, одно и то же), или Гольдшмидта (тоже интерпретация метода Ньютона). В идеале, сходимость - квадратичная.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 14:01 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 757
Откуда: GMT+6
Mirmik писал(а):
Я не совсем согласен про плавающую точку. Я специально устраивал тесты над плавающей арифметикой на восьмибитных аврках.
Да, я ошибся, давно не имел дела с плавающей точкой, всё стараюсь считать в целочисленной.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 14:26 
Заглядывает иногда

Зарегистрирован: 28 мар 2013, 11:01
Сообщения: 86
Kelvin писал(а):
Если не ошибаюсь, то алгоритм, запощенный SOVA и есть Ньютоновский

Нет, это Trial Subtraction.

Kelvin писал(а):
А чтобы быть быстрее этого алгоритма

Trial Subtraction это как раз самый медленный алгоритм. В общем случае дает один бит за одну итерацию. Метод Ньютона имеет квадратичную сходимость, т.е. количество бит на каждом шаге удваивается. Для чисел небольшой разрядности (8 бит) он будет тяжеловат, а вот для 32-битных самое оно.

Kelvin писал(а):
умножитель должен минимум в двое быстрее работать, чем логические операции.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 15:13 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 757
Откуда: GMT+6
Menzoda писал(а):
Нет, это Trial Subtraction.
Спасибо, теперь хоть знаю, как он называется.

Menzoda писал(а):
Trial Subtraction это как раз самый медленный алгоритм. В общем случае дает один бит за одну итерацию. Метод Ньютона имеет квадратичную сходимость, т.е. количество бит на каждом шаге удваивается. Для чисел небольшой разрядности (8 бит) он будет тяжеловат, а вот для 32-битных самое оно.

С сайта http://e-maxx.ru
Метод Ньютона
Изображение
Вычисление целочисленного корня
Код:
int n;
cin >> n;
int x = 1;
bool decreased = false;
for (;;) {
   int nx = (x + n / x) >> 1;
   if (x == nx || nx > x && decreased)  break;
   decreased = nx < x;
   x = nx;
}
cout << x;

UPD: на 31 битное число в среднем 16 итераций. Алгоритм Trial Subtraction в среднем дает столько - же итераций.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 16:33 
Заглядывает иногда

Зарегистрирован: 28 мар 2013, 11:01
Сообщения: 86
Квадратный корень методом Ньютона не вычисляют, вычисляют обратный квадратный корень (чтобы не надо было делить). При этом итерация имеет вид
Код:
x[i+1]=0.5*x[i]*(3 - n*x[i])
Первое приближение можно взять из таблицы, или вычислить каким-нибудь совсем простым способом. Пускай это приближение обеспечивает N старших бита, тогда первая итерация увеличит точность до 2N бит, а вторая до 4N бит. Обычно, двух-трех итераций достаточно, чтобы из относительно грубого приближения получить 32 бит точности. Так что никаких 16 итераций там и в помине нет.

Теперь, чтобы из обратного корня получить просто корень нужно его домножить на исходное число. В итоге получиться искомое значение с некоторой погрешностью. Теперь его нужно подкорректировать, если нужна абсолютная точность, а можно и не корректировать, если это не критично. Выглядит это все довольно громоздко, да, но в итоге гораздо быстрее. Хотя, принимая во внимание что корень 32-битного числа - это максимум 16 бит, то есть всего 16 итераций тривиального вычитания, метод Ньютона действительно может выйти дороже. Я просто сразу не сообразил, что нужно всего 16 бит. Вот у меня недавно была задача получить 31 бит, и там уже метод Ньютона без вариантов.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 17:06 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 757
Откуда: GMT+6
Menzoda
Это оно?
Изображение
Пойду тестировать...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 17:27 
Заглядывает иногда

Зарегистрирован: 28 мар 2013, 11:01
Сообщения: 86
Да. Всем известный быстрый обратный корень Кармака это очень завуалированный метод ньютона.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 17:44 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 757
Откуда: GMT+6
Протестировал, точность +- 1
Show Код теста


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 19:17 
Заглядывает иногда

Зарегистрирован: 28 мар 2013, 11:01
Сообщения: 86
Данный способ можно использовать если есть FPU, и только для float. Вот в таком виде, с приведением int к float, его не стоит использовать, так как не все значения int могут быть представлены в виде float.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 20:20 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 757
Откуда: GMT+6
Menzoda
Ок. тогда как ньютоном считать целочисленный корень?
Код:
int x_sqrt( int n)
{
   if (n==0) return 0;
   unsigned int b = 0x7f800000;
   unsigned int x = 0x3f00;
   while (!(n&b)) { b >>= 8; x >>= 4; } //Первое приближение
   int i;
   forn(i, 0, 4)
   {
      x = (x * (3 - n*x))>>1; //x[i+1]=0.5*x[i]*(3 - n*x[i])
   }
   return x;
}

На вход даем 64, на выходе получаем 184147621, как из этого числа получить 8?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 18 авг 2016, 22:37 
Заглядывает иногда

Зарегистрирован: 28 мар 2013, 11:01
Сообщения: 86
Так то это уравнение для обратного квадратного корня, на выходе должно получиться 1/8, а не 8, но в любом случае просто заменить float на int не получится, алгоритм достаточно сложный, так просто не объяснишь. Начинается с того, что исходное число нормализуется до числа в формате с фиксированной точкой Q32, лежащего на интервале [0.5, 1). Для него находится начальное приближение. Выполняется пару итераций метода Ньютона. В итоге получается искомое значение в формате Q31, лежащее на интервале [1, 2). Затем оно умножается на исходное нормализованное, чтобы получился просто корень, и денормализуется обратно.

Это алгоритм для нахождения корня числа с фиксированной точкой. Для просто целого вычисления будут попроще, ведь нужно всего 16 бит результата, но думаю алгоритм примерно одинаков. По крайней мере это более обобщенная версия, её можно доработать и для вычислений целых корней. А так лучше почитать литературу. Могу порекомендовать ARM System Developer's Guide, там всё это более-менее ясно объясняется, и код есть. Правда он для ассемблера ARM.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вычисление квадратного корня
СообщениеДобавлено: 19 авг 2016, 00:38 
Старожил

Зарегистрирован: 27 мар 2015, 01:22
Сообщения: 1946
bw429 писал(а):
Cthulhu писал(а):
sqrt?
стандартные функции, имеющие длительное время выполнения, невозможно использовать в программах, построенных на КА

Кто-нибудь проверял время выполнения sqrt из libm?
Show bench-libm.dox.txt

_________________
mcu.goodboard.ru


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3  След.


Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB