Ein Algorithmus zur Berechnung der größten Ganzen aus Wurzel d (Q796563)

Verff. beweisen den folgenden Algorithmus für die Bestimmung des größten Ganzen [\(\sqrt{d}]\) für \(d\in {\mathbb{N}}:\) Ist \(a_ 0=[{1\over2}(d+1)]\) und \(a_{n+1}=[{1\over2}(a_ n+[d/a_ n])],\) so wird \(a_ n=[\sqrt{d}],\) sobald \(a_{n+1}\geq a_ n\); für das kleinste m mit \(a_ m=[\sqrt{d}]\) gilt: \(-1+\log_ 2\sqrt{d}<m\leq \log_ 2(d-1).\)