Pourquoi ces deux méthodes d'échantillonnage sont-elles aussi longues?

Question

J'ai donc implémenté mon propre petit algorithme RSA et j'ai écrit une fonction pour trouver de grands nombres premiers.
J'ai d'abord écrit une fonction prime? qui teste la primalité, puis j'ai écrit deux versions d'une fonction de recherche principale. Dans la première version, je viens de tester BigIntegers aléatoire jusqu'à ce que je frappe un premier. Dans la deuxième version, j'échantais un BigInteger aléatoire, puis je l'incrémente jusqu'à ce que je trouve un premier.

(defn resampling [] 
    (let [rnd (Random.)] 
    (->> (repeatedly #(BigInteger. 512 rnd)) 
     (take-while (comp not prime?)) 
     (count)))) 

(defn incrementing [] 
    (->> (BigInteger. 512 (Random.)) 
     (iterate inc) 
     (take-while (comp not prime?)) 
     (count))) 

(let [n 100] 
    {:resampling (/ (reduce + (repeatedly n resampling)) n) 
    :incrementing (/ (reduce + (repeatedly n incrementing)) n)}) 

exécution de ce code a produit les deux moyennes de 332,41 pour la fonction de ré-échantillonnage et 310,74 pour la fonction incrémentiel.
Maintenant, le premier numéro me semble tout à fait logique. Le prime number theorem indique que le premier n est d'environ n*ln(n) (où ln est le logarithme naturel). Ainsi, la distance entre nombres premiers adjacents est approximativement de n*ln(n) - (n-1)*ln(n-1) ≈ (n - (n - 1))*ln(n) = ln(n) (pour de grandes valeurs de nln(n) ≈ ln(n - 1)). Puisque j'échantillonne des entiers de 512 bits, je m'attendrais à ce que la distance entre les nombres premiers soit au voisinage de ln(2^512) = 354.89. Par conséquent, l'échantillonnage aléatoire devrait prendre environ 354,89 tentatives en moyenne avant d'atteindre un taux préférentiel, ce qui ressort assez bien.
Le puzzle pour moi est pourquoi la fonction d'incrémentation prend à peu près autant de pas. Si j'imagine lancer une fléchette à une grille où les nombres premiers sont espacés de 355 unités, cela ne devrait prendre qu'environ la moitié de beaucoup de pas en moyenne pour atteindre le prochain plus haut, puisque je frapperais en moyenne entre deux nombres premiers.

(Le code de prime? est un peu longue. Vous pouvez jeter un coup d'oeil here.)

Answer 1

Vous supposez que les nombres premiers sont également distribués, qui ne semble pas être le cas.

Considérons le scénario possible suivant: Si les nombres premiers seraient toujours venir en paires par exemple 10...01 et 10...03 alors la paire suivante viendrait 2*ln(n). Pour l'algorithme d'échantillonnage, cette distribution ne fait aucune différence, mais pour l'algorithme incrémentant, la probabilité de commencer à l'intérieur d'une telle paire est presque 0, donc cela signifie qu'il faudrait parcourir la moitié de la grande distance en moyenne, ln(n).

En résumé: pour estimer correctement le comportement de l'algorithme incrémental, il ne suffit pas de connaître la distance moyenne entre les nombres premiers.