Fortran 95: super grands nombres pour le test principal

Question

Je suis assez nouveau à Fortran, comme dans l'apprentissage commencé il y a 2 jours nouveau. J'ai commencé à apprendre Fortran parce que je commençais à avoir des nombres premiers, et j'ai écrit un programme en python qui était si rapide, il pouvait déterminer que 123098237 était un nombre premier en 0.1 secondes. Impressionnant, je sais. Ce qui n'est pas impressionnant, c'est quand j'essaie de savoir si (2^127) -1 ou 170141183460469231731687303715884105727 (c'est, soit dit en passant) est un nombre premier. Le programme a duré tellement longtemps que j'ai fini par devoir l'arrêter. Donc, j'ai commencé à chercher des langages plus rapides pour l'écrire, donc j'ai écrit le programme en C. C'était plus rapide, mais le problème des super nombres premiers est entré en jeu. J'allais voir s'il y avait une solution mais ensuite j'ai entendu à travers la vigne que, si votre programmation avec des nombres, Fortran est le moyen le plus rapide et le meilleur à faire. Je me souviens vaguement des vieux livres de Fortran 77 de mon beau-père, mais ils étaient fondamentalement inutiles pour moi, parce qu'ils parlaient de travailler avec des cartes perforées. Donc, je suis allé en ligne, je me suis débrouillé pour Ubuntu 12.04 x86, j'ai eu un couple de fichiers PDF, et j'ai commencé à apprendre. Avant que vous le sachiez j'ai fait un programme qui a reçu l'entrée et a examiné pour la primalité, et a fonctionné! Mais, le même vieux problème est apparu, le nombre était trop grand. Et alors, comment gérer de gros nombres comme celui-ci avec Fortran?

Answer 1

Fortran, à l'instar de nombreux autres langages compilés, ne fournit pas de tels entiers ou opérations sur ces outils. Un compilateur à jour devrait fournir un nombre entier avec 18 chiffres décimaux, mais pas plus que cela.

Si vous souhaitez programmer en Fortran, types de données et les opérations de ces grands entiers utiliser votre moteur de recherche préféré sur des termes tels que Fortran multiples précision. Vous pouvez même rechercher ici SO sur les questions et réponses pertinentes.

Si vous voulez étudier les mathématiques de tels grands entiers coller avec Python; vous aurez du mal à écrire vous-même un logiciel qui correspond à sa vitesse de fonctionnement sur l'arithmétique de précision multiple. Une des raisons pour lesquelles Python prend beaucoup de temps pour déterminer la primalité d'un grand nombre est qu'il faut un programme, un programme écrit dans n'importe quelle langue, un long moment pour déterminer la primalité d'un grand nombre. Si vous creusez, vous trouverez probablement que les routines Python pertinentes appellent du code écrit en C ou quelque chose de similaire. Enquêter, si vous le souhaitez, sur le sujet de la complexité de calcul de la primalité . Je ne dis pas que vous ne serez pas capable d'écrire du code pour surpasser les intrinsèques de Python, juste que vous trouverez cela un défi.

Answer 2

La plupart des langages fournissent certains types intrinsèques standards qui sont parfaitement adaptés à la résolution de problèmes scientifiques et techniques standard. Vous n'avez pas besoin de chiffres à 80 chiffres pour calculer l'épaisseur d'une poutre de pont ou planifier une orbite de vaisseau spatial. Il serait difficile de mesurer à cette précision. En Fortran, si vous voulez faire des calculs de précision supplémentaires (par exemple, pour la théorie des nombres), vous devez regarder les bibliothèques qui augmentent la langue, par exemple, mpfun90 à http://crd-legacy.lbl.gov/~dhbailey/mpdist/ ou fmlib à http://myweb.lmu.edu/dmsmith/fmlib.html

Answer 3

Je suppose que votre algorithme est division de première instance. Si c'est vrai, vous avez besoin d'un meilleur algorithme; la langue d'implémentation n'aura pas d'importance.

Le pseudocode pour le test de primalité de Miller-Rabin est présenté ci-dessous.Il est probabiliste, mais vous pouvez réduire le risque d'erreur en augmentant le paramètre k, jusqu'à un maximum d'environ k = 25:

function isPrime(n, k=5) 
    if n < 2 then return False 
    for p in [2,3,5,7,11,13,17,19,23,29] 
     if n % p == 0 then return n == p 
    s, d = 0, n-1 
    while d % 2 == 0 
     s, d = s+1, d/2 
    for i from 0 to k 
     x = powerMod(randint(2, n-1), d, n) 
     if x == 1 or x == n-1 then next i 
     for r from 1 to s 
      x = (x * x) % n 
      if x == 1 then return False 
      if x == n-1 then next i 
     return False 
    return True 

Je vais laisser à vous de traduire à Fortran ou une autre langue; si vous programmez en C, il existe une bibliothèque appelée GMP fréquemment utilisée pour gérer de très grands nombres, et la fonction ci-dessus est intégrée à cette bibliothèque. C'est très rapide les nombres pairs qui sont des centaines de chiffres doivent être classés comme premiers ou composés presque instantanément.

Si vous voulez être certain de la primalité d'un nombre, il existe d'autres algorithmes qui peuvent réellement fournir une preuve de primalité. Mais ils sont beaucoup plus compliqués et beaucoup plus lents.

Vous pouvez être intéressé par l'essai Programming with Prime Numbers sur mon blog.