⁴³Wodurch zwar mehr Schritte als beim euklidischen Algorithmus nötig sind, sich die Ausführungszeit (durch Vermeidung von Langzahldivisionen) aber typischerweise verringert. Die Komplexität des Algorithmus bleibt unverändert quadratisch, kann aber durch eine systolische Implementierung nach [BK83, Jeb93, BB87] sogar bis auf $O (n)$ reduziert werden.