프리미엄 테스트가 무차별 방식보다 오래 걸리는데 어떻게 개선 할 수 있습니까?

Question

2^30-2^100 크기의 단일 시스템에서 소수를 계산하려고합니다.
내 알고리즘은 아래에 포함되어 있습니다.
나는이 파이썬 코드를 각 숫자에 대해 O(sqrt(n/2)) (나는 믿는다)으로 최적화했다 : 홀수 만 받아들이고 전달 된 숫자가 다른 메서드에서 이상하다는 것을 보장한다.

저는 페르마 소수성 테스트을 사용하여 프로세스 속도를 향상 시켰습니다. 그러나 숫자는 내장 된 math.pow() 방법에 비해 너무 큽니다. 그래서 지수로 제곱 한 값을 사용했습니다.
그러나 큰 수의 경우에는 매우 오랜 시간이 걸립니다.

구현이 잘못 되었습니까?
시간은 스퀘어 링 알고리즘에서 비롯됩니다. 반복 스택 또한 내 메모리를 먹어 치우며, 더 빠른 알고리즘으로 조사해야합니까?

숫자가 35184372088967이 소수인지 계산하려면 무차별 알고리즘을 사용하여 .00100111 초가 걸렸지 만 소수 테스트를 실행하려면 .40608 초가 걸립니다.

브 루트 포스 소수 검사 : 페르마의 알고리즘의

def isPrime(n): 
    for i in range(3,int(math.sqrt(n)),2): 
     if(n%i==0): 
      return False 
    return True 

구현 :

def couldBePrime(n): 
     if(n>308): 
      return power(2,n-1)%n==1 
     else: 
      return math.pow(2,n-1)%n==1 

(시간이 소요되는 부분) 알고리즘을 제곱하여 지수화 :

def power(base,exp): 
    if exp == 0: 
     return 1 
    elif exp == 1: 
     return base 
    elif (exp & 1) != 0: 
     return base * power(base * base, exp // 2) 
    else: 
     return power(base * base, exp // 2) 

Answer 1

버그 : math.pow 계산 부동 소수점 값 부동 소수점 계산은 대략적인 것이며 여기서 의미없는 결과를 제공합니다. power 함수에서 (비효율적으로) 정수 계산이 필요합니다. 파이썬에 내장 된 ** 연산자와 pow 함수 (다른 함수 인 math.pow은 아님)는 모두 정수에서 작동합니다.

많은 프로그래밍 언어에서와 마찬가지로 math이라는 라이브러리는 부동 소수점 계산과 관련되어 있으며 정수에서 수행 된 계산과 같은 다른 종류의 수학 계산이 아닙니다.

비효율 : b^e mod n을 계산하려면, 먼저 b^e를 계산 한 다음 n으로 결과를 나눌 필요없이 산술 모듈 n을 수행하는 것이 훨씬 효율적입니다. b^e를 계산하기 위해서는 매우 큰 숫자가 필요합니다. 계산이 더 높은 b의 큰 힘을 통과 할 때 숫자가 꽤 ​​빨리 커지기 때문에 속도가 느려집니다. (b^e를 계산하는 최적의 방법은 결정하기 쉽지 않지만 모든 방법은 b의 중간 승수를 계산하는 것뿐입니다. 실용적인 불확실성은 어떤 순서로 나타납니다.) 결과를 모듈로 n으로 만들려면 모든 연속 곱셈을 모듈로 n : b^2 mod n을 계산 한 다음, modulo n을 축소하여 b^4 mod n 등을 얻습니다. 곱셈을 수행 할 때마다 다른 작업을 수행하기 전에 나누기 나머지를 n 씩 취합니다.

파이썬에서는 표준 라이브러리 함수 pow (기억하지 말고, 은math.pow)은이를 수행합니다.파이썬이 기능을 가지고 있지 않은 경우 각 중간 결과 모듈로 n을 감소 있다면, 당신의 power 기능을 합리적인 방법은, 그것을 구현하기 간단한

def couldBePrime(n): 
    return pow(2, n-1, n) == 1 

으로합니다. 내장 함수를 호출

def power(base, exp, mod): 
    if exp == 0: 
     return 1 
    elif exp == 1: 
     return base % mod 
    elif (exp & 1) != 0: 
     return (base * power((base * base) % mod, exp // 2, mod)) % mod 
    else: 
     return power((base * base) % mod, exp // 2) 

는 훨씬 빨리, 물론입니다, 모두이 작업을 수행 할 수있는 매우 좋은 괜찮은하지만 방법은, 파이썬이기 때문에 더 빠른 속도에 비해 쓰기의 용이성을 위해 최적화 때문에 가능한 한 많이 수치 연산을 내장 함수에 그대로 두는 것이 가장 좋습니다.

추가 참고 사항 : 2의 거듭 제곱을 계산하려면 곱셈보다 훨씬 빠른 방법이 있습니다. bit shifting을 수행하십시오. 하지만 2^e가 아닌 2^e mod n을 계산하기를 원하기 때문에 여기서는 도움이되지 않습니다.