GCC f. AVR: SQRT von _Fract

Hier ein Algorithmus der aus einer Integer die Wurzel zieht. Er ist 
schnell (kleiner 200 Takte) und kurz (ca. 100 Bytes).


Quelle: 
https://stackoverflow.com/questions/1100090/looking-for-an-efficient-integer-square-root-algorithm-for-arm-thumb2

1

uint16_t SQRT16(uint16_t op)

2

{

3

  uint16_t res = 0;

4

  uint16_t one = 1 << 14; // The second-to-top bit is set: 1L<<30 for long

5

6

  // "one" starts at the highest power of four <= the argument.

7

  while (one > op)

8

  {

9

    one >>= 2;

10

  }

11

12

  while (one != 0)

13

  {

14

    if (op >= res + one)

15

    {

16

      op -= res + one;

17

      res += 2 * one;

18

    }

19

    res >>= 1;

20

    one >>= 2;

21

  }

22

  return (res);

23

}

Jim M. schrieb:
> Thomas schrieb:
>> Hier ein Algorithmus der aus einer Integer die Wurzel zieht
>
> Dann hat man aber immer noch das Problem aus dem _Fract (16-bittig
> Fließkomma) einen vernüntigen Integer zu machen. Wäre das trivial, hätte
> der OP sicher nicht gefragt.

Das ist trivial. Nur Shiften. _Fract-Vaiable z. B. mit  2^14 
multiplizieren, obigen Algorithnus ausführen, Ergebnis durch 2^7 
dividieren.

Beispiel:

1

0,25 * 2^14 -> 4096

2

sqrt(4096)  -> 64

3

64 / 2^7    -> 0,5