python에서 pow(n, n) 와 n**n 중 어느게 빠를까?

제곱근 계산을 위한 함수인 pow(n, n)와 n**n 중 어느 게 더 빠를까?

 

결론부터 말하면 pow() 함수와 **는 "거의" 동일 합니다. 네 "거의"요

 

**의 경우 bignum을 통해 연산을 합니다, 반면 pow()는 부동소수점으로 변환되어 이 변환되는 과정이 있어 시간이 조금 더 소요된다고 합니다.

 

하지만 결국 power() 연산은 같은 함수를 하기 때문에 거의 비슷합니다.

 

여기 까지가 동작 과정의 대한 이야기인데... 실제 어떻게 구현되어 있는지 살짝만 보겠습니다.

 

---

https://github.com/python/cpython/blob/667b91a5e210e20946ad41f1796c544a1becf1b6/Objects/longobject.c#L4022

 

cpython의 pow 계산하는 일부분만 가져왔습니다.

/* pow(v, w, x) */
static PyObject *
long_pow(PyObject *v, PyObject *w, PyObject *x)
{
    PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
    int negativeOutput = 0;  /* if x<0 return negative output */

    PyLongObject *z = NULL;  /* accumulated result */
    Py_ssize_t i, j, k;             /* counters */
    PyLongObject *temp = NULL;

    /* 5-ary values.  If the exponent is large enough, table is
     * precomputed so that table[i] == a**i % c for i in range(32).
     */
    PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                               0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    /* a, b, c = v, w, x */
    CHECK_BINOP(v, w);
    a = (PyLongObject*)v; Py_INCREF(a);
    b = (PyLongObject*)w; Py_INCREF(b);
    ....................................

    if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
        /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
        /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf    */
        for (i = Py_SIZE(b) - 1; i >= 0; --i) {
            digit bi = b->ob_digit[i];

            for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
                MULT(z, z, z);
                if (bi & j)
                    MULT(z, a, z);
            }
        }
    }
    else {
        /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
        Py_INCREF(z);           /* still holds 1L */
        table[0] = z;
        for (i = 1; i < 32; ++i)
            MULT(table[i-1], a, table[i]);

        for (i = Py_SIZE(b) - 1; i >= 0; --i) {
            const digit bi = b->ob_digit[i];

            for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
                const int index = (bi >> j) & 0x1f;
                for (k = 0; k < 5; ++k)
                    MULT(z, z, z);
                if (index)
                    MULT(z, table[index], z);
            }
        }
    }

    ......................
    
    return (PyObject *)z;
}

pow()는 cpython에서 Objects/longobject.c 에서 long_pow() 함수를 호출합니다.

여기에서 봐야 할 부분은 Left-to-right binary exponentiation입니다.

만일 저희가 기존 방식대로 3^65537을 한다면 3을 65537번 곱해야 하지만,  3을 65537번 곱하는 대신 65537이 2^16+1인 것을 착안해서 계산 속도를 높일 수 있습니다.

 

1. 3^2

2. (3^2)^2

3. (3^4)^2

4. (3^8)^2

...

식으로 하면 16번으로 하면 65536이 되는데, 여기에 *3을 하여 65537번을 만들수 있습니다.. 결국 16+1번 즉 17번만 계산하면 3^65537을 구할 수가 있습니다.

다시 여기에서 지수의 비트들을 왼쪽에서 오른쪽으로 한번씩 훑으면서 비트마다 

1. 해당 비트가 0일 경우 해당 값의 제곱

2. 해당 비트가 1일 경우 해당 비트 자릿수

를 모든 자리를 순회하여 곱하면 해당 값을 얻게 됩니다..

 

해당 알고리즘을의 식은 다음과 같습니다..

 

- 해당 내용은 http://cacr.uwaterloo.ca/hac/about/chap14.pdf 14.6.1장 Techniques for general exponentiation에 상세히 나와있습니다.

 

---

 

여기까지 pow()의 연산 방식과 동작 과정을 살짝 맛보기만 보았습니다. 간단하게 재귀식으로 구한 하실 수 있지만, 되도록이면 내장 함수로 되어 있는 함수를 쓰는 걸 추천합니다.

 

 

 

- 번외

pow() 함수를 풀어쓰면

y = b^x    ===    log b ( y ) = x 

 

와 같은 등식이 됩니다. 즉 아래와 같이 치환이 가능하죠.

그리고 위의 binary exponentiation으로 2의 승수로 풀어쓰면

2^(y*log2(x))

이 되는데 해당 수식은 x86의 모든 칩셋에

FLY2X , FLY2XP1으로 명령어 집합이 정의되어 있습니다.

즉 계산이 일반 n번 제곱하여 곱하는것보다 log로 치환하면 CPU 지원으로 엄청나게 빠르다는 이야기!! 

 

진짜 끝!!

 

 

 

 

 

참고 자료

- https://stackoverflow.com/questions/48839772/why-is-time-complexity-o1-for-powx-y-while-it-is-on-for-xy/48848512#48848512

- https://yeojin-dev.github.io/blog/exponentiation-by-squaring/

- https://books.google.co.kr/books?id=806xDwAAQBAJ&pg=PT256&lpg=PT256&dq=%EB%AA%A8%EB%93%88%EB%9F%AC&source=bl&ots=C3uMzxZ9BK&sig=ACfU3U1L9W7XS2hlRh3YGI-gKgkLN5oURA&hl=ko&sa=X&ved=2ahUKEwi11K2FkojoAhWZUt4KHZH_BVkQ6AEwAXoECAwQAQ#v=onepage&q=%EB%AA%A8%EB%93%88%EB%9F%AC&f=false

- https://stackoverflow.com/questions/4638473/how-to-powreal-real-in-x86