इस लेख में, मैं एक नया कम-विचलन quasi-random अनुक्रम प्रस्तुत करता हूं जो आधुनिक अनुक्रमों, जैसे कि सेबल, निडरराइटर, आदि पर महत्वपूर्ण सुधार प्रदान करता है।


चित्र 1. निम्न विचलन वाले विभिन्न अर्ध-यादृच्छिक क्रमों की तुलना। ध्यान दें कि मेरे द्वारा प्रस्तावित $$$आर$ परिणाम अन्य सभी तरीकों की तुलना में अधिक समान रूप से वितरित अंक बनाता है। इसके अलावा, अन्य सभी तरीकों में बुनियादी मापदंडों के सावधानीपूर्वक चयन की आवश्यकता होती है, और गलत चयन के मामले में अध: पतन होता है (उदाहरण के लिए, ऊपरी हिस्से में)

इस लेख में शामिल विषय

• कम आयाम एक आयाम में अनुक्रम
• दो आयामों में कम विचलन विधि
• पैकिंग दूरी
• मल्टीस्केल्स कम विसंगति समूह
• एक गोले की सतह पर अर्ध-यादृच्छिक क्रम
• क्वासिपरियोडिक प्लेन टाइलिंग
• कंप्यूटर ग्राफिक्स में डीथरिंग मास्क

कुछ समय पहले, यह पोस्ट हैकर न्यूज़ होमपेज पर पोस्ट की गई थी। आप उसकी चर्चा वहां पढ़ सकते हैं।

परिचय: यादृच्छिक बनाम अर्ध यादृच्छिक

चित्रा 1 में, आप देख सकते हैं कि एक इकाई वर्ग के अंदर एक बिंदु के एक साधारण वर्दी यादृच्छिक नमूने के साथ, अंक का एक संचय मनाया जाता है, और बिना अंक ("सफेद शोर") वाले क्षेत्र भी दिखाई देते हैं। एक कम-विचलन quasi- यादृच्छिक अनुक्रम एक निर्धारक तरीके से लगातार बिंदुओं के निर्माण (अनंत) की एक विधि है, जो पूरे अंतरिक्ष ("नीला शोर) की एक समान कवरेज सुनिश्चित करते हुए संचय (विचलन) की संभावना को कम करता है।

एक आयाम में अर्ध-यादृच्छिक क्रम

एक आयाम में कम विचलन के साथ पूरी तरह से निर्धारित अर्ध-आयामी अनुक्रम बनाने के तरीके बहुत अच्छी तरह से अध्ययन किए गए हैं और सामान्य शब्दों में हल किए गए हैं। इस पोस्ट में, मैं मुख्य रूप से खुले (अनंत) दृश्यों पर विचार करूंगा, पहले एक आयाम में, और फिर उच्च आयामों पर आगे बढ़ूंगा। खुले अनुक्रमों (यानी, में एक्स्टेंसिबल) का मौलिक लाभ $$$एन$ ) इस तथ्य में निहित है कि यदि सदस्यों की एक सीमित संख्या के आधार पर कुल त्रुटियां बहुत बड़ी हैं, तो पिछले सभी परिकलित बिंदुओं को समाप्त किए बिना अनुक्रम का विस्तार किया जा सकता है। ओपन सीक्वेंस बनाने के कई तरीके हैं। आप विभिन्न प्रकारों को उनके मूल (हाइपर) मापदंडों के निर्माण की श्रेणियों में विभाजित कर सकते हैं:

• अपरिमेय अंश: क्रोनकर, रिचटमेयर, रामशव
• (पारस्परिक रूप से) अभाज्य संख्याएँ: वान डेर कॉर्प्यूट, होल्टन, फ़ोरेट
• इरेड्यूसिबल पोलिनोमिअल्स: निडरेराइटर
• आदिम बहुपद: सेबल

संक्षिप्तता के लिए, इस पोस्ट में मैं मुख्य रूप से नए additive पुनरावर्ती की तुलना करूंगा $$$आर$ - एक अनुक्रम जो पहली श्रेणी से संबंधित है, वह है तर्कहीन संख्याओं के आधार पर पुनरावर्ती तरीके (जिन्हें अक्सर क्रोनकर, वेइल या रिचटेमीयर अनुक्रम कहा जाता है), जो कि रैंक 1 अक्षांश हैं, और एक होलटन अनुक्रम, जो कि कैनोनिकल वन-आयामी वैन डेर कॉर्पेट अनुक्रम पर आधारित है। क्रोनकर विहित पुनरावर्ती अनुक्रम को इस प्रकार परिभाषित किया गया है:

$$

$$R_1 (\ Alpha): \; \; t_n = \ {s_0 + n \ Alpha \}, \ quad n = 1,2,3, ...$$

जहाँ $$$\ अल्फा$ - कोई भी तर्कहीन संख्या। ध्यान दें कि प्रविष्टि $$$\ {x \}$ भिन्नात्मक भाग को दर्शाता है $$$x$ । गणना में, यह फ़ंक्शन अक्सर के रूप में व्यक्त किया जाता है

$$

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

पर $$$s_0 = 0$ अनुक्रम के पहले कुछ सदस्य $$$R (\ phi)$ के बराबर:

$$

$$t_n = 0.618, \; 0.236, \; 0.854, \; 0.472, \; 0.090, \; 0.708, \; 0.327, \; 0.944, \; 0.562, \; 0.180, \; 798, \; 416, \; 0.034, \; 0.652, \; 0.271, \; 0.888, ...$$

यह ध्यान रखना महत्वपूर्ण है कि अर्थ $$$s_0$ अनुक्रम की सामान्य विशेषताओं को प्रभावित नहीं करता है, और लगभग सभी मामलों में शून्य के बराबर है। हालांकि, कंप्यूटिंग में विकल्प $$$s \ neq 0$ स्वतंत्रता की एक अतिरिक्त डिग्री प्रदान करता है, जो अक्सर उपयोगी होता है। अगर $$$s \ neq 0$ , तो अनुक्रम को अक्सर "स्थानांतरित जाली अनुक्रम" कहा जाता है। इस तथ्य के बावजूद कि डिफ़ॉल्ट रूप से $$$s = 0$ मेरा मानना ​​है कि सैद्धांतिक और व्यावहारिक विचार हैं जिनके लिए मूल्य मानक होना चाहिए $$$s = 1/2$ । मूल्य $$$\ अल्फा$ सबसे छोटी संभव विसंगति दे अगर $$$\ अल्फा = 1 / \ phi$ जहाँ $$$\ phi$ - यह स्वर्णिम अनुपात है। वह है

$$

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

यह ध्यान रखना दिलचस्प है कि अन्य मूल्यों की एक अनंत संख्या है। $$$\ अल्फा$ , जो हमें इष्टतम विसंगति प्राप्त करने की भी अनुमति देते हैं, और वे सभी मोबियस परिवर्तन द्वारा एक दूसरे से संबंधित हैं

$$

$$\ अल्फा '= \ frac {p \ Alpha + q} {r \ Alpha + s} \ quad \ textrm {सभी पूर्णांकों के लिए} \; p, q, r, s \ quad \ textrm {ऐसा}} | ps-qr | = 1 $$$

अब हम इस पुनरावर्ती विधि की तुलना प्रसिद्ध वैन डेर कोरपूत क्रमों के निर्वहन क्रम के विपरीत क्रम से करते हैं [ वैन डेर कोरपूत, 1935 ]। वैन डेर कॉरपोरेट अनुक्रम वास्तव में अनुक्रमों का एक परिवार है, जिनमें से प्रत्येक को एक अद्वितीय हाइपरपैरेट द्वारा परिभाषित किया गया है $$$ब$ । बी = 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 \ _ [0,1] $ मे$$

• अगर $$$\ {x_i \}$ बराबर हैं $$$i / n$ , यह आयतों का सूत्र है;
• अगर $$$\ {x_i \}$ बेतरतीब ढंग से चयनित, तो यह मोंटे कार्लो विधि है ; और
• अगर $$$\ {x_i \}$ एक निम्न विचलन वाले अनुक्रम के तत्व हैं, फिर यह अर्ध-मोंटे कार्लो विधि है ।

नीचे दिया गया ग्राफ़ विशिष्ट त्रुटि घटता दिखाता है। $$$s_n = | A-A_n |$ इस फ़ंक्शन से जुड़े एक निश्चित अभिन्न अंग को अनुमानित करने के लिए, $$$f (x) = \ textrm {exp} (\ frac {-x ^ 2} {2}), \; x \ [0,1] $ मे$ के लिए: (i) additive पुनरावर्तन से अर्ध-यादृच्छिक बिंदु, जहां $$$\ अल्फा = 1 / \ phi$ , (नीला); (ii) वैन डेर कॉरपुत अनुक्रम से अर्ध यादृच्छिक अंक, (नारंगी); (iii) अनियमित रूप से चयनित बिंदु, (हरा); (iv) सेबल अनुक्रम (लाल)।

इससे पता चलता है कि $$$n = 10 ^ 6$ यादृच्छिक नमूने के साथ अंक समाधान एक त्रुटि की ओर जाता है $$$\ simeq 10 ^ {- 4}$ , वैन डेर कोर्पुट अनुक्रम में त्रुटि होती है $$$\ simeq 10 ^ {- 6}$ , जबकि $$$R (\ phi)$ - अनुक्रम एक त्रुटि की ओर जाता है $$$\ simeq 10 ^ {- 7}$ उस में $$$\ sim$ वैन डेर कोर्पुट की त्रुटि से 10 गुना बेहतर और $$$\ sim$ (वर्दी) यादृच्छिक नमूना की तुलना में 1000 गुना बेहतर है।


चित्रा 2. विभिन्न अर्ध-यादृच्छिक मोंटे कार्लो विधियों का उपयोग करके एक आयामी संख्यात्मक एकीकरण की तुलना। जितना कम मूल्य, उतना बेहतर। नई $$$R_2$ - अनुक्रम (नीला) और सेबल अनुक्रम (लाल) स्पष्ट रूप से सबसे अच्छा है।

निम्नलिखित यहाँ उल्लेख के लायक हैं:

• यह इस ज्ञान से मेल खाती है कि समान रूप से समान रूप से यादृच्छिक नमूने के लिए त्रुटियों में कमी आती है $$$1 / \ sqrt {n}$ , और दोनों अर्ध-यादृच्छिक अनुक्रम के लिए त्रुटि को जाता है $$$1 / n$ ।
• के लिए परिणाम $$$R_1 (\ phi)$ परिणाम (नीला) और सेबल अनुक्रम (लाल) सबसे अच्छे हैं।
• ग्राफ दर्शाता है कि वैन डेर कॉरप्यूट अनुक्रम अच्छा प्रदान करता है, लेकिन एकीकरण कार्यों के लिए अविश्वसनीय रूप से सुसंगत परिणाम!
• यहां देखा जा सकता है कि सभी मूल्यों के लिए $$$एन$ अनुक्रम $$$R_1 (\ phi)$ वैन डेर कोर्पुट अनुक्रम की तुलना में बेहतर परिणाम देता है।

नया क्रम $$$R_1$ , जो कि सुनहरे अनुपात का उपयोग करके क्रोनकर अनुक्रम है, एक आयामी कैसैरिज़ोंम मोंटे कार्लो एकीकरण के तरीकों के लिए सबसे अच्छा विकल्प है (क्वासिरजैंडम मोंटे कार्लो, क्यूएमसी)।

यह भी ध्यान देने योग्य है कि यद्यपि $$$\ अल्फा = \ phi$ सैद्धांतिक रूप से एक इष्टतम विकल्प प्रदान करता है, $$$\ sqrt {2}$ इष्टतम के बहुत करीब, और लगभग किसी भी अन्य तर्कहीन मूल्य $$$\ अल्फा$ एक आयामी एकीकरण के लिए बेहतर त्रुटि घटता प्रदान करता है। यही कारण है कि यह बहुत बार उपयोग किया जाता है $$$\ Alpha = \ sqrt {p}$ किसी भी अभाज्य संख्या के लिए। इसके अलावा, गणना के दृष्टिकोण से, अंतराल में चयनित यादृच्छिक मूल्य $$$0 अल्फ़ा [$ 0,1] मे$ यह लगभग निश्चित रूप से (मशीन सटीकता की सीमा के भीतर) एक अपरिमेय संख्या होगी, और इसलिए यह कम विचलन वाले अनुक्रम के लिए एक अच्छा विकल्प है। दृश्य सुगमता के लिए, उपरोक्त आंकड़ा नीडेराइटर अनुक्रम के परिणाम नहीं दिखाता है, क्योंकि वे सोबोल अनुक्रमों के परिणामों से व्यावहारिक रूप से अप्रभेद्य हैं और $$$आर$ । इस पोस्ट में उपयोग किए जाने वाले Niederreiter और Sable अनुक्रम (उनके अनुकूलित पैरामीटर चयन के साथ) को गणितज्ञ में गणना की गई थी, जिसे प्रलेखन में "बंद स्वामित्व और पूरी तरह से अनुकूलित जनरेटर" कहा जाता है।

दो आयामों में अर्ध-यादृच्छिक क्रम

उच्च आयामों में एक कम विचरण के निर्माण के लिए अधिकांश आधुनिक विधियां बस संयोजन (घटक द्वारा घटक) $$$ड$ एक आयामी अनुक्रम। संक्षिप्तता के लिए, पोस्ट में हम मुख्य रूप से होल्टन अनुक्रम [ होल्टन, 1960 ], सेबल अनुक्रम, और $$$ड$ -डिमेंटर क्रोनकर सीक्वेंस।

Holton अनुक्रम सरल का उपयोग कर बनाया गया है $$$ड$ विभिन्न वन-आयामी वैन डेर कॉरपोरेट सीक्वेंस, जिसका आधार अन्य सभी के लिए पारस्परिक रूप से सरल है। यही है, वे युग्मक सहसंबंध संख्या हैं। एक शक के बिना, इसकी स्पष्ट सादगी और तर्क के कारण सबसे आम विकल्प पहले का विकल्प है $$$ड$ अभाज्य संख्या। (२.३) होल्टन अनुक्रम द्वारा परिभाषित पहले ६२५ अंकों का वितरण चित्र १ में दिखाया गया है। हालांकि कई द्वि-आयामी होल्टन अनुक्रम कम विचलन वाले दृश्यों के उत्कृष्ट स्रोत हैं, यह सर्वविदित है कि उनमें से कई बहुत समस्याग्रस्त हैं और निम्न विचलन का प्रदर्शन नहीं करते हैं। उदाहरण के लिए, चित्रा 3 से पता चलता है कि होल्टन (11,13)-परिणाम बहुत ध्यान देने योग्य लाइनें उत्पन्न करता है। मॉडल और समस्याग्रस्त जोड़े के चयन के तरीकों को विकसित करने के लिए महान प्रयास किए गए थे। $$$(p_1, p_2)$ । उच्च आयामों में, समस्या और भी जटिल हो जाती है।

उच्च आयामों का सामान्यीकरण करते समय, क्रोनकर पुनरावर्ती विधियां और भी अधिक कठिनाइयों का सामना करती हैं। हालांकि उपयोग कर रहा है $$$\ Alpha = \ sqrt {p}$ उत्कृष्ट एक-आयामी अनुक्रम बनाए जाते हैं, यहां तक ​​कि उन primes के जोड़े को ढूंढना बेहद मुश्किल है जो एक दो-आयामी मामले के आधार के रूप में उपयोग किए जा सकते हैं जो समस्याग्रस्त नहीं है! उदाहरण के लिए, वर्कअराउंड के रूप में अन्य प्रसिद्ध अपरिमेय संख्याओं का उपयोग करने का सुझाव दिया गया था $$$\ phi, \ pi, e, ...$ । वे मध्यम रूप से स्वीकार्य परिणाम प्रदान करते हैं, लेकिन आमतौर पर उपयोग नहीं किए जाते हैं, क्योंकि वे आमतौर पर सही ढंग से चयनित होलटन अनुक्रम के रूप में अच्छे नहीं होते हैं। इन अध: पतन समस्याओं को हल करने के लिए महान प्रयास किए जा रहे हैं।

प्रस्तावित समाधान स्किपिंग / बर्निंग, लीपिंग / थिनिंग का उपयोग करते हैं। और अंतिम दृश्यों के कोडिंग (स्क्रैचिंग) के लिए, एक और तकनीक का उपयोग किया जाता है, अक्सर इस समस्या को दूर करने के लिए उपयोग किया जाता है। कम विचलन के साथ एक खुला (अनंत) अनुक्रम बनाने के लिए स्क्रबिंग का उपयोग नहीं किया जा सकता है।


चित्रा 3. (11,13) -होल्टन अनुक्रम स्पष्ट रूप से कम विचलन अनुक्रम (बाएं) नहीं है। न ही यह additive पुनरावर्ती (11,13)-परिणाम (बीच में) है। कुछ द्वि-आयामी योगात्मक पुनरावर्ती अनुक्रम जो अच्छी तरह से ज्ञात अपरिमेय संख्याओं का उपयोग करते हैं, वे बहुत अच्छे (दाएं) हैं।

इसी तरह, सेबल अनुक्रम के आम तौर पर बेहतर परिणामों के बावजूद, इसकी जटिलता और, इससे भी महत्वपूर्ण बात यह है कि हाइपरपैरमीटर के बहुत सावधानी से चयन की आवश्यकता इसे इतना अनुकूल नहीं बनाती है।

तो फिर, में $$$ड$ आयाम:

• विशिष्ट क्रोनकर दृश्यों के लिए एक विकल्प की आवश्यकता होती है $$$ड$ रैखिक स्वतंत्र अपरिमेय संख्या;
• होल्टन अनुक्रम की आवश्यकता है $$$ड$ परस्पर प्रधान जोड़ीदार पूर्णांक; और
• सेबल अनुक्रम के लिए एक विकल्प की आवश्यकता होती है $$$ड$ गाइड नंबर।

नया क्रम $$$R_d$ - एकमात्र $$$ड$ कम विचलन के साथ आयामी अर्ध-यादृच्छिक अनुक्रम, बुनियादी मापदंडों की पसंद की आवश्यकता नहीं है।

स्वर्ण अनुपात का सामान्यीकरण

tl; dr इस भाग में मैं एक नई कक्षा बनाने के बारे में बात करूँगा $$$ड$ कम विचलन के साथ -Dimensional खुला (अनंत) अनुक्रम, मूल मापदंडों की पसंद की आवश्यकता नहीं है, कम विचलन के उत्कृष्ट गुण हैं।

फाइबोनैचि अनुक्रम और / या सुनहरे अनुपात को सामान्य करने के कई तरीके हैं। सुनहरे अनुपात को सामान्य बनाने के लिए नीचे प्रस्तावित विधि नई नहीं है [ क्रैचैडैक, 2005 ]। इसके अलावा, विशेषता बहुपद बीजगणित के कई क्षेत्रों से जुड़ा हुआ है, जिसमें पेरोन संख्या और पिसो-विजयराघवन संख्या शामिल हैं । हालांकि, इस सामान्यीकृत रूप और कम विचलन वाले उच्च-आयामी अनुक्रमों के निर्माण के बीच स्पष्ट संबंध इसमें नया है। हम सुनहरे अनुपात के एक सामान्यीकृत दृष्टिकोण को परिभाषित करते हैं $$$\ phi_d$ एक अद्वितीय सकारात्मक जड़ के रूप में $$$x ^ {d + 1} = x + 1$ । वह है,

के लिए $$$d = 1$ । $$$\ phi_1 = 1.61803398874989484820458683436563 ...$ , जो विहित स्वर्ण अनुपात है।

के लिए $$$d = 2$ । $$$\ phi_2 = 1.32471795724474602596090885447809 ...$ । इस मूल्य को अक्सर एक प्लास्टिक स्थिरांक कहा जाता है और इसमें सुंदर गुण होते हैं ( यहां भी देखें)। यह माना जाता है कि यह मान इसी दो-आयामी समस्या के लिए इष्टतम होने की संभावना है [ हेंसले, 2002 ]।

के लिए $$$d = 3$ । $$$\ phi_3 = 1.22074408460575947536361685349108831 ...$

के लिए $$$d> 3$ , हालांकि इस समीकरण की जड़ों में एक बंद बीजीय रूप नहीं है, हम आसानी से एक संख्यात्मक पद्धति प्राप्त कर सकते हैं या तो मानक तरीकों से, उदाहरण के लिए, न्यूटन की विधि, या निम्नलिखित अनुक्रम के लिए ध्यान देने योग्य है। $$$R_d (\ phi_d)$ :

$$

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

$$

$$t_ {n + d + 1} \; = \; t_ {n + 1} + t_n, \ quad \ textrm {for} \; n = 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 + sqrt [3] {1 + ...$$

$$

$$\ phi_3 = \ sqrt [4] {1+ \ 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}$$

इस अनुक्रम, जिसे कभी-कभी सामान्यीकृत या आस्थगित फाइबोनैचि अनुक्रम कहा जाता है, का गहराई से अध्ययन किया गया है [ जैसे, 2004 , विल्सन, 1993 ], और इसके लिए अनुक्रम $$$d = 2$ अक्सर पडोवन अनुक्रम [ स्टुअर्ट, 1996 , OEIS A000931 ], और अनुक्रम कहा जाता है $$$d = 3$ [ OEIS A079398 ] में सूचीबद्ध। जैसा कि ऊपर कहा गया है, इस पोस्ट का मुख्य कार्य इस सामान्यीकृत अनुक्रम और निर्माण के बीच स्पष्ट संबंध का वर्णन करना है $$$ड$ कम विचलन के साथ-आयामी आयाम।

मुख्य परिणाम: निम्नलिखित nonparametric $$$ड$ -डिमेटिक ओपन (अनंत) क्रम $$$R_d (\ phi_d)$ अन्य मौजूदा तरीकों की तुलना में उत्कृष्ट कम विसंगति विशेषताओं है।

$$

$$\ mathbf {t} _n = \ {n \ pmb {\ Alpha} \}, \ quad n = 1,2,3, ... $$$

$$

$$\ textrm {जहाँ} \ quad \ pmb {\ Alpha} = (\ frac {1} {\ phi_d}, \ frac {1} {\ phi_d ^ 2}, \ frac {1} {phi_d ^ 3}, ... \ frac {1} {\ phi_d ^ d})$$

$$

$$\ textrm {और} \; \ phi_d \ \ textrm {एक अद्वितीय सकारात्मक जड़ है} x ^ {d + 1} = x + 1$$

दो आयामों के लिए, यह सामान्यीकृत अनुक्रम है $$$n = 150$ चित्र 1 में दिखाया गया है। अंक स्पष्ट रूप से बहुत अधिक समान रूप से वितरित किए जाते हैं $$$R_2$ (2, 3) की तुलना में परिणाम -होल्टन अनुक्रम, क्रोनकर अनुक्रम पर आधारित हैं $$$(\ sqrt {3}, \ sqrt {7})$ , Niederreiter और Sable क्रम। (Niederreiter और Sable अनुक्रमों की जटिलता के कारण, उन्हें इंटेल द्वारा प्रदान किए गए एक मालिकाना कोड का उपयोग करके Mathematica में गणना की गई थी।) इस प्रकार का अनुक्रम जिसमें बेस वेक्टर है। $$$\ pmb {\ अल्फा}$ एक एकल सामग्री मूल्य का एक कार्य है, जिसे अक्सर कोरोबोव अनुक्रम कहा जाता है [कोरोबोव, 1959]

विभिन्न दो-आयामी, कम-विचलन quasi-random अनुक्रमों की तुलना करने के लिए चित्र 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 

पायथन कोड टेम्पलेट। (ध्यान दें कि पायथन एरे और लूप खरोंच से शुरू होता है!)

 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) 

मैंने कोड को इस तरह से लिखा है कि यह इस पोस्ट में प्रयुक्त गणितीय संकेतन के अनुरूप है। हालांकि, प्रोग्रामिंग सम्मेलनों और / या दक्षता के कारणों के लिए, कुछ संशोधनों का उल्लेख करने योग्य है। सबसे पहले, जब से $$$R_2$ एक additive पुनरावर्ती अनुक्रम है, वैकल्पिक सूत्रीकरण $$$z$ जिसे फ्लोटिंग पॉइंट गुणा की आवश्यकता नहीं होती है और बहुत बड़ी मात्रा में उच्च सटीकता बनाए रखता है $$$एन$ का रूप है

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

दूसरी बात, ऐसी भाषाओं में जो वेक्टर कर सकती हैं, एक भिन्नात्मक कार्य का कोड निम्नानुसार वेक्टरकृत किया जा सकता है:

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

अंत में, हम फ़्लोटिंग पॉइंट और पूर्णांक संख्याओं के इन जोड़ो को सभी स्थिरांक को गुणा करके बदल सकते हैं $$$2 ^ {32}$ , और फिर फ़्रेक (।) फ़ंक्शन को तदनुसार बदलना। इस क्रम के आधार पर अन्य लोगों द्वारा बनाए गए स्रोत कोड डेमो इस प्रकार हैं:

• beta.observablehq.com/@jrus/plastic- resultence , जेक रुस द्वारा विकसित:
• www.shadertoy.com/view/4dtBWH , डेवलपर @ स्टिरर्स होस्ट (XGKICK):

न्यूनतम पैकिंग दूरी

नई $$$R_2$ परिणाम केवल दो आयामी अर्ध है - एक कम विचलन के साथ यादृच्छिक अनुक्रम जिसमें न्यूनतम पैकिंग दूरी केवल तक कम हो जाती है $$$1 / \ sqrt {n}$ ।

यद्यपि विसंगति गणना के मानक तकनीकी विश्लेषण का मूल्यांकन करना है $$$d ^ *$ - विसंगतियां, हम पहले दूसरे ज्यामितीय (और शायद बहुत अधिक सहज!) तरीकों के एक जोड़े का उल्लेख करेंगे कि नए अनुक्रम अन्य मानक तरीकों के लिए कितना बेहतर है। यदि हम बिंदुओं के बीच की दूरी को निरूपित करते हैं $$$मैं$ और $$$ज$ के लिए $$$d_ {ij}$ , और $$$d_0 = \ textrm {inf} \; d_ {ij}$ फिर नीचे दिया गया चार्ट दिखाता है कि यह कैसे बदलता है $$$d_0 (n)$ के लिए $$$आर$ परिणाम, (2,3) - होल्टन, सेबल, नीडेराइटर अनुक्रम और यादृच्छिक क्रम। इसे चित्र 6 में देखा जा सकता है।

पिछले आंकड़े की तरह, गुणांक द्वारा न्यूनतम दूरी मान सामान्यीकृत किया जाता है $$$1 / \ sqrt {n}$ । आप उसके बाद नोटिस कर सकते हैं $$$n = 300$ एक यादृच्छिक अनुक्रम (हरे) में अंक लगभग निश्चित रूप से दो बिंदु दिखाई देते हैं जो एक दूसरे के बेहद करीब हैं। यह भी देखा जाता है कि यद्यपि होल्टन की (2,3)-परिणाम यादृच्छिक नमूने की तुलना में बहुत बेहतर है, यह भी दुर्भाग्य से, asymptotically शून्य तक कम हो जाती है। सेबल अनुक्रम के लिए, सामान्यीकरण का कारण शून्य तक कम हो जाता है $$$d_0$ इस तथ्य में निहित है कि सेबल ने स्वयं दिखाया था कि सेबल अनुक्रम एक गति से गिरता है $$$/ एन$ - जो अच्छा है, लेकिन जाहिर है कि बहुत बुरा है $$$R_2$ जो केवल घटता है $$$1 / \ sqrt {n}$ ।

अनुक्रम के लिए $$$R (\ phi_2)$ (नीला) दो बिंदुओं के बीच की न्यूनतम दूरी लगातार अंतराल में आती है $$$0.549 / \ sqrt {n}$ को $$$0.868 / \ sqrt {n}$ । ध्यान दें कि 0.868 का इष्टतम व्यास 59.2% के पैकिंग कारक से मेल खाता है। इसकी तुलना अन्य हलकों की पैकिंग से करें ।

यह भी ध्यान दें कि ब्रिडसन पोइसन डिस्क नमूना , जो कि विस्तार योग्य नहीं है $$$एन$ और आमतौर पर डिफ़ॉल्ट रूप से सिफारिश की जाती है, यह अभी भी 49.4% का एक पैकिंग कारक बनाता है। यह विचार करने योग्य है कि अवधारणा $$$d_0$ कसकर दृश्यों को बांधता है $$$\ phi_d$ कम अव्यक्त संख्या / वैक्टर के साथ कम विसंगति $$$ड$ माप [ हेंसले, 2001 ]। यद्यपि हम दो आयामों में खराब रूप से अनुमानित संख्याओं के बारे में कम जानते हैं, निर्माण $$$\ phi_d$ हमें उच्च आयामों में खराब अनुमानित संख्याओं पर एक नया रूप प्रदान कर सकता है।


चित्रा 4. कम विचलन के साथ विभिन्न दृश्यों के लिए न्यूनतम जोड़ीदार दूरी। ध्यान दें $$$R_2$ - अनुक्रम (नीला) हमेशा सबसे अच्छा विकल्प होता है; इसके अलावा, यह एकमात्र अनुक्रम है जिसमें सामान्यीकृत दूरी शून्य पर नहीं होती है $$$n \ rightarrow \ infty$ । होल्टन का क्रम (नारंगी) दूसरा स्थान लेता है, और सेबल (हरा) और नीडेराइटर (लाल) क्रम इतना अच्छा नहीं है, लेकिन फिर भी यादृच्छिक (बैंगनी) से बहुत बेहतर है। बड़ा, बेहतर, क्योंकि यह लंबी पैकेजिंग दूरी से मेल खाता है।

वोरोनोई आरेख

अंकों के समान वितरण की कल्पना करने का एक और तरीका है कि पहले से वोरोनोई आरेख बनाया जाए $$$एन$ अपने क्षेत्र के आधार पर प्रत्येक क्षेत्र के बाद के रंग के साथ एक द्वि-आयामी अनुक्रम के अंक। नीचे दिया गया आंकड़ा (i) के लिए वोरोनोई रंग चार्ट दिखाता है $$$R_2$ दृश्यों कर रहे हैं; (ii) (२,३) होल्टन क्रम, (iii) प्रधान पुनरावृत्ति; और (iv) सरल यादृच्छिक नमूनाकरण। सभी आंकड़ों के लिए एक ही रंग के पैमाने का उपयोग किया जाता है। यहाँ फिर से, यह स्पष्ट है कि $$$R_2$ अनुक्रम होल्टन अनुक्रम या सरल यादृच्छिक नमूने की तुलना में बहुत अधिक समान वितरण प्रदान करता है। चित्र ऊपर के समान है, केवल प्रत्येक वोरोनोई सेल में कोने की संख्या के अनुसार रंगीन है। यह न केवल यहाँ स्पष्ट है कि $$$आर$ - अनुक्रम होल्टन या सरल यादृच्छिक नमूने की तुलना में अधिक समान वितरण प्रदान करता है, लेकिन यह तथ्य कि प्रमुख मूल्य अधिक ध्यान देने योग्य हैं $$$एन$ केवल हेक्सागोन्स से मिलकर! यदि हम सामान्यीकृत फाइबोनैचि अनुक्रम पर विचार करते हैं, तो $$$A_1 = A_2 = A_3 = 1; \ Quad A_ {n + 3} = A_ {n + 1} + A {n}$ । वह है $$$ए_ एन$ :

$$$ $ प्रदर्शन $ $ \ _ {आरंभ} {सरणी} 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 \\ 9 & \ textbf {12} & 16 & 21 & 28 & 37 & \ _ & textbf {49 और 65 & 86 \\ 114 & \ textbf {151 ) {97229} और 128801 & 170625 \\ 226030 & \ textbf {299426} और 396655 & 525456 & 696081 & 922111 & \ textbf {1221537} और 1618192 & 2143648 \\ \ end {सरणी} $ $ $ $ $ $ डिस्प्ले प्रदर्शित

जिसमें सभी मान $$$n = A_ {9k-2}$ या $$$n = A_ {9k + 2}$ केवल हेक्सागोन्स से मिलकर।


चित्रा 4. (i) के लिए प्रत्येक वोरोनोई बहुभुज के क्षेत्र के आधार पर वोरोनोई आरेखों के आकार का दृश्य $$$R_2$ दृश्यों कर रहे हैं; (ii) (2,3) -प्राइम के आधार पर परिणाम; (iii) होल्टन के (२, ३) परिणाम, (iv) निडरराइटर; (v) सेबल; और (iv) सरल यादृच्छिक नमूनाकरण। रंग प्रत्येक वोरोनोई बहुभुज के पक्षों की संख्या का संकेत देते हैं। मैं दोहराता हूं: यह स्पष्ट है कि $$$R (\ phi)$ परिणाम एक कम विचलन के साथ किसी भी अन्य अनुक्रम की तुलना में बहुत अधिक समान वितरण प्रदान करता है।

कुछ मूल्यों पर $$$एन$ के लिए वोरोनोई ग्रिड $$$R_2$ परिणाम केवल हेक्सागोन्स के होते हैं।

चित्रा 5. प्रत्येक वोरोनोई बहुभुज (i) के पक्षों की संख्या के आधार पर वोरोनोई आरेखों के आकार का दृश्य $$$R_2$ दृश्यों कर रहे हैं; (ii) (2,3) -प्राइम के आधार पर परिणाम; (iii) होल्टन के (२, ३) परिणाम, (iv) निडरराइटर; (v) सेबल; और (iv) सरल यादृच्छिक नमूनाकरण। रंग प्रत्येक वोरोनोई बहुभुज के पक्षों की संख्या का संकेत देते हैं। मैं दोहराता हूं: यह स्पष्ट है कि $$$R (\ phi)$ परिणाम एक कम विचलन के साथ किसी भी अन्य अनुक्रम की तुलना में बहुत अधिक समान वितरण प्रदान करता है।

एक विमान के लिए Delaunay अर्ध-यादृच्छिक टाइलिंग

$$$आर$ परिणाम केवल कम-विचलन quasi-random अनुक्रम है जिसे बनाने के लिए उपयोग किया जा सकता है $$$ड$ अपने Delaunay जाल का उपयोग कर आयामी quasiperiodic झुकाव।

डेलॉनाय ट्राइंगुलेशन, जो काउंट वोरोनोई के समान है, इन वितरणों को अलग तरीके से देखने का अवसर प्रदान करता है। हालांकि, इससे भी महत्वपूर्ण बात यह है कि, डेलुनाय ट्राइंगुलेशन एक विमान के कैसिपरियोडिक टाइलिंग (मोज़ेक टाइलिंग) बनाने के लिए एक नई विधि प्रदान करता है। Delaunay त्रिकोण $$$R_2$ परिणाम Holton अनुक्रम या यादृच्छिक नमूने की तुलना में बहुत अधिक समान पैटर्न प्रदान करता है। विशेष रूप से, यदि बिंदु वितरण का विलंबुन त्रिभुज प्रदर्शन किया जाता है, जहां $$$एन$ किसी भी सामान्यीकृत फाइबोनैचि अनुक्रम के बराबर: $$$A_N = $ 1,1,1,2,3,4,5,7,9,12,16,21,28,37, ...$ , फिर डेलुनाय त्रिभुज में केवल तीन समान रूप से युग्मित त्रिभुज होते हैं, यानी समांतर चतुर्भुज (रॉमबॉइड्स)! (एक त्रिकोण के अलावा जो एक उत्तल पतवार के साथ एक सामान्य शीर्ष है।) इसके अलावा।

मूल्यों पर $$$n = A_k$ डेलुनाय त्रिभुज $$$R_2$ परिणाम के रूप में क्सीपेरियोडिक झुकाव होते हैं, जिनमें से प्रत्येक में केवल तीन मूल त्रिकोण (लाल, पीले, नीले) होते हैं, जो हमेशा जोड़े में जुड़े होते हैं और तीन समांतर चतुर्भुज (रॉमबॉइड्स) के साथ विमान के एक अच्छी तरह से परिभाषित कैसिपरियोडिक टाइलिंग (टाइलिंग) बनाते हैं।

चित्रा 6. (i) के लिए डिलायने त्रिकोणासन का दृश्य $$$R (\ phi_2)$ दृश्यों कर रहे हैं; (ii) (२,३) होल्टन क्रम, (iii) प्रधान पुनरावृत्ति; और (iv) सरल यादृच्छिक नमूनाकरण। रंग प्रत्येक त्रिकोण के क्षेत्र को इंगित करते हैं। सभी चार रेखांकन समान पैमाने का उपयोग करते हैं। और यहाँ फिर से यह स्पष्ट है कि $$$R (\ phi_2)$ परिणाम एक कम विचलन के साथ किसी भी अन्य अनुक्रम की तुलना में बहुत अधिक समान वितरण प्रदान करता है।
ध्यान दें $$$R_2$ के आधार पर $$$\ phi_2 = 1.32471795724474602596$ piso की सबसे छोटी संख्या होने के नाते, a $$$\ phi = 1.61803 ...$ की सबसे बड़ी संख्या है)। पिस्सो के द्विघात और क्यूबिक संख्याओं के साथ क्वासिपरियोडिक टाइलिंग का संबंध नया नहीं है [ एलखराट और मासाकोवा], लेकिन मेरा मानना ​​है कि पहली बार क्वासिपरियोडिक टाइलिंग के आधार पर बनाया गया था $$$\ phi_2 = 1.324719 ...$ ।

नीचे दिए गए एनीमेशन में दर्शाया गया है कि अनुक्रम के लिए डिलाय जाल कैसे $$$R_2$ अंकों के क्रमिक जोड़ के साथ परिवर्तन। ध्यान दें कि जब अंकों की संख्या सामान्यीकृत फाइबोनैचि अनुक्रम के एक सदस्य के बराबर होती है, तो पूरे डेलॉनाय ग्रिड में केवल लाल, नीले और पीले समांतर चतुर्भुज (रॉमबॉइड्स) होते हैं, जो एक डबल क्विपरिपरियोडिक रूप में व्यवस्थित होते हैं।


चित्र 7

हालांकि लाल समानांतर चतुर्भुज की व्यवस्था काफी नियमितता को प्रदर्शित करती है, एक स्पष्ट रूप से देख सकता है कि नीले और पीले रंग के समानांतर चतुर्भुज को एक कैस्परिपरियोडिक रूप में रखा गया है। इस जाली का फूरियर स्पेक्ट्रम चित्र 11 में देखा जा सकता है, यह शास्त्रीय बिंदु स्पेक्ट्रा का प्रतिनिधित्व करता है। (ध्यान दें कि अपराधों पर आधारित एक पुनरावर्ती अनुक्रम भी इस अर्थ में क्वैसिपेरियोडिक लगता है कि यह एक गैर-दोहराए जाने वाला पैटर्न है। हालांकि, अंतराल में इसका पैटर्न। $$$एन$ इतना स्थिर नहीं है, और यह भी गंभीर रूप से बुनियादी मापदंडों की पसंद पर निर्भर करता है। इसलिए, हम क्वेशिपरियोडिक झुकाव में अपनी रुचि को केवल अनुक्रम द्वारा ध्यान केंद्रित करेंगे $$$R_2$ ।) इसमें केवल तीन त्रिकोण होते हैं: लाल, पीला, नीला। इस क्रम में ध्यान दें $$$R (\ phi_2)$ प्रत्येक रंग के सभी समांतर चतुर्भुज का आकार और आकार समान होता है। इन व्यक्तिगत त्रिकोणों का पहलू अनुपात अविश्वसनीय रूप से सुरुचिपूर्ण है। अर्थात्,

$$

$$\ textrm {क्षेत्र (लाल): क्षेत्र (पीला): क्षेत्र (नीला)} = 1: \ phi_2: \ phi_2 ^ 2$$

त्रिकोण के सापेक्ष आवृत्ति पर भी यही लागू होता है:

$$

$$f (\ textrm {red}): f (\ textrm {पीला}): f (\ textrm {नीला}) = 1: \ phi_2: 1$$

यह इस प्रकार है कि अंतरिक्ष में इन तीन त्रिकोणों द्वारा कवर किया गया कुल सापेक्ष क्षेत्र है:

$$

$$f (\ textrm {लाल}): f (\ textrm {पीला}): f (\ textrm {नीला}) = 1: \ phi_2 ^ 2: \ phi_2 ^ 2$$

यह भी माना जा सकता है कि हम अनुक्रम ए के आधार पर प्रतिस्थापन के माध्यम से इस कैसिपरियोडिक टाइलिंग बना सकते हैं

$$

$$A \ n सही गौरैया 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,4,4,4,5,7,8,9,12,15,17,21,27,32,38,48,59 , 70,86,107,129, ...$$

कुछ मूल्यों पर $$$n = B_k$ 3 डी Delaunay जाल एक अनुक्रम के साथ जुड़े $$$R_3$ एक क्वासिपरियोडिक क्रिस्टल जाली को परिभाषित करता है।

खंडित पैकेजिंग, भाग 2

नीचे दिया गया आंकड़ा पहले दिखाता है $$$n = 2500$ कम विचलन के साथ प्रत्येक दो आयामी अनुक्रम के लिए अंक। इसके अलावा, कोशिकाओं में से प्रत्येक 50 × 50 = 2500 केवल हरे रंग का होता है, अगर इसमें बिल्कुल 1 डॉट होता है। यही है, अधिक हरे वर्ग, 2500 कोशिकाओं में 2500 अंकों के वितरण के लिए समान वर्दी। प्रत्येक आंकड़े के लिए हरी कोशिकाओं का प्रतिशत इस प्रकार है: $$$R_2$ (75%), होल्टन (54%), क्रोनकर (48%), नीडेराइटर (54%), सेबल (49%) और यादृच्छिक (38%)।

ध्वनि तरंगें

बस मज़े के लिए, एक समाचार हैकर पाठक के अनुरोध पर , मैंने मॉडल किया कि ये सभी अर्ध-यादृच्छिक बिंदु वितरण कैसे ध्वनि कर सकते हैं! मैंने मैथेमेटिका से लिस्टप्ले फ़ंक्शन का उपयोग किया: " लिस्टप्ले [{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
Niederreiter	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_2D.mp3
Holton	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$ अंक टाइप करें $$$k$ , (कहाँ) $$$n_1 + n_2 + n_3 + ... + n_k = n$ ), तो कम वितरण के साथ मल्टीसेट का वितरण एक वितरण है जिसमें प्रत्येक $$$n_k$ समान रूप से वितरित अंक। हमारे मामले में, हमने पाया है $$$आर$ -हल्टन अनुक्रम और अनुक्रम कम विचलन वाले मल्टीसेट के अनुक्रमों के अनुकूल होना आसान है, बस प्रत्येक प्रकार के वैकल्पिक बिंदुओं को रखकर।

नीचे दिया गया आंकड़ा दिखाता है कि उन्हें कैसे वितरित किया गया है $$$n = 150$ डॉट्स, जबकि 75 नीले हैं, 40 पेपरपी हैं, 25 हरे हैं, और 10 लाल हैं। एक योगात्मक पुनरावर्ती अनुक्रम के लिए, यह तुच्छ रूप से हल किया गया है: पहले 75 सदस्य केवल नीले रंग के अनुरूप हैं, अगले 40 नारंगी से, अगले 25 से हरे, और अंतिम 10 से लाल डॉट्स। यह तकनीक होल्टन और क्रोनकर दृश्यों के लिए लगभग काम करती है, लेकिन निडरएटर और सेबल अनुक्रमों में बहुत खराब प्रदर्शन करती है। इसके अलावा, Niederreiter और Sable अनुक्रमों में बहु-स्तरीय बिंदु वितरण की निरंतर पीढ़ी के लिए कोई ज्ञात तकनीक नहीं है। इससे पता चलता है कि मल्टीस्केल्स बिंदुओं का वितरण , उदाहरण के लिए, जैसे कि मुर्गियों की आँखें , अब कम विचलन वाले दृश्यों का उपयोग करके सीधे वर्णित और निर्मित की जा सकती हैं।

अनुक्रम $$$R_2$ एक कम-विचलन quasi-random अनुक्रम है जो एक बहु-श्रेणी कम विचलन का आसान निर्माण प्रदान करता है।

चित्रा 9. कम विचलन के साथ बहुकोशिकीय अनुक्रम। क्रम में $$$आर$ न केवल सभी बिंदुओं को समान रूप से वितरित किया जाता है, बल्कि प्रत्येक व्यक्तिगत रंग के अंक भी।

एक क्षेत्र पर अर्ध यादृच्छिक अंक

कंप्यूटर ग्राफिक्स और भौतिकी के क्षेत्र में, तीन आयामी क्षेत्र की सतह पर अंक वितरित करना अक्सर आवश्यक होता है। ओपन (अनंत) अर्ध-यादृच्छिक अनुक्रमों का उपयोग करते समय, यह समस्या केवल अर्ध-यादृच्छिक बिंदुओं का उपयोग करके समान रूप से एक इकाई वर्ग में वितरित किए गए अर्ध-यादृच्छिक बिंदुओं को लैम्बर्ट समान प्रक्षेपण का उपयोग करके की जाती है। एक बिंदु रखने वाले लैम्बर्ट मानक प्रक्षेपण परिवर्तन $$$^ (u, v) \ _ in [[0,1] \ _ में (x, y, z) \ _ S ^ 2 $ मे$ फार्म है:

$$

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

$$

$$\ textrm {जहां} \ quad \ cos (\ lambda - \ pi / 2) = (2u-1); \ quad \ phi = 2 \ pi v$$

इसके बाद से $$$\ phi_2$ -यह अनुक्रम पूरी तरह से खुला है, यह आपको एक बिंदु पर एक बिंदु पर, गोले की सतह पर अंक के अनंत अनुक्रम को स्नैप करने की अनुमति देता है। यह अन्य तरीकों के विपरीत है, जैसे कि फाइबोनैचि सर्पिल की जाली , जिसके लिए पहले से बिंदुओं की संख्या जानने की आवश्यकता होती है। दृश्य निरीक्षण पर, हम फिर से स्पष्ट रूप से इसके लिए देख सकते हैं $$$n = 1200$ नई $$$R (\ phi_2)$ - सीक्वेंस होल्टन ओवरले या क्रोनमेकर सैंपलिंग की तुलना में बहुत बेहतर तरीके से वितरित किया गया है, जो बदले में यादृच्छिक नमूने की तुलना में बहुत अधिक समान है।


चित्र 10

कंप्यूटर ग्राफिक्स dithering

अधिकांश आधुनिक डिटेरिंग तकनीक (उदाहरण के लिए, फ्लॉयड-स्टाइनबर्ग डिथरिंग) त्रुटि वितरण पर आधारित हैं, जो कि GPU में समानांतर प्रसंस्करण और / या प्रत्यक्ष अनुकूलन के लिए बहुत उपयुक्त नहीं है। ऐसे मामलों में, स्थैतिक dither मास्क (यानी, लक्ष्य छवि पर पूरी तरह से निर्भर) के साथ बिंदु प्रदर्शन उत्कृष्ट प्रदर्शन विशेषताओं को दर्शाता है। संभवत: सबसे प्रसिद्ध और व्यापक रूप से इस्तेमाल किए जाने वाले डाइटिंग मास्क बेयर मैट्रिस पर आधारित हैं, लेकिन नए लोग नीले शोर की विशेषताओं को करीब से देखने की कोशिश करते हैं। कम विचलन और / या नीले शोर के साथ दृश्यों के आधार पर या तो मास्क बनाने की nontrivial कठिनाई यह है कि कम विचलन परियोजना वाले इन दृश्यों का पूर्णांक होता है $$$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$$

इसके अलावा, अगर एक त्रिकोणीय तरंग फ़ंक्शन को फ़्रेक (।) फ़ंक्शन के कारण होने वाली असंगतता को समाप्त करने के लिए जोड़ा जाता है, तो प्रत्येक पूर्णांक सीमा पर कार्य:

$$

$$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$$

D- R R- मास्क बनाने से ऐसे परिणाम मिलते हैं जो नीले शोर वाले मास्क के आधार पर आधुनिक तरीकों से प्रतिस्पर्धा करते हैं। लेकिन नीले शोर वाले मुखौटे के विपरीत, उन्हें अग्रिम में गणना करने की आवश्यकता नहीं है, क्योंकि उन्हें वास्तविक समय में गणना की जा सकती है।

यह ध्यान देने योग्य है कि यह संरचना भी मिटिंग द्वारा प्रस्तावित की गई थी , लेकिन वह गुणांक को अनुभवजन्य रूप से पाता है (और अंतिम मूल्यों को पुन: पेश नहीं करता है)। इसके अलावा, यह समझने में मदद करता है कि जॉर्ज जिमेनेज़ का अनुभवजन्य फॉर्मूला "कॉल ऑफ़ ड्यूटी" (जिसे अक्सर "इंटरलीव्ड ग्रेडिएंट नॉइज़" कहा जाता है) बनाने के लिए कितना अच्छा काम करता है ।

$$

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

हालाँकि, इसके लिए 3 फ़्लोटिंग-पॉइंट गुणन और दो% 1 ऑपरेटरों की आवश्यकता होती है, और पिछले सूत्र से पता चलता है कि हम ऐसा केवल दो फ़्लोटिंग-पॉइंट गुणन और एक% 1 ऑपरेशन के साथ कर सकते हैं। लेकिन इससे भी महत्वपूर्ण बात, यह पोस्ट इस बात की स्पष्ट गणितीय समझ प्रदान करती है कि इस रूप में एक घना मुखौटा इतना प्रभावी क्यों है, यदि इष्टतम नहीं है। इस लीथिंग मैट्रिक्स के परिणाम क्लासिक लीना 256 × 256 परीक्षण छवि के साथ-साथ शतरंज परीक्षण पैटर्न का उपयोग करके नीचे दिखाए गए हैं। यह मानक बायर डाइथिंग मास्क का उपयोग करने के परिणामों को भी दिखाता है, साथ ही नीले शोर के साथ एक उदाहरण भी। नीले रंग के दो सबसे सामान्य तरीके हैं- Void-and-Cluster और Poisson डिस्क का नमूना। संक्षिप्तता के लिए, मैंने केवल शून्य और क्लस्टर विधि के परिणाम दिखाए हैं। [ पीटर्स]। इंटरलेव्ड ग्रेडिएंट शोर बायर और ब्लू शोर की तुलना में बेहतर काम करता है, लेकिन उतना अच्छा नहीं है$$$R$-dizering। आप देख सकते हैं कि बायर डाइथरिंग हल्के भूरे रंग के क्षेत्रों में सफेद रंग की ध्यान देने योग्य असंगति को दर्शाता है। तड़पना$$$R$- अनुक्रम और नीला शोर आमतौर पर तुलनीय होते हैं, हालांकि मामूली अंतर को बाहर किया जा सकता है। यह आर-डाइथरिंग के कुछ पहलुओं पर ध्यान देने योग्य है:

• वह आइसोट्रोपिक नहीं है! फूरियर स्पेक्ट्र्रा केवल व्यक्तिगत और असतत अंक दिखाते हैं। यह क्वासिपरियोडिक झुकाव की एक क्लासिक विशेषता है और क्वैसिस्ट्रल्स का विवर्तन स्पेक्ट्रा है। विशेष रूप से, फूरियर स्पेक्ट्र्रा के लिए$$$R$ -मास्क इस तथ्य के अनुरूप हैं कि विहित आर-अनुक्रम के लिए डेलुनाय त्रिभुज में तीन समांतर चतुर्भुज के कैसिपरियोडिक टाइलिंग शामिल हैं।
• त्रिकोणीय लहर के साथ संयुक्त होने पर आर-डिटेरिंग एक अविश्वसनीय रूप से एक समान मुखौटा प्रदान करता है!
• R- , .
• , , R- , .
• $$$(I(x,y)$ , .

चित्रा 11. बाएं से दाएं: (i) मूल छवि (ii) त्रिकोणीय तरंग फ़ंक्शन के साथ संयुक्त आर-अनुक्रम; (iii) R अनुक्रम अलग है; (iv) एक नीली आवाज वाला डाईथिरिंग मास्क; (v) एक मानक बायर। आर-सीक्वेंस डाइथरिंग मास्क अन्य आधुनिक मास्क के मुकाबले काफी प्रतिस्पर्धी हैं। ध्यान दें कि लीना के चेहरे और कंधों पर R2 सबसे अच्छी गुणवत्ता दिखाता है। इसके अलावा, नीले शोर वाले मुखौटे के विपरीत, डाइटिंग आर-मास्क इतना सरल है कि इसे प्रारंभिक गणना की आवश्यकता नहीं है।

उच्च आयाम

पिछले अनुभाग के समान, लेकिन पांच (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. यह दर्शाता है कि आर अनुक्रम (नीला) होल्टन (नारंगी) की तुलना में लगातार बेहतर है; सेबल (हरा); Niederreiter (लाल); और यादृच्छिक (बैंगनी)। ध्यान रखें कि बड़ा बेहतर है, क्योंकि यह लंबी पैकेजिंग दूरी से मेल खाती है।

संख्यात्मक एकीकरण

निम्न ग्राफ़ विशिष्ट त्रुटि घटता दिखाता है। $$$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. मोंटे कार्लो अर्ध-आयामी एकीकरण के लिए यादृच्छिक तरीके। जितना कम मूल्य, उतना बेहतर। नया आर-सीक्वेंस और सेबल सीक्वेंस खुद को हॉल्टन सीक्वेंस से काफी बेहतर दिखाता है।