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 <iostream> #include <vector> #include <gmpxx.h> 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<string> 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", &cut); val = (val - cut + DECKSIZE) % DECKSIZE; } else if (line.substr(0, DWI.size()) == DWI) { sscanf(line.c_str(), "deal with increment %d", &increment); 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: Perl program
cut -7890 deal with increment 17 cut 3131 deal with increment 60 cut -5009 deal into new stack deal with increment 42 cut 9853 deal with increment 7 cut 9796 deal into new stack deal with increment 3 deal into new stack deal with increment 20 cut -8192 deal with increment 23 cut 9641 deal with increment 72 cut 7468 deal with increment 69 cut -7959 deal into new stack deal with increment 54 cut -3345 deal with increment 48 cut 105 deal with increment 67 deal into new stack deal with increment 66 cut 877 deal into new stack cut 2789 deal into new stack deal with increment 15 cut 8475 deal with increment 30 cut -7360 deal with increment 47 cut -4555 deal with increment 17 cut 1907 deal into new stack cut -1934 deal with increment 53 deal into new stack deal with increment 11 cut 8486 deal with increment 46 cut -4167 deal with increment 51 cut 3407 deal into new stack cut 7797 deal with increment 9 cut 6983 deal with increment 13 cut 4408 deal into new stack deal with increment 37 cut 422 deal with increment 18 cut 6433 deal with increment 11 cut 4689 deal into new stack cut 6073 deal with increment 25 cut -3262 deal with increment 21 cut -2736 deal into new stack deal with increment 53 cut -8515 deal with increment 9 cut 8314 deal with increment 41 deal into new stack deal with increment 34 cut 5004 deal with increment 53 cut 3004 deal into new stack deal with increment 6 cut -8757 deal with increment 38 cut -9534 deal with increment 27 cut 6052 deal with increment 54 cut 3907 deal into new stack cut 7995 deal into new stack cut 7291 deal with increment 15 cut 3884 deal with increment 4 cut -9637 deal with increment 59 cut -1150
_______________________________________________ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs