🚏 🕵🏿 📱 विकिपीडिया की तुलना में अरबों सरल संख्याओं को तेज़ी से भेजना 🌕 🍠 👖

( चित्र स्रोत )

यह सर्वविदित है कि Sieve of Eratosthenes (RE) सबसे पुराने एल्गोरिदम में से एक है जो कंप्यूटर के आविष्कार से बहुत पहले दिखाई दिया था। इसलिए, आप सोच सकते हैं कि सदियों से इस एल्गोरिथ्म का अध्ययन ऊपर और नीचे किया गया है और इसमें कुछ भी नहीं जोड़ा जा सकता है। यदि आप विकिपीडिया को देखते हैं, तो आधिकारिक स्रोतों का संदर्भ है जिसमें आप आसानी से डूब सकते हैं। इसलिए, मुझे आश्चर्य हुआ जब मैंने गलती से दूसरे दिन पता चला कि विकिपीडिया पर इष्टतम के रूप में प्रस्तुत किए जाने वाले विकल्प को काफी अनुकूलित किया जा सकता है।

यह ऐसा ही था। कार्यात्मक प्रोग्रामिंग (एफपी) पर एक लेख की चर्चा में, उन्होंने एक सवाल पूछा: इस प्रतिमान में आरई कैसे लिखें। AF के अल्प ज्ञान से अधिक होने के कारण, मैं उत्तरों को आंकने का साहस नहीं करता, लेकिन चर्चा में शामिल अन्य प्रतिभागियों ने सैद्धांतिक प्रस्ताव के बजाय संकेत देते हुए कुछ समाधानों को तुरंत अस्वीकार कर दिया।

$O (n \ log \ log n)$ (1)

प्रस्तावित कार्यान्वयन में कम्प्यूटेशनल जटिलता होगी

$O (n ^ 2 / \ log n)$ (2)

और इस तरह की जटिलता के साथ आप प्रतीक्षा नहीं कर सकते हैं, उदाहरण के लिए, 10 मिलियन संख्याएँ छीनी गई हैं। मेरी दिलचस्पी बन गई और मैंने सामान्य प्रक्रियात्मक प्रोग्रामिंग का उपयोग करते हुए, विकिपीडिया के अनुसार इष्टतम संस्करण को लागू करने की कोशिश की। डेल्फी -7 में, मुझे निम्नलिखित कोड मिला:

लिस्टिंग 1

program EratosthenesSieve; // Sieve of Eratosthenes {$APPTYPE CONSOLE} uses SysUtils, DateUtils,Math; const version ='1.0.1d1'; N = 1000000000; // number of primes var sieve : array [2..N] of boolean; // false if prime t0, t1,dt : TDateTime; O,C : Extended; procedure init; var i : integer; begin for i:=2 to n do sieve [i] := false; end; //init procedure calc (start : integer); var prime, i : integer; breakLoop, exitProc : Boolean; begin prime := start; exitProc := false; repeat // find next prime prime := prime+1; while (prime<N) and sieve[prime] do inc (prime); i:= sqr(prime); // delete if i<= N then begin breakLoop := false; repeat if i<= N then begin sieve [i] := true; inc (i,prime); end else // if i<= N breakLoop := true; until breakLoop; end else // if prime+prime<= N exitProc := true; until exitProc; end; //calc procedure print; var i :integer; found : integer; begin found := 0; for i:=2 to N do if not sieve [i] then begin // write (i,', '); inc(found); end; writeln; writeln ('Found ',found,' primes.'); end; // begin // program body writeln ('Sieve of Eratosthenes version ', version); writeln('N= ',N); init; t0 := now; writeln('Program started ',DateTimeToStr(t0)); t0 := now; calc (1); t1 := now; writeln('Program finished ',DateTimeToStr(t1)); dt := SecondSpan(t1,t0); writeln ('Time is ',FloatToStr(dt),' sec.'); O := N* ln(ln(N)); C := dt/O; writeln ('O(N ln ln N)= ',O,' C=',C); O := sqr(N)/ln(N); C := dt/O; writeln ('O(N*N/ln N)= ',O,' C=',C); print; writeln ('Press Enter to stop...'); readln; end.

उलटा मानों के साथ आरई को छलनी बूलियन सरणी द्वारा दर्शाया जाता है - यदि संख्या प्राइम है, तो इसे गलत के रूप में इंगित किया जाता है, जो स्थानांतरण के दौरान नकारात्मक संचालन (नहीं) की संख्या को कम करता है। कार्यक्रम में 3 प्रक्रियाएं हैं: आरई - इनीट की गणना, आरई में संख्याओं की गणना (स्थानांतरण और स्ट्राइकथ्रू) - कैल्क, और परिणाम के रूप में पाए गए प्रिंटों की छपाई - और प्रिंट की गई संख्याओं की संख्या गिना जाता है। मैं विशेष रूप से प्रिंट प्रक्रिया में प्राइम की टिप्पणियों के आउट-आउट आउटपुट पर ध्यान आकर्षित करूंगा: एन = 1000 पर परीक्षण के लिए, टिप्पणी को हटा दिया गया है।

यहां कैल्क प्रक्रिया में मैं विकिपीडिया सिफारिश का उपयोग करता हूं: अगले प्राइम नंबर के लिए, आरई से संख्या हटाएं

$i ^ 2, i ^ 2 + i, i ^ 2 + 2i, ...$

यह कार्यक्रम 17.6 सेकंड में एक बिलियन संख्याओं के माध्यम से विकसित हुआ। मेरे पीसी पर (3.4 गीगाहर्ट्ज इंटेल कोर आई 7 सीपीयू)।
इस कार्यक्रम को बनाने के बाद, मुझे अचानक सम और विषम संख्याओं के प्रसिद्ध गुणों को याद किया।

लेम्मा 1. 1) विषम + विषम = सम; 2) विषम + सम = विषम; ३) सम + भी = भी।

सबूत

1)

$(2n + 1) + (2m + 1) = 2n + 2m + 2$ विभाज्य द्वारा 2. टीसीडी।
2)

$(2n + 1) + (2m) = 2n + 2m + 1$ शेष के बिना 2 से विभाज्य नहीं। QED।
3)

$(2n) + (2m) = 2n + 2m$ विभाज्य द्वारा 2. टीसीडी।

लेम्मा 2. विषम संख्या का वर्ग विषम संख्या है।
सबूत।

$(2n + 1) ^ {2} = 4n ^ {2} + 4n + 1$ शेष के बिना 2 से विभाज्य नहीं। QED।

नोट। 2 से अधिक की एक अभाज्य संख्या विषम है।

इसलिए, आप केवल विषम संख्याओं को हटा सकते हैं:

$i ^ 2, i ^ 2 + 2i, i ^ 2 + 4i, ...$ (3)

लेकिन पहले आपको सभी सम संख्याओं को पार करना होगा। यह एक संशोधित init आरंभीकरण प्रक्रिया द्वारा किया जाता है।

लिस्टिंग 2

 program EratosthenesSieve; // Sieve of Eratosthenes {$APPTYPE CONSOLE} uses SysUtils, DateUtils,Math; const version ='1.0.1d1'; N = 1000000000; // number of primes var sieve : array [2..N] of boolean; // false if prime t0, t1,dt : TDateTime; O,C : Extended; procedure init; var i : integer; begin for i:=2 to n do sieve [i] := not odd(i); end; //init procedure calc (start : integer); var prime,prime2, i : integer; breakLoop, exitProc : Boolean; begin prime := start; exitProc := false; repeat // find next prime prime := prime+1; while (prime<N) and sieve[prime] do inc (prime); // i:= prime*prime; i:= sqr(prime); prime2 := prime+prime; // delete if i<= N then begin breakLoop := false; repeat if i<= N then begin sieve [i] := true; inc (i,prime2); end else // if i<= N breakLoop := true; until breakLoop; end else // if prime+prime<= N exitProc := true; until exitProc; sieve [2] := false; end; //calc procedure print; var i :integer; found : integer; begin found := 0; for i:=2 to N do if not sieve [i] then begin // write (i,', '); inc(found); end; writeln; writeln ('Found ',found,' primes.'); end; // begin // program body writeln ('Sieve of Eratosthenes version ', version); writeln('N= ',N); init; t0 := now; writeln('Program started ',DateTimeToStr(t0)); t0 := now; calc (2); t1 := now; writeln('Program finished ',DateTimeToStr(t1)); dt := SecondSpan(t1,t0); writeln ('Time is ',FloatToStr(dt),' sec.'); O := N* ln(ln(N)); C := dt/O; writeln ('O(N ln ln N)= ',O,' C=',C); O := sqr(N)/ln(N); C := dt/O; writeln ('O(N*N/ln N)= ',O,' C=',C); print; writeln ('Press Enter to stop...'); readln; end.

इस कार्यक्रम ने 9.9 सेकंड के लिए काम किया। - लगभग दोगुना तेज।

सैद्धांतिक के लिए कार्यक्रम के वास्तविक समय के संचालन के पत्राचार का आकलन करने के लिए, मैंने सुझाव दिया कि

$dt = C * O,$

जहाँ

$dt$ - मापा ऑपरेटिंग समय;

$सी$ - समय के आयाम के साथ निरंतर;

$O$ - सैद्धांतिक मूल्यांकन।

यहाँ से परिकलित किया गया

$सी$ मूल्यांकन करने के लिए (1) और (2)। के लिए

$N = 10 ^ 6$ और कम

$dt$ शून्य के करीब। इसलिए, मैं बड़े के लिए पहले कार्यक्रम पर डेटा लाता हूं

$एन$

$एन$	(1)	(2)
$10 ^ 7$	$1.69 \ cdot 10 ^ {- 9}$	$2.74 \ cdot 10 ^ {- 9}$
$10 ^ 8$	$5.14 \ cdot 10 ^ {- 9}$	$1.47 \ cdot 10 ^ {- 8}$
$10 ^ 9$	$5.80 \ cdot 10 ^ {- 9}$	$1.29 \ cdot 10 ^ {- 7}$

जैसा कि हम देखते हैं, अनुमान (1) वास्तविक परिणामों के बहुत करीब है। दूसरे कार्यक्रम के लिए, एक समान तस्वीर देखी जाती है। मुझे बहुत संदेह है कि मैंने अनुक्रम (3) का उपयोग करके अमेरिका की खोज की और मैं उस कार्य के लिंक के लिए बहुत आभारी रहूंगा जहां यह दृष्टिकोण लागू किया गया था। सबसे अधिक संभावना है, विकिपीडिया के लेखक खुद इलेक्ट्रॉनिक युद्ध की जानकारी के समुद्र में डूब गए और इस काम से चूक गए।

"रैखिक क्रम" के साथ विकिपीडिया एल्गोरिथ्म के लिए पुनश्च

विकिपीडिया की तुलना में अरबों सरल संख्याओं को तेज़ी से भेजना

More articles: