Wireframe

오일러 프로젝트 48

sooopd

‘n의 n 거듭제곱’의 합에 관한 문제.  이 문제에는 엄청나게 무식한 숫자인 1000^1000 이 등장하고 이는 무려 3000자리 숫자이다. 일단 문제를 살펴보자.

1^1 + 2^2 + 3^3 + … + 10^10 = 10405071317 입니다.
 
1^1 + 2^2 + 3^3 + … + 1000^1000 의 마지막 10자리 숫자는 무엇입니까?
(http://euler.synap.co.kr/prob_detail.php?id=48)

풀이

파이썬의 경우, 큰 수를 지원하는데, 1000^1000 과 같은 엄청 큰 수의 계산도 매우 빠르게 수행된다. 따라서 아래와 같이 나이브하게 작성된 코드도 아주 훌륭하게 수행된다.

def e48():
    print(str(sum((x**x for x in range(1, 1001))))[-10:])
%time e48()
#9110846700
#Wall time: 60 ms

Swift의 경우에는  큰수를 위한 BigNumber를 사용해야 한다. (https://gist.github.com/sooop/87acc0ff813c7f964a50388cf3de3c59) 그렇다고 하더라도 이 문제는 쉽게 계산되지는 않는다. 몇 가지 최적화가 필요하다.

  1. 마지막 10자리 숫자만 계산에 필요하다. 곱셈을 수행할 때, 여기에 영향을 주지 않는 더 큰 단위에 대해서는 굳이 계산을 수행할 필요가 없다.
  2. pow 함수를 따로 작성한다. 빠른 피보나치 변환에 나왔던 것처럼, 재귀적으로 수행되는 함수를 만들면 루프의 반복 횟수를 드라마틱하게 줄일 수 있다.

최적화

앞에서 소개한 팁 대로, 몇 가지 최적화를 수행해보자. BigNumber 는4자리 숫자 단위로 계산한다. 따라서 3차 이상의 항에 대해서는 곱셈에서 계산할 필요가 없다. 따라서 multiply(with:) 메소드를 약간 변경한 fastMultiply(with:) 를 다음과 같이 작성할 수 있다.

extension BigNumber {
  func fastMultiply(with other: BigNumber) -> BigNumber {
    let smallNodes = self.nodes.filter{ $0.level < 3 }.flatMap{ aNode in
      other.nodes.filter{ $0.level < 3 }.flatMap{ $0.multiply( aNode ) }
    }
    return BigNumber(nodes: smallNodes)
  }
}

그리고 빠른 거듭제곱 수행을 위해서 다음과 같이 pow() 함수를 개선한 fastPow() 를 작성한다.

func fastPow(_ a: BigNumber, _ b: Int) -> BigNumber {
  guard b > 0 else { return BigNumber(integer: 1) }
  let x = fastPow(a, b / 2)
  if b % 2 == 1 {
     return x.fastMultiply(with: x).fastMultiply(with: a)
  }
  return x.fastMultiply(with: x)
}

이제 최종 답은 다음과 같이 구할 수 있다. 파이썬에서 사용된 것처럼 나이브하게 작성한 코드와 성능차이가 얼마나 나는지는 직접 확인해보시라.

let x = (1...1000).map{ n in 
          let m = BigNumber(integer: n)
          return fastPow(m, n)
        }.reduce(BigNumber(integer: 0), +)
        .description
// 마지막 10개 글자
let ans = x[x.index(x.endIndex, offsetBy:-10)..<x.endIndex]
print(ans)
Exit mobile version