Re: GMP Problem with % under C++
Miki Hermann writes: I am very well familiar with the % operator in %. Swell. In the document, whose link you sent me, and which I have read before, it is mentioned that Function: mpz_class operator% (mpz_class a, mpz_class d) This means, that the % operator in GMP overloads the usual % operator in C++. Correctamente. Just to recall you, for integer a and b, b > 0, the result of the modulus operator is an integer in the range 0..b-1. If a is negative, the result is equal to (k*b + a) % b for any positive integer k making the expression (k*b + a) positive. By definition for a >= 0 and b > 0, we have a = q*b + (a % b), where q is an integer called quotient. Right, but that is irrelevant since % is not a mathematical modulus operator. Did you not just say you were "very well familiar" with it? Did you *really* read the page Marc pointed you to. This is all mentioned there. Please do read it and get on with your life. -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: GMP Problem with % under C++
I am very well familiar with the % operator in %. In the document, whose link you sent me, and which I have read before, it is mentioned that Function: mpz_class operator% (mpz_class a, mpz_class d) This means, that the % operator in GMP overloads the usual % operator in C++. Just to recall you, for integer a and b, b > 0, the result of the modulus operator is an integer in the range 0..b-1. If a is negative, the result is equal to (k*b + a) % b for any positive integer k making the expression (k*b + a) positive. By definition for a >= 0 and b > 0, we have a = q*b + (a % b), where q is an integer called quotient. Best regards, Miki On Thu, 2020-11-05 at 22:15 +0100, Marc Glisse wrote: > On Thu, 5 Nov 2020, Miki Hermann wrote: > > > 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++. > > It is very probable that you are not familiar with the % operator in > C or > C++, and that you did not read our documentation at > > https://gmplib.org/manual/C_002b_002b-Interface-Integers > ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: GMP Problem with % under C++
On Fri, Nov 6, 2020 at 8:27 AM Niels Möller wrote: > [snip] > > So your problem really is with % in C++, GMP just follows the > conventions for the builtin integers. > Rather, the OP is expecting that the ''%" operator in his C++ program will behave as mpz_mod() does - which is the same way as the "%" operator behaves in perl. To me, it's not surprising that he would have that expectation. I'm not saying that it's a *reasonable* expectation, as I don't know C++. To the op: If you want to get gmp performance into your perl script, then install Math::GMP and, instead of: use bigint; do: use bigint lib => 'GMP'; ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: GMP Problem with % under C++
Ciao, Il 2020-11-05 22:27 Niels Möller ha scritto: I think this is the same result you get with a plain (64-bit) long. The / and % operators in C++ produce a quotient rounded towards 0, so (f(1) - b) / DECKSIZE == 0, and the corresponding remainder is negative. I'm not that familiar with perl, but I guess it uses the mathematically more sane definition of always rounding the quotient towards -infinity, Every language has its own definition :-) https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages Ĝis, m ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: GMP Problem with % under C++
Miki Hermann writes: > 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 I think this is the same result you get with a plain (64-bit) long. The / and % operators in C++ produce a quotient rounded towards 0, so (f(1) - b) / DECKSIZE == 0, and the corresponding remainder is negative. I'm not that familiar with perl, but I guess it uses the mathematically more sane definition of always rounding the quotient towards -infinity, so that (f(1) - b) / DECKSIZE == -1. So your problem really is with % in C++, GMP just follows the conventions for the builtin integers. I'm not even sure if rounding is specified by the C++ standards, but rounding towards zero is what all C and C++ implementations I'm aware of use. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: GMP Problem with % under C++
On Thu, 5 Nov 2020, Miki Hermann wrote: 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++. It is very probable that you are not familiar with the % operator in C or C++, and that you did not read our documentation at https://gmplib.org/manual/C_002b_002b-Interface-Integers -- Marc Glisse ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
GMP Problem with % under C++
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", &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 De