Здравствуйте всем.
У меня возникла следующая задача. В цепи обратной связи мне надо произвести ряд арифметических преобразований, в том числе излечение корня и возведение в квадрат. Как это можно сделать максимально быстро на одном из микроконтроллеров AVR (извлечь корень и возвести в квадрат)?
Полная версия этой страницы: Извлечение корня и возведение в квадрат в AVR
#include <math.h>
корень - sqrt
квадрат x*x.
корень - sqrt
квадрат x*x.
Цитата(yanita @ Jul 14 2008, 14:06) 
Здравствуйте всем.
У меня возникла следующая задача. В цепи обратной связи мне надо произвести ряд арифметических преобразований, в том числе излечение корня и возведение в квадрат. Как это можно сделать максимально быстро на одном из микроконтроллеров AVR (извлечь корень и возвести в квадрат)?
У меня возникла следующая задача. В цепи обратной связи мне надо произвести ряд арифметических преобразований, в том числе излечение корня и возведение в квадрат. Как это можно сделать максимально быстро на одном из микроконтроллеров AVR (извлечь корень и возвести в квадрат)?
Ну квадрат - это просто умножить число на себя, не вижу проблем. Если у выбранного AVR нет аппаратного умножения - то традиционно, сложениями и сдвигами.
Корень - целочисленный - вычисляется вычитаниями и сдвигами, обсуждался много раз, искать надо.
Например, тут или тут
Цитата(yanita @ Jul 14 2008, 15:06)
У меня возникла следующая задача. В цепи обратной связи мне надо произвести ряд арифметических преобразований, в том числе излечение корня и возведение в квадрат. Как это можно сделать максимально быстро на одном из микроконтроллеров AVR (извлечь корень и возвести в квадрат)?
А числа целые или с плавающей точкой? Если с плавающей, то написать на Си, а если целые (или с фиксированной точкой), то искать "алгорим Ньютона" для извлечения корня.
Цитата(777777 @ Jul 14 2008, 14:36)
А числа целые или с плавающей точкой? Если с плавающей, то написать на Си, а если целые (или с фиксированной точкой), то искать "алгорим Ньютона" для извлечения корня.
У AVR нет аппаратного деления. Оно реализовано через вычитания и сдвиги. И корень можно вычислять через вычитания и сдвиги.Только при этом для деления число проходов цикла равно числу разрядов числа, а для корня - в два раза меньше. Правда, там ещё другие расходы есть (дополнительные операции ИЛИ, ещё один сдвиг), да и сдвиг на два у AVR реализуется как два сдвига на 1, итого вычисление корня по времени будет не в два раза быстрее программного деления, а близко к нему.
А "по Ньютону" нужно будет несколько делений, что будет в несколько раз дольше.
Обратите внимание на обсуждение по первой приведенной мной ссылке - там корень через вычитания/сдвиги оказался не медленнее "Ньютона" даже на 80386, который имеет аппаратное деление (впрочем, не слишком быстрое, но всё равно быстрее, чем программное через вычитания и сдвиги).
p.s. Александр Труш когда-то публиковал корень именно для AVR именно на асме. И где-то его недавно цитировали. Надо поискать.
Нашёл в своих завалах.
Ага, ещё и 24-битный аргумент. Видать, ему надо было именно столько (например, сумма не слишком болшьшого количества квадратов 10-битных отсчётов АЦП - 16 дико мало, 32 дико много).
Код
;*******************************************************************************
*********************
;*
;* Подпрограмма вычисления квадратного корня для 24-ти битного аргумента *
;* (c) 1998 Alexander Trush http://trush.da.ru trush@ropnet.ru 2:5020/392.40
;*
; Вы можете свободно использовать, распространять, модифицировать этот
; код до тех пор, пока вы указываете моё авторство и распространяете
; это требование. Кроме того, я хотел бы получать уведомление о
; применении этого кода по e-mail (trush@kbotd.ru).
sqrt24: ldi mask,1; Используем маску в регистре, т.к. команды EORI нет...
ldi count,12; Последний бит значения корня не требует специального
; подхода - есть запас от потери битов аж 4 бита
clr16 work_h, work_l
clr16 dist_h, dist_l; Очистка накопителя значения корня
sqrt24_1: cpi src_h, 64
cpc work_l, dist_l
cpc work_h, dist_h
brcs sqrt24_2
subi src_h, 64
sbc work_l, dist_l
sbc work_h, dist_h
sqrt24_2: rol dist_l
rol dist_h
eor dist_l, mask; Инверсия младшего бита значания корня,
; т.к. при заёме должны писать 0, и 1 при отсутствии
lsl src_l; Сдвиг аргумента на 2 бита
rol src_m; work_h:work_l:src_h:src_m:src_l <<= 2
rol src_h
rol work_l
rol work_h
lsl src_l
rol src_m
rol src_h
rol work_l
rol work_h
dec count; Получили ли все биты значения корня кроме последнего?..
brne sqrt24_1
cp dist_l, work_l
cpc dist_h, work_h
adc dist_l, src_m; Команды ADCI нет, а src_m точно здесь равен 0
adc dist_h, src_m
ret
;******************************************************************************
*********************
;*
;* Подпрограмма вычисления квадратного корня для 24-ти битного аргумента *
;* (c) 1998 Alexander Trush http://trush.da.ru trush@ropnet.ru 2:5020/392.40
;*
; Вы можете свободно использовать, распространять, модифицировать этот
; код до тех пор, пока вы указываете моё авторство и распространяете
; это требование. Кроме того, я хотел бы получать уведомление о
; применении этого кода по e-mail (trush@kbotd.ru).
sqrt24: ldi mask,1; Используем маску в регистре, т.к. команды EORI нет...
ldi count,12; Последний бит значения корня не требует специального
; подхода - есть запас от потери битов аж 4 бита
clr16 work_h, work_l
clr16 dist_h, dist_l; Очистка накопителя значения корня
sqrt24_1: cpi src_h, 64
cpc work_l, dist_l
cpc work_h, dist_h
brcs sqrt24_2
subi src_h, 64
sbc work_l, dist_l
sbc work_h, dist_h
sqrt24_2: rol dist_l
rol dist_h
eor dist_l, mask; Инверсия младшего бита значания корня,
; т.к. при заёме должны писать 0, и 1 при отсутствии
lsl src_l; Сдвиг аргумента на 2 бита
rol src_m; work_h:work_l:src_h:src_m:src_l <<= 2
rol src_h
rol work_l
rol work_h
lsl src_l
rol src_m
rol src_h
rol work_l
rol work_h
dec count; Получили ли все биты значения корня кроме последнего?..
brne sqrt24_1
cp dist_l, work_l
cpc dist_h, work_h
adc dist_l, src_m; Команды ADCI нет, а src_m точно здесь равен 0
adc dist_h, src_m
ret
;******************************************************************************
Цитата(ReAl @ Jul 14 2008, 15:59)
... Видать, ему надо было именно столько (например, сумма не слишком болшьшого количества квадратов 10-битных отсчётов АЦП - 16 дико мало, 32 дико много).
...
...
24р это стандартная длина мантиссы. ;О). Видно, поэтому.
Цитата(ReAl @ Jul 14 2008, 15:59)
Код
clr16 work_h, work_l
clr16 dist_h, dist_l; Очистка накопителя значения корня
clr16 dist_h, dist_l; Очистка накопителя значения корня
Еще бы выяснить, что такое clr16...
ну наверное это
clr work_h
clr work_l
clr work_h
clr work_l
Цитата(mse @ Jul 15 2008, 10:28)
24р это стандартная длина мантиссы. ;О). Видно, поэтому.
В этом случае, не сомневаюсь, он бы выложил и нормализацию, и работу с порядком.
Быстрый, но не очень точный способ извлечения корня:
Fast square root in C
Можно обойтись и без делений, если использовать аппроксимацию.
Для 0.5 <= x <= 1
sqrt(x) = 1.454895*x – 1.34491*x^2 + 1.106812*x^3 – 0.536499*x^4 + 0.1121216*x^5 + 0.2075806
Для значений x вне этого интервала, осуществляется масштабирование.
Fast square root in C
Можно обойтись и без делений, если использовать аппроксимацию.
Для 0.5 <= x <= 1
sqrt(x) = 1.454895*x – 1.34491*x^2 + 1.106812*x^3 – 0.536499*x^4 + 0.1121216*x^5 + 0.2075806
Для значений x вне этого интервала, осуществляется масштабирование.
Цитата(yanita @ Jul 14 2008, 15:06)
В цепи обратной связи мне надо произвести ряд арифметических преобразований, в том числе излечение корня и возведение в квадрат. Как это можно сделать максимально быстро на одном из микроконтроллеров AVR (извлечь корень и возвести в квадрат)?
Сделать быстро при таком варианте не получится. Мой опыт подсказывает, что надо поработать над алгоритмами регулирования.
Альтернативное предложение или идея.
Возможно системе регулирования для качественного регулирования можно сделать перерасчет входного сигнала под датчик, т.е. обратное преобразование. Тогда не требуется скоростная обработка в контуре регулирования.
Для индикации можно медленно пересчитать сигнал датчика по Вашим алгоритмам.
Неплохо бы уточнить, чем измеряем. Возможно, можно будет обойтись табличкой.
Цитата(SpyBot @ Jul 16 2008, 17:58)
Неплохо бы уточнить, чем измеряем. Возможно, можно будет обойтись табличкой.
Если озназначная функция и только одного параметра (датчика), то это хороший вариант.
Цитата(alexander55 @ Jul 16 2008, 12:42)
Сделать быстро при таком варианте не получится. Мой опыт подсказывает, что надо поработать над алгоритмами регулирования.
Началось за здравие, кончилось за упокой.
1. Алгоритмы регулирования - может быть FUZZY logic будет проще.
2. Не верю в то, что автору надо больше разрядов, чем в uint16_t. В таком случае посчитаем: умножение 16*16 =18 тактов. При поразрядном уравновешивании имеем 16*18 =288 тактов+пересылка и сравнение. Скажем, выйдет чуть более 300 тактов. Это почти 20 мкс на 16МГц. Это долго?!
Спасибо всем за помощь. Дело в том, что я не особо в микроконтроллерах разбираюсь. Структура измерительная, поэтому пожертвовать точностью никак не могу. Алгоритм измерения состоит из нескольких тактов и математической обработки, где и нужен корень. Математическая обработка не последующая, а в режиме измерения, поэтому обратная цепь становится инерцинной. Вот и хотелось бы добиться максимального быстродействия. Особенно интересует, насколько зависит быстродействие от алгоритмов того же деления и излечения корня. И еще какая разница, программировать контроллер на С или на асемблере, влияет ли на быстродействие?
Цитата(yanita @ Jul 17 2008, 17:48)
Вот и хотелось бы добиться максимального быстродействия. Особенно интересует, насколько зависит быстродействие от алгоритмов того же деления и излечения корня.
Если поставлено условие "добиться максимального быстродейтсвия", то не стоит ограничивать себя одним семейством МК. Нужно вначале просчитать какое быстродейтсвие требуется, и, взависимости от этого, выбрать МК.
Цитата
Особенно интересует, насколько зависит быстродействие от алгоритмов того же деления и излечения корня.
Если эти операции уже реализованы аппаратно, то быстродействие будет максимально возможным. В других случаях - сильно зависит.
Цитата
И еще какая разница, программировать контроллер на С или на асемблере,
На C писать проще, потому что C позволяет абстрагироваться от процессора, и заниматься непосредственно задачей. То есть не нужно вручную реализовавывать операции сложения, умножения деления требуемой разрядности, анализировать флаги и т.п, решать вопросы организации массивов и проч... Язык уже поддерживает все это в т.ч. и математику с плавающей точкой.
Цитата
влияет ли на быстродействие?
Влияет - на C в разы быстрее закончите проект, в разы проще будет добавить/изменить функциональность. По эффективности код может получиться лучше чем то, что небрежно нашкрябано на ассемблере (ведь чем больше проект тем небрежнее он будет писаться, а если делать весь проект на ассемблере, то писать придется много). С другой стороны на ассемблере можно максимально эффективно реализовать конкретный алгоритм. Если сбаллансировать между простой и эффективностью кода получится, что самый правильный подход - это написание всей программы на C, с последующей реализацией критических участков (от которых наиболее сильно зависит быстродействие) на ассемблере.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.