Re: Re: Working with factors of triangular numbers.
- To: mathgroup at smc.vnet.net
- Subject: [mg80061] Re: [mg79864] Re: Working with factors of triangular numbers.
- From: DrMajorBob <drmajorbob at bigfoot.com>
- Date: Sat, 11 Aug 2007 02:19:28 -0400 (EDT)
- References: <200707030923.FAA17995@smc.vnet.net> <24165820.1186478071750.JavaMail.root@m35> <op.twtzghhtqu6oor@monster.gateway.2wire.net> <21337500.1186772308221.JavaMail.root@m35>
- Reply-to: drmajorbob at bigfoot.com
FactorInteger is eventually called twice for even numbers and four times
for odd, but so far I haven't found a way to cache results more
efficiently than Mathematica does on its own.
Bobby
On Fri, 10 Aug 2007 08:58:01 -0500, Carl Woll <carlw at wolfram.com> wrote:
> 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 ha=
ve =
> 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 n=
ot =
> 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 fa=
ct =
>> 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]
>
-- =
DrMajorBob at bigfoot.com