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

[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;
  }    
}