sqrt() für Integer

Vielleicht postest du ja auch mal die URL des dazu gehörigen Threads?

Achwas Raketenwissenschaft. Geh den Code einfach mal durch.

Beispiel n = 25, 1 Byte

root = 0
rem = 25
place = 0x40 => 64, na dämmerts, genau 8²

while (place > remainder)
  place = place >> 2;
Es wird die Quadratzahl gesucht, die kleiner n ist und ein Quadrat von 
2^k, 64 >> 2 = 16 = 4²

place = 16

    while (place)
solange place nicht Null (in richtigen Programmiersprachen würde man 
schreiben while place > 0)

    if (remainder >= root + place)
25 >= 0 + 16, passt, also

            remainder = remainder - root - place;
25 - 0 - 16 = 9
            root = root + (place << 1);
0 + (16 << 1) = 32, klingt komisch ist aber erstmal so

und immer
        root = root >> 1;
32 >> 1 = 16, wieder zurück
        place = place >> 2;
place = 4 = 2², und die nächstkleinere Quadratzahl probieren

    if (remainder >= root + place)
9 >= 16 + 4, passt nicht, also weiter mit

        root = root >> 1;
16 >> 1 = 8
        place = place >> 2;
place = 1 = 1²

    if (remainder >= root + place)
9 >= 8 + 1, passt, also

            remainder = remainder - root - place;
9 - 8 - 1 = 0, nu gugge, es bleibt kein Rest, klar 25 = 5²
            root = root + (place << 1);
8 + (1 << 1) = 10

und wieder
        root = root >> 1;
10 >> 1 = 5, sieht schonmal gut aus
        place = place >> 2;
place = 0, damit simmer fertisch.


es bleibt
root = 5 = sqrt(25)
rem = 0

Und für große Zahlen geht das genauso, nur langweiliger.

Diese Funktion versteht jeder:

1

uint32_t isqrt32a(uint32_t n) {

2

  uint32_t root = 0;

3

4

  for(uint32_t bitval=0x8000; bitval; bitval>>=1) {

5

    if ((root + bitval) * (root + bitval) <= n)

6

      root += bitval;

7

  }

8

  return root;

9

}

Wegen der Multiplikation in jedem Schleifendurchlauf ist diese Methode
für CPUs ohne Multiplizierer nicht so gut geeignet.

Die folgende Funktion tut genau dasselbe:

1

uint32_t isqrt32b(uint32_t n) {

2

  uint32_t root = 0, remainder = n;

3

4

  for(uint32_t bitval=0x8000; bitval; bitval>>=1) {

5

    uint32_t deltaremainder = 2 * root * bitval + bitval * bitval;

6

    if (remainder >= deltaremainder) {

7

      remainder -= deltaremainder;

8

      root += bitval;

9

    }

10

  }

11

  return root;

12

}

Im Gegensatz zu isqrt32a wird hier nur mit Zweierpotenzen multipliziert.

Erklärung:

Statt in jedem Schleifendurchlauf das Quadrat des aktuellen Kandidaten
für root zu berechnen (was eine Multiplikation erfordert), wird der Rest
(remainder), d.h. die Differenz zwischen dem Radikanden und dem Quadrat
des Kandidaten berechnet. Tut man dies rekursiv (d.h. unter Verwendung
des jeweils letzten Werts von remainder), ist bei jeder verbleibenden
Multiplikation mindestens einer der beiden Faktoren eine Zweierpotenz.

Die (nicht sehr komplizierte) Mathematik dahinter:

1

  remainder     = n - root**2

2

  root'         = root + bitval

3

  remainder'    = n - root'**2

4

                = n - (root + bitval)**2

5

                = n - root**2 - 2*root*bitval - bitval**2

6

  deltareminder = remainder - remainder'

7

                = 2*root*bitval + bitval**2

8

  remainder'    = remainder - deltaremainder

remainder' darf dabei nicht negativ, d.h deltareminder nicht größer als
remainder werden, sonst war root' zu groß. Das wird in der If-Abfrage
abgeprüft, ggf. wird der alte Wert von root beibehalten.

Man kann nun isqrt32b noch etwas optimieren, so dass

- alle Multiplikationen durch Shifts ersetzt werden,

- alle Shifts eine konstante Shift-Weite ≤ 2 haben (gut für CPUs ohne
  Barrel-Shifter) und

- die ersten paar Schleifendurchläufe, in denen die If-Bedingung
  unabhängig von root falsch ist, in eine eigene, etwas vereinfachte
  Schleife ausgelagert werden.

Heraus kommt die vom TE gepostete Variante.

https://www.oldcalculatormuseum.com/fridenstw.html
ein paar Fotos des beschriebenen elektromechanischen Rechners, 
Leistenbruch-hervorrufendes Gewicht, die Lampen im Raum werden dunkler 
dazu das Geräusch
"punch-punch-cachunk, punch-punch-cachunk-DING, 
punch-punch-DING-clang-clang"
sehr schön formuliert. Erinnert mich an meinen LO-15 Fernschreiber.

Signalverarbeiter schrieb:
> Wird das eigentlich noch gelehrt? Oder ist es dem G8 zum Opfer gefallen?

Wenn überhaupt, wird es nur noch als Kuriosität gelehrt.

Wer braucht das schon noch? Früher hatte man Tafelwerke und 
Rechenschieber (schon da musste man das nicht mehr schriftlich können), 
heute gibt's Taschenrechner.

Einen Sinus oder Tangens kann man auch nicht „schriftlich“ ausrechnen.