वास्तविक संख्या को रेडिकल में परिवर्तित करें

Question

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

क्या उन्हें खोजने के लिए कोई रास्ता है? Decimals के आंशिक अनुमानों को खोजने के लिए continued fraction algorithm की तरह कुछ। भिन्नता की समस्या पर अधिक जानकारी के लिए, here देखें।

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

संपादित करें: जाहिर है बी को शून्य या सकारात्मक होना चाहिए। लेकिन कोई भी पूर्णांक हो सकता है।

Answer 1

निरंतर भिन्नताओं की कोई आवश्यकता नहीं है; बस b के सभी "छोटे" मानों के वर्ग-रूट की गणना करें (जो भी मूल्य आपको लगता है, वह अभी भी "छोटा" पर्याप्त है), दशमलव बिंदु से पहले सबकुछ हटाएं, और उन्हें सभी को सॉर्ट/स्टोर करें (b के साथ इसे उत्पन्न करने के साथ)।

फिर जब आपको वास्तविक संख्या का अनुमान लगाने की आवश्यकता होती है, तो उस कट्टरपंथी को ढूंढें जिसका दशमलव भाग वास्तविक संख्या के दशमलव भाग के कोठरी है। यह आपको b देता है - सही a चुनना घटाव का एक साधारण मामला है।

Answer 2

मुझे नहीं पता कि इस तरह की समस्या के लिए कोई मानक एल्गोरिदम है या नहीं, लेकिन यह मुझे साज़िश करता है, इसलिए यहां एक एल्गोरिदम विकसित करने का मेरा प्रयास है जो आवश्यक सन्निकटन पाता है।

r पर वास्तविक संख्या पर कॉल करें। फिर, सबसे पहले मुझे लगता है कि a नकारात्मक हो सकता है, उस स्थिति में हम समस्या को कम कर सकते हैं और अब केवल b को ढूंढना होगा जैसे कि sqrt(b) का दशमलव भाग r के दशमलव भाग का एक अच्छा अनुमान है। आइए अब rr = x.yx के साथ पूर्णांक और y दशमलव भाग के साथ लिखें।

Now: 
b = r^2 
    = (x.y)^2 
    = (x + .y)^2 
    = x^2 + 2 * x * .y + .y^2 
    = 2 * x * .y + .y^2 (mod 1) 

अब हम केवल x ऐसी है कि 0 = .y^2 + 2 * x * .y (mod 1) (लगभग) के खोजने के लिए।

भरने सूत्रों में है कि x ऊपर हम b और फिर a = r - b रूप a गणना कर सकते हैं। (इन सभी गणनाओं को सावधानीपूर्वक गोलाकार किया जाना चाहिए।)

अब, मुझे यह सुनिश्चित नहीं है कि इस x को इसे मजबूर करने के बिना कोई रास्ता नहीं है। लेकिन फिर भी, x पर्याप्त रूप से पर्याप्त खोजने के लिए कोई सरल लूप का उपयोग कर सकता है।

मैं इस (अर्ध छद्म कोड) की तरह कुछ की सोच रहा हूँ:

max_diff_low = 0.01 // arbitrary accuracy 
max_diff_high = 1 - max_diff_low 
y = r % 1 
v = y^2 
addend = 2 * y 
x = 0 
while (v < max_diff_high && v > max_diff_low) 
    x++; 
    v = (v + addend) % 1 
c = (x + y)^2 
b = round(c) 
a = round(r - c) 

अब, मुझे लगता है कि इस एल्गोरिथ्म काफी कुशल है, जबकि भी आप सन्निकटन की कामना की सटीकता निर्दिष्ट करने के लिए अनुमति देता है। एक चीज जो किया जा सकता है जो इसे ओ (1) एल्गोरिदम में बदल देगा, सभी x की गणना कर रहा है और उन्हें लुकअप टेबल में डाल रहा है। यदि कोई केवल r (उदाहरण के लिए) के पहले तीन दशमलव अंकों की परवाह करता है, तो लुकअप तालिका में केवल 1000 मान होंगे, जो केवल 4kb स्मृति है (मानते हैं कि 32 बिट पूर्णांक का उपयोग किया जाता है)।

आशा है कि यह बिल्कुल उपयोगी है। अगर किसी को एल्गोरिदम के साथ कुछ भी गलत लगता है, तो कृपया मुझे एक टिप्पणी में बताएं और मैं इसे ठीक कर दूंगा।

संपादित करें: प्रतिबिंब पर मैं दक्षता का अपना दावा वापसी। वास्तव में जहां तक ​​मैं कोई गारंटी नहीं दे सकता हूं कि ऊपर उल्लिखित एल्गोरिदम कभी समाप्त हो जाएगा, और यहां तक ​​कि अगर ऐसा होता है, तो बहुत अधिक x खोजने में काफी समय लग सकता है जो समीकरण को पर्याप्त रूप से हल करता है।

कोई भी अब तक पाया गया सर्वोत्तम x का ट्रैक रख सकता है और सटीकता की संभावित लागत पर एल्गोरिदम जल्दी से समाप्त होने के लिए समय के साथ सटीकता सीमा को आराम कर सकता है।

ये समस्याएं बिल्कुल मौजूद नहीं हैं, अगर कोई लुकअप टेबल की पूर्व-गणना करता है।

Answer 3

यह वास्तव में कंप्यूटर समस्या की तुलना में गणित की समस्या का अधिक है, लेकिन सवाल का जवाब देने के लिए मुझे लगता है कि आप सही हैं कि आप निरंतर भिन्नताओं का उपयोग कर सकते हैं। आप जो करते हैं वह पहले निरंतर अंश के रूप में लक्ष्य संख्या का प्रतिनिधित्व करता है। उदाहरण के लिए, यदि आप अनुकरणीय (3.14159265) अनुमान लगाने के लिए चाहते हैं तो सीएफ है:

3: 7, 15, 1, 288, 1, 2, 1, 3, 1, 7, 4 ...

अगला चरण वर्ग जड़ों के लिए सीएफ की एक तालिका बना रहा है, फिर आप तालिका में मानों को लक्ष्य मान के आंशिक भाग (यहां: 7, 15, 1, 288, 1, 2, 1, 3, 1) से तुलना करते हैं। , 7, 4 ...)। उदाहरण के लिए, मान लें कि आपकी तालिका में केवल 1-99 के लिए वर्ग की जड़ें थीं। फिर आप पाएंगे कि निकटतम मैच एसक्यूआरटी (51) होगा जिसमें 7: 7,14 दोहराया जाएगा। 7,14 पीआई के 7,15 के सबसे नज़दीक है। इस प्रकार यदि आपका जवाब होगा:

sqrt (51) -4

एक ख < 100 दिया निकटतम सन्निकटन जो .००,०१६ से बंद है के रूप में। यदि आप बड़े बी की अनुमति देते हैं तो आप बेहतर अनुमान लगा सकते हैं।

सीएफ का उपयोग करने का लाभ यह है कि यह काम करने, डबल्स या फ़्लोटिंग पॉइंट का उपयोग करने से तेज़ है। उदाहरण के लिए, उपर्युक्त मामले में आपको केवल दो पूर्णांक (7 और 15) की तुलना करना होगा, और आप तालिका में सबसे नज़दीकी प्रविष्टि को बहुत तेजी से ढूंढने के लिए अनुक्रमण का भी उपयोग कर सकते हैं।

Answer 4

यह बहुत कुशलता से mixed integer quadratic programming उपयोग किया जा सकता

परिभाषित करें (। हालांकि MIQP के रूप में कोई रन-टाइम की गारंटी देता है देखते हैं एनपी पूरा हो गया है):

d := the real number you wish to approximate 
b, a := two integers such that a + sqrt(b) is as "close" to d as possible 
r := (d - a)^2 - b, is the residual of the approximation 

लक्ष्य r कम करने के लिए है। सेटअप अपने द्विघात कार्यक्रम के रूप में:

x := [ s b t ] 
D := | 1 0 0 | 
    | 0 0 0 | 
    | 0 0 0 | 
c := [0 -1 0]^T 
with the constraint that s - t = f (where f is the fractional part of d) 
and b,t are integers (s is not) 

यह एक उत्तल (इसलिए बेहतर व्याख्या करने योग्य) मिश्रित D के बाद से पूर्णांक द्विघात कार्यक्रम है सकारात्मक अर्द्ध निश्चित है।

एक बार s,b,t गणना की जाती है, तो b=b, s=d-a और t का उपयोग करके उत्तर प्राप्त किया जा सकता है।

आपकी समस्या एनपी-पूर्ण हो सकती है, तो ऐसा साबित करना दिलचस्प होगा।

Answer 5

पिछले कुछ उत्तर समय या अंतरिक्ष जटिलता ओ (एन) के तरीकों का उपयोग करते हैं, जहां एन सबसे बड़ी "छोटी संख्या" है जिसे स्वीकार किया जाएगा। इसके विपरीत, निम्नलिखित विधि ओ (sqrt (n)) समय में है, और ओ (1) अंतरिक्ष में है।

मान लीजिए कि सकारात्मक वास्तविक संख्या r = x + y, जहां x=floor(r) और 0 ≤ y < 1। हम r को a + √b के रूप में अनुमानित करना चाहते हैं। x+y ≈ a+√b तो x+y-a ≈ √b, तो √b ≈ h+y कुछ पूर्णांक ऑफ़सेट h, और b ≈ (h+y)^2 के लिए। बी को पूर्णांक बनाने के लिए, हम सभी योग्य h पर (h+y)^2 के आंशिक भाग को कम करना चाहते हैं। पर h के योग्य मान हैं। निम्नलिखित पायथन कोड और नमूना आउटपुट देखें।

import math, random 

def findb(y, rhi): 
    bestb = loerror = 1; 
    for r in range(2,rhi): 
     v = (r+y)**2 
     u = round(v) 
     err = abs(v-u) 
     if round(math.sqrt(u))**2 == u: continue 
     if err < loerror: 
      bestb, loerror = u, err 
    return bestb 

#random.seed(123456)  # set a seed if testing repetitively 
f = [math.pi-3] + sorted([random.random() for i in range(24)]) 
print (' frac  sqrt(b)  error  b') 
for frac in f:     
    b = findb(frac, 12) 
    r = math.sqrt(b) 
    t = math.modf(r)[0]   # Get fractional part of sqrt(b) 
    print ('{:9.5f} {:9.5f} {:11.7f} {:5.0f}'.format(frac, r, t-frac, b)) 

(नोट 1: इस कोड को डेमो के रूप में है, findb() पैरामीटर y, r का आंशिक हिस्सा है, और rhi, सबसे बड़ी छोटी संख्या का वर्गमूल हैं आप का उपयोग बदलने के लिए इच्छा हो सकती है। । मापदंडों नोट 2: कोड के
if round(math.sqrt(u))**2 == u: continue
लाइन b का सही वर्ग मूल्यों लौटने से findb() रोकता है, मूल्य ख = 1 के लिए छोड़कर, क्योंकि कोई पूर्ण वर्ग सटीकता ख द्वारा की पेशकश की सुधार कर सकते हैं = 1)

।

नमूना उत्पादन निम्नानुसार है। मध्य में लगभग एक दर्जन लाइनों को बढ़ाया गया है। पहली आउटपुट लाइन से पता चलता है कि pi के आंशिक भाग का प्रतिनिधित्व करने के लिए यह प्रक्रिया b=51 उत्पन्न करती है, जो कि कुछ अन्य उत्तरों में समान मूल्य है।

frac  sqrt(b)  error  b 
    0.14159 7.14143 -0.0001642  51 
    0.11975 4.12311 0.0033593  17 
    0.12230 4.12311 0.0008085  17 
    0.22150 9.21954 -0.0019586  85 
    0.22681 11.22497 -0.0018377 126 
    0.25946 2.23607 -0.0233893  5 
    0.30024 5.29150 -0.0087362  28 
    0.36772 8.36660 -0.0011170  70 
    0.42452 8.42615 0.0016309  71 
    ... 
    0.93086 6.92820 -0.0026609  48 
    0.94677 8.94427 -0.0024960  80 
    0.96549 11.95826 -0.0072333 143 
    0.97693 11.95826 -0.0186723 143 

प्रोग्राम के अंत में निम्नलिखित कोड जोड़े गए, नीचे दिखाया गया आउटपुट भी दिखाई देता है। यह पीआई के आंशिक भाग के लिए करीब अनुमान दिखाता है।

frac, rhi = math.pi-3, 16 
print (' frac  sqrt(b)   error   b  bMax') 
while rhi < 1000: 
    b = findb(frac, rhi) 
    r = math.sqrt(b) 
    t = math.modf(r)[0]   # Get fractional part of sqrt(b) 
    print ('{:11.7f} {:11.7f} {:13.9f} {:7.0f} {:7.0f}'.format(frac, r, t-frac, b,rhi**2)) 
    rhi = 3*rhi/2 

    frac  sqrt(b)   error   b  bMax 
    0.1415927 7.1414284 -0.000164225  51  256 
    0.1415927 7.1414284 -0.000164225  51  576 
    0.1415927 7.1414284 -0.000164225  51  1296 
    0.1415927 7.1414284 -0.000164225  51  2916 
    0.1415927 7.1414284 -0.000164225  51  6561 
    0.1415927 120.1415831 -0.000009511 14434 14641 
    0.1415927 120.1415831 -0.000009511 14434 32761 
    0.1415927 233.1415879 -0.000004772 54355 73441 
    0.1415927 346.1415895 -0.000003127 119814 164836 
    0.1415927 572.1415909 -0.000001786 327346 370881 
    0.1415927 911.1415916 -0.000001023 830179 833569