Fast computation of continued fraction expansions. (Q2548173)

Unter Verwendung der in vorstehend referierter Arbeit [Verf. und \textit{V. Strassen}, Computing 7, 281--292 (1971; Zbl 0223.68007)] entwickelten schnellen Multiplikation wird ein Algorithmus angegeben, der den ggT zu ganzen Zahlen \(u,v>0\) und den regelmäß\ igen Kettenbruch zu \(u/v\) in \(O(n (\log n)^2 \log \log n)\) elementaren Schritten berechnet, wenn \(u,v\) als höchstens \(n\)-stellige Dualzahlen gegeben sind. Diese Methode beruht auf dem Begriff des ``Kettenbruchs zu einem Intervall'' und der Idee, die Berechnung zu einem Intervall der Länge \(\delta\) rekursiv jeweils auf die Kettenbruchberechnungen zu zwei Intervallen der ungefähren Länge \(\sqrt\delta\) zurückzuführen.