الجذر التربيعي الصحيح

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 117 صور
الموسوعة الحرة

في نظرية الأعداد ، الجذر التربيعي الصحيح (isqrt) لعدد صحيح غير سالب n هو العدد الصحيح غير السالب m الذي يمثل أكبر عدد صحيح أقل من أو يساوي الجذر التربيعي لـ n . الجذر التربيعي⁡(ن)=⌊ن⌋.{\displaystyle \operatorname {isqrt} (n)=\lfloor {\sqrt {n}}\rfloor .}

على سبيل المثال،الجذر التربيعي⁡(27)=⌊27⌋=⌊5.19615242270663...⌋=5.{\displaystyle \operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =\lfloor 5.19615242270663...\rfloor =5.}

ملاحظة تمهيدية

يتركy{\displaystyle y}وك{\displaystyle k}لتكن أعدادًا صحيحة غير سالبة.

الخوارزميات التي تحسب ( التمثيل العشري لـ)y{\displaystyle {\sqrt {y}}}يستمر التشغيل إلى ما لا نهاية على كل مدخلy{\displaystyle y}وهو ليس مربعًا كاملًا . [ ملاحظة 1 ]

الخوارزميات التي تحسب⌊y⌋{\displaystyle \lfloor {\sqrt {y}}\rfloor }لا تعمل إلى الأبد . ومع ذلك فهي قادرة على الحوسبةy{\displaystyle {\sqrt {y}}}بدقة تصل إلى أي مستوى مطلوبك{\displaystyle k}.

اختر أيًا منهاك{\displaystyle k}واحسب⌊y×100ك⌋{\textstyle \lfloor {\sqrt {y\times 100^{k}}}\rfloor }.

على سبيل المثال (الإعداد)y=2{\displaystyle y=2}): ك=0:⌊2×1000⌋=⌊2⌋=1ك=1:⌊2×1001⌋=⌊200⌋=14ك=2:⌊2×1002⌋=⌊20000⌋=141ك=3:⌊2×1003⌋=⌊2000000⌋=1414⋮ك=8:⌊2×1008⌋=⌊20000000000000000⌋=141421356⋮{\displaystyle {\begin{aligned}&k=0:\lfloor {\sqrt {2\times 100^{0}}}\rfloor =\lfloor {\sqrt {2}}\rfloor =1\\&k=1:\lfloor {\sqrt {2\times 100^{1}}}\rfloor =\lfloor {\sqrt {200}}\rfloor =14\\&k=2:\lfloor {\sqrt {2\times 100^{2}}}\rfloor =\lfloor {\sqrt {20000}}\rfloor =141\\&k=3:\lfloor {\sqrt {2\times 100^{3}}}\rfloor =\lfloor {\sqrt {2000000}}\rfloor =1414\\&\vdots \\&k=8:\lfloor {\sqrt {2\times 100^{8}}}\rfloor =\lfloor {\sqrt {20000000000000000}}\rfloor =141421356\\&\vdots \\\end{aligned}}}

قارن النتائج مع2=1.41421356237309504880168872420969807856967187537694...{\displaystyle {\sqrt {2}}=1.41421356237309504880168872420969807856967187537694...}

يبدو أن ضرب المدخلات بـ100ك{\displaystyle 100^{k}}يُعطي دقة تصل إلى k خانة عشرية. [ ملاحظة 2 ]

لحساب التمثيل العشري (الكامل) لـy{\displaystyle {\sqrt {y}}}يمكن للمرء أن ينفذالجذر التربيعي⁡(y){\displaystyle \operatorname {isqrt} (y)}عدد لا نهائي من المرات، متزايدy{\displaystyle y}بمعامل100{\displaystyle 100}في كل تمريرة.

افترض أنه في البرنامج التالي (جذر تربيعي للأبد{\displaystyle \operatorname {sqrtForever} }) الإجراءالجذر التربيعي⁡(y){\displaystyle \operatorname {isqrt} (y)}تم تعريفها بالفعل، ومن أجل هذا النقاش ، يمكن لجميع المتغيرات أن تحمل أعدادًا صحيحة ذات حجم غير محدود.

ثمجذر تربيعي للأبد⁡(y){\displaystyle \operatorname {sqrtForever} (y)}سيتم طباعة التمثيل العشري الكامل لـy{\displaystyle {\sqrt {y}}}[ ملاحظة 3 ]

استيراد الرياضيات # افترض حساب الجذر التربيعي كما هو موضح هنادالة sqrtForever ( y : int ): """ اطبع جذر(y) دون توقف """ result = math . isqrt ( y ) print ( str ( result ) + "." , end = "" ) # اطبع النتيجة متبوعة بفاصلة عشريةبينما صحيح : # كرر إلى ما لا نهاية ... ص * = ١٠٠ # مثال نظري: يتم تجاهل تجاوز القيمة النتيجة = math.isqrt ( ص ) اطبع ( str ( النتيجة % ١٠ ), نهاية = "" ) # اطبع الرقم الأخير من النتيجة

والخلاصة هي أن الخوارزميات التي تحسب isqrt()مكافئة حسابيًا للخوارزميات التي تحسبsqrt() .

اشتقاق آخر منy{\displaystyle {\sqrt {y}}}من⌊y⌋{\displaystyle \lfloor {\sqrt {y}}\rfloor }يتم تقديمها في القسم " الكسر المستمر لـ √c بناءً على isqrt" أدناه.

الخوارزميات الأساسية

الجذر التربيعي الصحيح لعدد صحيح غير سالبy{\displaystyle y}يمكن تعريفها على النحو التالي: ⌊y⌋=الأعلى{x:x2≤y<(x+1)2،x∈شمال}{\displaystyle \lfloor {\sqrt {y}}\rfloor =\max\{x:x^{2}\leq y<(x+1)^{2},x\in \mathbb {N} \}}

على سبيل المثال،الجذر التربيعي⁡(27)=⌊27⌋=5{\displaystyle \operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =5}لأن62>27 و 52≯27{\displaystyle 6^{2}>27{\text{ و }}5^{2}\ngtr 27}.

البرامج التالية المكتوبة بلغة بايثون هي تطبيقات مباشرة.

دالة isqrt ( y : int ) -> int : """  الجذر التربيعي الصحيح  (بحث خطي، تصاعدي)  """ # تقدير أولي أقل من القيمة الحقيقية، L <= isqrt(y) L = 0 بينما ( L + 1 ) * ( L + 1 ) <= y : L += 1إرجاع L
دالة isqrt ( y : int ) -> int : """  الجذر التربيعي الصحيح  (بحث خطي، تنازلي)  """ # تقدير أولي زائد، isqrt(y) <= R R = y بينما ( R * R > y ): R -= 1إرجاع R

البحث الخطي باستخدام الجمع

في البرنامج أعلاه (بحث خطي، تصاعدي) يمكن استبدال الضرب بالجمع، باستخدام التكافؤ (ل+1)2=ل2+2ل+1=ل2+1+∑أنا=1ل2.{\displaystyle (L+1)^{2}=L^{2}+2L+1=L^{2}+1+\sum _{i=1}^{L}2.}

دالة isqrt ( y : int ) -> int : """  الجذر التربيعي الصحيح  (بحث خطي، تصاعدي) باستخدام الجمع  """ L = 0 a = 1 d = 3بينما a ≤ y : a = a + d، d = d + 2 ، L = L + 1إرجاع L

يقوم البحث الخطي بفحص كل قيمة بالتسلسل حتى يصل إلى أصغر قيمةx{\displaystyle x}أينx2>y{\displaystyle x^{2}>y}.

يتم تحقيق تسريع العملية باستخدام البحث الثنائي بدلاً من ذلك.

دالة isqrt ( y : int ) -> int : """ الجذر التربيعي الصحيح (بحث ثنائي) """ L = 0 # الحد الأدنى للجذر التربيعي R = y + 1 # الحد الأعلى للجذر التربيعيبينما ( L ≠ R - 1 ): M = ( L + R ) // 2 # نقطة المنتصف للاختبار إذا ( M * M <= y ): L = M وإلا : R = Mإرجاع L

أمثلة عددية

  • الجذر التربيعي⁡(0)=0{\displaystyle \operatorname {isqrt} (0)=0}،الجذر التربيعي⁡(1)=1{\displaystyle \operatorname {isqrt} (1)=1}.
  • باستخدام البحث الثنائي، يتم حسابالجذر التربيعي⁡(131072){\displaystyle \operatorname {isqrt} (131072)}يتقارب إلى362{\displaystyle 362}في17{\displaystyle 17}خطوات التكرار عبر[ل،R]{\displaystyle [L,R]}تسلسل
[0،131073]→[0،65536]→[0،32768]→[0،16384]→[0،8192]→[0،4096]→[0،2048]→[0،1024]→[0،512]→[256،512]→[256،384]→[320،384]→[352،384]→[352،368]→[360،368]→[360،364]→[362،364]→[362،363]{\displaystyle {\begin{aligned}&[0,131073]\to [0,65536]\to [0,32768]\to [0,16384]\to [0,8192]\to [0,4096]\rightarrow [0,2048]\to [0,1024]\to [0,512]\\&\to [256,512]\to [256,384]\to [320,384]\to [352,384]\to [352,368]\to [360,368]\to [360,364]\to [362,364]\to [362,363]\end{aligned}}}
  • حسابالجذر التربيعي⁡(2000000){\displaystyle \operatorname {isqrt} (2000000)}يتقارب إلى1414{\displaystyle 1414}في21{\displaystyle 21}خطوات عبر[ل،R]{\displaystyle [L,R]}تسلسل
[0،2000001]→[0،1000000]→[0،500000]→[0،250000]→[0،125000]→[0،62500]→[0،31250]→[0،15625]→[0،7812]→[0،3906]→[0،1953]→[976،1953]→[976،1464]→[1220،1464]→[1342،1464]→[1403،1464]→[1403،1433]→[1403،1418]→[1410،1418]→[1414،1418]→[1414،1416]→[1414،1415]{\displaystyle {\begin{aligned}&[0,2000001]\to [0,1000000]\to [0,500000]\to [0,250000]\to [0,125000]\to [0,62500]\to [0,31250]\to [0,15625]\\&\to [0,7812]\to [0,3906]\to [0,1953]\to [976,1953]\to [976,1464]\to [1220,1464]\to [1342,1464]\to [1403,1464]\\&\to [1403,1433]\to [1403,1418]\to [1410,1418]\to [1414,1418]\to [1414,1416]\to [1414,1415]\end{aligned}}}
البحث الخطي (تصاعديًا، بدءًا من0{\displaystyle 0}) يحتاج1414 خطوة.

خوارزمية تستخدم طريقة نيوتن

إحدى طرق الحسابن{\displaystyle {\sqrt {n}}}والجذر التربيعي⁡(ن){\displaystyle \operatorname {isqrt} (n)}تتمثل الطريقة في استخدام طريقة هيرون ، وهي حالة خاصة من طريقة نيوتن ، لإيجاد حل للمعادلةx2-ن=0{\displaystyle x^{2}-n=0}، مما يعطي الصيغة التكرارية xك+1=12(xك+نxك)،ك≥0،x0>0.{\displaystyle x_{k+1}={\frac {1}{2}}\!\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.}

التسلسل​{xك}{\displaystyle \{x_{k}\}}يتقارب تربيعيًا إلىن{\displaystyle {\sqrt {n}}}مثلك→∞{\displaystyle k\to \infty }[ 1 ] [ ملاحظة 4 ]

باستخدام القسمة الصحيحة فقط

للحوسبة⌊ن⌋{\displaystyle \lfloor {\sqrt {n}}\rfloor }يمكن استخدام ناتج القسمة الإقليدية في كلتا عمليتي القسمة. تكمن ميزة ذلك في استخدام أعداد صحيحة فقط لكل قيمة وسيطة، مما يجعل استخدام تمثيلات الفاصلة العائمة غير ضروري.

يتركن>0{\displaystyle n>0}والتخمين الأوليx0>0{\displaystyle x_{0}>0}عرّف متتالية الأعداد الصحيحة:

xك+1=⌊xك+⌊ن/xك⌋2⌋،ك=0،1،2،...{\displaystyle x_{k+1}=\left\lfloor {\frac {x_{k}+\left\lfloor n/x_{k}\right\rfloor }{2}}\right\rfloor ,\quad k=0,1,2,\dots }

إثبات التقارب

1. الإيجابية: جميع الحدود أعداد صحيحة موجبة:xك>0{\displaystyle x_{k}>0}للجميعك{\displaystyle k}.

2. الرتابة:

  • لوxك>ن{\displaystyle x_{k}>{\sqrt {n}}}، ثم⌊ن/xك⌋≤ن/xك{\displaystyle \lfloor n/x_{k}\rfloor \leq n/x_{k}}؛
لذاxك+1=⌊xك+⌊ن/xك⌋2⌋<xك+ن/xك2<xك{\displaystyle x_{k+1}=\left\lfloor {\frac {x_{k}+\lfloor n/x_{k}\rfloor }{2}}\right\rfloor <{\frac {x_{k}+n/x_{k}}{2}}<x_{k}}.
وبالتالي يتناقص التسلسل.
  • لوxك<ن{\displaystyle x_{k}<{\sqrt {n}}}، ثم⌊ن/xك⌋≥ن/xك-1{\displaystyle \lfloor n/x_{k}\rfloor \geq n/x_{k}-1}؛
لذاxك+1≥xك+ن/xك-12>xك-1{\displaystyle x_{k+1}\geq {\frac {x_{k}+n/x_{k}-1}{2}}>x_{k}-1}.
وبالتالي، فإن التسلسل إما يزداد أو يبقى كما هو.

3. التقييد: المتتالية محدودة من الأسفل بـ 1 ومن الأعلى بـx0{\displaystyle x_{0}}لذلك فهي محدودة.

4. الاستقرار / التذبذب: تسلسل الأعداد الصحيحة الرتيب المحدود إما أن يستقر أو يتذبذب بين عددين صحيحين متتاليين:

xك+1=xك{\displaystyle x_{k+1}=x_{k}}أوxك+1=xك±1{\displaystyle x_{k+1}=x_{k}\pm 1}.

5. حالة "النقطة الثابتة" للأعداد الصحيحة: عند الاستقرار أو التذبذب:

xك+1=⌊(xك+⌊ن/xك⌋)/2⌋{\displaystyle x_{k+1}=\lfloor (x_{k}+\lfloor n/x_{k}\rfloor )/2\rfloor }.
وهذا يضمن أن يكون التسلسل إما عند⌊ن⌋{\displaystyle \lfloor {\sqrt {n}}\rfloor }أو التذبذب بين أقرب عددين صحيحين حولن{\displaystyle {\sqrt {n}}}.

6. الخلاصة: يستقر التسلسل في النهاية عند⌊ن⌋{\displaystyle \lfloor {\sqrt {n}}\rfloor }أو يتأرجح بين⌊ن⌋{\displaystyle \lfloor {\sqrt {n}}\rfloor }و⌈ن⌉{\displaystyle \lceil {\sqrt {n}}\rceil }.

ملاحظة:

  • ⌊ن⌋{\displaystyle \lfloor {\sqrt {n}}\rfloor }هي نقطة ثابتة صارمة ما لمن+1{\displaystyle n+1}مربع كامل.
  • لون+1{\displaystyle n+1}إذا كان مربعًا كاملًا، فإن المتتالية تتأرجح بين⌊ن⌋{\displaystyle \lfloor {\sqrt {n}}\rfloor }و⌈ن⌉{\displaystyle \lceil {\sqrt {n}}\rceil }.

مثال على التنفيذ

دالة isqrt ( n : int , x0 : int = 1 ) -> int : """  دالة isqrt باستخدام تكرار نيوتن-هيرون مع تخمين أولي محدد.  تستخدم كشف التذبذب ثنائي الدورة. الشروط المسبقة:  n >= 0 # جذر 0 = 0  x0 > 0، القيمة الافتراضية هي 1 # التخمين الأولي الناتج:  isqrt(n)  """ assert n >= 0 and x0 > 0 , "إدخال غير صالح"# isqrt(0) = 0; isqrt(1) = 1 إذا كان n < 2 : يُرجع nprev2 = -1 # x_ {i-2} prev1 = x0 # x_{i-1}بينما صحيح : x1 = ( prev1 + n // prev1 ) // 2# الحالة 1: تقارب (قيمة ثابتة) إذا كانت x1 == prev1 : أرجع x1# الحالة 2: التذبذب (دورتان) إذا كان x1 == prev2 و x1 != prev1 : # نحن نتبادل بين prev1 و prev2 # نختار الأصغر (الجذر الصحيح الصحيح) إرجاع min ( prev1 , x1 )# تقدم للأمام prev2 ، prev1 = prev1 ، x1

أمثلة عددية

يتقارب النداء isqrt(2000000)إلى1414{\displaystyle 1414}في 14 مرورًا عبر while:

1000000→500001→250002→125004→62509→31270→15666→7896→4074→2282→1579→1422→1414→1414{\displaystyle {\begin{aligned}&1000000\to 500001\to 250002\to 125004\to 62509\to 31270\to 15666\to 7896\to 4074\to 2282\\&\to 1579\to 1422\to 1414\rightarrow 1414\end{aligned}}}.

يتم الحصول على تكرار واحد عن طريق ضبطه x0على⌊ن/2⌋{\displaystyle \lfloor n/2\rfloor }مع الاستدعاء isqrt(2000000, 1000000). على الرغم من أن طريقة هيرون تتقارب بشكل تربيعي قريب من الحل، إلا أنه يتم اكتساب دقة أقل من بت واحد لكل تكرار في البداية. هذا يعني أن اختيار التقدير الأولي أمر بالغ الأهمية لأداء الخوارزمية. [ ملاحظة 5 ] عندما تتوفر عملية حساب سريعة للجزء الصحيح من اللوغاريتم الثنائي أو لطول البتn.bit_length() (كما هو الحال في بايثون على سبيل المثال )، فمن الأفضل البدء منx0=2⌊(سجل2⁡ن)/2⌋+1،{\displaystyle x_{0}=2^{\lfloor (\log _{2}n)/2\rfloor +1},}أيهما أصغر قوة للعدد اثنين أكبر منن{\displaystyle {\sqrt {n}}}في مثال الجذر التربيعي الصحيح للعدد 2000000 ،⌊سجل2⁡ن⌋=20{\displaystyle \lfloor \log _{2}n\rfloor =20}،x0=211=2048{\displaystyle x_{0}=2^{11}=2048}والتسلسل الناتج هو 2048→1512→1417→1414→1414.{\displaystyle 2048\rightarrow 1512\rightarrow 1417\rightarrow 1414\rightarrow 1414.}في هذه الحالة، نحتاج فقط إلى أربع خطوات تكرارية. وهذا يتوافق مع الاستدعاء isqrt(2000000, 2048).

خوارزمية رقمًا برقم

الخوارزمية التقليدية التي تستخدم القلم والورقة لحساب الجذر التربيعين{\displaystyle {\sqrt {n}}}تعتمد هذه الطريقة على العمل من خانات الأرقام الأعلى إلى الأدنى، ومع كل رقم جديد، يتم اختيار أكبر رقم يُنتج مربعًا.≤ن{\displaystyle \leq n}إذا توقفنا بعد خانة الآحاد، فإن النتيجة المحسوبة ستكون الجذر التربيعي الصحيح.

باستخدام عمليات البت

عند العمل بالنظام الثنائي ، يُبسط اختيار الرقم إلى الاختيار بين 0 (الرقم الأصغر) و1 (الرقم الأكبر)، ويمكن التعبير عن عمليات تغيير الأرقام باستخدام عمليات الإزاحة الثنائية. وباعتبار *الضرب، و الإزاحة إلى اليسار، و الإزاحة المنطقية إلى اليمين، فإن الخوارزمية التكرارية لإيجاد الجذر التربيعي الصحيح لأي عدد طبيعي هي:<<>>

دالة isqrt_recursive ( n : int ) -> int : تحقق مما إذا كان n أكبر من أو يساوي 0 ، "يجب أن يكون n عددًا صحيحًا غير سالب" إذا كان n < 2 : أرجع n# استدعاء تكراري: small_cand = isqrt_recursive ( n >> 2 ) << 1 # نفس 2 * isqrt(n // 4) large_cand = small_cand + 1 if large_cand * large_cand > n : return small_cand else : return large_cand

البرنامج غير التكراري المكافئ: [ 2 ] [ ملاحظة 6 ]

دالة isqrt_iterative ( x : int ) -> int : """ جاي، مارتن (1985). "الجذر التربيعي السريع للأعداد الصحيحة باستخدام خوارزمية المعداد للسيد وو" """ تحقق من أن x >= 0 ، "يجب أن يكون x عددًا صحيحًا غير سالب"العملية = x ؛ النتيجة = 0# ملاحظة: i << 1 يساوي 2 * i، و i << 2 يساوي 4 * i، i >> 1 يساوي i // 2، و i >> 2 يساوي i // 4...# يبدأ العدد "واحد" من أعلى قوة للعدد أربعة <= x، أي أن "واحد" = 1، بينما "واحد" <= op : "واحد " <<= 2، أي أن "واحد" >>= 2بينما واحد لا يساوي صفرًا : dltasqr = res + واحد إذا كان op >= dltasqr : op -= dltasqr res += واحد << 1 res >>= 1 واحد >>= 2إرجاع النتيجة

انظر طرق حساب الجذور التربيعية §  النظام العددي الثنائي (الأساس 2) للحصول على مثال. [ 2 ]

خوارزمية كاراتسوبا للجذر التربيعي

تُطبّق خوارزمية كاراتسوبا للجذر التربيعي نفس مبدأ فرق تسد المُستخدم في خوارزمية كاراتسوبا للضرب لحساب الجذور التربيعية للأعداد الصحيحة. وقد قام بول زيمرمان (1999) بتحليل هذه الطريقة تحليلاً رسميًا. [ 3 ] تقوم هذه الخوارزمية بتقسيم العدد المُدخل بشكل متكرر إلى نصفين، كبير وصغير، ثم تحسب الجذر التربيعي للنصف الكبير، وبعد ذلك تحدد الجذر التربيعي للنصف الصغير جبريًا.

الخوارزمية

يقدم بول زيمرمان (1999) الخوارزمية التالية. [ 3 ]

الخوارزمية الجذر التربيعي للباقي(ن=أ3ب3+أ2ب2+أ1ب+أ0){\displaystyle {\text{Algorithm }}{\text{SqrtRem}}(n=a_{3}b^{3}+a_{2}b^{2}+a_{1}b+a_{0})}
مدخل: 0≤أأنا<ب، مع أ3≥ب/4{\displaystyle {\text{Input: }}0\leq a_{i}<b,{\text{ with }}a_{3}\geq b/4}
الناتج: (s،ر) بحيث s2≤ن=s2+ر<(s+1)2{\displaystyle {\text{Output: }}(s,r){\text{ such that }}s^{2}\leq n=s^{2}+r<(s+1)^{2}}
(s′،ر′)←الجذر التربيعي للباقي(أ3ب+أ2){\displaystyle \qquad (s',r')\gets {\text{SqrtRem}}(a_{3}b+a_{2})}
(q،u)←DivRem(ر′ب+أ1،2s′){\displaystyle \qquad (q,u)\gets {\text{DivRem}}(r'b+a_{1},2s')}
s←s′ب+q{\displaystyle \qquad s\gets s'b+q}
ر←uب+أ0-q2{\displaystyle \qquad r\gets ub+a_{0}-q^{2}}
لو ر<0 ثم {\displaystyle \qquad {\text{if }}r<0{\text{ then }}}
ر←ر+2s-1{\displaystyle \qquad \qquad r\gets r+2s-1}
s←s-1{\displaystyle \qquad \qquad s\gets s-1}
يعود (s،ر){\displaystyle \qquad {\text{return }}(s,r)}

لأن استدعاءً تكراريًا واحدًا فقط يتم إجراؤه لكل مستوى، فإن التعقيد الكلي يظليا(ن){\displaystyle O(n)}في عدد البتات. كل مستوى يُجري عمليات حسابية خطية فقط على أرقام نصف الحجم.

مقارنة مع عملية الضرب في كاراتسوبا

ملكيةضرب كاراتسوباالجذر التربيعي على طريقة كاراتسوبا
عدد الاستدعاءات المتكررة لكل مستوى31
تكرارتي(ن)=3تي(ن/2)+يا(ن){\displaystyle T(n)=3T(n/2)+O(n)}تي(ن)=تي(ن/2)+يا(ن){\displaystyle T(n)=T(n/2)+O(n)}
التعقيد التقاربييا(نسجل2⁡3)≈يا(ن1.585){\displaystyle O(n^{\log _{2}3})\!\approx \!O(n^{1.585})}يا(ن){\displaystyle O(n)}
عملية رئيسيةثلاث عمليات ضرب جزئية وإعادة تركيبجذر تربيعي واحد متكرر وتصحيح جبري

الاستخدام والتاريخ

يُستخدم الجذر التربيعي على نمط كاراتسوبا بشكل أساسي في العمليات الحسابية ذات الدقة العالية على الأعداد الصحيحة الكبيرة جدًا، حيث يتكامل بكفاءة مع قسمة بيرنيكل-زيغلر وضرب كاراتسوبا . وقد حلله بول زيمرمان (1999) رسميًا لأول مرة. [ 3 ] وتشمل الأعمال العملية السابقة مارتن غاي (1985)، [ 2 ] وتظهر نسخ تكرارية منه في دونالد كنوث (1998). [ 4 ] وتُنفذ مكتبات GMP و MPIR الحديثة تقنيات تكرارية مماثلة.

التنفيذ بلغة بايثون

يُنفذ برنامج بايثون أدناه خوارزمية زيمرمان. بفرض عدد صحيحن≥0{\displaystyle n\geq 0}، SqrtRemويحسب في آن واحد جذره التربيعي الصحيحs=⌊ن⌋{\displaystyle s=\lfloor {\sqrt {n}}\rfloor }والباقي المقابلر=ن-s2{\displaystyle r=n-s^{2}}الخيار isqrt()متروك للتقدير . [ ملاحظة 5 ]

دالة SqrtRem ( n : int , word_bits : int = 32 ) -> tuple [ int , int ]: """  تعتمد هذه الدالة على خوارزمية الجذر التربيعي الصحيح من نوع Karatsuba لزيمرمان  [Zimmermann, 1999]. تقوم هذه الدالة بتقسيم المدخل n بشكل متكرر إلى أجزاء  بحجم `word_bits`، ثم تجمع النتائج الجزئية لحساب الجذر التربيعي الصحيح. الوسائط:  n (عدد صحيح): عدد صحيح غير سالب لحساب الجذر التربيعي له.  word_bits (عدد صحيح، اختياري): عدد البتات لكل "جزء" أو كتلة  مستخدمة عند تقسيم n بشكل متكرر. القيمة الافتراضية هي 32.  يمثل كل جزء جزءًا ثابت الحجم من n للخوارزمية. القيمة المرجعة:  tuple[int, int]: s = الجذر التربيعي الصحيح لـ n، r = باقي (n - s*s). ملاحظات:  يتحكم حجم الجزء في دقة الاستدعاء الذاتي. يؤدي استخدام قيمة أكبر لـ word_bits  إلى تقليل عمق الاستدعاء الذاتي ولكنه يزيد من حجم المسائل الفرعية؛ بينما  يؤدي استخدام قيمة أصغر لـ word_bits إلى زيادة عمق الاستدعاء الذاتي ولكنه يعمل على أجزاء أصغر. المرجع:  زيمرمان، ب. (1999). "جذر كاراتسوبا التربيعي"، تقرير بحثي رقم 3805، معهد أبحاث علوم الحاسوب والتحكم الآلي (Inria).  مؤرشف  على الرابط: https://inria.hal.science/inria-00072854v1/file/RR-3805.pdf إذا كان n < 0 : ارفع خطأ ValueError ( "يجب أن يكون n غير سالب" ) إذا كان n == 0 : أرجع 0 ، 0 # حالة بسيطة# تحديد عدد الأجزاء بحجم الكلمة (يحاكي تقسيم "الأجزاء" في زيمرمان) limblen = ( n . bit_length () + word_bits - 1 ) // word_bits# الحالة الأساسية: طرف واحد — احسب مباشرةً إذا كان طول الطرف <= 1 : s = isqrt ( n ) # أي دالة isqrt، على سبيل المثال، math.isqrt أو دالة مخصصة r = n - s * s أرجع s ، r# --- الخطوة 1: تقسيم n إلى جزأين: علوي وسفلي --- half_limbs = limblen // 2 shift = half_limbs * word_bits hi = n >> shift # النصف العلوي، يُقابل a3*b + a2 lo = n & (( 1 << shift ) - 1 ) # النصف السفلي، يُقابل a1*b + a0# --- الخطوة 2: استدعاء متكرر للجزء الأعلى --- s_high , r_high = SqrtRem ( hi , word_bits ) # الجذر التربيعي التقريبي للنصف الأعلى# --- الخطوة 3: إعادة التجميع لتقريب الجذر التربيعي الكامل --- الربع = إزاحة // 2 البسط = ( r_high << الربع ) | ( lo >> الربع ) # محاكاة خطوة زيمرمان DivRem المقام = s_high << 1 # حد 2*q = البسط // المقام إذا كان المقام صحيحًا، وإلا 0 # قسمة عددية صحيحة s_candidate = ( s_high << quarter ) + q # إعادة دمج الأعلى والأدنى# --- الخطوة 4: التحقق والتصحيح --- # تأكد من أن الباقي غير سالب وأن s*s <= n < (s+1)*(s+1) s = s_candidate r = n - s * sبينما r < 0 : # تصحيح المبالغة s -= 1 r = n - s * s بينما ( s + 1 ) * ( s + 1 ) <= n : # تصحيح التقليل s += 1 r = n - s * sأعد s و r

مثال على الاستخدام

for n in [( 2 ** 32 ) + 5 , 1234567890 , ( 1 << 1512 ) - 1 ]: s , r = SqrtRem ( n ) print ( f "SqrtRem( { n } ) = { s } , remainder = { r } " );
حساب

الجذر التربيعي لباقي قسمة 4294967301 يساوي 65536، والباقي يساوي 5

الجذر التربيعي لباقي قسمة 1234567890 = 3513641828، والباقي = 5763386306

SqrtRem(143665816004337822710282600285310394341474369045835074863414468709543787931907367746179403311452034095731304 0662341120712675104724642609551530845754081472546729572617 6390798239533794390664586422901425022705720782623275195705 3220218983971305018634078800548055251973907806245884614087189937340865371691338441989956445051526543084039211962387469415699218979531585795574920384684004258007709014706216763392717018544247025174258411677231986785008489302218244095) = 379032737378102767370356320425415662904513187772631008578870126471203845870697482014374611530431269030880793627229265919475483409207718357286202948008100864063587640630090308972232735749901964068667724412528434753635948938919935، الباقي = 758065474756205534740712640850831325809026375545262017157740252942407691741394964028749223060862538061761587254458531838950966818415436714572405896016201728127175281260180617944465471499803928137335448825056869507271897877839870

في لغات البرمجة

تخصص بعض لغات البرمجة عملية صريحة لحساب الجذر التربيعي للأعداد الصحيحة بالإضافة إلى الحالة العامة، أو يمكن توسيعها بواسطة المكتبات لهذا الغرض.

لغة البرمجةمثال على الاستخدامتم طرح الإصدار
كنيسة صغيرةBigInteger.sqrt(result, n);[ 5 ]BigInteger.sqrtRem(result, remainder, n);مجهول
لغة الشفرة الشائعة(isqrt n)[ 6 ]مجهول
كريستالMath.isqrt(n)[ 7 ]1.2
جافاn.sqrt()[ 8 ] (BigIntegerفقط)9
جولياisqrt(n)[ 9 ]0.3
خشب القيقبisqrt(n)[ 10 ]مجهول
طبيب عام/طبيب عامsqrtint(n)[ 11 ]1.35أ [ 12 ] (كما هو isqrt) أو قبل
PHPsqrt($num)[ 13 ]4
بايثونmath.isqrt(n)[ 14 ]3.8
مضرب(integer-sqrt n)[ 15 ](integer-sqrt/remainder n)مجهول
روبيInteger.sqrt(n)[ 16 ]2.5.0
الصدأn.isqrt()[ 17 ] n.checked_isqrt()[ 18 ]1.84.0
SageMathisqrt(n)[ 19 ]مجهول
مخطط(exact-integer-sqrt n)[ 20 ]R 6 RS
تي سي إلisqrt($n)[ 21 ]8.5
زيجstd.math.sqrt(n)[ 22 ]مجهول

الكسر المستمر لـ √c بناءً على isqrt

حساب الكسر المستمر البسيط لـج{\displaystyle {\sqrt {c}}}يمكن تنفيذ ذلك باستخدام عمليات الأعداد الصحيحة فقط، معالجذر التربيعي⁡(ج){\displaystyle \operatorname {isqrt} (c)}يُستخدم هذا الحد كبداية. تقوم الخوارزمية [ 23 ] بتوليد توسيع الكسر المستمر في شكله المتعارف عليه .

يتركأ0=⌊ج⌋{\displaystyle a_{0}=\lfloor {\sqrt {c}}\rfloor } ليكن الجذر التربيعي الصحيح لـج{\displaystyle c}.

لوج{\displaystyle c}إذا كان مربعًا كاملًا، فإن الكسر المستمر ينتهي فورًا:

ج=[أ0].{\displaystyle {\sqrt {c}}=[a_{0}].}

وإلا، فإن الكسر المستمر يكون دوريًا:

ج=[أ0؛أ1،أ2،...،أم¯]{\displaystyle {\sqrt {c}}=[a_{0};{\overline {a_{1},a_{2},\dots ,a_{m}}}]}،

حيث يشير الخط العلوي إلى الجزء المتكرر.

يمكن الحصول على الكسر المستمر من خلال العلاقة التكرارية التالية، والتي تستخدم فقط العمليات الحسابية للأعداد الصحيحة:

م0=0،د0=1،أ0=⌊ج⌋.{\displaystyle m_{0}=0,\quad d_{0}=1,\quad a_{0}=\lfloor {\sqrt {c}}\rfloor .}
لك≥0{\displaystyle k\geq 0}،
مك+1=دكأك-مك،دك+1=ج-مك+12دك،أك+1=⌊أ0+مك+1دك+1⌋.{\displaystyle m_{k+1}=d_{k}a_{k}-m_{k},\quad d_{k+1}={\frac {c-m_{k+1}^{2}}{d_{k}}},\quad a_{k+1}=\left\lfloor {\frac {a_{0}+m_{k+1}}{d_{k+1}}}\right\rfloor .}

بما أن عدد الثلاثيات الممكنة محدود(مك،دك،أك){\displaystyle (m_{k},d_{k},a_{k})}وفي النهاية يتكرر الأمر، ومن تلك النقطة فصاعدًا يصبح الكسر المستمر دوريًا.

التنفيذ بلغة بايثون

عند الإدخالج{\displaystyle c}، وهو عدد صحيح غير سالب، يحسب البرنامج التالي الكسر المستمر البسيط لـج{\displaystyle {\sqrt {c}}}الجذر التربيعي الصحيح⌊ج⌋{\displaystyle \lfloor {\sqrt {c}}\rfloor }يتم حسابها مرة واحدة. [ ملاحظة 5 ] يتم استخدام العمليات الحسابية للأعداد الصحيحة فقط. يُخرج البرنامج[أ0،(أ1،أ2،...،أم)]{\displaystyle [a0,(a1,a2,...,am)]}، حيث يمثل العنصر الثاني الجزء الدوري.

دالة حساب الكسر المستمر  للجذر التربيعي للعدد c باستخدام العمليات الحسابية الصحيحة. تُرجع الدالة مصفوفة من الأعداد الصحيحة تمثل الجزء الدوري . في حالة المربعات  الكاملة ، تكون الدورة فارغة  . مثال: `  a0 = isqrt ( c )` ، حيث a0 * a0 == c` ، و ` a0 = ( a0 , ( )) ` .m ، d ، a = 0 ، 1 ، a0 الفترة = [] المشاهدة = مجموعة ()بينما صحيح : m_next = d * a - m d_next = ( c - m_next * m_next ) // d a_next = ( a0 + m_next ) // d_nextإذا كانت ( m_next ، d_next ، a_next ) موجودة في seen : توقفتمت المشاهدة . أضف (( m_next , d_next , a_next )) الفترة . أضف ( a_next ) m , d , a = m_next , d_next , a_nextreturn ( a0 , tuple ( period ))

مثال على الاستخدام

for c in list ( range ( 0 , 18 )) + [ 114 ] + [ 4097280036 ]: cf = continued_fraction_sqrt ( c ) print ( f "sqrt( { c } ): { cf } " )

الناتج

المدخل (ج)الناتج (cf)الكسر المستمر
0[0]0=0{\displaystyle {\sqrt {0}}=0}
1[1]1=1{\displaystyle {\sqrt {1}}=1}
2[1; (2,)]2=[1؛2¯]{\displaystyle {\sqrt {2}}=[1;{\overline {2}}]}
3[1; (1, 2)]3=[1؛1،2¯]{\displaystyle {\sqrt {3}}=[1;{\overline {1,2}}]}
4[2]4=2{\displaystyle {\sqrt {4}}=2}
5[2؛ (4,)]5=[2؛4¯]{\displaystyle {\sqrt {5}}=[2;{\overline {4}}]}
6[2; (2, 4)]6=[2؛2،4¯]{\displaystyle {\sqrt {6}}=[2;{\overline {2,4}}]}
7[2; (1, 1, 1, 4)]7=[2؛1،1،1،4¯]{\displaystyle {\sqrt {7}}=[2;{\overline {1,1,1,4}}]}
8[2; (1, 4)]8=[2؛1،4¯]{\displaystyle {\sqrt {8}}=[2;{\overline {1,4}}]}
9[3]9=3{\displaystyle {\sqrt {9}}=3}
10[3؛ (6,)]10=[3؛6¯]{\displaystyle {\sqrt {10}}=[3;{\overline {6}}]}
11[3; (3, 6)]11=[3؛3،6¯]{\displaystyle {\sqrt {11}}=[3;{\overline {3,6}}]}
12[3; (2, 6)]12=[3؛2،6¯]{\displaystyle {\sqrt {12}}=[3;{\overline {2,6}}]}
13[3; (1, 1, 1, 1, 6)]13=[3؛1،1،1،1،6¯]{\displaystyle {\sqrt {13}}=[3;{\overline {1,1,1,1,6}}]}
14[3; (1, 2, 1, 6)]14=[3؛1،2،1،6¯]{\displaystyle {\sqrt {14}}=[3;{\overline {1,2,1,6}}]}
15[3؛ (1، 6)]15=[3؛1،6¯]{\displaystyle {\sqrt {15}}=[3;{\overline {1,6}}]}
16[4]16=4{\displaystyle {\sqrt {16}}=4}
17[4؛ (8,)]17=[4؛8¯]{\displaystyle {\sqrt {17}}=[4;{\overline {8}}]}
114[10; (1, 2, 10, 2, 1, 20)]114=[10؛1،2،10،2،1،20¯]{\displaystyle {\sqrt {114}}=[10;{\overline {1,2,10,2,1,20}}]}[ ملاحظة 7 ]
4097280036
[64009; (1, 1999, 3, 4, 1, 499, 3, 1, 3, 3, 1, 124, ... ..., 3, 1, 3, 499, 1, 4, 3, 1999, 1, 128018)] الفترة: 13032 حدًا [ ملاحظة 8 ]                

انظر أيضاً

ملحوظات

  1. ↑ الجذور التربيعية للأعداد المربعة الكاملة (مثل 0، 1، 4، 9، 16) هي أعداد صحيحة. في جميع الحالات الأخرى، تكون الجذور التربيعية للأعداد الصحيحة الموجبة أعدادًا غير نسبية.
  2. ↑ ليس من المستغرب أن يكون الضرب المتكرر في 100 سمة مميزة في كتاب جارفيس (2006).
  3. ↑ يتم تمثيل الجزء الكسري من الجذور التربيعية للأعداد المربعة الكاملة على النحو التالي: 000... .
  4. ↑ انظر طريقة هيرون .
  5. يمكن كتابة طريقة نيوتن على النحو التالي ( مع تحديد التخمين الأولي إلىs{\displaystyle s}): 
    دالة isqrt ( s : int ) -> int : """إيجاد الجذر التربيعي باستخدام تكرار نيوتن/هيرون.""" L , R = 1 , s بينما L < R : R = L + (( R - L ) // 2 ) L = s // R إرجاع R
    الحسابات
    • الجذر التربيعي⁡(0)=0{\displaystyle \operatorname {isqrt} (0)=0}،الجذر التربيعي⁡(1)=1{\displaystyle \operatorname {isqrt} (1)=1}.
    • حسابالجذر التربيعي⁡(2000000){\displaystyle \operatorname {isqrt} (2000000)}يتكون من13[ل،R]{\displaystyle 13\;[L,R]}خطوات:
    [1،2000000]→[2،1000000]→[3،500001]→[7،250002]→[15،125004]→[31،62509]→[63،31270]→[127،15666]→[253،7896]→[490،4074]→[876،2282]→[1266،1579]→[1406،1422]→[1414،1414]{\displaystyle {\begin{aligned}&[1,2000000]\to [2,1000000]\to [3,500001]\\&\to [7,250002]\to [15,125004]\to [31,62509]\\&\to [63,31270]\to [127,15666]\to [253,7896]\\&\to [490,4074]\to [876,2282]\to [1266,1579]\\&\to [1406,1422]\to [1414,1414]\end{aligned}}}
    يتضح أن تحسن أداء طريقة نيوتن مقارنةً بالبحث الثنائي يعود إلى حقيقة أن⌊s⌋{\displaystyle \lfloor {\sqrt {s}}\rfloor }يتم التعامل معها في وقت واحد من اليسار واليمين ، بينما يقوم البحث الثنائي بتعديل جانب واحد فقط في كل تكرار.
  6. ↑ تم شرح الخوارزمية في Square_root_algorithms#Binary numeral system (base 2)
  7. ↑ انظر المثال في مقالة الكسر المستمر الدوري .
  8. ↑ توسيع الكسر المستمر لـ4097280036{\displaystyle {\sqrt {4097280036}}}يبلغ طول هذه المتسلسلة 13032 حدًا. ورغم أن بايثون لا تستطيع عرض المتسلسلة كاملةً على الشاشة نظرًا لطولها، إلا أن كتابة الناتج إلى ملف تتم بنجاح.

مراجع

  1. ↑ جونسون، إس جي (4 فبراير 2015). "الجذور التربيعية باستخدام طريقة نيوتن" (ملف PDF) . دورة معهد ماساتشوستس للتكنولوجيا 18.335: مقدمة في الطرق العددية . تم الاطلاع عليه بتاريخ 12 أكتوبر 2025 .
  2. 1 2 3 غاي، مارتن (1985). "الجذر التربيعي السريع للأعداد الصحيحة باستخدام خوارزمية المعداد للسيد وو" . جامعة كنت في كانتربري (UKC). مؤرشف من الأصل في 6 مارس 2012. تم الاطلاع عليه في 5 أكتوبر 2025 .
  3. 1 2 3 زيمرمان، بول (1999). "جذر كاراتسوبا التربيعي" (ملف PDF) . تقرير بحثي رقم 3805. معهد أبحاث علوم الحاسوب والتحكم الآلي (Inria ) (نُشر في 24 مايو 2006). مؤرشف (ملف PDF) من الأصل في 11 مايو 2023.
  4. ↑ كنوت، دونالد إي. (1998). فن برمجة الحاسوب، المجلد 2: الخوارزميات شبه العددية ( الطبعة الثالثة). أديسون-ويسلي. ISBN  9780201896848.
  5. ↑ "BigInteger - وثائق Chapel 2.1" . وثائق Chapel - وثائق Chapel 2.1 .
  6. ↑ "CLHS: Function SQRT, ISQRT" . Common Lisp HyperSpec (TM ) .
  7. ↑ "الرياضيات - كريستال 1.13.2" . وثائق واجهة برمجة تطبيقات لغة برمجة كريستال .
  8. ↑ "BigInteger (Java SE 21 & JDK 21)" . وثائق JDK 21 .
  9. ↑ "الرياضيات - لغة جوليا" . وثائق جوليا - لغة جوليا .
  10. ↑ "مساعدة iroot- Maple" . مساعدة - Maplesoft .
  11. ↑ "كتالوج وظائف GP/PARI: الوظائف الحسابية" . مقر تطوير PARI/GP .
  12. ↑ "فهرس /archive/science/math/multiplePrecision/pari/" . موارد PSG الرقمية . مؤرشف من الأصل في 6 نوفمبر 2024.
  13. ↑ "الدوال الرياضية" . توثيق PHP .
  14. ↑ "الدوال الرياضية" . وثائق مكتبة بايثون القياسية .
  15. ↑ "4.3.2 الأرقام العامة" . وثائق Racket .
  16. ↑ "فئة عدد صحيح - وثائق RDoc" . وثائق RDoc .
  17. ↑ "i32 - Rust" . std - Rust .
  18. ↑ "i32 - Rust" . std - Rust .
  19. ↑ "عناصر حلقة الأعداد الصحيحة ℤ - حلقات التبديل القياسية" . وثائق SageMath .
  20. ↑ "التقرير السابع المنقح حول لغة البرمجة الخوارزمية Scheme" . معايير Scheme .
  21. ↑ "صفحة دليل الدوال الرياضية - دوال Tcl الرياضية" . دليل Tcl/Tk 8.6 .
  22. ↑ "std.math.sqrt.sqrt - وثائق Zig" . الصفحة الرئيسية ⚡ لغة برمجة Zig .
  23. ↑ بيسيانو، ماريوس (5 فبراير 2003). "دورة الكسر المستمر لجذر(ن)" (ملف PDF) . النظرية 2.3. مؤرشف (ملف PDF) من الأصل في 21 ديسمبر 2015. تم الاطلاع عليه في 5 أكتوبر 2025 .