[python] 숫자가 완벽한 제곱인지 확인

관심이 있으시면 math stackexchange에서 “제곱근을 추출하는 것보다 더 빨리 완벽한 제곱을 감지”라는 유사한 질문에 대한 순수 수학 응답을 얻었습니다 .

내 자신의 isSquare (n) 구현이 최고가 아닐 수도 있지만 마음에 듭니다. 이 방법을 실제로 클릭하기 위해 수개월 동안 수학 이론, 디지털 계산 및 파이썬 프로그래밍에 대해 공부하고 다른 공헌자 등과 비교했습니다. 그래도 단순성과 효율성이 마음에 듭니다. 나는 더 잘 보지 못했습니다. 네가 어떻게 생각하는지 내게 말해 줘.

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이 True로 미끄러지도록합니다 (필요하거나 다음 블록은 무한 루프입니다).

다음 코드 블록은 비트 시프트 및 비트 논리 연산을 사용하여 매우 빠른 하위 알고리즘에서 4의 거듭 제곱을 체계적으로 제거합니다. 우리는 궁극적으로 원래 n의 isSquare를 찾는 것이 아니라 가능하다면 4의 거듭 제곱으로 축소 된 k <n의 isSquare를 찾는 것입니다. 이것은 우리가 작업하는 숫자의 크기를 줄이고 실제로 바빌로니아 방식의 속도를 높이지만 다른 검사도 더 빠르게 만듭니다.

세 번째 코드 블록은 간단한 부울 비트 논리 테스트를 수행합니다. 완전 제곱의 최하위 3 자리 (2 진수)는 001입니다. 항상. 어쨌든 이미 설명 된 4의 거듭 제곱으로 인한 선행 0을 저장합니다. 테스트에 실패하면 사각형이 아님을 즉시 알 수 있습니다. 통과하면 확신 할 수 없습니다.

또한 테스트 값에 대해 1로 끝났다면 테스트 번호는 원래 1을 포함하여 4의 거듭 제곱이었습니다.

세 번째 블록과 마찬가지로 네 번째 블록은 단순 계수 연산자를 사용하여 10 진수의 1 자리 값을 테스트하고 이전 테스트를 통과하는 값을 포착하는 경향이 있습니다. 또한 mod 7, mod 8, mod 9 및 mod 13 테스트.

다섯 번째 코드 블록은 잘 알려진 완벽한 사각형 패턴 중 일부를 확인합니다. 1 또는 9로 끝나는 숫자 앞에는 4의 배수가옵니다. 그리고 5로 끝나는 숫자는 5625, 0625, 225 또는 025로 끝나야합니다. 다른 숫자를 포함했지만 중복되거나 실제로 사용 된 적이 없다는 것을 깨달았습니다.

마지막으로 여섯 번째 코드 블록은 최고 답변자 인 Alex Martelli의 답변과 매우 유사합니다. 기본적으로 고대 바빌로니아 알고리즘을 사용하여 제곱근을 찾지 만 부동 소수점을 무시하고 정수 값으로 제한합니다. 속도와 테스트 가능한 값의 크기 확장 모두를 수행합니다. 시간이 훨씬 적게 걸리기 때문에 목록 대신 세트를 사용했고, 2로 나누는 대신 비트 시프트를 사용했으며, 훨씬 더 효율적으로 초기 시작 값을 현명하게 선택했습니다.

그건 그렇고, Alex Martelli의 권장 테스트 번호와 다음과 같이 훨씬 더 큰 몇 가지 번호를 테스트했습니다.

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

다음 결과를 인쇄했습니다.

1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True
1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False

그리고 이것은 0.33 초 만에 이루어졌습니다.

내 생각에, 내 알고리즘은 Alex Martelli와 동일하게 작동하며 모든 이점을 제공하지만 다음과 같은 추가 이점이 있습니다. 매우 효율적인 단순 테스트 거부로 많은 시간을 절약 할 수 있습니다. 4, 속도, 효율성, 정확도 및 테스트 가능한 숫자의 크기를 개선합니다. 아마도 Python이 아닌 구현에서 특히 그렇습니다.

모든 정수의 약 99 %는 바빌로니아 루트 추출이 구현되기 전에 비 정사각형으로 거부되며, 바빌로니아가 정수를 거부하는 데 걸리는 시간은 2/3입니다. 그리고 이러한 테스트가 프로세스 속도를 크게 향상 시키지는 않지만 4의 모든 거듭 제곱을 나눔으로써 모든 테스트 수를 홀수로 줄이면 실제로 바빌로니아 테스트가 가속화됩니다.

시간 비교 테스트를했습니다. 1에서 1000 만까지의 모든 정수를 연속적으로 테스트했습니다. Babylonian 방법 만 사용하면 (특별히 맞춤화 된 초기 추측과 함께) Surface 3에 평균 165 초 (100 % 정확도)가 걸렸습니다. 내 알고리즘 (바빌로니아 제외)의 논리 테스트 만 사용하면 127 초가 걸렸고 실수로 완벽한 제곱을 거부하지 않고 모든 정수의 99 %를 비 정사각형으로 거부했습니다. 통과 한 정수 중 3 %만이 완벽한 제곱 (훨씬 더 높은 밀도)이었습니다. 논리적 테스트와 바빌로니아 루트 추출을 모두 사용하는 위의 전체 알고리즘을 사용하여 100 % 정확도를 가지며 단 14 초 만에 테스트 완료를 달성했습니다. 처음 1 억 개의 정수는 테스트하는 데 약 2 분 45 초가 걸립니다.

편집 : 나는 시간을 더 줄일 수 있었다. 이제 0에서 1 억까지의 정수를 1 분 40 초 안에 테스트 할 수 있습니다. 데이터 유형과 긍정 성을 확인하는 데 많은 시간이 낭비됩니다. 처음 두 가지 확인을 제거하고 실험을 1 분 줄였습니다. 네거티브와 플로트가 완벽한 제곱이 아니라는 것을 사용자가 충분히 똑똑하다고 가정해야합니다.