Re: How do I do very big integer computing by

• To: mathgroup at smc.vnet.net
• Subject: [mg115417] Re: How do I do very big integer computing by
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Mon, 10 Jan 2011 02:40:32 -0500 (EST)

```----- Original Message -----
> From: "a boy" <avvboy at gmail.com>
> To: mathgroup at smc.vnet.net
> Sent: Sunday, January 9, 2011 1:19:42 AM
> Subject: [mg115375] Re: How do I do very big integer computing by Mathematica?
> I asked how to do very-big-integer computing. For example:
> Mod[2^2^64,1342352]
> It's pity, this code causes overflow!

It is fairly clear that, both for theoretical and practical reasons, computer numbers need to be bounded. So the question up for grabs is where to put the bounds. Maybe for 64 bit machines Mathematica integers should go higher than at present.

But that misses the point, which is that taking mod of a large number that is formed by an iteration (Power, in this case) can often be done by interleaving Mod and thus avoiding overflow.

> is there some funtions like this: StringMod["111...111","345"]

I have absolutely no idea what a putative StringMod would do.

There is a way to get the result in question without an intermediate overflow.

In[16]:= PowerMod[2, 2^64, 1342352]
Out[16]= 963840

PowerMod internally will interleave Power steps (squaring) and Times steps with Mod.

Daniel Lichtblau
Wolfram Research

> On Sun, Jan 9, 2011 at 8:17 AM, Daniel Lichtblau <danl at wolfram.com>
> wrote:
>
> >
> > ----- Original Message -----
> > > From: "a boy" <avvboy at gmail.com>
> > > To: mathgroup at smc.vnet.net
> > > Sent: Saturday, January 8, 2011 2:37:07 AM
> > > Subject: [mg115335] How do I do very big integer computing by
> > Mathematica?
> > > I'm going to search big Fibonacci prime numbers. I think there is
> > > a
> > > simple primality test algorithm for Fibonacci number, like
> > > Lucas=96
> > > Lehmer primality test for 2^n-1 . I'm lazy and don't want to write
> > > many codes. So i want to ask:
> > >
> > > p=43,112,609;
> > > s[0]=4;
> > > s[n_]:=s[n-1]^2-4
> > > pt=Mod[s[p-2], 2^p-1]==0
> > >
> > > how do I compute s[43,112,609-2] directly? It seems the largest
> > > integer in M~ is 2^32^32, isn't it?
> >
> > Not exactly certain what you want to do from that description. But
> > something that might help is to interleave Mod[] operations provided
> > the
> > modulus is not too large for Mathematica.
> >
> > Daniel Lichtblau
> > Wolfram Research
> >
> >
> >

```

• Prev by Date: Re: How to change the directory for the docs?
• Next by Date: Re: 2 obvious
• Previous by thread: Re: Number of zeros finite or infinite?
• Next by thread: DesignerUnits 2011-01-08 for Mathematica 8, 7, 6