Modulo for large answer

Question

Hello

I have come across a question to print answer as module..

I do understand that every data type has max limit to store the value..beyond that we cannot store values. That is the reason why we use modulo but how to use it ks something I am not getting.

Any help would be helpful

Thanks..
-ketan

Answer 1

an example illustrating your problem would be appreciated! :)

Answer 2

Indeed. Hi Ketan Lalcheta, i like this question and I am following this.

I tried this:
void Test2()
{

const unsigned int M = 1000000007;

cout << "Max possible int value is : " << INT_MAX << endl;

unsigned long long i = INT_MAX;

cout << "double of the same is: ";

cout << (2*i) << endl;

i = (2*i)%M;

cout << i << endl;

}

changed int to unsigned long long, and had something promising.(this is concluding that the size limit where (2*i) is operating is of the size of unsigned long long)

But I'm sorry, I don't have a proper explanation for you cause myself I'm still learning. Let's hope someone to answer and clear our doubt.

Answer 3

Hi RKK

My concern is that how module is helping to extend the limit of data type.

If int can't store some value beyond some limit, how modulo help to extend capacity?

Below is sample code :
https://code.sololearn.com/cTFAmkXGg0z8/?ref=app

Test2 also don't provide proper value of doubling int capacity

Answer 4

INT_MAX in climits gives us the maximum value of a SIGNED integer which is 2147483647

In Test2 function,application of the modulo operator(or any operator for that matter) to an unsigned integer causes all integers in that expression to be promoted to unsigned integers.

An unsigned integer has a range of between 0 and 4294967295
Now,the expression 2*i has an unsigned value of 4294967294 or a signed value of -2.
Since you're using a modulo operator with M which is unsigned,the -2 gets promoted to 4294967294
The final expression now becomes
4294967294%1000000007 which equals 294967266.

Answer 5

If you have to do an arithmetic operation between 2 very large numbers, e.g 64 bit numbers, it will result in overflow. The true result of the operation couldn’t be represented.

So, we need a intermediate value to store the value. If the question says to print the answer in modulo 1e9 + 7, that means the answer can be very huge, and should be between represented from 0 to 1e9 + 7.

Here are some modulo operations.
(a + b) % m = (a%m + b%m) % m
(a - b) % m = (a%m - b%m) % m
(a * b) % m = (a%m * b%m) % m
Doesn’t apply for division.

So you know when 2 numbers are too large to process, you can convert them into their modulo, and then apply the operation to obtain the result.

Answer 6

Anthony Maina and Bobby Fischer ,

Thanks a lot for your response...

My concern is that we are not able to get true result for large number by any means... So , we can't do anything with modulo also... Right?

It's just a representation of large result... So , it is just for manipulation on online challenge and don't have some practical use cases.. is this true ? As result represented is not the actual result...

I used to handle large operations as string manipulation... There also you don't get proper number in digits but it is string with actual equivalent value...

Is there any applicable usage of large module or is it mere for challenge purpose only ?

Answer 7

yes
yes
no
yes

Answer 8

Okay