вычисление корня, быстрое вычисление приближённого корня Опции

[haki]

ATMega8515. Не имеет FPU. ИМС во многом минималистична. Но если ей необходимо вычислять периоды шага для шагового двигателя, встаёт вопрос быстрого вычисления корня для формул разгона и торможения. Собственно сам вопрос заключается в том, как быстро вычислять корни используя лишь сложение, вычитание и умножение. При этом желательно оставаться в области целых чисел эмулирующих псевдо натуральные с фиксированной точкой для простоты.
Примерная формуля выглядит следующим образом: N = x*sqrt(y). это сильно упрощённая формула для наглядности.

[Maverick]

ATMega8515. Не имеет FPU. ИМС во многом минималистична. Но если ей необходимо вычислять периоды шага для шагового двигателя, встаёт вопрос быстрого вычисления корня для формул разгона и торможения. Собственно сам вопрос заключается в том, как быстро вычислять корни используя лишь сложение, вычитание и умножение. При этом желательно оставаться в области целых чисел эмулирующих псевдо натуральные с фиксированной точкой для простоты.
Примерная формуля выглядит следующим образом: N = x*sqrt(y). это сильно упрощённая формула для наглядности.

Уоррен "Алгоритмические трюки для программистов", там есть "аппаратный" алгоритм на Си:

Код

unsigned x, y;
unsigned sqrt(){
  y = 0;
  unsigned m = 1 << 30;    
  while( m ){
    unsigned b =  y | m;
    y >>= 1;
    if( x >= b ){
        x -= b;
        y |= m;
    }            
    m >>= 2;
  }    
}

[kovigor]

Примерная формуля выглядит следующим образом: N = x*sqrt(y). это сильно упрощённая формула для наглядности.

Можно использовать, например, табличный метод, или алгоритм "цифра за цифрой" (CORDIC).
А почему вы на Си не пишете ?

[Maverick]

...необходимо вычислять периоды шага для шагового двигателя...

сходные задачи решаем...

[haki]

Можно использовать, например, табличный метод, или алгоритм "цифра за цифрой" (CORDIC).
А почему вы на Си не пишете ?

Я не говорил про язык, тут речь про алгоритм. Таблицы не уместны. Посмотрите сколько памяти у МК, еле хватает на переменные.

[Сергей Борщ]

Попробуйте подойти к проблеме с другой стороны:
http://www.embedded.com/design/mcus-proces...es-in-real-time
И чтож за монстра вы строите, что вам не хватает памяти 8515 ни на таблицы, ни на переменные для одного шаговичка? Может в консерватории что-то не так?

исправил ссылку

[-SANYCH-]

Вот еще примеры вычисления квадратного корня:
http://algolist.manual.ru/maths/count_fast/intsqrt.php

[Tanya]

Таблицы не уместны. Посмотрите сколько памяти у МК, еле хватает на переменные.

Мне вот как-то хватает. Это ведь не переменные, а постоянные. Масштабируемые.

[Iptash]

Без sqrt разве нельзя обойтись?. Я управление шаговиком сделал на младшей CPLD MAX II в микрошаговом режиме с разгоном/торможением, все очень
реально работало и еще место на кристале осталось.

[Corvus]

AVR 446 в помощь. Даже исходники есть.
http://www.atmel.com/images/doc8017.pdf

[zöner]

может, как-нибудь преобразовать расчеты, и вместо корня вычислять квадрат ?
N2 = x* x * y

Сообщение отредактировал zöner - Jul 1 2013, 10:48

[Александр77]

Если достаточно найти целую часть, то можно воспользоваться методом из википедии

Арифметическое извлечение квадратного корня

Для квадратов чисел верны следующие равенства:
1 = 1^2
1 + 3 = 2^2
1 + 3 + 5 = 3^2
\sum^n_{k=1}{(2k-1)}=n^2
и так далее.

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

9-1=8
8-3=5
5-5=0

Выполнено 3 действия, квадратный корень числа 9 равен 3.