Например TDA7294

Форум РадиоКот • Просмотр темы - квадратный корень на асме AVR
Форум РадиоКот
Здесь можно немножко помяукать :)

Текущее время: Чт мар 05, 2026 14:33:36

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


ПРЯМО СЕЙЧАС:



Форум закрыт Эта тема закрыта, Вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 40 ]  1,  
Автор Сообщение
 Заголовок сообщения: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 16:24:47 
Подскажите пожалуйста удобоваримый алгоритм для целочисленного расчёта квадратного корня из 32-битного числа для реализации на ассемблере AVR (mega128). Попалась “sqrt32_fast” - square root routine - но она нерабочая. Есть реализации на Си, например:
Код:
unsigned short isqrt( unsigned long ul) {
  unsigned long sqr = 0;
  unsigned long temp;
  unsigned long mask = 0x40000000;
  do{
    temp = sqr | mask;
    sqr >>= 1;
    if( temp <= ul ){
      sqr |= mask;
      ul -= temp;
    }
  }while( mask >>= 2 );
  if( sqr < ul && sqr < 0xFFFF ) ++sqr; // округление результата
  return (unsigned short)sqr;


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


Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 17:11:33 
Встал на лапы
Аватар пользователя

Зарегистрирован: Вт мар 22, 2011 22:31:01
Сообщений: 102
Рейтинг сообщения: 0
В асме не силен, даю подробные комментарии, думаю разберемся:
Код:
unsigned short isqrt( unsigned long ul) { //объявление функции с одним параметром - без знаковое целое 2  байта
  unsigned long sqr = 0;   // объявление переменной - без знаковое целое 2  байта
  unsigned long temp;     // объявление переменной - без знаковое целое 2  байта
  unsigned long mask = 0x40000000; // объявление переменной   - без знаковое целое 2  байта. В переменную записывается значение 0x40000000
  do{                                               //  цикл с пост условием (проверка произойдет после выполнения тела цикла)
    temp = sqr | mask;                      // побитное "или"  между  sqr и mask, результат записывается в temp
    sqr >>= 1;                                  // сдвиг переменной sqr на 1 бит вправо
    if( temp <= ul ){                          // условный оператор если temp меньше равно  ul
      sqr |= mask;                             //  побитное "или"  между  sqr и mask, результат записывается в sqr
      ul -= temp;                               //  вычисляется разница между  ul и temp результат записывается в ul
    }
  }while( mask >>= 2 );                  // Сдвинуть mask  на два бита в право, результат записать в mask,  выполнять цикл пока mask > 0.
  if( sqr < ul && sqr < 0xFFFF ) ++sqr; // округление результата  (если sqr меньше ul "и" sqr меньше 0xFFFF в sqr записывается sqr+1)
  return (unsigned short)sqr;           // возвращение результата работы функции, тип переменной приводится к без знаковое целое 1  байт


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 17:26:49 
Сверлит текстолит когтями
Аватар пользователя

Карма: 4
Рейтинг сообщений: 30
Зарегистрирован: Ср янв 05, 2011 16:25:15
Сообщений: 1163
Рейтинг сообщения: 0
Errorkpi писал(а):
unsigned long sqr = 0; // объявление переменной - без знаковое целое 2 байта
unsigned long - 4 байта
2 orinoko на ассемблер перевести можно, но понятнее вряд-ли будет - AVR 8-ми битный, а корень берется из 4-х байтной величины.


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 17:33:49 
Мудрый кот
Аватар пользователя

Карма: 24
Рейтинг сообщений: 286
Зарегистрирован: Чт июн 10, 2010 08:55:35
Сообщений: 1810
Откуда: Сибирские Афины
Рейтинг сообщения: 0
Можно попробовать посмотреть в исходниках avr-libc в математической библиотеке...

_________________
Когда уже ничего не помогает - прочтите, наконец, инструкцию.
Лучший оптимизатор находится у вас между ушей. (Майкл Абраш, программист Quake и QuakeII)
Избыток информации ведёт к оскудению души - Леонтьев А. (сказано в 1965 г.)


Вернуться наверх
 
Эиком - электронные компоненты и радиодетали
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 17:34:36 
Большое спасибо за подробное описание. Если честно, меня смущали только 3 строчки. Попробую перевести на асм.


Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 17:39:28 
Встал на лапы
Аватар пользователя

Зарегистрирован: Вт мар 22, 2011 22:31:01
Сообщений: 102
Рейтинг сообщения: 0
ChipKiller писал(а):
unsigned long - 4 байта

да конечно 4 байта. Извините бес попутал :)
ChipKiller писал(а):
на ассемблер перевести можно, но понятнее вряд-ли будет - AVR 8-ми битный, а корень берется из 4-х байтной величины.

Дык какая разница со сколькими байтами работать. Я когда-то и с трех! байтными числами работал, когда мне памяти не хватало... Причем выполнял с ними весь спектр арифметических и логических операций


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 17:52:21 
Тут же дело не в понятности. У меня вся программа написана на асме. Мне необходимо произвести расчёт среднеквадратического значения, имея массив 16-битных чисел. Вся остальная обработка уже реализована. Осталась фигня :) - корень. Да и 4-байтные числа меня не пугают. Нелинейные преобразования на асме, в которые входит и корень - это весьма специфичные задачи.


Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 18:05:18 
Kavka писал(а):
Можно попробовать посмотреть в исходниках avr-libc в математической библиотеке...

Посмотрел. Там расчёт числа с плавающей точкой. Как то не понял, что там и как.


Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 18:12:07 
Мудрый кот
Аватар пользователя

Карма: 24
Рейтинг сообщений: 286
Зарегистрирован: Чт июн 10, 2010 08:55:35
Сообщений: 1810
Откуда: Сибирские Афины
Рейтинг сообщения: 0
Опс. Извиняюсь. День выдался сумотошным, рецидивы 1-го апреля, видать... :))

_________________
Когда уже ничего не помогает - прочтите, наконец, инструкцию.
Лучший оптимизатор находится у вас между ушей. (Майкл Абраш, программист Quake и QuakeII)
Избыток информации ведёт к оскудению души - Леонтьев А. (сказано в 1965 г.)


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 18:58:59 
промоделировал я этот алгоритм в Labview. Что-то не правильно в этом алгоритме. Несколько раз перепроверил. При любом входном значении на выходе 0x7FFF. :(

Чуть позже:
Но исходник на Си работает правильно. Я моделировал по комментариям. Всё ли верно в комментариях (не считая типы переменных)

С алгоритмом разобрался (пятница... вечер...)


Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 21:54:28 
Друг Кота
Аватар пользователя

Карма: 62
Рейтинг сообщений: 889
Зарегистрирован: Вт апр 24, 2007 07:45:40
Сообщений: 6288
Откуда: Minsk
Рейтинг сообщения: 0
Тема еще актуальна ? Лет 12 тому назад делал такое. Значит, аргумент - 2-байтное беззнаковое целое число ?


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Пт апр 01, 2011 22:51:43 
Потрогал лапой паяльник
Аватар пользователя

Зарегистрирован: Сб фев 07, 2009 19:21:25
Сообщений: 346
Рейтинг сообщения: 0
у меня есть алгоритм дл PIC но думаю его лехко можно переписать и под AVR если желаете скину.

_________________
Мечтатель - не тот, кто сидит на диване и думает о несбыточном, а тот, кто всеми силами стремится воплотить несбыточное в реальность.


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Сб апр 02, 2011 08:19:26 
Jack_A писал(а):
Тема еще актуальна ? Лет 12 тому назад делал такое. Значит, аргумент - 2-байтное беззнаковое целое число ?

Аргумент - 4 байтное беззнаковое число (32-битное). Результат - 2-байтное
Цитата:
у меня есть алгоритм дл PIC но думаю его легко можно переписать и под AVR если желаете скину.

На просторах инета я видел решение для пика, причём вроде как фирменное. Но там очень уж непохожая с атмелом архитектура АЛУ. Проще написать с нуля.
Попробую за выходные написать (время найти надо). Я обязательно выложу, что получится, на всеобщее обозрение.


Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Сб апр 02, 2011 10:16:06 
Друг Кота

Карма: 67
Рейтинг сообщений: 1032
Зарегистрирован: Пт мар 07, 2008 06:54:43
Сообщений: 4409
Откуда: Ижевск
Рейтинг сообщения: 0
Здравствуйте. Мне нравится "Итерационный аналитический алгоритм" http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 0%BD%D1%8C За небольшое количество приближений получается точный результат


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Сб апр 02, 2011 11:11:07 
Друг Кота
Аватар пользователя

Карма: 62
Рейтинг сообщений: 889
Зарегистрирован: Вт апр 24, 2007 07:45:40
Сообщений: 6288
Откуда: Minsk
Рейтинг сообщения: 0
akl писал(а):
Здравствуйте. Мне нравится "Итерационный аналитический алгоритм" http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 0%BD%D1%8C За небольшое количество приближений получается точный результат

Хороший алгоритм, быстро сходится. А для поиска первого приближения я высчитывал номер позиции самого старшего ненулевого бита и делил его на 2, число с 1 в этой позиции ( остальные нули ) было хорошим приближением.

00100000 1100110101 --> 01000000


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Сб апр 02, 2011 11:15:54 
Друг Кота

Карма: 67
Рейтинг сообщений: 1032
Зарегистрирован: Пт мар 07, 2008 06:54:43
Сообщений: 4409
Откуда: Ижевск
Рейтинг сообщения: 0
Интересно. :beer: Я составлял таблицу квадратов, находил по ней диапазон попадания корней и затем уже приближался. Тоже довольно быстро.


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Сб апр 02, 2011 11:55:00 
Метод приближений - это по-моему метод Герона. Есть ещё метод Ньютона. Самый простой - это метод, при котором происходит вычитание по очереди нечётных чисел, но при больших числах он очень затратный по времени.


Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Сб апр 02, 2011 13:21:29 
Ну в общем вот - предоставляю вашему вниманию полный текст расчёта квадратного корня. Принимаются все замечания по оптимизации. Время расчёта при частоте кварца 16 МГц - ~65 мкс. В принципе, меня устраивает. У меня лимит по времени - 80 мкс. Но, как говорят, нет предела совершенству. Возможно, даже в таком виде кому-то будет полезна.
Большое спасибо все принимающим участие в данном вопросе. Отдельное спасибо Errorkpi за расшифровку программы на Си


Вложения:
CalcSquareRoot.asm [4.05 KiB]
Скачиваний: 795
Вернуться наверх
   
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Сб апр 02, 2011 23:58:37 
Опытный кот
Аватар пользователя

Карма: 7
Рейтинг сообщений: 52
Зарегистрирован: Чт дек 31, 2009 19:27:45
Сообщений: 842
Откуда: Бровари, Україна
Рейтинг сообщения: 0
orinoko писал(а):
Есть реализации на Си, например:
Код:
unsigned short isqrt( unsigned long ul) {
  unsigned long sqr = 0;
  unsigned long temp;
  unsigned long mask = 0x40000000;
...
Какая приятная встреча :-) Где только не гулял этот исходник со времени опубликования в RU.ALGORITHMS (смотреть в самом низу страницы) в 1998 и в RU.EMBEDDED в 1999...
Там в RU.ALGORITHMS и объяснение есть. И другие варианты, но только для асма i386

_________________
Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.


Вернуться наверх
 
 Заголовок сообщения: Re: квадратный корень на асме AVR
СообщениеДобавлено: Вс апр 03, 2011 00:14:07 
Опытный кот
Аватар пользователя

Карма: 7
Рейтинг сообщений: 52
Зарегистрирован: Чт дек 31, 2009 19:27:45
Сообщений: 842
Откуда: Бровари, Україна
Рейтинг сообщения: 0
orinoko писал(а):
Но, как говорят, нет предела совершенству.
Так все ж четыре unsigned long лезут в регистры.
Четыре переменных по 4 байта, 16 регистров. Зачем lds/sts в цикле?

Как-то так можно
Код:
; Распределить по вкусу регистры
; temp0,temp1,temp2,temp3
; sqr0,sqr1,sqr2,sqr3
; mask0,mask1,mask2,mask3
; ul0,ul1,ul2,ul3 -- это аргумент функции


   lds   ul0, InputNum
   lds   ul1, InputNum+1
   lds   ul2, InputNum+2
   lds   ul3, InputNum+3

   clr   sqr0
   clr   sqr1
   movw   sqr2, sqr0
   movw   mask0, sqr0
   clr   mask2
   ldi   mask3, 0x40

loop:
   movw   temp0, sqr0
   movw   temp2, sqr2
   or   temp0, mask0
   or   temp1, mask1
   or   temp2, mask2
   or   temp3, mask3
   lsr   sqr3
   rol   sqr2
   rol   sqr1
   rol   sqr0
   cp   ul0, temp0
   cpc   ul1, temp1
   cpc   ul2, temp2
   cpc   ul3, temp3
   brcs skip
      or   sqr0, mask0
      or   sqr1, mask1
      or   sqr2, mask2
      or   sqr3, mask3
      sub   ul0, temp0
      sbc   ul1, temp1
      sbc   ul2, temp2
      sbc   ul3, temp3
skip:
   lsr   mask3
   rol   mask2
   rol   mask1
   rol   mask0
   lsr   mask3
   rol   mask2
   rol   mask1
   rol   mask0
   ; while( mask >>= 2 )
   mov   temp0, mask0
   or   temp0, mask1
   or   temp0, mask2
   or   temp0, mask3
   brne loop

   ; если mask0..mask3 разместить в r24,r25,r26,r27,
   ; то последние команды можно заменить на
   ; while( mask >>= 2 )
   sbiw   mask0, 0
   brne loop
   sbiw   mask2, 0
   brne loop

_________________
Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.


Вернуться наверх
 
Показать сообщения за:  Сортировать по:  Вернуться наверх
Форум закрыт Эта тема закрыта, Вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 40 ]  1,  

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


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

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


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB
Extended by Karma MOD © 2007—2012 m157y
Extended by Topic Tags MOD © 2012 m157y