Implementazione esponenziale rapida

Question

Qualcuno potrebbe indicare un sito in cui posso trovare un algoritmo per calcolare in modo efficiente l'espiazione di interi con grandi potenze usando C #?

ad es. Voglio calcolare 2 ^ 60000 o 3 ^ 12345

Answer 1

A meno che non si tratti di compiti a casa, probabilmente non vorrai realizzare la tua implementazione di esponenziale di precisione arbitraria. Il calcolo di grandi esponenti del tipo che descrivi è complicato - prestazioni a parte.

Consiglierei di utilizzare una delle librerie aritmetiche di precisione arbitraria esistenti, come GMP - la maggior parte dei quali ha librerie per accedervi da C #.

F # ha il supporto per l'aritmetica di precisione arbitraria usando la classe BigInt (a cui puoi anche accedere da C # se importi l'assembly in cui si trova). Tuttavia, non so quanto sia ottimizzata l'espiazione di BigInt.

Se stai semplicemente cercando di conoscere algoritmi efficienti per l'espiazione, potresti voler esaminare la Square -And-Moltiplica algoritmo per esponenziale.

Answer 2

L'esponenziazione di numeri interi può essere effettivamente calcolata utilizzando un metodo noto come "esponenziazione mediante quadratura" link .

Questo metodo può anche essere utilizzato per calcolare l'esponenziale modulare link , che viene utilizzato in alcuni metodi di crittografia asimmetrica come RSA.

Answer 3

Dai un'occhiata: IntX per lavorare con LARGE interi. Potrebbe essere necessario scrivere la propria implementazione del potere, ma poiché la moltiplicazione è supportata, questo non dovrebbe essere così difficile.

Modifica di 280Z28: Un'altra implementazione che include test rapidi di Pow, ModPow e primalità è questa Implementazione di BigInteger (Code Project), che ho usato in passato su problemi di Project Euler, anche se ora lavoro con .NET 4.0 e uso implementazione System.Numerics.BigInteger .