For my Discrete Structures class, I must calculate 53^37 (mod 77) in C++. On paper I know this is equivalent to 4, but after trying to code it myself and googling around, I cannot seem to get it to equal anything other than 16. I'm assuming it's because 53^37 is too big of a number to store.
Asked
Active
Viewed 129 times
0
-
7Think about what happens to the value (mod 77) on each multiplication. You don't need to calculate 53^37. – chris Oct 31 '20 at 03:22
-
As for any of the standard built-in types, even in modern C++, you will not be able to compile or calculate this with any basic integral or integer type. The operations on the values will cause an overflow. Either you will need to include a "large int" library that also supports the pow function for integers or write your own. – Francis Cugler Oct 31 '20 at 03:55
2 Answers
1
Taking 53^37 literally we can say 53*53*53*53*... a total of 37 times. We can rearrange it to be 53*53 = 2809 then it will result on 2809*2809*2809*... 18 times * a lone 53 at the end. Then find 2809 mod 77 = 37, this means that for each multiplication you get a reminder of 37 and we have 18 multiplications to do,
37 ^ 18 = 16890053810563300749953435929, then we multiply the lone 53 to get 895172851959854939747532104237.
This number is still too big so we repeat the process, 37 ^ 18 = 1369 ^ 9, we find 1369 mod 77 = 60, then it is 60 ^ 9 * a lone 53 = 534117888000000000, 534117888000000000 mod 77 = 4. This can be done recursively for any initial exponent.
Oslier
- 127
- 5
0
I tried the calculator in my phone. It would not calculate. I tried it with PHP. I got 16. I tired it with the 64-bit Windows 10 built-in calculator. It gave me "4". I tried it with 32-bit Windows XP's calculator. I also got "4". So, I guess the C++ math library cannot handle the big number. You can use other math library. I google to see what other math library people are using.
Most of them points to this GMP math library that can handle very big number. I have not done C++ for a long time. I am not sure this will work for you or not. But you can give it a try.
The main site looks very bad. https://gmplib.org/
I think this site has better example. https://www.cs.colorado.edu/~srirams/courses/csci2824-spr14/gmpTutorial.html
The PHP site has very good example. https://www.php.net/manual/en/ref.gmp.php
