تحقق مما إذا كان الرقم مربعًا مثاليًا

Question

كيف يمكنني التحقق مما إذا كان الرقم مربعًا مثاليًا؟

السرعة ليست مصدر قلق ، في الوقت الحالي ، مجرد العمل.

Answer 1

مشكلة الاعتماد على أي حساب عائم (math.sqrt(x), ، أو x**0.5) هو أنه لا يمكنك أن تكون متأكدًا حقًا من أنها دقيقة (لأعداد صحيحة كبيرة بما فيه الكفاية x, ، لن يكون ، وربما يفيض). لحسن الحظ (إذا لم يكن المرء على عجل ؛-) هناك العديد من أساليب عدد صحيح نقي ، مثل ما يلي ...:

def is_square(apositiveint):
  x = apositiveint // 2
  seen = set([x])
  while x * x != apositiveint:
    x = (x + (apositiveint // x)) // 2
    if x in seen: return False
    seen.add(x)
  return True

for i in range(110, 130):
   print i, is_square(i)

تلميح: إنه يعتمد على "الخوارزمية البابلية" للاطلاع على الجذر التربيعي ، انظر ويكيبيديا. هو - هي يفعل اعمل على أي رقم إيجابي لديك ذاكرة كافية للحساب للمتابعة إلى الانتهاء ؛-).

تعديل: دعونا نرى مثالا ...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

هذه المطبوعات ، حسب الرغبة (وفي فترة زمنية معقولة أيضًا ؛-):

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

من فضلك ، قبل اقتراح حلول تستند إلى نتائج متوسطة النقطة العائمة ، تأكد من أنها تعمل بشكل صحيح على هذا المثال البسيط - إنه ليس كذلك الذي - التي صعب (تحتاج فقط إلى بعض الاختبارات الإضافية في حالة حدوث SQRT قليلاً) ، فقط يأخذ بعض العناية.

ثم حاول مع x**7 وإيجاد طريقة ذكية للعمل حول المشكلة ستحصل عليها ،

OverflowError: long int too large to convert to float

سيتعين عليك الحصول على المزيد والمزيد من الذكاء مع استمرار النمو ، بالطبع.

اذا انا كان على عجل ، بالطبع ، سأستخدمه GMPY -ولكن بعد ذلك ، أنا متحيز بوضوح ؛-).

>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0

نعم ، أنا أعلم ، هذا أمر سهل للغاية يبدو وكأنه غش (بالطريقة التي أشعر بها تجاه بيثون بشكل عام ؛-)-لا يوجد ذكاء على الإطلاق ، مجرد توجيه وبساطة مثالية (وفي حالة GMPY ، السرعة الشديدة ؛-) ...

Answer 2

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

بيثون ≥ 3.8 لديه math.isqrt. إذا كنت تستخدم نسخة أقدم من Python ، ابحث عن ""def isqrt(n)" التنفيذ هنا.

import math

def is_square(i: int) -> bool:
    return i == math.isqrt(i) ** 2

Answer 3

نظرًا لأنه لا يمكنك أبدًا الاعتماد على المقارنات الدقيقة عند التعامل مع حسابات النقطة العائمة (مثل هذه الطرق لحساب الجذر التربيعي) ، سيكون تطبيق أقل عرضة للخطأ

import math

def is_square(integer):
    root = math.sqrt(integer)
    return integer == int(root + 0.5) ** 2

يتصور integer هو 9. math.sqrt(9) ممكن ان يكون 3.0, ، ولكن يمكن أن يكون أيضا شيء مثل 2.99999 أو 3.00001, ، لذلك تربيع النتيجة غير موثوقة. مع العلم أن int يأخذ قيمة الأرضية ، وزيادة قيمة التعويم 0.5 يعني أولاً أننا سنحصل على القيمة التي نبحث عنها إذا كنا في نطاق حيث float لا يزال لديه دقة جيدة بما فيه الكفاية لتمثيل الأرقام القريبة من الأرقام التي نبحث عنها.

Answer 4

import math

def is_square(n):
    sqrt = math.sqrt(n)
    return (sqrt - int(sqrt)) == 0

المربع المثالي هو رقم يمكن التعبير عنه كمنتج لعامتين متساويتين. math.sqrt(number) إرجاع أ float. int(math.sqrt(number)) يلقي النتيجة int.

إذا كان الجذر التربيعي عدد صحيح ، مثل 3 ، على سبيل المثال ، إذن math.sqrt(number) - int(math.sqrt(number)) سيكون 0 ، و if البيان سيكون False. إذا كان الجذر التربيعي رقمًا حقيقيًا مثل 3.2 ، فسيكون ذلك True وطباعة "إنها ليست مربع مثالي".

فشل ل A Non-Square كبير مثل 15241578966620942600211155616526328303567490.

Answer 5

إذا كنت مهتمًا ، فلدي استجابة نقية على سؤال مماثل في Math stackexchange ، "اكتشاف المربعات المثالية بشكل أسرع من استخراج الجذر التربيعي".

قد لا يكون تنفيذي الخاص لـ Issquare (N) هو الأفضل ، لكني أحب ذلك. استغرقني عدة أشهر من الدراسة في نظرية الرياضيات ، والحساب الرقمي وبرمجة Python ، ومقارنة نفسي بالمساهمين الآخرين ، وما إلى ذلك ، للنقر مع هذه الطريقة حقًا. أنا أحب بساطتها وكفاءتها رغم ذلك. لم أر أفضل. قل لي ما هو رأيك.

def isSquare(n):
    ## Trivial checks
    if type(n) != int:  ## integer
        return False
    if n < 0:      ## positivity
        return False
    if n == 0:      ## 0 pass
        return True

    ## Reduction by powers of 4 with bit-logic
    while n&3 == 0:    
        n=n>>2

    ## Simple bit-logic test. All perfect squares, in binary,
    ## end in 001, when powers of 4 are factored out.
    if n&7 != 1:
        return False

    if n==1:
        return True  ## is power of 4, or even power of 2


    ## Simple modulo equivalency test
    c = n%10
    if c in {3, 7}:
        return False  ## Not 1,4,5,6,9 in mod 10
    if n % 7 in {3, 5, 6}:
        return False  ## Not 1,2,4 mod 7
    if n % 9 in {2,3,5,6,8}:
        return False  
    if n % 13 in {2,5,6,7,8,11}:
        return False  

    ## Other patterns
    if c == 5:  ## if it ends in a 5
        if (n//10)%10 != 2:
            return False    ## then it must end in 25
        if (n//100)%10 not in {0,2,6}: 
            return False    ## and in 025, 225, or 625
        if (n//100)%10 == 6:
            if (n//1000)%10 not in {0,5}:
                return False    ## that is, 0625 or 5625
    else:
        if (n//10)%4 != 0:
            return False    ## (4k)*10 + (1,9)


    ## Babylonian Algorithm. Finding the integer square root.
    ## Root extraction.
    s = (len(str(n))-1) // 2
    x = (10**s) * 4

    A = {x, n}
    while x * x != n:
        x = (x + (n // x)) >> 1
        if x in A:
            return False
        A.add(x)
    return True

واضحة ومباشرة جدا. أولاً ، يتحقق من أن لدينا عددًا صحيحًا ، وإيجابية في ذلك. وإلا لا يوجد أي جدوى. إنه يتيح 0 من خلال صحيح (ضروري وإلا فإن الكتلة التالية هي حلقة لا حصر لها).

تزيل الكتلة التالية من التعليمات البرمجية بشكل منهجي من القوى التي تبلغ 4 في أسماك فرعية سريعة جدًا باستخدام عمليات التحول والمنطق بت. في النهاية ، لا نجد issquare من n الأصلي ولكن من AK

تقوم الكتلة الثالثة من التعليمات البرمجية بإجراء اختبار بسيط بوليان. أقل ثلاثة أرقام مهمة ، في ثنائي ، من أي مربع مثالي هي 001. دائما. باستثناء الأصفار الرائدة الناتجة عن صلاحيات 4 ، على أي حال ، والتي تم حسابها بالفعل. إذا فشل الاختبار ، فأنت تعرف على الفور أنه ليس مربعًا. إذا مرت ، لا يمكنك التأكد.

وأيضًا ، إذا انتهى بنا المطاف مع 1 لقيمة اختبار ، فإن رقم الاختبار كان في الأصل قوة 4 ، بما في ذلك ربما 1 نفسه.

مثل الكتلة الثالثة ، يختبر الرابع قيمة مكان في العشرية باستخدام مشغل معامل بسيط ، ويميل إلى التقاط القيم التي تنزلق عبر الاختبار السابق. أيضا اختبار mod 7 و mod 8 و mod 9 و mod 13.

تقوم الكتلة الخامسة من الكود بفحص بعض الأنماط المربعة المثالية المعروفة. تسبق الأرقام التي تنتهي في 1 أو 9 بمضاعفات من أربعة. والأرقام التي تنتهي في 5 يجب أن تنتهي في 5625 ، 0625 ، 225 ، أو 025. لقد أدرجت الآخرين لكنني أدركت أنها كانت زائدة عن الحاجة أو لم تستخدم فعليًا.

أخيرًا ، تشبه الكتلة السادسة من الكود إلى حد كبير ما هو المستجيب الأول - Alex Martelli - الجواب. يجد بشكل أساسي الجذر التربيعي باستخدام الخوارزمية البابلية القديمة ، ولكن تقييده على القيم الصحيحة مع تجاهل النقطة العائمة. تم على حد سواء من أجل السرعة وتوسيع نطاق القيم القابلة للاختبار. لقد استخدمت مجموعات بدلاً من القوائم لأن الأمر يستغرق وقتًا أقل بكثير ، استخدمت تحولات بت بدلاً من التقسيم بمقدار اثنين ، واخترت بذكاء قيمة البداية الأولية بشكل أكثر كفاءة.

بالمناسبة ، لقد اختبرت رقم الاختبار الموصى به لـ Alex Martelli ، بالإضافة إلى عدد قليل من الأرقام التي يبلغ حجمها أكبر ، مثل:

x=1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625 ** 2
for i in range(x, x+2):
    print(i, isSquare(i))

طبع النتائج التالية:

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

وفعلت هذا في 0.33 ثانية.

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

يتم رفض ما يقرب من 99 ٪ من جميع الأعداد الصحيحة على أنها غير مربعة قبل تنفيذ استخراج الجذر البابلي ، وفي 2/3 الوقت الذي سيستغرقه البابلي لرفض عدد صحيح. وعلى الرغم من أن هذه الاختبارات لا تسرع العملية بشكل كبير ، فإن التخفيض في جميع أرقام الاختبار إلى فردية من خلال تقسيم جميع القوى 4 هل حقا يسارع الاختبار البابلي.

فعلت اختبار مقارنة الوقت. لقد اختبرت جميع الأعداد الصحيحة من 1 إلى 10 ملايين متتالية. باستخدام الطريقة البابلية فقط في حد ذاتها (مع تخمين أولي مصمم خصيصًا) ، استغرق الأمر 3 سطحي 3 بمعدل 165 ثانية (بدقة 100 ٪). باستخدام الاختبارات المنطقية فقط في الخوارزمية الخاصة بي (باستثناء البابلية) ، استغرق الأمر 127 ثانية ، فقد رفض 99 ٪ من جميع الأعداد الصحيحة على أنها غير مربعة دون رفض أي مربعات مثالية. من بين تلك الأعداد الصحيحة التي مرت ، كانت 3 ٪ فقط مربعات مثالية (كثافة أعلى بكثير). باستخدام الخوارزمية الكاملة أعلاه التي تستخدم كل من الاختبارات المنطقية واستخراج الجذر البابلي ، لدينا دقة 100 ٪ ، واختبار الانتهاء في 14 ثانية فقط. يستغرق أول 100 مليون عدد من الأعداد الصحيحة ما يقرب من دقيقتين 45 ثانية للاختبار.

تحرير: لقد تمكنت من إسقاط الوقت أبعد من ذلك. يمكنني الآن اختبار الأعداد الصحيحة من 0 إلى 100 مليون في دقيقة واحدة 40 ثانية. يضيع الكثير من الوقت التحقق من نوع البيانات والإيجابية. قم بإزالة أول شيكين وقطعت التجربة لمدة دقيقة. يجب على المرء أن يفترض أن المستخدم ذكي بما يكفي ليعرف أن السلبيات والطفارات ليست مربعات مثالية.

Answer 6

يمكن حل هذا باستخدام ال decimal وحدة للحصول على جذور مربعة دقة تعسفية وشيكات سهلة لـ "الدقة":

import math
from decimal import localcontext, Context, Inexact

def is_perfect_square(x):
    # If you want to allow negative squares, then set x = abs(x) instead
    if x < 0:
        return False

    # Create localized, default context so flags and traps unset
    with localcontext(Context()) as ctx:
        # Set a precision sufficient to represent x exactly; `x or 1` avoids
        # math domain error for log10 when x is 0
        ctx.prec = math.ceil(math.log10(x or 1)) + 1  # Wrap ceil call in int() on Py2
        # Compute integer square root; don't even store result, just setting flags
        ctx.sqrt(x).to_integral_exact()
        # If previous line couldn't represent square root as exact int, sets Inexact flag
        return not ctx.flags[Inexact]

للتظاهر مع القيم الضخمة حقًا:

# I just kept mashing the numpad for awhile :-)
>>> base = 100009991439393999999393939398348438492389402490289028439083249803434098349083490340934903498034098390834980349083490384903843908309390282930823940230932490340983098349032098324908324098339779438974879480379380439748093874970843479280329708324970832497804329783429874329873429870234987234978034297804329782349783249873249870234987034298703249780349783497832497823497823497803429780324
>>> sqr = base ** 2
>>> sqr ** 0.5  # Too large to use floating point math
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: int too large to convert to float

>>> is_perfect_power(sqr)
True
>>> is_perfect_power(sqr-1)
False
>>> is_perfect_power(sqr+1)
False

إذا قمت بزيادة حجم القيمة التي يتم اختبارها ، فإن هذا في النهاية يصبح بطيئًا إلى حد ما (يأخذ ما يقرب من ثانية لمدة 200000 بت) ، ولكن لأرقام أكثر اعتدالًا (على سبيل المثال ، 20.000 بت) ، فإنه لا يزال أسرع مما يلاحظه الإنسان القيم الفردية (~ 33 مللي ثانية على الجهاز الخاص بي). ولكن نظرًا لأن السرعة لم تكن شاغلك الأساسي ، فهذه طريقة جيدة للقيام بذلك مع مكتبات Python القياسية.

بالطبع ، سيكون استخدامه أسرع بكثير gmpy2 واختبار فقط gmpy2.mpz(x).is_square(), ، ولكن إذا لم تكن حزم الطرف الثالث هي الشيء الخاص بك ، فإن ما سبق يعمل بشكل جيد.

Answer 7

لقد نشرت للتو تباينًا طفيفًا على بعض الأمثلة المذكورة أعلاه على موضوع آخر (العثور على مربعات مثالية) وأعتقد أنني سأتضمن تباينًا طفيفًا لما نشرته هنا (باستخدام NSQRT كمتغير مؤقت) ، في حالة اهتمامه / الاستخدام:

import math

def is_square(n):
  if not (isinstance(n, int) and (n >= 0)):
    return False 
  else:
    nsqrt = math.sqrt(n)
    return nsqrt == math.trunc(nsqrt)

إنه غير صحيح للحصول على غير مربع كبير مثل 15241578966620942600211155616526328303567490.

Answer 8

اجابتي هي:

def is_square(x):
    return x**.5 % 1 == 0

يقوم بشكل أساسي بجذر تربيعي ، ثم Modulo by 1 لتجريد الجزء الأيمن وإذا كانت النتيجة 0 عودة True خلاف ذلك العودة False. في هذه الحالة ، يمكن أن يكون X أي عدد كبير ، ليس بنفس حجم الرقم العائم Max الذي يمكن أن يتعامل معه Python: 1.7976931348623157e+308

إنه غير صحيح للحصول على غير مربع كبير مثل 15241578966620942600211155616526328303567490.

Answer 9

هذه هي طريقتي:

def is_square(n) -> bool:
    return int(n**0.5)**2 == int(n)

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

إنه غير صحيح لمربع كبير مثل 15241578966620942600211155616526328303567489.

Answer 10

يمكنك البحث الثنائي للجذر التربيعي المستدير. مربع النتيجة لمعرفة ما إذا كان يطابق القيمة الأصلية.

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

Answer 11

1. قرر المدة التي سيكون فيها الرقم.
2. خذ دلتا 0.000000000000 ....... 000001
3. معرفة ما إذا كان (SQRT (x))^2 - x أكبر / متساوية / أصغر من دلتا ويقرر بناءً على خطأ دلتا.

Answer 12

لا يتعلق هذا الرد بسؤالك المعلن ، ولكن لسؤال ضمني أراه في الرمز الذي نشرته ، أي ، "كيف تتحقق مما إذا كان هناك شيء صحيح؟"

الإجابة الأولى التي ستحصل عليها عمومًا إلى هذا السؤال هي "لا!" وهذا صحيح أنه في بيثون ، عادة ما يكون TypeChecking هو الشيء الصحيح الذي يجب القيام به.

بالنسبة لتلك الاستثناءات النادرة ، بدلاً من البحث عن نقطة عشرية في تمثيل السلسلة للرقم ، فإن الشيء الذي يجب القيام به هو استخدام Isinstance وظيفة:

>>> isinstance(5,int)
True
>>> isinstance(5.0,int)
False

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

>>> x=5.0
>>> round(x) == x
True

ولكن كما غطت أي شخص آخر بالتفصيل ، هناك مشكلات في نقطة عائمة يجب مراعاتها في معظم الأمثلة غير العليا لهذا النوع من الأشياء.

Answer 13

إذا كنت ترغب في الحصول على حلقة على نطاق وفعل شيء لكل رقم ليس مربعًا مثاليًا ، فيمكنك فعل شيء مثل هذا:

def non_squares(upper):
    next_square = 0
    diff = 1
    for i in range(0, upper):
        if i == next_square:
            next_square += diff
            diff += 2
            continue
        yield i

إذا كنت تريد أن تفعل شيئًا لكل رقم مربع مثالي ، يكون المولد أسهل:

(n * n for n in range(upper))

Answer 14

أعتقد أن هذا يعمل وبسيط للغاية:

import math

def is_square(num):
    sqrt = math.sqrt(num)
    return sqrt == int(sqrt)

إنه غير صحيح للحصول على غير مربع كبير مثل 15241578966620942600211155616526328303567490.

Answer 15

import math

def is_square(n):
    sqrt = math.sqrt(n)
    return sqrt == int(sqrt)

فشل ل A Non-Square كبير مثل 15241578966620942600211155616526328303567490.