The biggest exponent that can be computed

Question

I am struggling with my crypt assignments and constantly getting overflow errors. Below is a simplified version of the problems I am experiencing

In[5]:= a:= 44^65537

In[6]:= b:= 22^65537

In[7]:= GCD[a,b]

Out[7]= 2265.....312 very big number

However I want to get an exponent with up to 13 digits or 48 bits to be exact.

If I do

In[8]:= a:= 44^6553700000000

In[9]:= b:= 22^6553700000000

In[10]:= GCD[a,b]

General::ovfl: Overflow occurred in computation.

General::ovfl: Overflow occurred in computation.

GCD::exact: Argument Overflow[] in GCD[Overflow[], Overflow[]] is not an exact number.

Out[10]= GCD[Overflow[], Overflow[]]

And now those question pop into my head

• The numbers becomes so big that the RAM can't handle it ?
• There is limit for the exponential power in Mathematica ?
• There is limit in my OS ?
• Numbers so big are impossible to calculate ?

Any input is appreciated !

Answer 1

Your first port of call should be to have a look at the documentation for $MaxNumber, which says:

$MaxNumber gives the maximum arbitrary‐precision number that can be represented on a particular computer system.

On my machine, $MaxNumber returns $1.605216761933662 \times 10^{1355718576299609}$.

With regards to your number, $44^{6553700000000}$, I initially had to use this online calculator to convert it, it's approximately $3.36*10^{10770695805887}$. So, we need to compare the exponents, which initially seems fine.

10770695805887 > 1355718576299609
(* False *)

However, actually calculating this number exactly takes a very long time... as pointed out by Daniel Lichtblau it is likely a memory limitation!

Changing to machine-precision works fine though, since that is 53 bits...look at Control the Precision and Accuracy of Numerical Results, but unfortunately that won't work with GCD[a, b] as machine-precision numbers are not exact.

44.^6553700000000
(* 3.3617443923642*10^10770695805887 *)

Answer 2

This works fine for me (v.10.0.0 on Mac Pro):

Clear[a, b]
a = 44^(65537);
b = 22^(65537);
c = GCD[a, b];

Where all the digits of c are computed and revealed within about 2 seconds.

N@c

2.265859854928417*10^87978

Answer 3

Many times you can solve this kind of problems using realtions such as

GCD[a,b]=GCD[b,Mod[a,b]]

and substituting conventional functions for modular ones more specialized.

For example, instead of

Mod[x^y,z]  

you have to use

PowerMod[x,y,z] 

that works if z is not too big, even if x^y is huge.

Coming back to your example and using different formulas

 In[8]:= a:= 44^6553700000000

 In[9]:= b:= 22^6553700000000

 In[10]:= GCD[a,b]

You want to calculate

 GCD[(2*m)^x,m^x]

I would take this formula (you can find it on the Wikipedia)

gcd(a + m·b, b) = gcd(a, b)

And for you

 GCD[44^6553700000000, 22^6553700000000] = 
 GCD[(2*22)^6553700000000, 22^6553700000000] =
 GCD[(2^6553700000000)*(22^6553700000000), 22^6553700000000] =
 GCD[0,22^6553700000000]=22^6553700000000

You can check it with smaller numbers.

Though I know Mathematica should do it by its own means.