10827 c++ - a^b

큰 수 string 계산 c++ 버전.

 

cmath 함수인 pow를 사용하지 못하는 이유는 부동소수점 연산을 사용하여 근사값을 계산하기 때문입니다.
부동소수점은 IEEE 754 표준을 따르며, C++의 double 타입은 약 15~17자리 십진수 정밀도를 제공합니다.

테스트 케이스를 보면 소수점들이 들어가 있는데 이를 부동소수점으로 저장하면 이진수로 근사 처리되어 미세한 차이가 발생합니다.
부동소수점 연산은 각 단계에서 오차를 누적시킵니다. 거듭제곱 연산은 반복 곱셈을 포함하므로, 결과에 포함된 오차가 더 커집니다.

#include <cmath>
int main(void) {
  double s;
  double p;

  cin >> s >> p;
  cout.precision(20);

  cout << pow(s, p);

  return 0;
}

 

그래서 해당 문제에서는 고정 소수점으로 처리를 해야하며 해결하기 위해서는 문자열 기반 계산을 사용합니다.

finder로 소수점을 찾고 power 연산을 재귀적으로 처리하여 곱셈을 해줍니다.
문제에는 조건에 음수가 없어서 해당  처리를 하지 않았습니다.

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

string Add(string &s1, string &s2) {
  string result(max(s1.size(), s2.size()), '0');

  bool carry = false;

  for (int i = 0; i < result.size(); i++) {
    int temp = carry;
    carry = false;

    if (i < s1.size()) temp += s1[s1.size() - i - 1] - '0';
    if (i < s2.size()) temp += s2[s2.size() - i - 1] - '0';
    if (temp >= 10) {
      carry = true;

      temp -= 10;
    }
    result[result.size() - i - 1] = temp + '0';
  }
  if (carry) result.insert(result.begin(), '1');

  return result;
}

string Multiply(string &s1, string &s2) {
  string result = "0";

  for (int i = 0; i < s2.size(); i++) {
    string line(s1);
    int carry = 0;
    for (int j = s1.size() - 1; j >= 0; j--) {
      int temp = carry;
      carry = 0;
      temp += (s1[j] - '0') * (s2[s2.size() - i - 1] - '0');
      if (temp >= 10) {
        carry = temp / 10;
        temp %= 10;
      }
      line[j] = temp + '0';
    }
    if (carry > 0) line.insert(line.begin(), carry + '0');
    line += string(i, '0');
    result = Add(result, line);
  }

  return result;
}

string power(string &s1, int p) {
  if (p == 1) return s1;
  string result = power(s1, p - 1);
  result = Multiply(result, s1);
  return result;
}

int main(void) {
  string s;
  int p;
  cin >> s >> p;

  auto finder = find(s.begin(), s.end(), '.');
  int idx = 0;

  if (finder != s.end()) {
    idx = s.end() - finder - 1;

    s.erase(finder);
  }
  idx *= p;

  string result = power(s, p);

  if (idx > 0) result.insert(result.end() - idx, '.');
  cout << result << "\n";

  return 0;
}