كانت هناك حاجة للتحقق مما إذا كان العدد الصحيح هو مربع ، وإذا كان الأمر كذلك ، فقم بحساب الجذر. وأريد القيام بذلك في حساب عدد صحيح. من الواضح أن طريقة نيوتن يمكن تنفيذها في أعداد صحيحة ، لكنها تتطلب القسمة في كل خطوة. ولكن هل يمكن أن يكون الأمر خلاف ذلك؟ العثور على الجذر التربيعي modulo قوة اثنين ، وتحقق مما إذا كان سيكون الجذر التربيعي العادي.
يمكنك قصر نفسك على أرقام فردية: بالنسبة للرقم الزوجي ، إذا كان عدد الأرقام الصفرية الأقل أهمية هو رقم فردي ، فلا يوجد أي جذر ، ولكن إذا كان الرقم زوجيًا ، فيمكنك تحويل الرقم إلى اليمين ، وحساب جذر الرقم الفردي ، والانتقال إلى النصف الأيسر من الرقم الأصلي للصفر.
بالنسبة إلى N و 2
k ، k> 3 ، إذا كانت N ≡ 1 mod 8 ، فهناك 4 جذور مختلفة modulo 2
k ، وإلا لا توجد جذور. نحن بحاجة إلى أصغر من جذور x الأربعة. الثلاثة جذور الأخرى هي 2
ك - س ، 2
ك - 1 + س و 2
ك - 2
ك - 1 - س
أود الحصول على شيء مشابه لحساب
المعامل العكسي 2 ك - مضاعفة عدد البتات الصالحة لكل تكرار.
افترض أن لدينا بالفعل الجذر x
0 من N modulo 2
k :
N - x 0 2 = 2 k aونريد أن نجد
x 1 = x 0 + 2 k-1 y ، بحيث يوجد في N - x
1 2 عدد أقل من البتات صفر.
N - (x 0 + 2 k-1 y) 2 = 2 k a - 2 k x 0 * y - 2 2k-2 y 2قسّم على 2
k :
a - x 0 * y - 2 k-2 2 y 2وتساوي 0 modulo 2
k-2 :
y = a * x 0 -1 mod 2 k-2المستلمة
x 1 = x 0 + 2 k-1 a * (x 0 -1 mod 2 k-2 )وأخيرًا
x 1 = x 0 + (N - x 0 2 ) / 2 * (x 0 -1 mod 2 k-2 )من البتات k في التكرار التالي ، تحصل على 2 (k-1) بت. في الوقت نفسه ، نعتبر عكس الجذر في كل تكرار.
رمز الاختبار:
uint8_t sqr16(uint16_t n) { if (n % 8 != 1) return 0; uint16_t sqr = (n + 1) / 2; //4 bit uint16_t inv = 2 - sqr; sqr += inv * (n-sqr*sqr)/2; //6 bit inv *= 2 - sqr * inv; sqr += inv * (n-sqr*sqr)/2; //10 bit //inv *= 2 - sqr * inv; if (sqr & 256) sqr = 0u - sqr; sqr = (uint8_t)sqr; // lowest root if (n == sqr*sqr) return sqr; return 0; }
بإضافة بضع تكرارات ، نحصل على الجذر من uint_64