1
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ OScam - you should learn the difference between := and = in Mathematica - have a look here: mathematica.stackexchange.com/questions/18393/… $\endgroup$ – dr.blochwave Jan 5 '15 at 22:44
  • 1
    $\begingroup$ 2^48 bits is 2^(48) / 8 = 2^45 bytes. That comes to 32 terabytes, at least using the 2^10=1K convention. So yeah, you may be up against limitations imposed by RAM, Mathematica and OS. $\endgroup$ – Daniel Lichtblau Jan 5 '15 at 23:01
  • $\begingroup$ Thank you for making my question clean and nice, thanks for pointing out difference := and = i didn't knew about difference. $\endgroup$ – OScam Jan 6 '15 at 0:24
4
$\begingroup$

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 *)
$\endgroup$
  • $\begingroup$ Sorry, I messed up the edit :D $\endgroup$ – Sektor Jan 5 '15 at 22:37
  • 1
    $\begingroup$ No long-term harm done :-) $\endgroup$ – dr.blochwave Jan 5 '15 at 22:38
  • $\begingroup$ 20686623745 Out[1]= 2.174188391646043 10 $\endgroup$ – OScam Jan 6 '15 at 0:26
  • $\begingroup$ i am using mac book pro windows 8.1 maxnumber shows me: 20686623745 Out[1]= 2.174188391646043 10 Does This power 20686623745 mean my PC can calculate upto this number ? if i use better Machine with more ram , problem can solve ? apologize for asking too much i am total noob :( $\endgroup$ – OScam Jan 6 '15 at 0:34
  • $\begingroup$ Yes, if that's what it returns then that's the largest number Mathematica can achieve. Using a better machine won't necessarily solve your problem - calculating $44^{6553700000000}$ exactly might well be beyond the capability of Mathematica. $\endgroup$ – dr.blochwave Jan 6 '15 at 8:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Same here. Finished instantly. $Version == "10.0 for Mac OS X x86 (64-bit) (December 4, 2014)" $\endgroup$ – evanb Jan 5 '15 at 22:47
  • 2
    $\begingroup$ This doesn't answer the question? The problem was with larger exponents... $\endgroup$ – dr.blochwave Jan 6 '15 at 8:16
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.