Re: How do little quickest ?
- To: mathgroup at smc.vnet.net
- Subject: [mg93485] Re: [mg93475] How do little quickest ?
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 11 Nov 2008 07:45:20 -0500 (EST)
- References: <gf3mj0$en2$1@smc.vnet.net> <200811091026.FAA20573@smc.vnet.net> <200811100831.DAA26388@smc.vnet.net>
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
- References:
- Re: NIntegrate[UnitStep[...]PDF[...],{x,...}] hard to integrate
- From: er <erwann.rogard@gmail.com>
- How do little quickest ?
- From: Artur <grafix@csl.pl>
- Re: NIntegrate[UnitStep[...]PDF[...],{x,...}] hard to integrate