Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2007
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2007

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

Search the Archive

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]


  • Prev by Date: Re: 64 bit Kernel does not run on iMac Intel
  • Next by Date: Re: Cube codes just done in Mathematica
  • Previous by thread: Re: Re: Working with factors of triangular numbers.
  • Next by thread: Re: Re: Working with factors of triangular numbers.