Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Re: Re: Re: Timing

Artur wrote:
> Many thanks for Andrzej Kozlowski for this procedure!
> I was execute these on my computer and received follwing Timing
> Table[f[n], {n, 2, 20}] // Timing = 0.071
> Table[f[n], {n, 2, 21}] // Timing = 0.089
> Table[f[n], {n, 2, 22}] // Timing = 525.756
> but increasing limit of n to 23 was catastrophe on my computer (probably 
> RAM memory is limit)
> 
> Could help me sombody with big memory size computer check these 
> procedure for n=23 (next true should occured for n=31)
> Or sombody can explained this catastrophe in relation hardware-software 
> relation or estimated how increased time if increased n (is this time 
> polynomial time or not)
> 
> Best wishes
> Artur

Apparently you wish to replicate

http://www.research.att.com/~njas/sequences/?q=3%2C5%2C7%2C13%2C17%2C19%2C31%2C61%2C89&language=english&go=Search

First, the way you are going about this is hopeless. You are generating 
huge integers, on the order of many millions of bits, just to see if 
they are divisible by much smaller integers on the order of perhaps 
dozens of bits. This "catastrophe" is entirely self inflicted; you 
simply MUST avoid the huge numbers in the first place. Functions like 
Mod can be real helpful, in such circumstances.

So you can tackle it as follows. Treat Sqrt[2] as a variable, that is, 
use polynomials in x, reduced by x^2-2. Also you want to do reduction 
modulo 2^n-1, since all you care about is whether the remainder is zero. 
This can be interleaved with powering, for efficiency (avoids huge 
numbers/expressions).

Back before version 6 there was an add-on package PolynomialPowerMod 
that handled such things, but (I think) was restricted to prime number 
moduli. Anyway, I got a bit frustrated trying to figure out how to do 
this efficiently using built-in functions in version 6. This is an 
admission that either the documentation was lacking, or I was too tired. 
Also, I ran afoul of a difficult-to-track crash bug in our development 
kernel, and I need to look into that. So I just wrote a bit of code to 
do what we need here.

ppMod[poly_, n_, {p2_,m_}] := Module[
   {bits=Reverse[IntegerDigits[n,2]], pj=poly, oldpj, res=1},
   If [bits[[1]]==1, res = pj];
   Do[
     pj = PolynomialMod[pj^2, {p2,m}];
     If [bits[[j]]==1, res = PolynomialMod[res*pj,{p2,m}]],
     {j, 2, Length[bits]}];
   res
   ]

Timing[Map[First,Select[Table[{n, PolynomialMod[
   (ppMod[3+2*x,2^(n-1)-1,{x^2-2,2^n-1}] -
     ppMod[3-2*x,2^(n-1)-1,{x^2-2,2^n-1}])*(x/8),
   {x^2-2,2^n-1}]}, {n,1,1000}], #[[2]]===0&]]]

Out[10]= {158.978, {1, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607}}


Daniel Lichtblau
Wolfram Research
  • Prev by Date: Re: Re: Player Pro and Packages
  • Next by Date: Re: Re: Wolfram User Interface Research? [off-topic!]
  • Previous by thread: Re: Re: Re: Re: Timing
  • Next by thread: Re: Re: Timing