विभाजन के द्वारा विभाजन को कैसे कार्यान्वित करें?

Question

एक साक्षात्कार सवाल।

कैसे इसके द्वारा विभाजन लागू करने के लिए? मान लीजिए कि वे सभी int हैं।

मेरा विचार

1. ही भाजक जोड़ें जब तक यह लाभांश से बड़ा है। प्रत्येक पुनरावृत्ति, जोड़ से पहले योग परिणाम रखें।
2. उद्धरण अंतिम अतिरिक्त से पहले योग परिणाम है। शेष को quotient * divisor + reminder == dividend तक 1 जोड़कर गिना जा सकता है।

यह O(e^n) है, कोई बेहतर विचार? बिट ऑपरेशन?

Answer 1

डिजिटल अंकगणित में हम बहाल करने और गैर बहाल सरल विभाजन एल्गोरिदम, जो इसके अलावा/घटाव पर आधारित होते हैं जैसे तरीकों नाम कर सकते हैं। इन विधियों में पुनरावृत्तियों की संख्या O(n) (जहां n बिट्स की संख्या है) हैं। न्यूटन-रैफसन या पारस्परिक गणना जैसे विधियां हैं जो गुणा पर आधारित हैं और उनमें पुनरावृत्तियों की संख्या O(log n) है। शेष -

int r = m; 
int q = 0; 

while(r >= n) 
{ 
    int k = 1; 
    int x = n; 
    int t; 

    while((t = x+x) < r) 
    { 
     x = t; 
     k += k; 
    } 

    q += k; 
    r -= x; 
} 

परिणाम q है - भागफल, r: n द्वारा http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 2

m विभाजित पर एक नजर डालें।

विचार यह है कि x+xx*2 जैसा ही है।

युपीडी:

कुछ शिकायत कर सकते हैं कि r -= x अलावा नहीं है। खैर हम एल्गोरिथ्म अद्यतन कर सकते हैं घटाव का उपयोग नहीं करने के लिए: - भागफल

int p = 0; 
int q = 0; 

while(p+n <= m) 
{ 
    int k = 1; 
    int x = n; 
    int t; 

    while(p + (t = x+x) < m) 
    { 
     x = t; 
     k += k; 
    } 

    q += k; 
    p += x; 
} 

परिणाम q है। शेष -

int r = 0; 

while(p < m) 
{ 
    int x = 1; 
    int t; 

    while(p + (t = x+x) < m) 
    { 
     x = t; 
    } 

    r += x; 
    p += x; 
} 

परिणाम r है: - (ऊपर से उत्पादन p)

हम शेष की जरूरत है तो हम इस प्रकार आगे बढ़ें।

एल्गोरिथ्म स्पष्ट रूप से बहुपद (घातीय नहीं) चल रहा है समय है।

Answer 3

आप अपने लघुगणक घटकों में विभाजन टूट जाएगा और फिर उन की गणना।