Perché l'efficienza relativa di queste routine in Mathematica?

Question

Sono stato sorpreso da una differenza di orario che Daniel Lichtblau pointed out in due modi per ottenere le differenze tra il numero di fattori primi (PrimeOmega) e il numero di fattori primi distinti (PrimeNu) di un numero intero, n. Così ho deciso di esaminarlo un po 'oltre.

Le funzioni g1 e g2 di seguito sono piccole variazioni del numero di telefono ones utilizzato da Daniel e da altri tre. Restituiscono tutti il ​​numero di numeri interi quadrati liberi da 1 a n. Ma le differenze sono piuttosto drammatiche. Qualcuno può spiegare le ragioni dietro le differenze. In particolare, perché lo Sum in g5 offre un tale vantaggio di velocità?

g1[n_] := Count[PrimeOmega[Range[n]] - PrimeNu[Range[n]], 0] 

g2[n_] := Count[With[{fax = FactorInteger[#]}, 
Total[fax[[All, 2]]] - Length[fax]] & /@ Range[n], 0] 

g3[n_] := Count[SquareFreeQ/@ Range[n], True] 

(* g3[n_] := Count[SquareFreeQ[#] & /@ Range[n], True] Mr.Wizard's suggestion 
    incorporated above. Better written but no significant increase in speed. *) 

g4[n_] := n - Count[MoebiusMu[Range[n]], 0] 

g5[n_] := Sum[MoebiusMu[d]*Floor[(n - 1)/d^2], {d, 1, Sqrt[n - 1]}] 

Il confronto:

n = 2^20; 
Timing[g1[n]] 
Timing[g2[n]] 
Timing[g3[n]] 
Timing[g4[n]] 
Timing[g5[n]] 

I risultati:

{44.5867, 637461} 
{11.4228, 637461} 
{4.43416, 637461} 
{1.00392, 637461} 
{0.004478, 637461} 

---

Edit:

Mysticial sollevato la possibilità che quest'ultimo ro utines stava raccogliendo i frutti del suo ordine - che potrebbe essersi verificato qualche caching.

Quindi cerchiamo di eseguire il confronto in ordine inverso:

n = 2^20; 
Timing[g5[n]] 
Timing[g4[n]] 
Timing[g3[n]] 
Timing[g2[n]] 
Timing[g1[n]] 

I risultati del confronto invertiti:

{0.003755, 637461} 
{0.978053, 637461} 
{4.59551, 637461} 
{11.2047, 637461} 
{44.5979, 637461} 

Verdetto: Una stima ragionevole, ma non supportate dai dati.

Answer 1

ModebiusMu per numeri piccoli ha un codice di setacciamento rapido dedicato che in effetti scorcia la fattorizzazione effettiva, contando solo quando trova i fattori. Non aggiungerà esponenti come PrimeOmega, quindi ha davvero meno compiti. Inoltre può cortocircuitare ogni volta che rileva un fattore primo con molteplicità.

Credo che il limite sia, per coincidenza, da qualche parte intorno al 2^20. Non ha avuto il tempo di testare, ma potrebbe essere più lento un po 'più alto.

Risposte per g4. Ovviamente g5 sta usando l'intelligenza da parte del programmatore (non c'è niente di sbagliato in questo ovviamente), quindi il guadagno di velocità.

Per quanto riguarda g3, è in sostanza una chiamata a g4 in termini di codice di implementazione. Il collo di bottiglia, in questo caso, è un overhead di pre-elaborazione perché è implementato in matematica anziché in codice C. Sospetto che ciò sarebbe meno visibile se venissero utilizzati input più ampi, poiché in tali casi si impiegherebbe più tempo a fare il vero lavoro piuttosto che nel sovraccarico dell'interprete Mathematica. Ancora una volta, non ho provato questo.