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?
Ich habe dasselbe noch mit einem Array of Byte versucht - dieses war noch langsamer als die Stringrechnung.
Ich werde auf Java umsteigen, da sind große Int's gang und gebe
