mod of two big hex numbers in c++

Question

i have two large hex numbers each one at least 70 digits (in decimal) and i am trying to calculate the value hex_a%hex_b:

string hex_a="1133A5DCDEF3216A63EB879A82F5A1DC4490CCF6412492CF1B242DB";
string hex_b="AAB3A5DCDEF3216A6AAA2F5A1DC4490CCF6412492CF1B242DB";

i try to convert the two hex numbers to decimal with stoi and store the value in string:

string a=to_string(stoi(hex_a, 0, 16));

but i am getting an error when using stoi method:

terminate called after throwing an instance of 'std::out_of_range'
  what():  stoi
Aborted (core dumped)

how can i calculate mod of two big numbers in c++ ?

Answer 1

You can utilize boost/multiprecision/cpp_int:

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <sstream>
#include <string>

using boost::multiprecision::cpp_int;

int main() {
  std::string hex_a = "0x1133A5DCDEF3216A63EB879A82F5A1DC4490CCF6412492CF1B242DB";
  std::string hex_b = "0xAAB3A5DCDEF3216A6AAA2F5A1DC4490CCF6412492CF1B242DB";
  cpp_int a(hex_a), b(hex_b);
  cpp_int result = a % b;
  std::cout << "Result as int: " << result << '\n';
  std::stringstream ss;
  ss << std::hex << result;
  std::string result_hex = ss.str();
  std::cout << "Result as hex: 0x" << result_hex << '\n';
  return 0;
}

Or GNU Multiple Precision Arithmetic Library (GMP), which might be faster:

#include <gmp.h>

int main() {
  mpz_t a, b, result;
  mpz_init(a);
  mpz_init(b);
  mpz_init(result);
  mpz_set_str(a, "1133A5DCDEF3216A63EB879A82F5A1DC4490CCF6412492CF1B242DB", 16);
  mpz_set_str(b, "AAB3A5DCDEF3216A6AAA2F5A1DC4490CCF6412492CF1B242DB", 16);
  mpz_mod(result, a, b);
  gmp_printf("Result as int: %Zd\n", result);
  gmp_printf("Result as hex: Ox%Zx\n", result);
  mpz_clear(a);
  mpz_clear(b);
  mpz_clear(result);
  return 0;
}

Output:

Result as int: 887778964514700662847592530576646032246936850244260028835776
Result as hex: 0x8d6e6cdeb792c9d42b257481c738989f678484c94fd6b567c0

Confirmation of the same result in Python:

>>> hex_a = "0x1133A5DCDEF3216A63EB879A82F5A1DC4490CCF6412492CF1B242DB"
>>> hex_b = "0xAAB3A5DCDEF3216A6AAA2F5A1DC4490CCF6412492CF1B242DB"
>>> a = int(hex_a, 16)
>>> b = int(hex_b, 16)
>>> result = a % b
>>> print(f'Result as int: {result}')
Result as int: 887778964514700662847592530576646032246936850244260028835776
>>> print(f'Result as hex: 0x{result:x}')
Result as hex: 0x8d6e6cdeb792c9d42b257481c738989f678484c94fd6b567c0