How to solve this easy in c or c++?

Question

print 10**1000 % 7

In C I get a syntax error because it exceeds the memory limit I guess. Can I somehow solve this easy in C or C++, such that it would give me a modulo of 10 to the power of 1000?

Don't just spam languages in the tags, the answer depends on the language. — Cory Kramer, Mar 19 '14 at 18:57
To represent so big numbers, that long long does not suffice, "bignums" are used — Jack L., Mar 19 '14 at 18:59
possible duplicate of http://stackoverflow.com/questions/18060242/how-to-store-extremely-large-numbers — Corley Brigman, Mar 19 '14 at 19:05
Are you asking about specifically `m^n%p` expressions - in which case there are tricks to be played. If you are asking "how do I deal with really large numbers in general", then it's a different question. — Mats Petersson, Mar 19 '14 at 19:05
So what is the question? You seem to be asking how to do this in C or C++. But you chose a python answer... — juanchopanza, Mar 19 '14 at 21:29

score 5 · Accepted Answer · answered Mar 19 '14 at 18:59

5

In addition to that not being valid syntax in C/C++, it's bad practice in python.

If you do

pow(10,1000,7)

It will use modular exponentiation so it will be much faster than doing

10 ** 1000 % 7

answered Mar 19 '14 at 18:59

Igglyboo

837
8
21

Which library are you getting that `pow` from? – juanchopanza Mar 19 '14 at 19:12
@juanchopanza pow is a builtin – Igglyboo Mar 19 '14 at 19:29
In which language? AFAIK C or C++ don't have built-in functions. They may have some operators, but `pow` is not one of them. – juanchopanza Mar 19 '14 at 19:30
@juanchopanza I was referring to his code which is written in python. – Igglyboo Mar 19 '14 at 19:30
1

Oh I see. But they are asking how to do this in C or C++, so you're not answering the question. – juanchopanza Mar 19 '14 at 19:32

LearningC · Answer 2 · 2014-03-20T07:00:57.807

3

you can use pow for power operation. here the size of result is large value so you need to divide the problem into smaller part and solve smaller ones to get the solution in c or you'll need to handle large numbers.
you can apply modulus rules to reduce the problem as,

10^1000 % 7 =((10%7)^1000)%7
10^1000 % 7 =(((((10^10)%7)^10)%7)^10)%7

combine these rules and use to reduce the numbers generated in steps by (mod 10).use inbuilt pow() function in c to get power of number as X^y=pow(x,y)

edited Mar 20 '14 at 07:00

answered Mar 19 '14 at 18:59

LearningC

3,182
1
12
19

The rule you use "a^b (mod p) = a^(b mod p) (mod p)" is only valid if `a` and `p` are coprime. Counterexample - 2^10 (mod 8) != 2^2 (mod 8) – M.M Mar 20 '14 at 01:48
@MattMcNabb ok. thanks. but the rule i specified is like 2^10(mod 8)=(2^2(mod 8))^5 (mod 8). – LearningC Mar 20 '14 at 06:58

score 2 · Answer 3 · answered Mar 19 '14 at 19:11

The most general way to solve these types of big-integer problems in small (e.g. 32-bit) registers is with exponentiation by squaring, and taking modulo at each step. E.g. 10^10 is still too big to fit in a 32-bit int, though you could probably just use a long these days.

haccks · Answer 4 · 2014-03-19T21:36:44.983

1

In C (and C++ too AFAIK) this is not a valid syntax. You can use pow function for exponentiation. But keep in mind that return value of pow is double and modulo operator works for int. You need some cautions.

long result = (long)pow(10, 1000);
result = result % 7;

edited Mar 19 '14 at 21:36

answered Mar 19 '14 at 18:57

haccks

104,019
25
176
264

1

A float Pow followed by a modulo operation won't yield any meaningful result. Same problem with using e.g. Pascal's Math.Pow. – Marco van de Voort Mar 19 '14 at 20:43
@MarcovandeVoort; Hey, yor point is valid! Adding to the answer. – haccks Mar 19 '14 at 20:45
1

The improvement doesn't help. Floating point numbers only have about 18 significant digits and 10^1000 has a thousand. One needs big integer, or rewriting (LearningC's) for this – Marco van de Voort Mar 19 '14 at 21:33

Chris Dodd · Answer 5 · 2014-03-20T01:25:28.327

1

The easiest way to do this is to reduce the terms by the modulus. The general formula is

a^b mod c ≡ (a mod c)^{(b mod φ(c))} mod c

So in this case you get

10¹⁰⁰⁰ mod 7 = (10 mod 7)^{(1000 mod φ(7))} mod 7.

10 mod 7 = 3

φ(7) = 6

1000 mod 6 = 4

3⁴ = 81

81 mod 7 = 4

so 10¹⁰⁰⁰ mod 7 = 4

edited Mar 20 '14 at 01:25

answered Mar 20 '14 at 01:19

Chris Dodd

119,907
13
134
226

score 0 · Answer 6 · edited May 23 '17 at 10:31

in C and C++ there's no ** operator, you have to use the pow function, that however works only for floating-point types; and the % operator works only for integral types, for FP types you have to use fmod;
anyhow, if you have insert some constant 10**n you would just write 1En (say, 1E42);
.... but there's no standard type able to hold a number as big as 1E1000; even if some FP type were able to hold it, you couldn't reliably use fmod on it, due to the finite precision of the mantissa.

So, how does Python do? Under the hood, beyond the range of "normal" types it uses an arbitrary precision library. You can do the same in your C++ program, providing such library (for example you could use GMP).

But: the expression you provide can be calculated without actually computing 10**1000 and its modulus. Read Modulus power of big numbers

How to solve this easy in c or c++?

6 Answers6