¿Por qué la eficiencia relativa de estas rutinas en Mathematica?

Question

Me sorprendió la diferencia de tiempo que Daniel Lichtblau pointed out de dos maneras de llegar a las diferencias entre el número de factores primos (PrimeOmega) y el número de distintos factores primos (PrimeNu) de un entero, n. Así que decidí analizarlo un poco más.

Las funciones g1 y g2 a continuación son pequeñas variaciones del ones Daniel utilizado, así como de otros tres. Todos devuelven la cantidad de enteros sin cuadrados desde 1 hasta n. Pero las diferencias son bastante dramáticas. ¿Alguien puede explicar las razones detrás de las diferencias? En particular, ¿por qué el Sum en g5 proporciona tal ventaja de velocidad?

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]}] 

La comparación:

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

Los resultados:

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

---

Editar:

Mysticial planteó la posibilidad de que este último ro utines estaban cosechando los beneficios de su orden, que algo de almacenamiento en caché puede haber estado sucediendo.

Así que vamos a ejecutar la comparación en el orden inverso:

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

resultados de las comparaciones Invertida:

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

veredicto: Una suposición razonable, pero no respaldadas por los datos.

Answer 1

ModebiusMu para números pequeños tiene un código de cribado rápido dedicado que, de hecho, abrevia la factorización real, solo cuenta a medida que encuentra factores. No agregará exponentes como PrimeOmega por lo que realmente tiene menos de una tarea. También puede cortocircuitar cada vez que detecta un factor primo con multiplicidad.

Creo que el corte es, coincidentemente, en algún lugar alrededor de 2^20. No tuve tiempo para probar, pero de hecho puede ser un poco más lento.

Eso responde para g4. Obviamente, g5 está usando astucia por parte del programador (nada malo con eso, por supuesto), de ahí la ganancia de velocidad.

En cuanto a g3, es en esencia una llamada a g4 en términos de código de implementación. El cuello de botella, en este caso, está preprocesando sobrecarga porque está implementado en mathematica en lugar de código C. Sospecho que esto sería menos visible si se usaran entradas más grandes, ya que en tales casos se gastaría más tiempo haciendo el trabajo real en lugar de en la parte superior del intérprete de Mathematica. Nuevamente, no he probado esto.