👰🏾 ❕ 👳 غربلة مليارات الأرقام البسيطة بشكل أسرع من ويكيبيديا 🏧 👶 👩🏾‍🔧

( مصدر الشكل )

من المعروف أن Sieve of Eratosthenes (RE) هي واحدة من أقدم الخوارزميات التي ظهرت قبل اختراع أجهزة الكمبيوتر بوقت طويل. لذلك ، قد تعتقد أن هذه الخوارزمية قد درست على مدار القرون لأعلى ولأسفل ولا يمكن إضافة أي شيء إليها. إذا نظرت إلى ويكيبيديا ، هناك بحر من الإشارات إلى مصادر موثوقة يمكنك من خلالها الغرق بسهولة. لذلك ، فوجئت عندما اكتشفت بالصدفة في اليوم الآخر أن الخيار المقدم على النحو الأمثل على ويكيبيديا يمكن تحسينه بشكل كبير.

كان هكذا. في مناقشة لمقال عن البرمجة الوظيفية (FP) ، سأل سؤالًا : كيفية كتابة تعلم اللغة الألمانية في هذا النموذج. امتلاك أكثر من المعرفة الضئيلة بالعربية ، لا أجرؤ على الحكم على الإجابات ، لكن المشاركين الآخرين في المناقشة رفضوا بعض الحلول المقترحة على الفور ، مشيرين إلى أنه بدلاً من التعقيد النظري

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

سيكون للتطبيق المقترح تعقيد حسابي

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

وبهذا التعقيد ، لا يمكنك الانتظار عند فرز 10 ملايين رقم على سبيل المثال. أصبحت مهتمًا وحاولت تنفيذ الإصدار الأمثل وفقًا ليكيبيديا ، باستخدام البرمجة الإجرائية المعتادة. في Delphi-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.

تمثل RE صفيف Boolean الغربال ذي قيم معاكسة - إذا كان الرقم أوليًا ، فسيتم الإشارة إليه على أنه خطأ ، مما يقلل من عدد عمليات النفي (لا) أثناء غربلة. هناك 3 إجراءات في البرنامج: تهيئة RE - init ، والحسابات (غربلة وتصحيح الأرقام في RE) - calc ، وطباعة الأعداد الأولية الموجودة كنتيجة - طباعة ، ويتم حساب عدد الأرقام التي تم العثور عليها. سألفت الانتباه بشكل خاص إلى إخراج التعليقات التمهيدية في إجراء الطباعة: للاختبار عند N = 1000 ، تتم إزالة التعليق.

هنا في إجراء calc ، استخدم توصية Wikipedia: بالنسبة للرقم الأولي التالي i ، احذف الأرقام من RE

، ، ،

$i ^ 2، i ^ 2 + i، i ^ 2 + 2i، ...$

غربل هذا البرنامج مليار رقم في 17.6 ثانية. على جهاز الكمبيوتر (3.4 جيجاهيرتز Intel Core i7 CPU).
بعد أن صنعت هذا البرنامج ، تذكرت فجأة الخصائص المعروفة للأرقام الفردية والزوجية .

Lemma 1. 1) فردي + فردي = متساوي ؛ 2) غريب + حتى = غريب ؛ 3) حتى + حتى = حتى.

دليل

1)

$(2n + 1) + (2m + 1) = 2n + 2m + 2$ القسمة على 2. TCD.
2)

$(2n + 1) + (2m) = 2n + 2m + 1$ غير قابل للقسمة على 2 دون الباقي. وهو المطلوب.
3)

$(2n) + (2m) = 2n + 2m$ القسمة على 2. TCD.

Lemma 2. مربع رقم فردي هو رقم فردي.
برهان.

$(2n + 1) ^ {2} = 4n ^ {2} + 4n + 1$ غير قابل للقسمة على 2 دون الباقي. وهو المطلوب.

المذكرة. عدد أولي أكبر من 2 غريب.

لذلك ، يمكنك فقط حذف الأرقام الفردية:

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

لكن أولاً تحتاج إلى شطب جميع الأرقام الزوجية. يتم ذلك عن طريق إجراء تهيئة التهيئة المعدلة.

ادراج 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$ - قياس وقت التشغيل ؛

$C$ - ثابت مع البعد الزمني ؛

$يا دولا$ - التقييم النظري.

تحسب من هنا

$C$ لتقييم (1) و (2). إلى

$N = 10 ^ 6$ و أقل

$dt$ قريبة من الصفر. لذلك ، أحمل البيانات على البرنامج الأول للكبير

$N.$

$N$	(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: