في هذه المقالة ، أقدم تسلسلًا جديدًا شبه منخفض الاختلاف يوفر تحسينًا كبيرًا على المتواليات الحديثة ، مثل Sable و Niederreiter ، إلخ.


الشكل 1. مقارنة بين مختلف سلاسل شبه عشوائية مع اختلاف التباعد. لاحظ أن المقترح من قبلي $$$R$ ، وبالتالي يخلق نقاط موزعة بالتساوي أكثر من جميع الطرق الأخرى. علاوة على ذلك ، تتطلب جميع الطرق الأخرى اختيارًا دقيقًا للمعلمات الأساسية ، وفي حالة التحديد غير الصحيح يؤدي إلى الانحطاط (على سبيل المثال ، في الجزء العلوي الأيمن)

المواضيع المشمولة في هذه المقالة

• انخفاض تسلسل الاختلاف في بعد واحد
• طرق الاختلاف المنخفضة في بعدين
• مسافة التعبئة
• مجموعات متعددة التباين المنخفض
• تسلسلات شبه عشوائية على سطح الكرة
• بلاط شبه كاشط الدوري
• أقنعة التدرج في رسومات الكمبيوتر

منذ بعض الوقت ، تم نشر هذا المنشور على الصفحة الرئيسية لأخبار هاكر. يمكنك قراءة مناقشته هناك .

مقدمة: عشوائي مقابل شبه عشوائي

في الشكل 1 ، يمكنك ملاحظة أنه مع أخذ عينات عشوائية موحدة بسيطة لنقطة داخل مربع وحدة ، يتم ملاحظة تراكم النقاط ، وأيضًا المناطق التي لا تحتوي على نقاط ("الضوضاء البيضاء"). التسلسل شبه العشوائي المنخفض هو طريقة لإنشاء نقاط متتالية (غير محدودة) بطريقة حتمية ، مما يقلل من احتمال التراكم (الاختلاف) ، مع ضمان تغطية موحدة لكامل المساحة ("الضوضاء الزرقاء") في نفس الوقت.

متواليات شبه عشوائية في بعد واحد

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

• الكسور غير المنطقية: كرونيكر ، ريتشتماير ، رامشو
• (متبادل) الأعداد الأولية: Van der Corpute، Holton، Foret
• كثيرات الحدود غير القابلة للاختزال: Niederreiter
• كثيرات الحدود البدائية: السمور

من أجل الإيجاز ، في هذا المنشور سأقارن بشكل رئيسي العودية المضافة الجديدة $$$R$ - تسلسل ينتمي إلى الفئة الأولى ، أي الطرق العودية القائمة على أرقام غير منطقية (تسمى غالبًا تسلسلات Kronecker أو Weil أو Richtmeier) ، والتي تعتبر المشابك من الرتبة 1 ، وتسلسل Holton ، الذي يستند إلى تسلسل van der Corpute أحادي الأبعاد. يُعرّف تسلسل العودية Kronecker المتعارف عليه بأنه:

$$

$$R_1 (\ alpha): \؛ \؛ t_n = \ {s_0 + n \ alpha \} ، \ quad n = 1،2،3 ، ...$$

اين $$$\ alpha$ - أي رقم غير منطقي. لاحظ أن الإدخال $$$\ {x \}$ يدل على الجزء الكسري $$$x$ . في الحسابات ، يتم التعبير عن هذه الوظيفة غالبًا

$$

$$R_1 (\ alpha): \؛ \؛ t_n = s_0 + n \ alpha \؛ (\ textrm {mod} \؛ 1) ؛ \ quad n = 1،2،3 ، ...$$

في $$$s_0 = 0$ أعضاء القليلة الأولى من التسلسل $$$R (\ phi)$ يساوي:

$$

من المهم أن نلاحظ أن المعنى $$$s_0$ لا يؤثر على الخصائص العامة للتسلسل ، وفي جميع الحالات تقريبًا تساوي الصفر. ومع ذلك ، في حساب الخيار $$$s \ neq 0$ يوفر درجة إضافية من الحرية ، والتي غالبا ما تكون مفيدة. إذا $$$s \ neq 0$ ، ثم يُسمى التسلسل غالبًا "تسلسل الشبكة المنقولة". على الرغم من حقيقة أنه افتراضيا $$$s = 0$ أعتقد أن هناك اعتبارات نظرية وعملية يجب أن تكون القيمة قياسية بها $$$s = 1/2 دولا$ . القيمة $$$\ alpha$ إعطاء أصغر التناقض ممكن إذا $$$\ alpha = 1 / \ phi$ اين $$$\ phi$ - هذه هي النسبة الذهبية. هذا هو

$$

$$\ phi \ equiv \ frac {\ sqrt {5} +1} {2} \ simeq 1.61803398875 ...؛$$

ومن المثير للاهتمام أن نلاحظ أن هناك عدد لا حصر له من القيم الأخرى. $$$\ alpha$ ، والتي تسمح لنا أيضًا بالحصول على التناقض الأمثل ، وكلها مرتبطة ببعضها البعض عن طريق تحويل Mobius

$$

$$\ alpha '= \ frac {p \ alpha + q} {r \ alpha + s} \ quad \ textrm {for all integers} \؛ p ، q ، r ، s \ quad \ textrm {مثل هذا} | ps-qr | = 1$$

الآن نقوم بمقارنة هذه الطريقة العودية بتسلسلات فان دير كوربوت المعروفة بترتيب عكسي لتصريفات [ فان دير كوربوت ، 1935 ]. إن تسلسلات Van der Corpute هي في الواقع مجموعة من التتابعات ، يتم تعريف كل منها بمقياس تشعبي فريد $$$ب$ . الأعضاء القليلة الأولى في التسلسل بـ b = 2 متساوون:

$$

$$t_n ^ {[2]} = \ frac {1} {2} ، \ frac {1} {4} ، \ frac {3} {4} ، \ frac {1} {8} ، \ frac {5} {8} ، \ frac {3} {8} ، \ frac {7} {8} ، \ frac {1} {16} ، \ frac {9} {16} ، \ frac {5} {16} ، \ frac {13} {16} ، \ frac {3} {16} ، \ frac {11} {16} ، \ frac {7} {16} ، \ frac {15} {16} ، ...$$

في المقطع التالي ، نقارن الخصائص العامة وفعالية كل من هذه التسلسلات. النظر في مشكلة حساب جزء لا يتجزأ

$$

$$A = \ int_0 ^ 1 f (x) \ textrm {d} x$$

يمكننا تقريبها كـ:

$$

$$A \ simeq A_n = \ frac {1} {n} \ sum_ {i = 1} ^ {n} f (x_i) ، \ quad x_i \ in [0،1]$$

• إذا $$$\ {x_i \}$ متساوون $$$i / n$ ، هذه هي صيغة المستطيلات ؛
• إذا $$$\ {x_i \}$ تم اختيارها عشوائيا ، ثم هذه هي طريقة مونت كارلو . لكن
• إذا $$$\ {x_i \}$ هي عناصر التسلسل مع اختلاف التباعد ، ثم هذه هي الطريقة شبه مونت كارلو .

يوضح الرسم البياني أدناه منحنيات الخطأ النموذجية. $$$s_n = | A-A_n |$ لتقريب تكامل معين مرتبط بهذه الوظيفة ، $$$f (x) = \ textrm {exp} (\ frac {-x ^ 2} {2})، \؛ x \ in [0،1]$ لـ: (i) نقاط شبه عشوائية من الإعادة المضافة ، حيث $$$\ alpha = 1 / \ phi$ ، (الأزرق) ؛ (2) شبه نقاط عشوائية من تسلسل van der Corput ، (برتقالي) ؛ (3) النقاط المختارة بشكل عشوائي ، (الأخضر) ؛ (رابعا) تسلسل السمور (أحمر).

هذا يدل على أن ل $$$n = 10 ^ 6$ حل النقاط مع أخذ العينات العشوائية يؤدي إلى خطأ $$$\ simeq 10 ^ {- 4}$ فان دير كوربو تسلسل يؤدي إلى خطأ $$$\ simeq 10 ^ {- 6}$ ، اين $$$R (\ phi)$ - التسلسل يؤدي إلى خطأ $$$\ simeq 10 ^ {- 7}$ هذا في $$$\ sim$ 10 مرات أفضل من خطأ فان دير كوربوت و $$$\ sim$ 1000 مرة أفضل من أخذ العينات العشوائية (الموحدة).


الشكل 2. مقارنة التكامل العددي أحادي البعد باستخدام أساليب مونتي كارلو شبه عشوائية. كلما انخفضت القيمة ، كان ذلك أفضل. جديد $$ - تسلسل (الأزرق) وتسلسل السمور (أحمر) هي الأفضل بشكل واضح.

فيما يلي جدير بالذكر هنا:

• هذا يتوافق مع معرفة أن الأخطاء لأخذ العينات العشوائية موحدة تقلل إلى $$$1 / \ sqrt {n}$ ، والخطأ لكلا التسلسلين شبه العشوائي يميل إلى $$$1 / ن$ .
• نتائج ل $$$R_1 (\ phi)$ تعتبر النتائج (الأزرق) وتتابعات السمور (الحمراء) هي الأفضل.
• يوضح الرسم البياني أن تسلسل van der Corpute يوفر نتائج جيدة ، لكنها متسقة بشكل لا يصدق لمهام التكامل!
• يمكن أن نرى هنا أنه لجميع القيم $$$ن$ تسلسل $$$R_1 (\ phi)$ تسفر عن نتائج أفضل من تسلسل van der Corput.

تسلسل جديد $$$R_1$ ، وهو تسلسل Kronecker باستخدام النسبة الذهبية ، هو واحد من أفضل الخيارات لأساليب تكامل عشوائية شبه كاروية أحادية البعد (Quasirandom Monte Carlo، QMC).

تجدر الإشارة إلى أنه بالرغم من ذلك $$$\ alpha = \ phi$ يوفر نظريا خيارا مثاليا $$$\ sqrt {2}$ قريبة جدا من الأمثل ، وتقريبا أي قيمة أخرى غير عقلانية $$$\ alpha$ يوفر منحنيات خطأ متفوقة للتكامل أحادي البعد. هذا هو السبب في كثير من الأحيان يتم استخدامه $$$\ alpha = \ sqrt {p}$ لأي رقم أولي. علاوة على ذلك ، من وجهة نظر الحسابات ، فإن القيمة العشوائية المحددة في الفاصل الزمني $$$\ alpha \ in [0،1]$ من شبه المؤكد (ضمن حدود دقة الماكينة) أن يكون عددًا غير منطقي ، وبالتالي يعد اختيارًا جيدًا للتسلسل مع اختلاف التباعد. من أجل الوضوح البصري ، لا يُظهر الشكل أعلاه نتائج تسلسل Niederreiter ، لأنه لا يمكن تمييزها عمليًا عن نتائج تسلسلات Sobol و $$$R$ . تم احتساب تسلسل Niederreiter و Sable (بالإضافة إلى اختيار المعلمة المحسنين) اللذين تم استخدامهما في هذا المنشور في Mathematica باستخدام ما يسمى "المولدات المغلقة والمُحسَّنة بالكامل من مكتبة Intel MKL" في الوثائق.

متواليات شبه عشوائية في بعدين

تجمع معظم الأساليب الحديثة لبناء تباين منخفض في الأبعاد العليا ببساطة (مكونًا تلو الآخر) $$$د$ تسلسل أحادي البعد. للإيجاز ، في المنشور سننظر بشكل رئيسي في تسلسل Holton [ Holton ، 1960 ] ، وتسلسل Sable ، و $$$د$ تسلسل كرونكر الأبعاد.

تم بناء تسلسل Holton باستخدام بسيطة $$$د$ مختلف متواليات فان دير كوربوت أحادية البعد ، والتي أساسها بسيط متبادل لجميع الآخرين. وهذا هو ، وهي أرقام coprime الزوجية. بلا شك ، الخيار الأكثر شيوعًا بسبب بساطته ومنطقه الواضحين هو الخيار الأول $$$د$ الأعداد الأولية. يوضح الشكل 1. توزيع أول 625 نقطة يحددها Holton (2،3) - نتيجة لذلك. على الرغم من أن العديد من متواليات Holton ثنائية الأبعاد هي مصادر ممتازة للتسلسلات ذات التباعد المنخفض ، من المعروف جيدًا أن العديد منها يمثل مشكلة كبيرة ولا تظهر تباعدًا منخفضًا. على سبيل المثال ، يوضح الشكل 3 أن نتيجة Holton (11،13) تولد خطوطًا ملحوظة جدًا. بُذلت جهود كبيرة لتطوير طرق اختيار النموذج والأزواج الإشكالية. $$$(p_1 ، p_2)$ . في الأبعاد العليا ، تصبح المشكلة أكثر تعقيدًا.

عند التعميم على أبعاد أعلى ، تعاني أساليب كرونيكر العودية من صعوبات أكبر. على الرغم من استخدام $$$\ alpha = \ sqrt {p}$ يتم إنشاء تسلسلات أحادية البعد ممتازة ، من الصعب للغاية العثور على أزواج من الأعداد الأولية التي يمكن استخدامها كأساس لحالة ثنائية الأبعاد ليست مشكلة! تم اقتراح استخدام أرقام غير منطقية معروفة كحل بديل ، على سبيل المثال $$$\ phi ، \ pi ، e ، ...$ . إنها توفر نتائج مقبولة بشكل معتدل ، ولكن لا يتم استخدامها بشكل عام ، لأنها عادة لا تكون بنفس جودة تسلسل Holton المحدد بشكل صحيح. تبذل جهود كبيرة لحل هذه المشاكل التنكس.

تستخدم الحلول المقترحة القفز / الحرق ، القفز / الترقق. ولترميز التسلسل النهائي (الترميز) ، يتم استخدام تقنية أخرى ، غالبًا ما تستخدم للتغلب على هذه المشكلة. لا يمكن استخدام التخليط لإنشاء تسلسل مفتوح (غير محدود) مع تباعد منخفض.


الشكل 3. الشكل (11،13) - سلسلة هولتون من الواضح أنها ليست تسلسل تباعد منخفض (يسار). كما أنها ليست مكررة العودية (11،13) ، نتيجة (في الوسط). بعض التتابعات العودية المضافة ثنائية الأبعاد التي تستخدم أرقام غير منطقية معروفة جيدة جدًا (يمين).

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

لذلك مرة أخرى ، في $$$د$ القياسات:

• تتطلب تسلسل Kronecker النموذجي اختيارًا $$$د$ أرقام غير منطقية مستقلة خطيا ؛
• يتطلب تسلسل هولتون $$$د$ الأعداد الصحيحة الزوجية المتبادلة؛ لكن
• يتطلب تسلسل السمور اختيارًا $$$د$ أرقام دليل.

تسلسل جديد $$$R_d$ - الوحيد $$$د$ تسلسل شبه عشوائي الأبعاد مع اختلاف التباعد ، لا تتطلب اختيار المعلمات الأساسية.

تعميم النسبة الذهبية

في هذا الجزء سأتحدث عن كيفية بناء فصل جديد $$$د$ - تسلسل مفتوح (لا نهائي) ذو أبعاد منخفضة مع اختلاف التباعد ، لا يتطلب اختيارًا للمعايير الأساسية ، وله خصائص ممتازة من التباعد المنخفض.

هناك العديد من الطرق لتعميم تسلسل فيبوناتشي و / أو النسبة الذهبية. الطريقة المقترحة أدناه لتعميم النسبة الذهبية ليست جديدة [ Krchadinac، 2005 ]. بالإضافة إلى ذلك ، يرتبط كثير الحدود المميزة بالعديد من مناطق الجبر ، بما في ذلك أرقام بيرون وأرقام بيسو فياجياراجان . ومع ذلك ، فإن العلاقة الواضحة بين هذا النموذج المعمم وبناء متواليات عالية الأبعاد مع اختلاف متباعد جديدة في هذا الصدد. نحدد وجهة نظر معممة للنسبة الذهبية $$$\ phi_d$ كجذر إيجابي فريد من نوعه $$$x ^ {d + 1} = x + 1$ . هذا هو ،

ل $$$د = 1 دولا$ ، $$$\ phi_1 = 1.61803398874989484820458683436563 ...$ ، وهي النسبة الذهبية الكنسي.

ل $$$د = 2 دولا$ ، $$$\ phi_2 = 1.32471795724474602596090885447809 ...$ . تسمى هذه القيمة غالبًا بالبلاستيك ولها خصائص جميلة (انظر أيضًا هنا ). من المفترض أن تكون هذه القيمة على الأرجح هي الأمثل للمشكلة المقابلة ثنائية الأبعاد [ Hensley، 2002 ].

ل $$$د = 3 دولارا$ ، $$$\ phi_3 = 1.220744084605759475361685349108831 ...$

ل $$$د> 3 دولا$ ، على الرغم من أن جذور هذه المعادلة لا تحتوي على شكل جبري مغلق ، يمكننا بسهولة الحصول على تقريب رقمي إما بالطرق القياسية ، على سبيل المثال ، طريقة نيوتن ، أو عن طريق الإشارة إلى التسلسل التالي $$$R_d (\ phi_d)$ :

$$

$$t_0 = t_1 = ... = t_ {d} = 1 ؛$$

$$

$$t_ {n + d + 1} \؛ = \؛ t_ {n + 1} + t_n، \ quad \ textrm {for} \؛ ن = 1،2،3 ، ..$$

هذا التسلسل معين من الثوابت $$$\ phi_d$ تم تسمية المهندس المعماري والراهب هانز فان دي لان في عام 1928 باسم " الأرقام التوافقية ". يمكن التعبير عن هذه المعاني الخاصة بأناقة كما يلي:

$$

$$\ phi_1 = \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1 + ...}}}}}$$

$$

$$\ phi_2 = \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1 + ...}}}}}}$$

$$

$$\ phi_3 = \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1 + ...}}}}}}$$

لدينا أيضا خاصية أنيقة جدا التالية:

$$

$$\ phi_d = \ lim_ {n \ to \ infty} \؛ \؛ \ frac {t_ {n + 1}} {t_n}$$

هذا التسلسل ، الذي يُسمى أحيانًا تسلسل فيبوناتشي المعمم أو المؤجل ، تمت دراسته بعمق كبير [ As، 2004 ، Wilson، 1993 ] ، والتسلسل الخاص بـ $$$د = 2 دولا$ غالبًا ما يطلق عليه تسلسل بادوفان [ ستيوارت ، 1996 ، OEIS A000931 ] ، والتسلسل $$$د = 3 دولارا$ المدرجة في [ OEIS A079398 ]. كما ذكر أعلاه ، فإن المهمة الرئيسية لهذا المنشور هي وصف العلاقة الصريحة بين هذا التسلسل المعمم والبناء $$$د$ تسلسل الأبعاد مع اختلاف التباعد.

النتيجة الرئيسية: اللامعلمية التالية $$$د$ الأبعاد المفتوحة (لانهائية) التسلسل $$$R_d (\ phi_d)$ لديه خصائص تباين منخفضة ممتازة مقارنة بالطرق الأخرى الموجودة.

$$

$$\ mathbf {t} _n = \ {n \ pmb {\ alpha} \} ، \ quad n = 1،2،3 ، ...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} = (\ frac {1} {\ phi_d} ، \ frac {1} {\ phi_d ^ 2} ، \ frac {1} {\ phi_d ^ 3} ، ... \ frac {1} {\ phi_d ^ d})$$

$$

$$\ textrm {and} \؛ \ phi_d \ \ textrm {هو جذر إيجابي فريد} x ^ {d + 1} = x + 1$$

لبعدين ، وهذا التسلسل المعمم ل $$$ن = 150 دولا$ هو مبين في الشكل 1. من الواضح أن النقاط موزعة بالتساوي بشكل أكبر $$ - النتائج من (2 ، 3) - تسلسلات هولتون ، متسلسلات كرونكر بناءً على $$$(\ sqrt {3}، \ sqrt {7})$ ، تسلسل Niederreiter و Sable. (نظرًا لتعقيد تسلسل Niederreiter و Sable ، تم حسابهما في Mathematica باستخدام رمز الملكية الذي توفره Intel.) هذا هو نوع التسلسل الذي يكون فيه المتجه الأساسي $$$\ pmb {\ alpha}$ هي وظيفة ذات قيمة مادية واحدة ، غالبًا ما تسمى تسلسل Korobov [Korobov ، 1959]

انظر مرة أخرى إلى الشكل 1 لمقارنة مختلف تسلسلات شبه عشوائية متباينة الأبعاد.

الرمز والعروض التوضيحية

في بعد واحد ، والرمز الزائف ل $$$ن$ عضو ( $$$ن$ = 1،2،3 ، ....) كما هو محدد

 g = 1.6180339887498948482 a1 = 1.0/g x[n] = (0.5+a1*n) %1 

في بعدين ، والرمز الزائف للإحداثيات $$$x$ و $$$ذ$$$$ن$ عضو ( $$$ن$ = 1،2،3 ، ....) يتم تعريفها على أنها

 g = 1.32471795724474602596 a1 = 1.0/g a2 = 1.0/(g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 

الكود الكاذب في ثلاثة أبعاد للإحداثيات $$$x$ ، $$$ذ$ و $$$z$$$$ن$ عضو ( $$$ن$ = 1،2،3 ، ....) كما هو محدد

 g = 1.22074408460575947536 a1 = 1.0/g a2 = 1.0/(g*g) a3 = 1.0/(g*g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 z[n] = (0.5+a3*n) %1 

قالب رمز بايثون. (لاحظ أن صفائف وحلقات Python تبدأ من الصفر!)

 import numpy as np # Using the above nested radical formula for g=phi_d # or you could just hard-code it. # phi(1) = 1.61803398874989484820458683436563 # phi(2) = 1.32471795724474602596090885447809 def phi(d): x=2.0000 for i in range(10): x = pow(1+x,1/(d+1)) return x 

 # Number of dimensions. d=2 # number of required points n=50 g = phi(d) alpha = np.zeros(d) for j in range(d): alpha[j] = pow(1/g,j+1) %1 z = np.zeros((n, d)) # This number can be any real number. # Common default setting is typically seed=0 # But seed = 0.5 is generally better. for i in range(n): z[i] = (seed + alpha*(i+1)) %1 print(z) 

كتبت الرمز بطريقة تتوافق مع التدوين الرياضي المستخدم في هذا المنشور. ومع ذلك ، لأسباب تتعلق ببرمجة الاتفاقيات و / أو الكفاءة ، تجدر الإشارة إلى بعض التعديلات. أولا ، منذ ذلك الحين $$ هو تسلسل العودية المضافة ، صياغة بديلة $$$z$ الذي لا يتطلب مضاعفة النقطة العائمة ويحافظ على دقة عالية لكبير جداً $$$ن$ لديه النموذج

 z[i+1] = (z[i]+alpha) %1 

ثانياً ، في اللغات التي يمكن أن تتجه ، يمكن توجيه رمز الدالة الكسرية كما يلي:

 for i in range(n): z[i] = seed + alpha*(i+1) z = z %1 

أخيرًا ، يمكننا استبدال هذه الإضافات بأرقام الفاصلة العائمة والأعداد الصحيحة بضرب جميع الثوابت في $$$2 ^ {32}$ ، ثم تغيير frac (.) تعمل وفقًا لذلك. فيما يلي عروض تجريبية للشفرة المصدرية التي أنشأها أشخاص آخرون بناءً على هذا التسلسل:

• beta.observablehq.com/@jrus/plastic-sequence ، تم تطويره بواسطة Jake Rus :
• www.shadertoy.com/view/4dtBWH ، المطور @ Stirners Host (XGKICK):

الحد الأدنى بعد التعبئة

جديد $$ - النتيجة هي شبه تسلسل ثنائي الأبعاد شبه عشوائي مع اختلاف متباعد حيث يتم تقليل الحد الأدنى لمسافة التعبئة فقط إلى $$$1 / \ sqrt {n}$ .

على الرغم من أن التحليل الفني القياسي لحساب التباين هو تقييم $$$د ^ *$ - التناقضات ، سنذكر أولاً بضع طرق هندسية أخرى (وربما أكثر بديهية!) لإظهار مدى تفضيل التسلسل الجديد على الطرق القياسية الأخرى. إذا أشرنا إلى المسافة بين النقاط $$$i$ و $$$j$ ل $$$d_ {ij}$ و $$$d_0 = \ textrm {inf} \؛ d_ {ij}$ ثم يظهر الرسم البياني أدناه كيف يتغير $$$d_0 (n)$ ل $$$R$ -نتيجة ، (2،3) - تسلسلات Holton و Sable و Niederreiter وتسلسلات عشوائية. ويمكن ملاحظة ذلك في الشكل 6.

كما في الشكل السابق ، يتم ضبط قيمة المسافة الدنيا بواسطة المعامل $$$1 / \ sqrt {n}$ . قد تلاحظ ذلك بعد $$$ن = 300 دولا$ نقاط في تسلسل عشوائي (أخضر) من شبه المؤكد أن نقطتين تظهران قريبتان جدًا من بعضهما البعض. يُلاحظ أيضًا أنه على الرغم من أن نتائج هولتون (2،3) أفضل بكثير من أخذ العينات العشوائية ، إلا أنها للأسف تنخفض إلى الصفر. بالنسبة لتسلسل Sable ، ينخفض ​​سبب التطبيع إلى الصفر $$$d_0 دولا$ يكمن في حقيقة أن سابل نفسه أظهر أن تسلسل سابل يسقط بسرعة $$$/ ن$ - وهذا أمر جيد ، ولكن من الواضح أنه أسوأ بكثير من $$ مما يقلل فقط من قبل $$$1 / \ sqrt {n}$ .

للتسلسل $$$R (\ phi_2)$ (الأزرق) الحد الأدنى للمسافة بين نقطتين يقع باستمرار في الفاصل الزمني من $$$0.549 / \ sqrt {n}$ قبل $$ . لاحظ أن القطر الأمثل عند 0.868 يتوافق مع عامل التعبئة بنسبة 59.2٪. قارن هذا مع العبوات الأخرى من الدوائر .

نلاحظ أيضا أن Bridson Poisson أخذ العينات القرص ، وهو غير قابل للتوسيع ل $$$ن$ وعادة ما ينصح به بشكل افتراضي ، فإنه لا يزال يخلق عامل تعبئة بنسبة 49.4 ٪. يجدر النظر في هذا المفهوم $$$d_0 دولا$ يربط بإحكام التسلسل $$$\ phi_d$ تناقض منخفض مع أعداد / ناقلات ضعيفة التقريب في $$$د$ القياسات [ هينسلي ، 2001 ]. على الرغم من أننا لا نعرف سوى القليل عن الأرقام التقريبية السيئة في بعدين ، والبناء $$$\ phi_d$ يمكن أن توفر لنا نظرة جديدة على أعداد تقريبية سيئة في أبعاد أعلى.


الشكل 4. الحد الأدنى للمسافة الزوجية لمختلف التسلسلات مع اختلاف التباعد. لاحظ ذلك $$ - التسلسل (الأزرق) هو الخيار الأفضل دائمًا ؛ بالإضافة إلى ذلك ، هذا هو التسلسل الوحيد الذي لا تميل فيه المسافة الطبيعية إلى الصفر عند $$$n \ rightarrow \ infty$ . يحتل تسلسل هولتون (البرتقالي) المركز الثاني ، وتسلسلتا سابل (الأخضر) ونيديرييتر (أحمر) ليست جيدة جدًا ، لكنها لا تزال أفضل بكثير من العشوائية (الأرجواني). أكبر ، كلما كان ذلك أفضل ، لأن هذا يتوافق مع مسافة التعبئة والتغليف أطول.

مخططات فورونوي

هناك طريقة أخرى لتصور التوزيع الموحد للنقاط وهي إنشاء مخطط فورونوي من الأول $$$ن$ نقاط من تسلسل ثنائي الأبعاد مع تلوين لاحق لكل منطقة اعتمادا على منطقتها. يوضح الشكل أدناه مخططات الألوان Voronoi لـ (i) $$ عواقب (2) (2،3) سلاسل هولتون ، (3) العودية الأولية ؛ و (رابعا) أخذ عينات عشوائية بسيطة. لجميع الشخصيات تستخدم مقياس اللون نفسه. هنا مرة أخرى ، فمن الواضح أن $$ يوفر التسلسل توزيعًا أكثر انتظامًا من تسلسل Holton أو أخذ عينات عشوائية بسيطة. الصورة هي نفسها كما هو مذكور أعلاه ، ملونة فقط وفقًا لعدد القمم في كل خلية Voronoi. ليس من الواضح هنا فقط $$$R$ - يوفر التسلسل توزيعا أكثر اتساقا من Holton أو أخذ عينات عشوائية بسيطة ، ولكن حقيقة أن القيم الأساسية أكثر وضوحا $$$ن$ تتكون من السداسي فقط! إذا أخذنا في الاعتبار تسلسل فيبوناتشي المعمم ، إذن $$$A_1 = A_2 = A_3 = 1 ؛ \ quad A_ {n + 3} = A_ {n + 1} + A {n}$ . هذا هو $$$A_n$ :

$$عرض $$ $$ \ تبدأ {array} {r} 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 \\ 9 & \ textbf {12} & 16 & 21 & 28 & 37 & \ textbf {49} & 65 & 86 \\ 114 & \ textbf {151 } & 200 & 265 & 351 & 465 & \ textbf {616} & 816 & 1081 \\ 1432 & \ textbf {1897} & 2513 & 3329 & 4410 & 5842 & \ textbf {7739} & 10252 & 13581 \\ 17991 & & textbf {23833} & 31572 & 414024 & 7 {97229} & 128801 & 170625 \\ 226030 & \ textbf {299426} & 396655 & 525456 & 696081 & 922111 & \ textbf {1221537} & 1618192 & 2143648 \\ \ end {array} $$ عرض $$

كل القيم فيها $$$n = A_ {9k-2}$ او $$$n = A_ {9k + 2}$ تتكون فقط من السداسي.


الشكل 4. رسم تصوري لشكل مخططات فورونوي بناءً على مساحة كل مضلع فورونوي لـ (i) $$ عواقب (2) (2،3) - النتائج على أساس الأعداد الأولية ؛ (3) (2،3) - نتيجة لهولتون ، (رابعا) Niederraiter ؛ (5) السمور ؛ و (رابعا) أخذ عينات عشوائية بسيطة. تشير الألوان إلى عدد جوانب كل مضلع Voronoi. أكرر: من الواضح أن $$$R (\ phi)$ -توفر النتيجة توزيعًا أكثر تناسقًا من أي تسلسل آخر بانحراف منخفض.

في بعض القيم $$$ن$ شبكة فورونوي ل $$ ، النتيجة تتكون فقط من السداسي.

الشكل 5. تصوّر شكل مخططات فورونوي بناءً على عدد جوانب كل مضلع فورونوي لـ (i) $$ عواقب (2) (2،3) - النتائج على أساس الأعداد الأولية ؛ (3) (2،3) - نتيجة لهولتون ، (رابعا) Niederraiter ؛ (5) السمور ؛ و (رابعا) أخذ عينات عشوائية بسيطة. تشير الألوان إلى عدد جوانب كل مضلع Voronoi. أكرر: من الواضح أن $$$R (\ phi)$ -توفر النتيجة توزيعًا أكثر تناسقًا من أي تسلسل آخر بانحراف منخفض.

Delaunay تبليط شبه عشوائي لطائرة

$$$R$ - النتيجة هي التسلسل شبه العشوائي الوحيد المنخفض الاختلاف الذي يمكن استخدامه لإنشاء $$$د$ -الألبسة شبه الدورية الأبعاد باستخدام شبكة Delaunay لها.

يوفر تثليث Delaunay ، الذي يشبه Count Voronoi ، فرصة للنظر في هذه التوزيعات بشكل مختلف. ومع ذلك ، الأهم من ذلك ، يوفر تثليث Delaunay طريقة جديدة لإنشاء تبليط شبه دوري (تبليط الفسيفساء) للطائرة. ديلوناي تثليث $$ - توفر النتائج نمطًا موحدًا أكثر من تسلسل Holton أو أخذ العينات العشوائية. على وجه الخصوص ، إذا تم تنفيذ التثليث Delaunay من توزيعات نقطة ، حيث $$$ن$ يساوي أي من تسلسل فيبوناتشي المعمم: $$$A_N = $ 1،1،1،2،3،4،5،7،9،12،16،21،28،37 $ ..$ ، ثم يتألف تثليث Delaunay من ثلاثة مثلثات متماثلة متطابقة ، أي متوازيات متوازية (rhomboids)! (باستثناء المثلثات التي لها رأس شائع مع بدن محدب.) علاوة على ذلك ،

في القيم $$$n = A_k$ تثليث ديلوناي $$ - تشكل النتائج أمورا شبه دورية ، يتألف كل منها من ثلاثة مثلثات أساسية فقط (حمراء وصفراء وزرقاء) ، ترتبط دائمًا في أزواج وتشكل قرميد شبه دوري (رصيف) محدد جيدًا للمستوى بثلاثة متوازيات (المعينية).

الشكل 6. التصور من التثليث Delaunay ل (ط) $$$R (\ phi_2)$ عواقب (2) (2،3) سلاسل هولتون ، (3) العودية الأولية ؛ و (رابعا) أخذ عينات عشوائية بسيطة. تشير الألوان إلى مساحة كل مثلث. تستخدم الرسوم البيانية الأربعة نفس المقياس. وهنا مرة أخرى ، من الواضح ذلك $$$R (\ phi_2)$ -توفر النتيجة توزيعًا أكثر تناسقًا من أي تسلسل آخر بانحراف منخفض.
لاحظ ذلك $$ بناء على $$$\ phi_2 = 1.32471795724474602596$ كونه أصغر عدد من piso ، (أ $$$\ phi = 1.61803 ...$ هو أكبر عدد من بيزو). إن الربط بين البلاط شبه الفصلي والأرقام التربيعية والمكعبية لـ Piso ليس جديدًا [ Elkharrat و Masakova] ، لكنني أعتقد أنه لأول مرة تم إنشاء بلاط شبه شبه دوري على أساس $$$\ phi_2 = 1.324719 ...$ .

توضح الرسوم المتحركة أدناه كيف تتداخل شبكة Delaunay مع التسلسل $$ يتغير مع الإضافة التدريجية للنقاط. لاحظ أنه عندما يكون عدد النقاط مساويًا لعضو في تسلسل فيبوناتشي المعمم ، فإن شبكة Delaunay بأكملها تتكون فقط من متوازيات متوازية حمراء وزرقاء وصفراء (المعينية) ، مرتبة في شكل شبه شبه دوري.


الشكل 7

على الرغم من أن ترتيب المتوازيات الحمراء يدل على انتظام كبير ، يمكن للمرء أن يرى بوضوح أن يتم وضع متوازي الاضلاع الأزرق والأصفر في شكل شبه دوري. يمكن رؤية طيف فورييه لهذه الشبكة في الشكل 11 ؛ فهو يمثل أطياف النقطة الكلاسيكية. (لاحظ أن التسلسل العودية القائم على الأعداد الأولية يبدو أيضًا شبه دوري ، بمعنى أنه نمط غير متكرر مرتب. ومع ذلك ، فإن نمطه في الفاصل الزمني $$$ن$ ليس ثابتا جدا ، ويعتمد أيضا بشكل حاسم على اختيار المعلمات الأساسية. لذلك ، سوف نركز اهتمامنا على الأعمدة شبه الدورية فقط بالتسلسل $$ .) يتكون من ثلاثة مثلثات فقط: أحمر ، أصفر ، أزرق. لاحظ أنه في هذا التسلسل $$$R (\ phi_2)$ جميع المتوازيات من كل لون لها نفس الحجم والشكل. نسبة العرض إلى الارتفاع لهذه المثلثات الفردية أنيقة بشكل لا يصدق. وهي

$$

$$\ textrm {Area (red): Area (yellow): Area (blue)} = 1: \ phi_2: \ phi_2 ^ 2$$

الأمر نفسه ينطبق على التردد النسبي للمثلثات:

$$

$$f (\ textrm {red}): f (\ textrm {yellow}): f (\ textrm {blue}) = 1: \ phi_2: 1$$

من هذا ، فإن إجمالي المساحة النسبية التي تغطيها هذه المثلثات الثلاثة في الفضاء هو:

$$

$$f (\ textrm {red}): f (\ textrm {yellow}): f (\ textrm {blue}) = 1: \ phi_2 ^ 2: \ phi_2 ^ 2$$

يمكن أيضًا افتراض أننا قادرون على إنشاء هذا التجانب شبه الدوري من خلال الاستبدال استنادًا إلى التسلسل A. أي

$$

$$A \ rightarrow B؛ \ quad B \ rightarrow C؛ \ quad C \ rightarrow BA$$

لثلاثة أبعاد ، إذا أخذنا في الاعتبار تسلسل فيبوناتشي المعمم ، إذن $$$B_1 = B_2 = B_3 = B_4 = 1 ؛ \ quad B_ {n + 4} = B_ {n + 1} + B {n}$ . هذا هو

$$

$$B_n = \ {1،1،1،1،2،2،2،3،4،4،5،7،8،9،12،15،17،21،27،32،38،48،59 ، 70،86،107،129، ...$$

في بعض القيم $$$n = B_k$ شبكة Delaunay ثلاثية الأبعاد مرتبطة بالتسلسل $$$R_3 دولا$ ، ويحدد شعرية وضوح الشمس شبه الدورية.

التعبئة والتغليف حسب الطلب ، الجزء 2

الشكل أدناه يوضح الأول $$$ن = 2500 دولا$ نقاط لكل تسلسل ثنائي الأبعاد مع اختلاف التباعد. علاوة على ذلك ، تكون كل خلية من الخلايا 50 × 50 = 2500 بلون أخضر فقط إذا كانت تحتوي على نقطة واحدة بالضبط . أي أنه كلما زاد عدد المربعات الخضراء ، زاد توزيع 2500 نقطة في 2500 خلية. النسبة المئوية للخلايا الخضراء لكل من الأرقام هي كما يلي: $$ (75 ٪) ، هولتون (54 ٪) ، كرونكر (48 ٪) ، Niederreiter (54 ٪) ، السمور (49 ٪) وعشوائية (38 ٪).

موجات الصوت

للمتعة فقط ، بناءً على طلب قارئ أخبار هاكر ، قمت بنمذجة كيف يمكن أن يبدو كل توزيعات النقاط شبه العشوائية هذه! لقد استخدمت وظيفة Listplay من Mathematica: " ListPlay [{a1، a2، ...}] تنشئ كائنًا يعيد إنتاج نفسه كصوت ، ويتم إعطاء السعة كتسلسل من المستويات." لذلك ، بدون أي تعليقات ، سأسمح لك بأن تقرر بنفسك أي من تفضله من بين التوزيعات شبه أحادية البعد (أحادية) والتوزيعات شبه العشوائية ثنائية الأبعاد (استريو).

	أحادي	ستيريو
عشوائية	http://extremelearning.com.au/wp-content/uploads/2018/04/random_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/random_2D.mp3
السمور	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_2D.mp3
نيدرييتر	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_2D.mp3
هولتون	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_2D.mp3
كرونيكر	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_2D.mp3
ر	http://extremelearning.com.au/wp-content/uploads/2018/04/R1_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/R2_2D.mp3

مجموعات متعددة التباين المنخفض

توضح بعض متواليات الاختلاف المنخفض ما يسمى "الاختلاف المنخفض متعدد الطبقات". حتى هذه اللحظة ، افترضنا أننا عندما نحتاج إلى التوزيع بالتساوي قدر الإمكان $$$ن$ نقاط ، ثم كل النقاط هي نفسها والتي لا يمكن تمييزها عن بعضها البعض. ومع ذلك ، في العديد من الحالات ، هناك أنواع مختلفة من النقاط. نحن نعتبر مشكلة التوزيع الموحد $$$ن$ بحيث لا يتم توزيع جميع النقاط فقط بالتساوي ، ولكن أيضًا نقاط من نفس الفئة. على وجه الخصوص ، افترض أن هناك $$$n_k$ اكتب النقاط $$$ك$ ، (أين $$$n_1 + n_2 + n_3 + ... + n_k = n$ ) ، ثم توزيع multiset مع توزيع منخفض هو التوزيع الذي في كل منها $$$n_k$ نقاط موزعة بالتساوي. في حالتنا ، وجدنا ذلك $$$R$ -تسلسل وتسلسل Holton سهل التكيف مع تسلسل مجموعات متعددة مع اختلاف تباعد ، ببساطة عن طريق وضع نقاط بالتناوب من كل نوع.

يوضح الشكل أدناه كيف يتم توزيعها $$$ن = 150 دولا$ النقاط ، بينما 75 باللون الأزرق و 40 من الفلفل الأخضر ، و 25 باللون الأخضر ، و 10 باللون الأحمر. للحصول على تسلسل تكراري إضافي ، يتم حل هذا بشكل تافه: أول 75 عضوًا يتطابقون ببساطة مع اللون الأزرق ، ومن 40 إلى البرتقالي ، ومن 25 إلى الأخضر ، وآخر 10 إلى النقاط الحمراء. تعمل هذه التقنية تقريبًا لتسلسلات Holton و Kronecker ، ولكنها تؤدي أداءً سيئًا للغاية في تتابعات Niederreiter و Sable. علاوة على ذلك ، لا توجد تقنيات معروفة لتوليد توزيعات النقاط متعددة النطاق في تسلسل Niederreiter و Sable. هذا يدل على أن توزيعات النقاط متعددة الطبقات ، على سبيل المثال ، مثل عيون الدجاج ، يمكن الآن وصفها وصنعها مباشرة باستخدام تسلسلات ذات تباعد منخفض.

تسلسل $$ هو عبارة عن تسلسل شبه عشوائي منخفض الاختلاف يوفر سهولة في بناء اختلاف متعدد الطبقات.

الرقم 9. تسلسل متعدد النطاقات مع اختلاف التباعد. في التسلسل $$$R$ لا يتم توزيع جميع النقاط فقط بالتساوي ، ولكن أيضًا نقاط كل لون على حدة.

شبه نقاط عشوائية على الكرة

في مجالات رسومات الكمبيوتر والفيزياء ، غالبًا ما يكون من الضروري توزيع نقاط على سطح كرة ثلاثية الأبعاد بالتساوي قدر الإمكان. عند استخدام تسلسلات شبه عشوائية مفتوحة (غير محدودة) ، يتم تقليل هذه المشكلة فقط إلى وضع نقاط شبه عشوائية موزعة بشكل موحد في مربع وحدة على سطح الكرة باستخدام إسقاط لامبرت المتساوي. إسقاط لامبرت القياسية تحويل وضع نقطة $$$(u، v) \ in U [0،1] \ to (x، y، z) \ in S ^ 2$ لديه النموذج:

$$

$$(x، y، z) = (\ cos \ lambda \ cos \ phi، \ cos \ lambda \ sin \ phi، \ sin \ lambda)$$

$$

$$\ textrm {where} \ quad \ cos (\ lambda - \ pi / 2) = (2u-1)؛ \ quad \ phi = 2 \ pi v$$

منذ هذا $$$\ phi_2$ -التسلسل مفتوح بالكامل ، فهو يتيح لك التقاط تسلسل لا حصر له من النقاط على سطح الكرة ، نقطة واحدة في وقت واحد. هذا يتناقض مع الطرق الأخرى ، مثل شعرية دوامة فيبوناتشي ، والتي تتطلب معرفة عدد النقاط مقدما. على الفحص البصري ، يمكننا أن نرى ذلك بوضوح مرة أخرى $$$ن = 1200 دولا$ جديد $$$R (\ phi_2)$ - يتم توزيع التسلسل بشكل أفضل بكثير من أخذ عينات Holton تراكب أو أخذ عينات Kronecker ، والذي بدوره يكون أكثر تجانسًا من أخذ العينات العشوائية.


الشكل 10

تردد رسومات الحاسوب

تعتمد معظم أساليب التدرج الحديثة (على سبيل المثال ، تدرج فلويد شتاينبرغ) على توزيع الأخطاء ، وهو ليس مناسبًا للمعالجة الموازية و / أو التحسين المباشر في وحدة معالجة الرسومات. في مثل هذه الحالات ، يُظهر التدرج الموضعي باستخدام أقنعة التدرج الثابتة (أي ، يعتمد تمامًا على الصورة المستهدفة) خصائص أداء ممتازة. ربما تستند أقنعة التدرج الأكثر شهرة والأكثر استخدامًا على مصفوفات باير ، ولكن الأحدث تحاول محاكاة خصائص الضوضاء الزرقاء عن قرب. تتمثل الصعوبة غير التافهة في إنشاء أقنعة التدرج استنادًا إلى تسلسلات تباعد منخفضة و / أو ضوضاء زرقاء في أن تسلسلات التباعد المنخفضة هذه تشير إلى عدد صحيح $$$Z$ إلى نقطة ثنائية الأبعاد في الفاصل الزمني $$$[0،1) ^ 2$ . , / $$$[0,1)$ . , $$$R$ -. (x,y) $$$I(x,y)$ , :

$$

$$I(x,y) = \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1);$$

$$

$$\textrm{} \quad \pmb{\alpha} =(\alpha_1,\alpha_2) = (\frac{1}{\phi_2}, \frac{1}{\phi_2^2})$$

$$

$$\textrm{} \; \phi_2\ \textrm{ - } x^3\;=x+1$$

$$$x = 1.32471795724474602596…$ ,

$$

$$\alpha_1 = 0.75487766624669276; \alpha_2 = 0.569840290998$$

, , frac(.) :

$$

$$T(z) =\begin{cases} 2z, & \text{if } 0\leq z <1/2 \\ 2-2z, & \text{if} 1/2 \leq z < 1 \end{cases}$$

$$

$$I(x,y) = T \left[ \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1) \right];$$

/ . ,

$$

$$\lim_{n \rightarrow \infty} \frac{A_n}{A_{n+1}} = 0.754878 ; \quad \lim_{n \rightarrow \infty} \frac{A_n}{A_{n+2}} = 0.56984$$

$$

$$A_n x + A_{n+1} y \; (\textrm{mod} A_{n+2}) \textrm{ for integers } \;\; x,y$$

R- , . , , .

, , ( ). , , , «Call of Duty» ( «Interleaved Gradient Noise»).

$$

$$I(x,y) = (\textrm{FractionalPart}[52.9829189*\textrm{FractionalPart}[0.06711056*x + 0.00583715*y]]$$

3 %1, , %1. , , , . «Lena» 256×256, . , . — Void-and-Cluster Poisson disc sampling. Void and cluster. [ ]. Interleaved gradient noise , , , $$$R$ -. , - . $$$R$ - , . R-:

• ! . . , $$$R$ - , R- .
• R- !
• R- , .
• , , R- , .
• $$$(I(x,y)$ , .

11. : (i) (ii) R-, ; (iii) R- ; (iv) (v) . R- . , R2 . , , R- , .

, (5) , () $$$R(\phi_5)$ -, (2,3,5,7,11)- . $$$1/ \sqrt[5]{n}$ . , « » , — $$$R_5$ -. $$$R(\phi_5)$ - $$$n \simeq 10^6$ $$$0.8/\sqrt{n}$ $$$0.631/\sqrt{n}$ .

$$$R_2$ — $$$d$ - , $$$n^{-1/d}$ .

12. , R- () (); (); (); (). , , , .

$$$s_n = |A-A_n|$ , $$$\sigma = \sqrt{d}$ ، $$$f(x) = \textrm{exp}(\frac{-x^2}{2d}), \; x \in [0,1]$ , : (i) $$$R_{\phi}$ (); (ii) (); (iii) (); (iv) (). , $$$n=10^6$ . , , $$$R$ - . , $$$R$ -.


13. - 8- . , . R- , .