Algorithme pour effectuer des opérations arithmétiques sur de très grands nombres

J’ai besoin d’un algorithme pour effectuer des opérations arithmétiques sur de grands nombres (qui sont bien au-dessus de la plage de float, double int ou de tout autre type de données). Je suis obligé d’écrire le code en C. J’ai essayé de regarder ici: Knuth, Donald, L’art de la programmation informatique, ISBN 0-201-89684-2, Volume 2: Algorithmes séminumériques, Section 4.3.1: Les algorithmes classiques mais ne pouvait pas le supporter. J’ai juste besoin de l’algorithme, pas du code.

    De plus, pour autant que je sache, vous n’obtiendrez pas beaucoup mieux que le simple algorithme linéaire O (n), c’est-à-dire, ajoutez simplement chiffre par chiffre. De toute façon, vous devez probablement lire l’intégralité de l’entrée, elle est donc au moins linéaire. Vous pourrez peut-être faire diverses astuces pour obtenir la constante.

    Votre problème principal sera la multiplication, en raison de la nature quadratique de l’algorithme de base de la multiplication longue. Vous voudrez peut-être envisager l’une des méthodes beaucoup plus rapides données ici . La méthode Karatsuba est un peu délicate à mettre en œuvre mais c’est probablement l’algorithme non-sortingvial le plus simple qui vous donnera un gain. Sinon, vous devrez vous pencher un peu plus sur les méthodes de transformation rapide de Fourier, telles que l’ algorithme de Schönhage-Strassen ou celui de Fürer .

    Voir aussi la notation Big O.

    Je pense que l’algorithme de Karatsuba est préférable pour effectuer des opérations arithmétiques sur les grands nombres. Pour n suffisamment grand, une autre généralisation, l’algorithme de Schönhage – Strassen, est encore plus rapide. Vous pouvez rechercher l’algorithme dans Karatsuba ou Karatsuba_Multiplication

    Il n’y a pas d’algorithme pour effectuer des opérations arithmétiques sur de très grands nombres. Les opérations arithmétiques restnt les mêmes. Ce dont vous avez besoin est en classe comme http://www.codeproject.com/KB/cs/BigInt.aspx

    Le livre Nombres premiers et méthodes informatiques de factorisation de Riesel comprend un appendice avec un code facile à lire pour l’arithmétique à précision multiple.

    Pour les algorithmes seulement, lisez Knuth vol 2 ou Crandall et Pomerance. Pour le codage, je suggérerais de commencer par utiliser les algorithmes évidents avant de passer aux transformations de Karatsuba ou de Fourier.