غربال إراتوستينس

[الفجر الابيض]

السلام عليكم ورحمة الله


معروف برمجيا ان  غربال إراتوستينس هو اسرع غربال موجود حاليا لغربلة الاعداد الاولية
جربته بنفسي ووجدت انه يغربل 5 مليار رقم في ثانية ونصف
و كانت عندي فكرة طبقتها ايضا وعملت عليها فترة طويلة والان اكتملت وجربتها وغربلت 5 مليار رقم في نصف ثانية على نفس الجهاز ونفس المواصفات
وبلغة rust تنخفض الى 0.33 ثانية
وجربته على دلفي وعلى Rust وعلى .net 
بصراحة نشر الغربال قد يعطي شهرة له و اسم ولكن لا فائدة مادية فيه
فهل يمكن الاستفادة منه ماديا بشكل او باخر 
أي هل يمكن لبعض الشركات ان تشتريه ليس للاستخدام فقط او احتكاره اونما حتى كأسم اي ابيعهم كل شئ .
ونشره بلا فائدة لا فائدة فيه بل فساد ايضا فهذا شئ يهم كل المخترقين ومن يفكون البيانات المشفرة وما شابه

[mo7ammed]

وعليكم السلام ورحمة الله وبركاته،

ما شاء الله عليك اخي.

يمكنك الاعلان عنها وتنزيل ملفات تنفيذية للإختبارات، وكتابة منشورات في عدة مواقع مثل Linkedin، ايضاً يمكنك تنزيل ال Benchmark على Github فقط بدون السورس مع ذكر انه يتم بيع السورس من خلال ترخيص تجاري للشركات فقط.

ايضاً هل من الممكن ذكر سرعة غربلة كل من دلفي و.net و rust على 5 مليار رقم؟

ايضا هل جربت المقارنة مع خوارزميات احدث مثل غربال أتكين؟

بالتوفيق لك

---

---

ايضاً من الممكن مقارنته مع Dave drag-races الخاصة بتحدي الأعداد الأولية Primes:
المشروع على github
https://github.com/PlummersSoftwareLLC/Primes

---

وجدت أن خورازمية : Segmented Sieve هي الآسرع مع الأرقام الكبيرة، يمكن اضافتها للمقارنة ايضاً

[الفجر الابيض]

شكرا اخي على الاهتمام والمساعدة

بصراحة قارنته مع غربال إراتوستينس فقط لان البحث قادني الى انه اسرع كود موجود حاليا ولا ضير من تجربته مع غرابيل اخرى مثل غربال أتكين
سوف اجربه وانشر النتيجة
بالنسبة للمقارنة الدوت نت استغرقت 0.5 ثانية والدلفي ابطاء بهامش بسيط جدا وبالبحث وجدت ان الدوت نت فيها ميزات حديثة تجعلها اسرع في العمليات الحسابية البحثة اما Rust فقط كسرت الحاجز وفازت بي 0.3 ملي ثانية وهذه اللغة التي تتفوق على الجميع في انتاج برامج ومكتبات بسرعة البرق وقدرتها الرهيبة على ادارة الذاكرة و الحسابات
على العموم انا اعمل على كسر حاجز 0.3 ملي ثانية
فهنا يعتبر الخط الفاصل لاقصى حدود المعالج ، وما يفعله البعض هو عمليات تسخينية للمعالج قبل البدء في الغربلة قد تعطي هامش بسيط اضافي
ولكن الاهم هو طريقة الحساب وتقسيم عمل الانوية بعضها يغربل وبعضها يجمع البواقي فكل هذه التفاصيل الصغيرة مهمة جدا
ولاول مرة ارى صحراء الارقام الاولية في المليارات والتريليونات كنت اسمع بها ولكن دخلتها بنفسي هذه المرة
ارض من الاصفار ممتدة بين الملايين من الهكتارات حتى ترى رقم اولي وحيد مرمي هنا او هناك على جنبات الطريق
ومليارات الاصفار حتى تتفاجاء بواحة من الارقام الاولية داخل هذه الصحراء
كان الامر عجيب وغريب تشعر انك بداخل فضاء شاسع تمر بنجوم متناثرة تتباعد لملايين السنين الضوئية وفهمت وقتها لماذا لا يستطيعون ايجاد دالة تتكهن بالرقم الاولي القادم
في المئات والالاف وحتى الملايين من السهل جدا التنبؤ بالرقم القادم ولكنها مجرد معادلات تعويضية ستفشل في تلك الصحراء لانه اي ارقام تعويضية ستصبح لاشئ امام ذلك الفراغ الرهيب .
للباحثين في هذه الاعداد لا يمكنني ان اصف او استخلص ما رأيته لاصفه كمساعدة الا ان المسافات بين الارقام غير ثابتة لانها على مسار مشدود
تخيل انك تضع الارقام على شريط مطاط لمسافة كيلومتر ثم قمت بشده وقتها الارقام باماكن سوف تكون قريبة وفي الوسط سوف تتباعد كثيرا جدا .
هذه هي المساعدة الوحيدة التي استطيع ان اقولها وهي الوحيدة التي معي
لا تضيع تفكيرك في المسافات بين الارقام فهي غير ثابتة وبنفس الوقت هي واحدة ولكنها متمددة فالمسافة بين 13 و 17 هي اربعة ولكنها تصبح 400 في الملايين و4000 في الميليارات وهكذا واعتقد يجب اسقاط هذا على الفضاء لانه يتمدد وينكمش ويلتوي وهكذا تماما ما يحدث
وان صح ذلك فستكون هناك ارقام عبارة عن بوابات لارقام اولية متقدمة جدا ، مثلا الرقم 41 بمعادلة يقودك الى رقم في المليار
اعتبروها مثل الثقوب السوداء او البوابات الزمنية او في انحناء الفضاء
وبالتوفيق للجميع

[الفجر الابيض]

قبل قليل كسرت حاجز 300 ملي ثانية الى 0.194 ملي ثانية بلغة Rust
بالبحث هناك غربال مفتوح المصدر تم تطويره على مدار العديد من السنوات على جهازي الخمسة مليار رقم اخذ فيها 77 ملي ثانية
التحدي بين اجتهاد شخصي له عدة ايام وبين خبراء عالميين لهم سنوات من التطوير واقترابي منهم الى هذه الدرجة يعتبر خطوة مشجعة
الفارق بيني وبينهم ان حلقة الشطب الداخلية لديهم مكتوبة يدوياً بلغة التجميع وهنا من يثقنها يفوز
كل هذه السرعات حديثة العهد والمولد

---

قبل قليل كسرت حاجز 194 ملي ثانية الى 137 ملي ثانية

---

قبل قليل وتحسين الذاكرة كسرت حاجز 137 الى 80 ملي ثانية اننا نقترب من الرقم العالمي ولازال بجعبتي فكرة قد تنقلنا لابعاد مستحيلة

[mo7ammed]

قبل قليل كسرت حاجز 300 ملي ثانية الى 0.194 ملي ثانية بلغة Rust
بالبحث هناك غربال مفتوح المصدر تم تطويره على مدار العديد من السنوات على جهازي الخمسة مليار رقم اخذ فيها 77 ملي ثانية
التحدي بين اجتهاد شخصي له عدة ايام وبين خبراء عالميين لهم سنوات من التطوير واقترابي منهم الى هذه الدرجة يعتبر خطوة مشجعة
الفارق بيني وبينهم ان حلقة الشطب الداخلية لديهم مكتوبة يدوياً بلغة التجميع وهنا من يثقنها يفوز
كل هذه السرعات حديثة العهد والمولد

---

قبل قليل كسرت حاجز 194 ملي ثانية الى 137 ملي ثانية

---

قبل قليل وتحسين الذاكرة كسرت حاجز 137 الى 80 ملي ثانية اننا نقترب من الرقم العالمي ولازال بجعبتي فكرة قد تنقلنا لابعاد مستحيلة

ما شاء الله، بالتوفيق وإن شاء الله نسمع قريباً بأنك كسرت حاجز ال 77 ملي ثانية.

بخصوص غربال غربال إراتوستينس، هو ليس الأسرع، لكنه سريع مع الأرقام كفاية للأرقام الغير كبيرة مثل ما تقوم به

الأسرع هو : Segmented Sieve

[الفجر الابيض]

الأسرع هو : Segmented Sieve

هو  هذا الذي نحن في تحدي معه الان وهو الذي بجهازي حقق 77 ملي ثانية
حقيقة ان تحقيق 80 ملي ثانية يعتبر انجاز كبير بعد مراجعتي لكود c++ ومع انني لست ضليعا باللغة وجدت ان ما يهمهم مجرد العد فقط كمهندس المساحة اما برمجتي انا فتعمل كعامل البناء
فانا اقوم ببناء الحائط ثم اقول فيه 7 اعداد اولية ام هم فينظرون للحائط ويقولون فيه 7 اعداد اولية
وموقعهم هنا

https://github.com/kimwalisch/primesieve

بمعنى ان الدالة الخاصة بي يمكن الاعتماد عليها في الطباعة والعرض والعد وغيرها ولهذا تجد ان لديهم اكثر من نسخة واحدة للطباعة واخرى للعد فقط والخ
والتي نحن في تحدي معها هي اداة بناء ضد اداة عد ولهذا ساجرب ترك البناء وتجربة العد لنرى ان كان سيتحسن الاداء
ايضا هم يستخدمون بعض الحيل او بين قوسين (غش مشروع) فلديهم جداول فيها مضاعفات الاعداد و بعض الاعداد الاولية مثلا من 1 الى 136 وهذا لاختصار بعض دورات المعالج داخل الحلقات
انا لست بخبرتهم في ادارة الذاكرة او ترويض المعالج ولكن اعتمد على افكار معينة في القفزات و الفلترة وهي التي جعلتني الحق بهم رغم بساطة خبرتي فمع ادارة ذاكرة ممتازة وترويض جيد للمعالج + تنفيذ القفزات الفعالة والفلترة المختصرة يمكن بسهولة تجاوز 77 ملي ثانية

معلومة جانبية من التجارب : في حالات معينة كنت اسمع ازيز خفيف من المعالج ملايين العمليات في اجزاء من الثانية ومستحيل ان يكون للمعالج صوت وبعد البحث تبين انه صوت ليس من المعالج وانما هو كمية الطاقة الرهيبة التي تنتقل للمعالج لتنفيذ مهام ثقيلة او نتيجة تولد مجالات كهرومغناطيسية في الدوائر وحول الناقلات للمعالج
ولهذا كلما سمعت هذا الصوت اعيد ضبط الكود حتى يصل الى مرحلة الصمت المطلق

[الفجر الابيض]

كما توقعت كعد فقط بدون بناء اي لا يمكن الطباعة او حفظ في ملف او ماشابه
توصلت للنتيجة

وقت التنفيذ: 31 ms
maxLimit:99000000000UL
العناصر المتبقية: 4078566781

0.31 ملي ثانية وليس فقط لي 5 مليار رقم وانما الى 99 مليار رقم
وهذا في الجولة التسخينية الاولى الجولة الثانية يكملها في صفر من الزمن
وهذا لان التجربة على  .NET
في النقرة الأولى، تقوم بيئة .NET بتحويل كود الـ VB.NET إلى لغة الالة وتخصيصه خصيصا لممعالج . 
في النقرة الثانية الكود المترجم والمحسن جاهز تماما للانطلاق بدون اي وقت ضائع .
المعالجات الحديثة ذكية جدا في النقرة الثانية يكون المعالج قد حفظ نمط القفزات الرياضية التي برمجناها فيقوم بتنفيذها بشكل استباقي
لهذا بالموقع المذكور فوق اجدهم يكتبون صفر زمن امام بعض الاختبارات واستغربت تماما من نتائجهم الغير مقبولة فيزيائيا لي
وربما هي ذاكرة الكاش لا اعلم تحتاج الى تتبع
الان العداد والبناء جاهزان سوف احولهما الى RUST وانشرهما

[mo7ammed]

ما شاء الله
قفزة كبيرة في الاداء.

بالتوفيق أخي وإن شاء الله خوارزميتك تصبح المعيار الأساسي للغربلة

[الفجر الابيض]

الاسرار التي اكتشفتها في التعامل مع ذاكرة المعالج

1: تقسيم الذاكرة الى اجزاء صغيرة تناسب حجم ذاكرة L1 لاجراء عمليات عليها بسرعة عالية فنحن لا نستطيع اجبار المعالج على وضع قيم في احد المستويات الثلاثة L1-L2-L3 كيفما نشاء وانما هو من يقرر بناء على حجم البيانات واهمية سرعة تنفيذها خاصة المتكرر منها مثل حسابات Loop
2: المصفوفات غالبا سيتم وضعها في المستوى الثاني او الثالث بحسب الاهمية ايضا والحجم
3: في العمليات المتعددة الخيوط يجب مراعاة وصول الخيوط للبيانات المشتركة فاذا كان لدينا مصفوفة مرتبطة بعملية كتابة وقراءة فان الكتابة والقراءة نسبة السرعة بينهم هي 5:1 والكتابة ابطاء بخمس مرات ، وهنا يلجاء البعض الى انشاء حلقتين او استخدام Sleep وامور مشابهة وكلها تضر بالاداء

الحل الامثل بالنسبة لي هي تخيل ان لدينا ارنب وكلب نريد ان نطلقهما وان يصلا الى خط النهاية معا او يصل الارنب قبل الكلب بفارق ضئيل
نحن لدينا المسافة لخط النهاية وفارق السرعة وخط النهاية يمثل المصفوفة


المعطيات:

• المسافة الكلية (الأرقام): 28.000.000 رقم (double).
  
• سرعة الأرنب (الكتابة): 5 ملي ثانية لكل 28 مليون رقم (5.6 مليون رقم/ملي ثانية).
  
• سرعة الكلب (القراءة): 1 ملي ثانية لكل 28 مليون رقم (28 مليون رقم/ملي ثانية).
  

كود :

t_rabbit(X) = X / سرعة_الأرنب t_rabbit(X) = X / 5.6  (بوحدة ملي ثانية)

كود :

t_dog(X) = D + (X / سرعة_الكلب) t_dog(X) = D + (X / 28)  (بوحدة ملي ثانية)

شرط الوصول الأمن

كود :

t_rabbit(N) = t_dog(N)  (حيث N = 28,000,000) N / 5.6 = D + N / 28

فارق البداية الامن

كود :

D = N / 5.6 - N / 28 D = (N * (28 - 5.6)) / (5.6 * 28) D = (28,000,000 * 22.4) / 156.8 D = 627,200,000 / 156.8 D ≈ 4,000,000  (أي 4 ملي ثانية)

الخلاصة بدل من ان استخدم المكابح اطلقهما بكامل سرعتهما ولكن اطلق الكلب بوقت متأخر قليلا ليصل مع الارنب لنهاية الخط

4: ايضا عند التعامل مع ذاكرة المعالج فالكود لن يعمل على كل الاجهزة وانما يجب ان يتم قراءة ذاكرة المعالج وعدد انويته وبعدها يتم اتخاد قرار تقسيم الذاكرة وتوزيع المهمة على عدد انوية المعالج فمعالج يستطيع وضع 500 مليون رقم بذاكرته ولكن معالج اخر ذاكرته لا تسع هذا الحجم

[الفجر الابيض]

جزئية مطاردة الكلب للارنب يجب ان نتوقف عندها قليلا لانها غير أمنة
كحسابيا ومنطقيا هي صحيحة ولكن تبين ان هناك حالات يحدث فيها تأخير فعندما يكون لدينا خيطين لاسباب معينة قد يقرر المعالج ايقاف الارنب اما لعملية على الشبكة او القرص او لاي شئ اخر ويستمر الكلب في الركض ويلحق بالارنب ويتجاوزه وتحدث المشكلة
ولان الكتابة ابطاء اذا اطلقنا 15 ارنب و 5 كلاب ايضا ستحدث مشكلة لان الكلاب سوف تتسابق على الارانب وتتشاجر عليها وتحدث مشكلة
هناك عدة حلول مثلا استخدام مؤشر يمثل موقع الارنب ونترك الكلب يركض باقصى سرعة طالما ان موقعه لا يسبق المؤشر واذا وصل الى مكان الارنب ندخله بحالة انتظار قليلة وبذلك لا يلحق بالارنب ابدا حتى النهاية ومع توزيع وتقسيم مسافة المضمار على عدد المسارات نقلص المسافة كثيرة فالرقم 28 مليون اذا قسمناه على 20 مسار اي 20 ارنب وكلب سيصبح مليون و400 الف فقط