Re: Re: Re: How do little quickest ?
- To: mathgroup at smc.vnet.net
- Subject: [mg93508] Re: [mg93497] Re: [mg93487] Re: [mg93475] How do little quickest ?
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Thu, 13 Nov 2008 04:02:21 -0500 (EST)
- References: <gf3mj0$en2$1@smc.vnet.net> <200811091026.FAA20573@smc.vnet.net>
- Reply-to: drmajorbob at longhorns.com
Daniel,
Your code took 189 seconds to reach 26 on my machine, while my code took
704 seconds to do the same.
Well done, as usual!
Bobby
On Wed, 12 Nov 2008 05:45:06 -0600, Daniel Lichtblau <danl at wolfram.com>
wrote:
> Artur wrote:
>> Now the quickest procedure is:
>>
>> aa = {}; Do[Print[x]; rmin = 10^10; k = 2^x; w = Floor[(k - 1)/2];
>> Do[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, 2}];
>> AppendTo[aa, rmin], {x, 2, 30}]; aa
>>
>> because all possible numbers was odd <{n, 1, w, 2} inspite
>> {n, 1, w}> and GCD checking was delated because GCD[2^x-(2n-1),(2n-1)]=1
>>
>> What to do yet because time is still expotential and for x=27 my
>> computer need whole day to count.
>>
>> Best wishes
>> Artur
>>
>> Mathematical problem is following:
>>
>> I need help with finding rule on follwing problem
>>
>> Sequences:
>>
>> B={1, 3, 7, 15, 27, 63, 125, 243, 343, 999, 1805, 3721, 8181, 16335,
>>
>> 32761, 65533, 112847, 190269, 519375, 1046875, 1953125}
>>
>> C={2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384,
>>
>> 32768, 65536, 131072, 262144, 524288, 1048576, 2097152}
>>
>> A={1, 1, 1, 1, 5, 1, 3, 13, 169, 25, 243, 375, 11, 49, 7, 3, 18225,
>>
>> 71875, 4913, 1701, 144027}
>>
>> C(n) = 2^n
>>
>> A(n) = C(n) - B(n)
>>
>> A(n) < B(n) < C(n)
>>
>> is obtained by algorhitm such
>>
>> that GCD[A(n),B(n),C(n)] = 1 and product of distinct prime divisors of
>>
>> A(n)*B(n)*C(n) have minimal value.
>>
>> I'm looking for formula for B(n).
>>
>> Who can help?
>> [...]
>
> There is no way to avoid the exponential aspect unless you have some
> theory to use that allows you to skip large swatches of the potential
> products. Otherwise you need to evaluate twice as many for each
> increment in size. And of course it gets worse if the complexity of
> computing those factorizations grows. (This will not play a role until
> one tries to handle 2^32 or so, as that is where Mathematica will no
> longer always succeed in factoring via trial division.)
>
> The code below is around 3.5 times faster than what I last sent, for the
> size range in question. It avoids direct factorization, instead using a
> standard sieving approach. I opted to work with sums of (approximated)
> logs rather than products of factors, just to be certain I could use
> packed arrays to sufficient size. The disadvantage is that this is
> memory intensive and will require a 64 bit machine in order to have any
> hope for handling the full range you have in mind (2^30).
>
> flatfax = Compile[{{n,_Integer}}, Module[
> {fx, len=2^(n-1), pr=3, start, logpr},
> fx = Table[0.,{len}];
> While[pr<=2*len,
> start = Round[(pr+1)/2.];
> logpr = Log[N[pr]];
> Do [fx[[j]] += logpr, {j,start,len,pr}];
> pr = NextPrime[pr];
> ];
> fx
> ]]
>
> minprods = Compile[{{fx,_Real,1}},
> Module[{len=Length[fx], loglen, n, parts},
> loglen = Floor[Log[2,N[len]]];
> Table[
> n = 2^(j-1);
> parts = Take[fx,2*n];
> parts = Take[parts,n] + Reverse[Drop[parts,n]];
> Min[parts]
> , {j,1,loglen}]
> ]]
>
> In[78]:= Timing[Round[2*Exp[minprods[flatfax[26]]]]]
>
> Out[78]= {168.059, {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}}
>
> In a new session tried to go to 28, and ran out of memory. As I said,
> this will require a large machine and even then I'm not sure one will
> squeak past the memory limits. Alternatively, try working with products
> of prime factors rather than sums of logs of said factors, see if you
> can stay within integer packed array size limits. I think this will
> break down at the minprods step, because some of the products will
> exceed machine integer size even though the minimal ones do not.
>
> One thing I can say is, if you seek further speed improvement, the place
> to focus is flatfax. particularly in the loops. Possibly creating a
> SparseArray vector with Log[pr] in nonzero positions, then adding to the
> fx table (I have no idea whether this will make things faster or slower)
>
>
> Daniel Lichtblau
> Wolfram Research
>
--
DrMajorBob at longhorns.com
- References:
- Re: NIntegrate[UnitStep[...]PDF[...],{x,...}] hard to integrate
- From: er <erwann.rogard@gmail.com>
- Re: NIntegrate[UnitStep[...]PDF[...],{x,...}] hard to integrate