Easyelectronics.ru

Электроника для всех
Текущее время: 29 сен 2020, 03:14

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



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

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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
Нужен алгоритм быстрого вычисления квадратного корня. Прошу поделиться примерами, ссылками. Сам ни разу не математик. Для AVR. Си. Переменная unsigned long.


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

Зарегистрирован: 14 апр 2014, 11:06
Сообщения: 1643
Откуда: Курск
sqrt?


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

Зарегистрирован: 23 янв 2012, 00:31
Сообщения: 1799
Откуда: Новокузнецк
А чем алгоритм на итерационной формуле герона не подошел?
Код:
uint32_t mySqrt(uint32_t data)
{
   uint32_t x;
   uint8_t i;
   x = (data / 0x1388 + 0x1388) >> 1;

   for (i = 0; i < 13; ++i) {
      x = (data / x + x) >> 1;
   }
   return(x);
}

_________________
elisey.su


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

Зарегистрирован: 18 июл 2016, 21:17
Сообщения: 746
Cthulhu писал(а):

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


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

Зарегистрирован: 22 мар 2010, 22:54
Сообщения: 3995
bw429 писал(а):
стандартные функции, имеющие длительное время выполнения, невозможно использовать в программах, построенных на КА
и это замечательно! правда, это ничего не изменит, как жрали кактусы, так и дальше будут.


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

Зарегистрирован: 04 окт 2011, 10:19
Сообщения: 2079
https://www.google.ru/#newwindow=1&q=cordic+sqrt


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

Зарегистрирован: 30 янв 2014, 18:09
Сообщения: 647
Откуда: Киев
demiurg1978 писал(а):
Нужен алгоритм быстрого вычисления квадратного корня. Прошу поделиться примерами, ссылками. Сам ни разу не математик. Для AVR. Си. Переменная unsigned long.

Вот. Отлаженный и оптимизированный.
Show


Последний раз редактировалось SOVA 04 авг 2016, 20:06, всего редактировалось 1 раз.

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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
SOVA писал(а):
...

Премного благодарю! Проверил ваш и елисея варианты. Ваш вариант выиграл. 606 тактов против 8465 тактов. Число 1023*1023*64 = 66977856UL.
Какие-либо другие варианты не проверял. Есть варианты на chipenable. Но там оговорка, что точность не проверена. И разрядность 16 бит.

bw429 писал(а):
стандартные функции, имеющие длительное время выполнения, невозможно использовать в программах, построенных на КА

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


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

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
demiurg1978 писал(а):
SOVA писал(а):
...

Премного благодарю! Проверил ваш и елисея варианты. Ваш вариант выиграл. 606 тактов против 8465 тактов.

ну ещё бы, в формуле герона - через деление, а оно ой какое не быстрое.

бинарный поиск вот ещё проверьте, он всяко быстрее должен быть, только он результат не округляет, а дробную часть отбрасывает. то есть sqrt(15) == 3, sqrt(16) == 4.
Код:
uint16_t _sqrt(uint32_t x) {
  uint16_t y0 = 0;
  uint16_t y1 = 0xFFFF;
  while (y1 - y0 > 1) {
    uint16_t y = (y0 + y1) >> 1;
    uint32_t y2 = y * y;
    if (y2 == x) return y;
    if (y2 > x) y1 = y;
    else y0 = y;
  }
  return (y0 + y1) >> 1;
}


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


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

Зарегистрирован: 23 янв 2012, 00:31
Сообщения: 1799
Откуда: Новокузнецк
demiurg1978 писал(а):
Есть варианты на chipenable. Но там оговорка, что точность не проверена. И разрядность 16 бит.

А там тоже самое. Я свой вариант оттуда взял)

_________________
elisey.su


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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
_pv писал(а):
...

Можно ваш быстрый вариант?


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

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
так в сообщении же
Код:
uint16_t _sqrt(uint32_t x) {
  uint16_t y0 = 0;
  uint16_t y1 = 0xFFFF;
  while (y1 - y0 > 1) {
    uint16_t y = (y0 + y1) >> 1;
    uint32_t y2 = y * y;
    if (y2 == x) return y;
    if (y2 > x) y1 = y;
    else y0 = y;
  }
  return (y0 + y1) >> 1;
}


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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
_pv писал(а):
...

Что-то у вас не так. Симулирование программы зависло на вашем примере. То есть, наглухо зациклилась.


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

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
давайте листинг,
компилятор с типами что-то нахимичил.
скорее всего умножил не правильно.
вместо uint32_t y2 = y * y;
надо
uint32_t y2 = y;
y2 *= y;


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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
Show


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

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
да, компилятор не догадался, что умножение 16*16 даёт 32 бита, а не 16.
ну раз размер int 16 бит, наверное имел право.

вместо uint32_t y2 = y * y;
надо
uint32_t y2 = y;
y2 *= y;


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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
_pv писал(а):
...

Ваш вариант дольше. 744 тактов против 595 тактов от Sova.


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

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
потому что так он умножает не 16*16, а 32*16. что на 8 битном МК несколько печальнее.
можно листинг рабочего варианта?


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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
Show


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

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
строчку
if (y2 == x) return y;
можно убрать, лишних 4 такта проверок, да 16 раз в цикле. должно стать быстрее на 64 такта.

а с умножением более менее всё в порядке похоже.


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

Зарегистрирован: 25 фев 2011, 18:45
Сообщения: 3691
Откуда: Новосибирск
Было 744, стало 651.


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

Зарегистрирован: 04 окт 2012, 00:23
Сообщения: 2736
Откуда: Москва
https://www.youtube.com/watch?v=UvKJGxvlDt4 Что-то мне подсказывает , что такой алгоритм будет бысрее


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

Зарегистрирован: 30 янв 2014, 18:09
Сообщения: 647
Откуда: Киев
Делайте проверку не на одном круглом значении, а на нескольких, вида x * x + y, в разных диапазонах. Тогда статистика покажет среднее число тактов. А так вы можете считать только одну цепочку условий.
У себя я не считал такты, а смотрел осциллографом время выполнения программы. На STM8 получилось 2,5мс.


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

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3459
Код:
uint16_t _sqrt(uint32_t x) {
  uint16_t y0 = 0;
  uint16_t y1 = 0xFFFF;
  uint8_t n = 16;
  while (n--) {
    uint16_t y = (y0 + y1) >> 1;
    uint32_t y2 = y;
    y2 *= y;
    if (y2 > x) y1 = y;
    else y0 = y;
  }
  return (y0 + y1) >> 1;
}

еще на 50-100 тактов короче должно быть. и от входного параметра тут длительность выполнения не зависит.


Последний раз редактировалось _pv 05 авг 2016, 13:27, всего редактировалось 1 раз.

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

Зарегистрирован: 04 окт 2011, 10:19
Сообщения: 2079
Код:
uint16_t _sqrt(uint32_t x) {
  uint16_t y;
  uint32_t y2;
  uint16_t y0 = 0;
  uint16_t y1 = 0xFFFF;
  uint8_t n = 16;
  while (n) {
    --n;
    y = (y0 + y1) >> 1;
    y2 = y * y;
    if (y2 > x) y1 = y;
    else y0 = y;
  }
  return (y0 + y1) >> 1;
}


и так еще можно попробовать


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


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


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

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


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

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

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