गणित में इन दिनचर्या की सापेक्ष दक्षता क्यों?

Question

मैं एक कारक अंतर से आश्चर्यचकित था कि डैनियल लिचब्लू pointed out प्रमुख कारकों (PrimeOmega) की संख्या और अलग-अलग प्राइम कारकों (PrimeNu) की संख्या के बीच अंतर को प्राप्त करने के दो तरीकों से आश्चर्यचकित था, एन। तो मैंने थोड़ा और आगे देखने का फैसला किया।

फ़ंक्शन g1 और g2 नीचे दिए गए ones डैनियल के साथ-साथ तीन अन्य उपयोग किए गए हैं। वे सभी 1 से एन तक स्क्वायर-फ्री पूर्णांक की संख्या वापस कर देते हैं। लेकिन मतभेद काफी नाटकीय हैं। क्या कोई मतभेदों के पीछे कारणों को समझा सकता है। विशेष रूप से, g5 में इतनी गति का लाभ क्यों प्रदान करता है?

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

तुलना:

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

परिणाम:

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

---

संपादित करें:

Mysticial संभावना उठाया कि बाद ro यूटिन अपने आदेश के लाभ उठा रहे थे - कि कुछ कैशिंग चल रही हो सकती है।

तो चलो उलटे क्रम में तुलना चलाते हैं: उलट तुलना की

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

परिणाम:

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

फैसले: एक उचित अनुमान है, लेकिन डेटा द्वारा समर्थित नहीं।

Answer 1

छोटी संख्याओं के लिए मोडबियसमु कुछ समर्पित तेज़ सिविंग कोड है जो असल में शॉर्टकट वास्तविक कारककरण है, बस इसे कारकों के रूप में गिनती है। यह प्राइम ओमेगा जैसे घाटियों को नहीं जोड़ देगा, इसलिए इसमें वास्तव में एक कार्य कम है। जब भी यह बहुतायत के साथ एक प्रमुख कारक का पता लगाता है तो यह शॉर्ट सर्किट भी कर सकता है।

मेरा मानना ​​है कि कटऑफ, संयोग से, लगभग 2^20 के आसपास है। परीक्षण करने का समय नहीं था लेकिन यह वास्तव में थोड़ा अधिक धीमा हो सकता है।

जी 4 के लिए उत्तर। जाहिर है जी 5 प्रोग्रामर के हिस्से पर चतुरता का उपयोग कर रहा है (निश्चित रूप से कुछ भी गलत नहीं है), इसलिए गति लाभ।

जी 3 के लिए, यह संक्षेप में कार्यान्वयन कोड के मामले में जी 4 के लिए एक कॉल है। बाधा, इस मामले में, preprocessing ओवरहेड है क्योंकि यह सी कोड के बजाय गणित में लागू किया गया है। मुझे संदेह है कि अगर बड़े इनपुट का उपयोग किया जाता है तो यह कम दिखाई देगा, क्योंकि ऐसे मामलों में गणित दुभाषिया ओवरहेड के बजाय वास्तविक काम करने में अधिक समय व्यतीत किया जाएगा। फिर से, मैंने इसका परीक्षण नहीं किया है।