빅 정수 또한 이론을 알고 있습니다 ... 실제로는 녹슬지 않습니다.

Question

그래서 간단한 정수 클래스를 만들려고 노력 중이며 인터넷과 일부 페이지를 읽었지만 막혀 있습니다. . 나는 이론을 알고 있고 나는 캐리가 필요하다는 것을 안다. 그러나 내가 본 모든 예들, 그들은 문자들과 10 진법에 더 많이 촛점을 맞추었고, 나는 좀 더 빨라진 다른 접근법을 사용하고있다. 더하기 대입 연산자에 대한 도움을 주시면 감사하겠습니다. 나머지는 직접 알아볼 것입니다.

#include <iostream> 
#include <string> 
#include <vector> 

using std::cout; 
using std::endl; 

class big_integer { 
    using box = std::vector<int unsigned>; 
    box data {0}; 

    box split(std::string const & p_input) const { 
     box output; 
     for (size_t i {}; i < p_input.size(); i += 8) { 
      output.push_back(stoi(p_input.substr(i, 8))); 
     } 
     return output; 
    } 

public: 
    big_integer(std::string const & p_data) 
     : data {split(p_data)} 
    {} 

    big_integer(int unsigned const p_data) 
     : data {p_data} 
    {} 

    big_integer & operator +=(big_integer const & p_input) { 
     int carry {}; 

     for (size_t i {}; i < data.size(); ++i) { 

      //Need help here! 
      //All examples I see either use primitive arrays 
      //or are too esoteric for me to understand.    
      //data[i] += p_input.data[i] + carry; 

     } 

     return *this; 
    } 

    std::string to_string() const { 
     std::string output; 
     output.reserve(data.size() * 8); 
     for (auto const i : data) { 
      output.append(std::to_string(i)); 
     } 
     return output; 
    } 
}; 

std::ostream & operator <<(std::ostream & p_output, big_integer const & p_input) { 
    return p_output << p_input.to_string(); 
} 

int main() { 
    big_integer test1 {"126355316523"}; 
    big_integer test2 {255}; 

    test1 += test1; 

    cout << test1 << endl; 
    cout << test2 << endl; 
    return 0; 
} 

Answer 1

오른쪽. 그래서 기본적인 문제는 unsigned과 carry을주는 unsigned + unsigned + carry하는 방법입니다. 16 비트 정수를 고려하면 (32 비트에서 동일하게 작동하지만 입력이 더 많음) 첫 번째 숫자에서 0xFFFF + 0xFFFF == 0xFFFE + 1의 자리 올림 다음의 숫자 0xFFFF + 0xFFFF + carry == 0xFFFF + 캐리. 따라서 캐리는 오직 하나 일 수 있습니다. 이 알고리즘은 다음

unsigned lhs, rhs, carry_in; // Input 
    unsigned sum, carry_out;  // Output 

    sum = lhs + rhs; 
    carry_out = sum < lhs ; 
    sum += carry_in; 
    carry_out = carry_out || sum < lhs; 

기본적 아이디어는 unsigned의 첨가를 수행하고 배치를 검출 (따라서 수행)하는 것이다. 매우 성가신 것은 이것이 내가 사용했던 모든 명령어 세트의 명령어 인 "carry with add"를 구현하기위한 조건부 로직과 다중 명령어의 대량이라는 것입니다. (참고 : 오히려 ||보다 carry_out 사용 |의 최종 계산을 가치가있을 수 있습니다 - 그것은 성능 불량 인 분기 저장 도움이된다면 언제나처럼, 프로필을 볼 수 있습니다..)

당신은 결국에가는 경우 곱셈을 지원하려면 "자리"의 두 배인 유형이 필요합니다.이 경우 추가 할 수도 있습니다. 위의 변수를 사용하고 "부호 오래 오래"가정하는 것은 당신의 "폭"유형 :

const auto temp = (unsigned long long)lhs + rhs + carry_in; 
    sum = temp; // Will truncate. 
    carry_out = temp > UINT_MAX; 

당신의 "폭"유형을 선택하는 것은 까다로운 일이 될 수 있습니다. 첫 번째 단계에서 숫자에 uint32_t, 넓은 유형에 uint64_t을 사용하는 것이 가장 좋습니다.

다중 정밀도 산술을 구현하는 방법에 대한 자세한 내용은 Chapter 14 from Handbook of Applied Cryptography이 유용합니다.