MathGroup Archive 2008

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

Search the Archive

Re: How do little quickest ?


Artur wrote:
> Dear Mathematica Gurus!
> Who know how do quickest following prcedure:
> 
> aa = {}; Do[Print[x]; rmin = 10^10; k = 2^x; w = Floor[(k - 1)/2];
>  Do[If[GCD[n, k, k - n] == 1, m = FactorInteger[k n (k - n)]; rad = 1;
>     Do[rad = rad m[[s]][[1]], {s, 1, Length[m]}];
>    If[rad < rmin, rmin = rad]], {n, 1, w}];
>  AppendTo[aa, rmin], {x, 2, 30}]; aa
> 
> Best wishes
> Artur

The main speed improvement is to separate the FactorInteger uses, so 
that you are not needing to split the large products. After that you can 
get modest improvements by avoiding the GCD, avoiding the factorization 
of 2^x, etc. The code below handles 2^26 in around 11 minutes, and 
roughly doubles for each increment of x. This doubling appears to be 
largely due to doubling the number of iterations. I expect that will 
persist a while, possibly to 30. Eventually one will also hit the 
effects of FactorInteger on larger numbers causing further slowdowns.

Timing[
  t = TimeUsed[];
  Table[
   Print["x ",x];
   rmin = 10^10;
   k = 2^x;
   w = 2^(x-1) - 1;
   Do[
    m = Join[FactorInteger[n], FactorInteger[k-n]];
    rad = 2*Apply[Times,Map[First,m]];
    If[rad < rmin, rmin = rad]
    , {n,1,w,2}];
   Print[(t2 = TimeUsed[])-t];
   t = t2;
   rmin
   , {x, 2, 26(*30*)}]]

x 2
0.
x 3
0.
x 4
0.004
x 5
0.
x 6
0.
x 7
0.001
x 8
0.000999
x 9
0.002
x 10
0.004
x 11
0.007998
x 12
0.013998
x 13
0.028996
x 14
0.059991
x 15
0.121981
x 16
0.247962
x 17
0.511923
x 18
1.04584
x 19
2.12268
x 20
4.31834
x 21
8.99563
x 22
18.5022
x 23
38.2052
x 24
78.97
x 25
164.433
x 26
345.533

Out[1]= {663.131, {6, 14, 30, 30, 42, 30, 78, 182, 1110, 570,
  1830, 6666, 2310, 2534, 5538, 9870, 20010, 141270, 14070,
  480090, 155490, 334110, 1794858, 2463270, 2132130}}

Daniel Lichtblau
Wolfram Research



  • Prev by Date: Re: How do little quickest ?
  • Next by Date: Re: Fourier Transform
  • Previous by thread: Re: Re: How do little quickest
  • Next by thread: Re: How do little quickest ?