Dear Sirs.
I have installed and started to use the GMP library. I wanted to use it
on Part B of the problem presented in Advent of Code 2019 on Day 22.
Previously, I was able to solve that problem only in Perl, using the
bigint library.
I am using Fedora 33. I downloaded and installed the GMP package by the
instruction 'sudo dnf install gmp gmp-devel'. The installation passed
without problems. The command 'sudo dnf info gmd' gives the following
answer:
Name : gmp
Epoch : 1
Version : 6.2.0
Release : 5.fc33
Architecture : x86_64
Size : 799 k
Source : gmp-6.2.0-5.fc33.src.rpm
Repository : @System
From repo : fedora
Summary : A GNU arbitrary precision library
URL : http://gmplib.org/
License : LGPLv3+ or GPLv2+
The command 'sudo dnf info gmd-devel' gives the following answer:
Name : gmp-devel
Epoch : 1
Version : 6.2.0
Release : 5.fc33
Architecture : x86_64
Size : 351 k
Source : gmp-6.2.0-5.fc33.src.rpm
Repository : @System
From repo : fedora
Summary : Development tools for the GNU MP arbitrary precision library
URL : http://gmplib.org/
License : LGPLv3+ or GPLv2+
The command 'uname -a' gives the following answer:
Linux kupka.lix.polytechnique.fr 5.8.17-300.fc33.x86_64 #1 SMP Thu Oct
29 15:55:40 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
I compiled the C++ sources with the command
g++ -o 22b-gmp 22b-gmp.cpp -lgmpxx -lgmp
The last line of the output of the command 'g++ -v' is
gcc version 10.2.1 20201016 (Red Hat 10.2.1-6) (GCC)
The result of the command '22b-gmp < 22input.txt' is:
*** b = 62010736820046
f(1) - b = -15681174147849
a = -15681174147849
On position 2020 is the card 102220661749926
For comparison, the result of the same computation in Perl with the
bigint package, by means of the command '22b-verbose.pl < 22input.txt"
is
*** b = 62010736820046
f(1) - b = -15681174147849
a = 103634543366198
On position 2020 is the card 93750418158025
My Perl program 22b-verbose.pl gives the right answer, as it was
approved by the Advent of Code website.
As you can see, the modulo operation % on Line 90 of the source file
22b-gmp.cpp has not been executed properly.
I am not sure if I used the GMP package properly or if I did everything
right, but it seems to me that very probably there is a problem
somewhere in the GMP package and/or its interface with C++. Please,
find enclosed the source of the C++ program (22b-gmp.cpp), the Perl
program (22-verbose.pl), and the input to both (22input.txt).
Thanks you very much in advance with dealing with my request.
Yous sincerely,
Nicolas (Miki) Hermann
#include
#include
#include
using namespace std;
const mpz_class DECKSIZE = mpz_class("119315717514047");
const mpz_class TURNSIZE = mpz_class("101741582076661");
const int CARD = 2020;
const string CUT = "cut";
const string DWI = "deal with increment";
const string DINS = "deal into new stack";
vector prog;
void read_input () {
string line;
while(getline(cin, line))
prog.push_back(line);
}
mpz_class f (mpz_class val) {
string line;
for (int step = 0; step < prog.size(); ++step) {
string line = prog[step];
int cut;
int increment;
if (line.substr(0, CUT.size()) == CUT) {
sscanf(line.c_str(), "cut %d", );
val = (val - cut + DECKSIZE) % DECKSIZE;
} else if (line.substr(0, DWI.size()) == DWI) {
sscanf(line.c_str(), "deal with increment %d", );
val = (increment * val) % DECKSIZE;
} else if (line.substr(0, DINS.size()) == DINS) {
val = DECKSIZE - 1 - val;
}
}
return val;
}
mpz_class inverse (const mpz_class a, const mpz_class n) {
mpz_class t = 0;
mpz_class newt = 1;
mpz_class r = n;
mpz_class newr = a;
while (newr != 0) {
mpz_class quo = r / newr;
mpz_class temp = r;
r = newr;
newr = temp % newr;
temp = t;
t = newt;
newt = temp - quo * newt;
}
if (r > mpz_class("1")) {
cerr << a << " is not invertible" << endl;
exit(1);
}
if (t < 0)
t += n;
return t;
}
mpz_class power (mpz_class x, mpz_class n) {
if (n == 0)
return 1;
mpz_class y = 1;
while (n > 1) {
if (n % 2 == 0) {
x = (x * x) % DECKSIZE;
n /= 2;
} else {
y = (x * y) % DECKSIZE;
x = (x * x) % DECKSIZE;
n = (n-1)/2;
}
}
return (x * y) % DECKSIZE;
}
int main(int argc, char **argv)
{
read_input();
mpz_class b = f(0);
mpz_class a = (f(1) - b) % DECKSIZE;
cout << "*** b= " << b << endl;
cout << "f(1) - b = " << f(1) - b << endl;
cout << "a= " << a << endl;
mpz_class ainv = inverse(a, DECKSIZE);
mpz_class a1inv = inverse(a-1, DECKSIZE);
mpz_class atok = power(a, TURNSIZE);
mpz_class rhs = (CARD - b * (atok-1) * a1inv) % DECKSIZE;
mpz_class atokinv = inverse(atok, DECKSIZE);
mpz_class x = (rhs * atokinv) % DECKSIZE;
cout << "On position " << CARD << " is the card " << x << endl;
}
22b-verbose.pl
Description:
