Schnelle Implementierung Potenzierung

Question

Könnte jemand bitte eine Website verweisen, wo ich einen Algorithmus effizient finden zu integer Potenzierung zu große Leistungen mit C # berechnen?

zB. Ich möchte 2 ^ 60000 oder 3 ^ 12345 berechnen

Answer 1

Wenn diese Hausaufgaben sind, werden Sie wahrscheinlich nicht wollen, eine eigene Implementierung von beliebiger Genauigkeit Potenzierung rollen. Die Berechnung großen Exponenten des Typs Sie beschreiben, ist kompliziert -. Leistung beiseite

Ich würde empfehlen, einen des bestehenden beliebiger Genauigkeit arithmetische Bibliotheken, wie GMP - von denen die meisten Bibliotheken auf sie zuzugreifen von C #.

F # hat die Unterstützung für beliebig genaue Arithmetik der BigInt-Klasse (die man auch von C # zugreifen können, wenn Sie die Montage es in importieren). Aber ich weiß nicht, wie optimiertem BigInt Potenzierung ist.

Wenn Sie einfach sind versuchen, über effiziente Algorithmen für Potenzierung zu lernen, können Sie in den Platz suchen möchten -and-Multiply Algorithmus zur Potenzierung.

Answer 2

Integer Potenzierung kann effektiv ein Verfahren bekannt, wie berechnet werden "Binäre Exponentiation" Link .

Dieses Verfahren kann auch die modulare Potenzierung Link zur Berechnung verwendet werden, die in verwendet wird, einige asymmetrische Verschlüsselungsverfahren wie RSA.

Answer 3

Check this out: IntX mit großen ganzen Zahlen arbeiten. Möglicherweise müssen Sie Ihre eigene Implementierung der Macht schreiben, aber da die Multiplikation unterstützt wird, soll dies nicht so schwer sein.

Bearbeiten von 280Z28: Eine weitere Implementierung, die eine schnelle Pow umfasst, ModPow und Primtests ist diese BigInteger Implementierung (Code Project), die ich auf Projekt Euler Probleme in der Vergangenheit verwendet haben - obwohl ich jetzt mit .NET 4.0 und verwenden seine System.Numerics.BigInteger Umsetzung.