كيفية التحقق من أن الجذر التربيعي لعدد هو عدد صحيح: 5 طرق في Java

مقدمة: مشكلة تهز Stack Overflow

تخيل: أنت تكتب كودًا يعالج آلاف الأرقام في الثانية. تحتاج إلى استبعاد تلك التي يكون جذرها التربيعي عددًا صحيحًا (1، 4، 9، 16...). يبدو الأمر بسيطًا؟ استخدمت Math.sqrt()، وتحقق من الباقي - وانتهى الأمر. لكن الأمر ليس بهذه السهولة.

السؤال "Fastest way to determine if an integer's square root is an integer" على Stack Overflow حصد بالفعل أكثر من 100,000 مشاهدة. لماذا؟ لأن Math.sqrt() هي عملية فاصلة عائمة، مما يعني أنها بطيئة وعرضة لأخطاء التقريب. بالنسبة للأعداد الكبيرة (مثل 2^50)، قد "يكذب" double ببساطة.

في هذه المقالة، سنستعرض 5 طرق في Java: من الأكثر سذاجة إلى الخوارزميات السريعة التي تستخدم العمليات البتية والحساب الصحيح. ستعرف أي طريقة أسرع حقًا، وأيها أكثر أمانًا. هيا بنا!

صياغة المشكلة

نحتاج إلى كتابة دالة boolean isPerfectSquare(long n) تُرجع true إذا كان n مربعًا كاملاً (perfect square). أمثلة:

\n
• isPerfectSquare(25) → true (5*5)
\n
• isPerfectSquare(26) → false
\n
• isPerfectSquare(0) → true (0*0)
\n
• isPerfectSquare(1) → true
\n

سنختبر على long، لأن int حالة خاصة، و long يعطي مساحة أكبر للأخطاء.

الطريقة 1: الساذجة - Math.sqrt + التحقق من الباقي

أبسط طريقة تخطر ببال المبتدئ:

public static boolean isPerfectSquareSqrt(long n) {\n    if (n < 0) return false;\n    double sqrt = Math.sqrt(n);\n    long floorSqrt = (long) sqrt;\n    return floorSqrt * floorSqrt == n;\n}\n

المشكلة رقم 1: الدقة. بالنسبة للأعداد الأكبر من ~2^53 (9,007,199,254,740,991)، يتوقف double عن تمثيل الأعداد الصحيحة بدقة. مثال: n = 999999999999999999L - سيعيد Math.sqrt نتيجة غير صحيحة.

المشكلة رقم 2: السرعة. Math.sqrt هي تعليمة معالج (FSQRT)، لكنها لا تزال أبطأ من العمليات الحسابية البسيطة.

متى تستخدم: فقط مع int أو long صغيرة (< 10^12)، حيث السرعة ليست حرجة.

الطريقة 2: الجذر التربيعي الصحيح عبر Newton-Raphson

طريقة نيوتن (Newton-Raphson) هي طريقة كلاسيكية لحساب الجذر التربيعي بدون أعداد فاصلة عائمة. نقوم بتحسين التقريب بشكل تكراري:

public static boolean isPerfectSquareNewton(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long x = n;\n    long y = (x + 1) / 2;\n    while (y < x) {\n        x = y;\n        y = (y + n / y) / 2;\n    }\n    return x * x == n;\n}\n

الخوارزمية تتقارب بسرعة كبيرة - في O(log log n) تكرار. بالنسبة للأعداد حتى Long.MAX_VALUE، تحتاج فقط 6-8 تكرارات.

المزايا: دقة مطلقة لجميع long (حتى 2^63-1). لا تستخدم double.

العيوب: القسمة عملية مكلفة. بالنسبة للأعداد الصغيرة جدًا (n < 4)، يمكن إضافة فحص في البداية.

الطريقة 3: البحث الثنائي عن الجذر

خوارزمية كلاسيكية أخرى - نبحث عن الجذر بالبحث الثنائي على الفترة [0, n]. بالنسبة لـ long، القيمة القصوى للجذر هي 3,037,000,499 (sqrt(Long.MAX_VALUE)).

public static boolean isPerfectSquareBinary(long n) {\n    if (n < 0) return false;\n    if (n < 2) return true;\n    long low = 1;\n    long high = 3037000499L; // sqrt(Long.MAX_VALUE)\n    while (low <= high) {\n        long mid = (low + high) >>> 1;\n        long square = mid * mid;\n        if (square == n) return true;\n        else if (square < n) low = mid + 1;\n        e