오일러 프로젝트 16

오일러 프로제긑 16 번도 큰 수와 관련된 것이다. 을 10진수로 풀어 썼을 때의 모든 자리 숫자의 합을 구한다.

2^15 = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다. 2^1000의 각 자리수를 모두 더하면 얼마입니까?
http://euler.synap.co.kr/prob_detail.php?id=16

접근

은 파이썬과 같이 큰 수를 지원하는 언어의 경우 간단히 풀이된다

def p16():
    print(sum([int(x) for x in str(2**1000)]))
%time p16()
# 1366
# Wall time: 0 ns

한편 Swift에서의 정수는 64비트 크기를 가지므로 이렇게 큰 수를 다룰 수는 없다. (은 302자리 숫자이다) 따라서 큰 수를 계산하기 위한 별도의 타입이 필요하다. 13번 문제에서 소개하고 있는 BigNumber타입을 이용해서 BigNumber(integer: 2) 로 값을 만들고 이를 1000번 곱하면 된다.

func pow(_ base: BigNumber, _ m: Int) -> BigNumber {
  guard m > 0 else { return BigNumber(integer: 1 }
  var r = base
  for _ in 2..m {
    r = r * base
  }
  return r
}
let r = pow(BigNumber(integer: 2), 1000)
print(r.description.characters.flatMap{ Int(String($0)) }.reduce(0, +))

개선사항

1000제곱을 구하기 위해서 999번 곱하는 것은 조금 무식하지 않은가? 좀 더 빠른 거듭 제곱 계산 방식을 생각해보자. 지수법칙에 의하면 이다.  따라서 위에서 작성한 pow() 함수는 아래와 같이 개량할 수 있다.(참고로 이렇게 개량한 버전은 특히 오일러 프로젝트 48번 문제에서 큰 빛을 발한다.)

func powFast(_ base: BigNumber, _ m: Int) -> BigNumber {
  guard m > 0 else { return BigNumber(interger: 1) }
  let a = powFast(base, m/2)
  let result = a * a
  return ( m % 2 == 1) ? result * base : result
}