**연산자에대한 고찰

**연산자는 거듭제곱을 해주는 연산자이다

2^50을 2**50으로 쓸 수 있다.

 

나는 2**50은 

let result = 1;
let base = 2;
for (let i = 0; i < 50; i++) {
  result *= base;
}

과 마찬가지로 50번 반복을 할 줄알았는데

 

for 반복문, **연산자와

내가 쓴 거듭제곱의 시간복잡도를 O(logN)으로 줄이는 알고리즘

거듭제곱 시간복잡도 줄이기

function pow(base, exponent) {
  let mul = 1n;
  while (exponent > 1n) {
    if (exponent % 2n === 0n) {
      base *= base;
      exponent /= 2n;
    } else {
      mul *= base;
      base *= base;
      exponent /= 2n;
    }
  }
  return base * mul;
}

3가지 경우에대해서 

console.time()을 이용해서 시간을 재보았다

console.time("pow");
let a = pow(2n, 1100000n);
console.timeEnd("pow");

console.time("**");
let b = 2n ** 1100000n;
console.timeEnd("**");

console.time("for");
let result = 1n;
let base = 2n;
for (let i = 0n; i < 1100000n; i++) {
  result *= base;
}
console.timeEnd("for");

결과

pow: 3.253ms
**: 0.037ms
for: 11.483s

for가 압도적으로 많이 걸린다는것을 알 수 있다.

그런데 O(logN)으로 줄인 알고리즘보다 **이 더 빠르다는것을 알 수 있다.

 

조금 더 지수를 높여서 pow와 **을 비교해보면

console.time("pow");
let a = pow(2n, 1000000000n);
console.timeEnd("pow");

console.time("**");
let b = 2n ** 1000000000n;
console.timeEnd("**");

결과

pow: 12.323s
**: 11.084ms

**이 훨씬 빠르다는것을 알 수 있다.

 

현재 2의 10억승인데 pow의 경우 29번의 반복밖에 하지 않지만 12.3초나 걸린다

숫자가 커짐에 따라서 단순 곱셈자체가 오래걸리는거로 보인다.

그러면 **은 어떠한 알고리즘으로 되어있는지 검색해봐도 안나온다...

혹시 아시는분은 댓글달아주시면 감사하겠습니다.

 

---

그런데 이상한점이

4350085n ** 23377121n
이 연산은
**을 쓰든 pow함수를 쓰든 12초가 걸린다

이것저것 값 넣어보면서 해보니까

base가 2일때만 **이 압도적으로 빠르고

나머지일땐 똑같다

console.time("**");
let a = 3n ** 233771210n;
console.timeEnd("**");

console.time("pow");
let b = pow(3n, 233771210n);
console.timeEnd("pow");
// 결과
**: 7.719s
pow: 7.362s

console.time("**");
let a = 2n ** 233771210n;
console.timeEnd("**");

console.time("pow");
let b = pow(2n, 233771210n);
console.timeEnd("pow");
//결과
**: 3.655ms
pow: 3.975s

base가 2일때는 ** 연산은 비트 연산을 하는게 아닐까 싶다

2의 제곱 연산시 2진법에서는

10 -> 100
100 -> 10000
1000 -> 1000000

처럼 0을 2배로 붙여주면 된다