Da Du eine exakte Lösung möchtest, bringt Extended gar nichts. Das wusstest Du vorher, hast es auch bewiesen und hast es nun belegt.
Der Grund für deine langsame Implementierung liegt zum Einen in der Forderung nach Exaktheit und zum Anderen an der Umsetzung mittels Strings. Alternativen, d.h. Datenstrukturen, die beliebig lange Zahlen repräsentieren, wurden Dir hier auch genannt.
Also: Umsetzen!
