1 Востаннє редагувалося koala (10.10.2021 10:16:35)

Тема: Перевірка великого числа на квадрат

Проста задача: перевірити, чи є ціле число повним квадратом.

Наївне рішення:

def is_square(x):
    return (x**.5).is_integer()

Виявлений баг: якщо число велике (більше значущих цифр, ніж обробляє float), то is_integer може дати true через округлення. Наприклад, is_square(10**100+1) дає True, хоча має дати False.

Гаразд, наївне рішення №2:

def is_square(x):
    return int(x**.5)**2==x

Виявлений баг: якщо число по-справжньому велике (довжина більша, ніж обробляє float), то знову буде помилка, цього разу - виключна ситуація OverflowError. Наприклад, для is_square(10**1000) має бути True, а маємо помилку.

Правильне рішення: починаючи з Python 3.8, додано функцію math.isqrt, що обчислює цілу частину квадратного кореня саме як ціле число.

import math
def is_square(x):
    return math.isqrt(x)**2==x
Подякували: mamkin haker, leofun01, dot3

2

Re: Перевірка великого числа на квадрат

Для попередніх версій Python можна скористатися функціями is_square та isqrt з пакета gpmy2, або ж запрограмувати цілочисельний метод Ньютона:

def isquare(n):
    x_old = None
    x = n//2
    while x!=x_old:
        x_old, x = x, (x+n//x)//2
    return x
Подякували: mamkin haker, FakiNyan, dot, leofun014