[PYTHON] 어떻게 파이썬은 내장 함수 pow ()를 구현 했습니까?

어떻게 파이썬은 내장 함수 pow ()를 구현 했습니까?

** b % c를 계산하는 프로그램을 작성해야합니다. 여기서 b와 c는 모두 매우 큰 숫자입니다. ** b % c를 사용하면 정말 느립니다. 그런 다음 내장 함수 pow ()가 pow (a, b, c)를 호출하여이 작업을 매우 빠르게 수행 할 수 있다는 것을 알았습니다.  파이썬이 어떻게 구현하는지 알고 싶습니다. 아니면이 기능을 구현하는 소스 코드 파일을 어디에서 찾을 수 있습니까?

해결법

1. ==============================

   1.a, b 및 c가 정수인 경우 구현은 이진 지수 및 첫 번째 단계를 포함하여 각 단계의 모듈로 c를 줄여 더 효율적으로 만들 수 있습니다 (시작하기 전에 모듈로 c를 줄임). 이것은 long_pow ()의 구현이 실제로 무엇을하는지입니다.

   a, b 및 c가 정수인 경우 구현은 이진 지수 및 첫 번째 단계를 포함하여 각 단계의 모듈로 c를 줄여 더 효율적으로 만들 수 있습니다 (시작하기 전에 모듈로 c를 줄임). 이것은 long_pow ()의 구현이 실제로 무엇을하는지입니다.

2. ==============================

   2.다음 두 가지 구현을 고려하여 (x ** y) % z를 신속하게 계산할 수 있습니다.

   다음 두 가지 구현을 고려하여 (x ** y) % z를 신속하게 계산할 수 있습니다.

   파이썬에서 :

   def pow_mod(x, y, z):
       "Calculate (x ** y) % z efficiently."
       number = 1
       while y:
           if y & 1:
               number = number * x % z
           y >>= 1
           x = x * x % z
       return number
   

   C :

   #include <stdio.h>
   
   unsigned long pow_mod(unsigned short x, unsigned long y, unsigned short z)
   {
       unsigned long number = 1;
       while (y)
       {
           if (y & 1)
               number = number * x % z;
           y >>= 1;
           x = (unsigned long)x * x % z;
       }
       return number;
   }
   
   int main()
   {
       printf("%d\n", pow_mod(63437, 3935969939, 20628));
       return 0;
   }
   

3. ==============================

   3.이 파일의 1426 행은 math.pow를 구현하는 파이썬 코드를 보여 주지만, 기본적으로 그 함수의 최적화 된 버전을 가지고있는 표준 C 라이브러리를 호출하기 위해 사용됩니다.

   이 파일의 1426 행은 math.pow를 구현하는 파이썬 코드를 보여 주지만, 기본적으로 그 함수의 최적화 된 버전을 가지고있는 표준 C 라이브러리를 호출하기 위해 사용됩니다.

   파이썬은 집중적 인 숫자 처리를 위해 상당히 느릴 수 있지만 사이코는 표준 라이브러리를 호출하는 C 코드만큼 속도가 빠르다.

4. ==============================

   4.파이썬에 대해서는 잘 모르지만, 강력한 능력이 필요하다면, 제곱 법으로 지수를 쓸 수 있습니다 :

   파이썬에 대해서는 잘 모르지만, 강력한 능력이 필요하다면, 제곱 법으로 지수를 쓸 수 있습니다 :

   http://en.wikipedia.org/wiki/Exponentiation_by_squaring

   이것은 지수의 교환 적 속성을 사용하는 간단한 재귀 적 방법입니다.

5. ==============================

   5.파이썬은 일반적인 경우에는 C 수학 라이브러리를 사용하고 일부 개념 (예 : 무한대)에 대해서는 자체 논리를 사용합니다.

   파이썬은 일반적인 경우에는 C 수학 라이브러리를 사용하고 일부 개념 (예 : 무한대)에 대해서는 자체 논리를 사용합니다.

6. ==============================

   6.Python에서 pow (x, n) 구현하기

   Python에서 pow (x, n) 구현하기

   def myPow(x, n):
           p = 1
           if n<0:
               x = 1/x
               n = abs(n)
   
           # Exponentiation by Squaring
   
           while n:
               if n%2:
                   p*= x
               x*=x
               n//=2
           return p
   

   Python에서 pow (x, n, m) 구현하기

   def myPow(x,n,m):
               p = 1
               if n<0:
                   x = 1/x
                   n = abs(n)
               while n:
                   if n%2:
                       p*= x%m
                   x*=x%m
                   n//=2
               return p
   

   설명을 보려면이 링크를 체크 아웃하십시오.

from https://stackoverflow.com/questions/5246856/how-did-python-implement-the-built-in-function-pow by cc-by-sa and MIT license