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!
Welche Datenstrukturen wären das?
Wie soll das denn funktionieren ohne einen unbegrenzten Datentyp wie String oder BigInt?:
Gehe zurück zur Seite eins des Threads und schaue dir den zweiten Post (ja, den direkt unter deinen Eröffnungspost) an.
Hier hat Dejan Vu dir zwei Datentypen/-strukturen verlinkt.
Einfach mal anschauen, runterladen und ausprobieren.