फूरियर डिवीजन एल्गोरिदम के पीछे तर्क क्या है? विकिपीडिया से

Question

fourier division। (view in full-resolution)

एल्गोरिथम के पीछे तर्क क्या है:

यहाँ एक ही का एक स्क्रीनशॉट है?

मुझे पता है कि इसका उपयोग बहुत बड़ी संख्याओं को विभाजित करने के लिए किया जा सकता है, लेकिन यह वास्तव में कैसे काम करता है?

Answer 1

यह लांग डिवीजन एल्गोरिदम का एक चालाक परिवर्तन प्रतीत होता है। चालाक भाग ऐसा लगता है कि वे केवल पहले "अंक", ए 1 के लिए प्रभाग ऑपरेशन का उपयोग कर रहे हैं, और दूसरे को (x) का उपयोग उसी तरीके से करने से बचने के लिए अपने अगले चरण में उन्हें लागू करके अंतराल शेष से उत्पाद (आंशिक मात्रात्मक के खिलाफ)।

यह वैध रूप से किया जा सकता है और यह हमेशा काम करता है कि इस तथ्य के कारण शायद "अंक" (आधार 100, इस मामले में) वास्तविक अंक नहीं हैं और वैध रूप से मूल्यों को उनके आधार से अधिक मान सकते हैं (यानि, 100 से अधिक) और शून्य से भी कम। यह ऑपरेशन के लिए प्रत्येक "अंक" के आवेदन के समय में अधिक लचीलापन की अनुमति देता है, उदाहरण के लिए, विभाजक के द्वितीयक अंकों (ए (x> 1)) के अनुप्रयोग को परिभाषित करने तक, आंशिक भाग से उत्पन्न होने तक एक चरण (1) द्वारा पूर्व चरण विभाजन, जो बदले में उन्हें एक विभाजन संचालन के बजाय उत्पाद घटाव के रूप में लागू करने की अनुमति देता है।

Answer 2

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

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

मानक गुणा एल्गोरिदम में डेटा के प्रवाह का अध्ययन करने से प्राप्त करने के लिए एक और अंतर्ज्ञान है। यदि आप इसे कंप्यूटर हार्डवेयर में लिखते हैं, तो आप देख सकते हैं कि 8-बिट गुणक इकाइयों की एक वर्ग सरणी उनके 32 और बिट संख्याओं को उनके नीचे और दाएं किनारों पर व्यवस्थित करती है और डेटा को ऊपर और बाईं ओर ले जाती है, जो ऊपर के किनारे पर निकलती है एक 64-बिट उत्तर में सरणी। शीर्षतम बाएं इकाई यूनिटप्लिकैंड के शीर्ष अंकों का उपयोग करके उत्पाद के शीर्ष TWO (8-बिट) अंकों को प्रदान करती है और शेष सरणी से दाईं ओर ले जाती है। ठीक? खैर, सरणी के दाईं ओर किनारे के साथ कहें, शीर्ष किनारे के साथ 64-बिट डिवाइडर और 32-बिट विभाजक इनपुट के रूप में लेने के लिए विपरीत में चल रहे सरणी की कल्पना करें। फिर यह नीचे किनारे के साथ 32-बिट मात्रात्मक आउटपुट करता है (शेष को भी उत्पन्न किया जाना चाहिए .. मो के बारे में भूल जाओ)। अब सरणी में सबसे ऊपरी बाएं इकाई सरणी के शीर्ष से लाभांश के शीर्ष दो अंकों में ले जाती है, सरणी के दाईं ओर से विभाजक का शीर्ष अंक, और कोटेन्ट डाउनवार्ड के शीर्ष अंक को उत्सर्जित करता है सरणी (और नीचे से बाहर) और सरणी में एक शेष अधिकार।

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

और निश्चित रूप से, हम कंप्यूटर एएलयू में हार्डवेयर में कोई माइक्रोकोड आवश्यक नहीं कर सकते हैं।

कम से कम, मुझे लगता है कि इस विधि का उपयोग किया जाता है जहां कुछ और अरब ट्रांजिस्टर के पक्ष में माइक्रोक्रोड को छोड़ दिया गया है। मैं नवीनतम सीपीयू के इंटीरियर के लिए गुप्त नहीं हूं, लेकिन उनके पास जलने के लिए ट्रांजिस्टर हैं।