Re: Re: Working with factors of triangular numbers.
- To: mathgroup at smc.vnet.net
- Subject: [mg80033] Re: [mg79864] Re: Working with factors of triangular numbers.
- From: Carl Woll <carlw at wolfram.com>
- Date: Sat, 11 Aug 2007 02:04:56 -0400 (EDT)
- References: <200707030923.FAA17995@smc.vnet.net> <24165820.1186478071750.JavaMail.root@m35> <op.twtzghhtqu6oor@monster.gateway.2wire.net>
Nice. I have some comments below, and a suggestion for further speed
improvements.
DrMajorBob wrote:
> Here's a significantly faster code (for n=12,13 anyway).
>
> Clear[lldaux5, lld5, t5, factorCounts]
> factorCounts[1] = factorCounts[2] = factorCounts[3] = {1};
> factorCounts[4] = {2};
> factorCounts[7] = {3};
> factorCounts[k_Integer] :=
> If[EvenQ@k, factorCounts[(k + 2)/2, k - 1],
> factorCounts[(k - 1)/2, k + 2]]
> factorCounts[j_Integer, k_Integer] :=
> Switch[GCD[j, k],
> 1,
> Join[FactorInteger@j, FactorInteger@k],
> 3, Replace[
> Join[FactorInteger[j/3],
> FactorInteger[k/3]], {3, s_} :> {3, s + 2}, {1}]][[All, -1]] //
> Sort
> lldaux5[{}] := 0
> lldaux5[x_List] /; MemberQ[x, 1] :=
> Count[x, 1] + lldaux5@DeleteCases[x, 1]
> lldaux5[Lpow_] :=
> lldaux5[Lpow] =
> With[{Mtup = Tuples[Range[0, #] & /@ Lpow]},
> Total[Quiet@
> LinearProgramming[ConstantArray[-1, Length[Mtup]],
> Transpose@Mtup, Thread@{Lpow, 0},
> Array[{0, 1} &, Length[Mtup]], Integers]] - 1]
> lld5[n_Integer] := lldaux5@factorCounts@n
> t5[n_] := # (# + 1)/2 &@NestWhile[# + 1 &, 2, lld5[#] < n &]
>
> T2c /@ Range[10] // Timing
> t5 /@ Range[10] // Timing
>
> {0.422, {3, 15, 55, 253, 1081, 13861, 115921, 665281, 18280081,
> 75479041}}
>
> {1.046, {3, 15, 55, 325, 1081, 18145, 226801, 665281, 18280081,
> 75479041}}
>
> T2c[11] // Timing
> t5[11] // Timing
>
> {1.625, 2080995841}
>
> {3.063, 2080995841}
>
> Timing differences aren't reliable either way for n<=11, but beyond
> that it's a different story:
>
> T2c[12] // Timing
> t5[12] // Timing
>
> {27., 68302634401}
>
> {17.187, 68302634401}
>
> T2c[13] // Timing
> t5[13] // Timing
>
> {150.172, 924972048001}
>
> {64.032, 924972048001}
>
> t5[14] // Timing
>
> {516.546, 48318396825601}
>
> The trick (already used by someone else, I think)
>
> lldaux5[x_List] /; MemberQ[x, 1] :=
> Count[x, 1] + lldaux5@DeleteCases[x, 1]
>
> means that if the factor counts includes n ones, the LP problem used
> by T2c has 2^n times as many variables as the one used by t5. Yet
> this yielded only a 10-15% improvement, by itself.
It might be possible to speed up this even further by figuring out how
to get the longest pairs, longest triplets, etc approach to work. I have
an idea on how to do this, but it'll need to wait until I have more
spare time. On the other hand, I think the majority of time is spent
factoring integers, so speeding up this portion of the algorithm may not
be so important.
>
> A bigger gain was achieved in factorCounts, based on one of Carl
> Woll's ideas in
>
> http://forums.wolfram.com/mathgroup/archive/2007/Jul/msg00411.html
>
> factorCounts[k_Integer] :=
> If[EvenQ@k, factorCounts[(k + 2)/2, k - 1],
> factorCounts[(k - 1)/2, k + 2]]
>
> Several fine adjustments were required to get any improvement at all.
> Defining factorCounts for 1,2,3,4, and 7 removed steps from the code
> for other cases, and it was crucial to take full advantage of the
> fact that the GCD of the two factors could only be 1 or 3.
Clever use of GCD so that you can just use Join.
One other idea I had here was the following. As you run through k you
are essentially using FactorInteger twice, once for the larger factor of
k, and then for the smaller factor of k+3 (up to a factor of 2 or 3). By
increasing k in steps of 3, you can remember the FactorInteger results
of the larger factors, so that in the next step you don't need to use
FactorInteger on the smaller factors. Since FactorInteger is the most
expensive operation on average, this might produce another factor of ~2
speedup.
Carl
>
> Bobby
>
[snip]