Not Yet Answered # Big numbers

Discussion Starter nameless987 TheBeast32 54 Discussion Starter nameless987 grumpier 149 TheBeast32 54 Discussion Starter nameless987 grumpier 149 Discussion Starter nameless987 grumpier 149 Discussion Starter nameless987 grumpier 149 iamthwee 1,547 Write a C program that should create a 10 element array of random integers (0 to 9). The program should total all of the numbers in the odd positions of the array and compare them with the total of the numbers in the even positions of the array and indicate ...

0

Now I have problem with fmod...

i calculated with y=pow(a,e)

then fmod(y,n)... but now i seems that that fmod has to small range of results (same thing is with %)

is there some other function for mod?

0

Use the GMP library. It works for me. If you're using Dev-C++, you can just search for packages online with the built in "Check for updates/packages" thing, and find it in the list. If not go here: http://gmplib.org/

0

How to instal GMP library....dev c++ won'r downlod it, and i don't knoe how to install one i have downloaded from http://gmplib.org/

0

Talking about using a sledgehammer to crack a nut. No need to use high precision integers at all.

(a^b) mod c can be evaluated using a loop, using modulo arithmetic.

The basic property you need to know is that (x*y) mod z is equal to ((x mod z)*(y mod z)) mod z). From that it is possible to compute (a^b) mod c. I'll leave the precise code as an exercise.

0

Dev-C++ WILL download it. You have to pick the option in the package downloader that says community devpaks, scroll down and find it. Download it, and it should automatically bring you to an installer.

0

I tried to download it in that way...but i get some error that this file doesn't exist..

i figured out that i must use this kind calculations if i want to work with big nombers:

P = Cd % n

= 62^65 % 133

= 62 * 62^64 % 133

= 62 * (62^2)32 % 133

= 62 * 3844^32 % 133

= 62 * (3844 % 133)^32 % 133

= 62 * 120^32 % 133

.

.

.

= 62 * 36^16 % 133

= 62 * 99^8 % 133

= 62 * 92^4 % 133

= 62 * 85^2 % 133

= 62 * 43 % 133

= 2666 % 133

= 6

How can i write this in c++?

please help

0

i figured out that i must use this kind calculations if i want to work with big nombers:

P = Cd % n

= 62^65 % 133

= 62 * 62^64 % 133

= 62 * (62^2)32 % 133

= 62 * 3844^32 % 133

= 62 * (3844 % 133)^32 % 133

= 62 * 120^32 % 133

.

.

.

= 62 * 36^16 % 133

= 62 * 99^8 % 133

= 62 * 92^4 % 133

= 62 * 85^2 % 133

= 62 * 43 % 133

= 2666 % 133

= 6

How can i write this in c++?

please help

Try to express it as a loop construct. Your logic here is, mathematically, equivalent to what I said in my previous post.

0

The basic property you need to know is that (x*y) mod z is equal to ((x mod z)*(y mod z)) mod z). From that it is possible to compute (a^b) mod c. I'll leave the precise code as an exercise.

can you explain me how can i this basic property use for (a^b) mod c.

i'm not that good with this kind of math :$

0

Look at a small example

(21^5) mod 13

Step 1: 21 mod 13 = 8 (i.e remainder on dividing 21 by 13 is 8).

Step 2: ((21 mod 13) * (21 mod 13)) mod 13 = (8 * 8) mod 13 = 64 mod 13 = 12. This means 21^2 mod 13 = 12

Step 3: Use fact (from step 2) that 21^2 mod 13 is 12 and (from step 1) 21 mod 13 is 8. So 21^3 mod 13 = ((21^2 mod 13)*(21 mod 13)) mod 13 = (12*8) mod 13 = 96 mod 13 = 5.

Step 4: Use fact (from step 3) that 21^3 mod 13 = 5 and (from step 1) that 21 mod 13 = 8. So 21^4 mod 13 = ((21^3 mod 13) * (21 mod 13)) mod 13 = (5*8) mod 13 = 40 mod 13 = 1.

Step 5: Use fact (from step 4) that 21^4 mod 13 = 1 and (from step 1) that 21 mod 13 = 8. 21^5 mod 13 = ((21^4 mod 13) * (21 mod 13)) mod 13 = (1*8) mod 13 = 8 mod 13 = 8.

I've used a small values here (i.e. you can compute 21^5 by hand, and then find the remainder on dividing by 13). And you will find - if you do it that way - it is 8. The difference is that the method I've described will also work for 21^65 mod 30001 (albeit more iterations) without producing a value that can't be stored in a 32 bit integer along the way.

0

```
for(i=0;i<strlen(pra);i++)
{
tra=c[i];
y=1;
for(int u=0;u<d;u++)
{
y*=tra%n;
y=y%n;
}
p2[i]=y;
```

i use this code for calculating tra^d mod n

all numbers are int (tra, y, n, d)

it works for numbers

tra=31

d=7

n=33

but for numbers

tra=64

d=233

n=781

doesn't work

0

Ah. I forgot to take into account all the constraints to reduce overflow. You're probably using a 16 bit integer. n^2 needs to be representable in your integer type. 781^2 will not be representable in a 16 bit int, but will be with a 32 bit integer.

You can push to larger values of n by using the modulo relationship for addition (a + b) mod n = ((a mod n) + (b mod n)) mod n. If you use that, only 2*n needs to be representable in your integer type.

0

I would definitely recommend using the GMP library here.

I have dev-cpp and this is how I used it.

1) Download the devpack zip file provided by theBeast32

2) Unzip it.

3) Copy it into the directory `C:\Dev-Cpp\Packages`

4) Run it.

5) Open up Dev-cpp and create a console windows project.

6) Now the important bit.

Go to Tools > compiler options >

and paste into the box 'Add the following commands when calling the compiler':

`-lgmpxx -lgmp`

Make sure to tick the box is ticked.

**test code**

```
#include <iostream>
#include "gmp.h"
#include "gmpxx.h"
using namespace std;
mpz_class factorial ( mpz_class, mpz_class );
int main()
{
mpz_class a, b, c;
a = "125";
b = "107";
c = factorial ( a, b );
cout << c;
getchar();
return 0;
}
mpz_class factorial ( mpz_class a, mpz_class b )
{
mpz_class c = a;
for ( mpz_class i = b; i > 1; i-- )
{
c = c * a;
}
return c;
}
```

Now just hit the compile and run button.

**output**

```
23408381773460991635779247069293382849575116693970916581685777269301916383369998
24743317548769632316721526895315710009819587668709957465602306134616903764463545
37270758622261454531755971164574958720550057478249073028564453125
```

And you can even use the modulus operator as normal which is `%`

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

the function that I created to find the ...