MathGroup Archive 2004

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

Search the Archive

Re: Re: Re: Mathematica slows down

  • To: mathgroup at smc.vnet.net
  • Subject: [mg53019] Re: Re: [mg52964] Re: [mg52956] Mathematica slows down
  • From: DrBob <drbob at bigfoot.com>
  • Date: Mon, 20 Dec 2004 06:34:36 -0500 (EST)
  • References: <20041219150315.KXWY27357.lakermmtao01.cox.net@smtp.east.cox.net>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

We're adding and subtracting large integers, and it makes sense that order can affect how large the intermediate results may get. Starting with smaller numbers should do better. My solution with Dot and Bill Rowe's solution with ListConvolve may optimize this (in the background).

Bobby

On Sun, 19 Dec 2004 10:03:15 -0500, Bob Hanlon <hanlonr at cox.net> wrote:

> Dr. Bob,
>
> Presumably it has to do with whether intermediate results are effectively
> cached.  Note that the order in which calls to Prime are made matters
>
> m=10000;
> r=Range[m];
> rr=Reverse[r];
>
> Timing[p=Prime[r];]
>
> {0.03 Second,Null}
>
> Timing[pr=Prime[rr];]
>
> {1.33 Second,Null}
>
> p == Reverse[pr]
>
> True
>
> Consequently, additional inefficiencies in the original algorithm are probably
> due to the sequencing of the calls to Prime.  Here is the original algorithm
> (except Print)
>
> NumP=15000;
>
> Timing[For[k=1,k<NumP,k++,
>     Gap[1]=Prime[k+1]-Prime[k];
>     Gap[2]=Prime[k+2]-2Prime[k+1]+Prime[k];
>     Gap[3]=Prime[k+3]-3Prime[k+2]+3Prime[k+1]-Prime[k];
>     Gap[4]=Prime[k+4]-4Prime[k+3]+6Prime[k+2]-4Prime[k+1]+Prime[k];
>     If[Mod[k,15000]==0,Print[k]]]]
>
> {41.13 Second,Null}
>
> Just restructuring the order of the calls to Prime--even without eliminating
> any redundant calls--makes a significant difference
>
> Timing[For[k=1,k<NumP,k++,
>     Gap[1]=-Prime[k+1]+Prime[k+1];
>     Gap[2]=Prime[k]-2Prime[k+1]+Prime[k+2];
>     Gap[3]=-Prime[k]+3Prime[k+1]-3Prime[k+2]+Prime[k+3];
>     Gap[4]=Prime[k]-4Prime[k+1]+6Prime[k+2]-4Prime[k+3]+Prime[k+4];
>     If[Mod[k,15000]==0,Print[k]]]]
>
> {17.68 Second,Null}
>
>
> Bob Hanlon
>
>>
>> From: DrBob <drbob at bigfoot.com>
To: mathgroup at smc.vnet.net
>> Date: 2004/12/18 Sat PM 12:14:01 EST
>> To: hanlonr at cox.net,  mathgroup at smc.vnet.net
>> Subject: [mg53019] Re: [mg52964] Re: [mg52956] Mathematica slows down
>>
>> Bob, I'm puzzled.
>>
>> NumP = 15000;
>> Timing[
>>    Table[pk[n] = Prime[n], {n, NumP}];
>>    For[k = 1, k ? NumP, k++, Gap[1] = pk[k + 1] - pk[k];
>>      Gap[2] = pk[k + 2] - 2pk[k + 1] + pk[k];
>>      Gap[3] = pk[k + 3] - 3pk[k + 2] + 3pk[k + 1] - pk[k];
>>      Gap[4] = pk[k + 4] - 4pk[k + 3] + 6pk[k + 2] - 4pk[k + 1] + pk[k];
>>      If[Mod[k, 1000] == 0, Print[k]]]
>>    ]
>>
>> (prints omitted)
>> {0.671 Second, Null}
>>
>> Timing[k = 1; primes = Table[Prime[k + i], {i, 0, 4}];
>>    While[k ? NumP, gaps = {{-1, 1, 0, 0, 0}, {1, -2, 1, 0, 0}, {-1, 3, -3,
>>     1, 0}, {1, -4, 6, -4, 1}}.primes;
>>      If[Mod[k, 1000] == 0, Print[gaps]];
>>      primes = Rest[Append[primes, Prime[k + 5]]]; k++]]
>>
>> (prints omitted)
>> {0.156 Second, Null}
>>
>> I'm puzzled that we get these huge speed-ups from eliminating redundant
> calls to Prime. The original code called it 14 times for each k, while these two
> solutions call Prime only once for each -- without significantly reducing other
> operation counts, or so it appears. Yet your code is 30 times faster and mine
> is 100 times faster (with the same number of calls to Prime). I'd expect us to
> get at most a 14-to-one speed increase, or thereabouts.
>>
>> Bobby
>>
>> On Sat, 18 Dec 2004 03:59:37 -0500 (EST), Bob Hanlon
> <hanlonr at cox.net> wrote:
>>
>> > I don't know what changes; however, you can speed it up by avoiding
>> > repeated calls of Prime for the same values
>> >
>> > NumP=15000;
>> >
>> > Table[pk[n]=Prime[n],{n,NumP}];
>> >
>> > For[k=1,k<NumP,k++,
>> >   Gap[1]=pk[k+1]-pk[k];
>> >   Gap[2]=pk[k+2]-2pk[k+1]+pk[k];
>> >   Gap[3]=pk[k+3]-3pk[k+2]+3pk[k+1]-pk[k];
>> >   Gap[4]=pk[k+4]-4pk[k+3]+6pk[k+2]-4pk[k+1]+pk[k];
>> >   If[Mod[k,1000]==0,Print[k]]]
>> >
>> >
>> > Bob Hanlon
>> >
>> >>
>> >> From: George Szpiro <george at netvision.net.il>
To: mathgroup at smc.vnet.net
>> > To: mathgroup at smc.vnet.net
>> >> Date: 2004/12/17 Fri AM 05:20:43 EST
>> >> To: mathgroup at smc.vnet.net
>> >> Subject: [mg53019] [mg52964] [mg52956] Mathematica slows down
>> >>
>> >> Hello,
>> >>
>> >> the following program runs ok for the first 6,000 iterations, then slows
>> >> down considerably, and then seems to speed up again after 10,000.
> Does
>> >> anyone know what is going on?
>> >>
>> >> Thanks,
>> >> George
>> >>
>> >>
>> >> NumP=15000;
>> >>
>> >> For[k=1,k<NumP,k++,
>> >>
>> >>   Gap[1]=Prime[k+1]-Prime[k];
>> >>   Gap[2]=Prime[k+2]-2Prime[k+1]+Prime[k];
>> >>   Gap[3]=Prime[k+3]-3Prime[k+2]+3Prime[k+1]-Prime[k];
>> >>   Gap[4]=Prime[k+4]-4Prime[k+3]+6Prime[k+2]
> -4Prime[k+1]+Prime[k];
>> >>
>> >>   If[Mod[k,1000]==0, Print[ k]]
>> >>
>> >>
>> >>   ]
>> >>
>> >>
>> >>
>> >
>> >
>> >
>> >
>>
>>
>>
>> --
>> DrBob at bigfoot.com
>> www.eclecticdreams.net
>>
>>
>
>
>
>



-- 
DrBob at bigfoot.com
www.eclecticdreams.net


  • Prev by Date: Re: Re: Re: Mathematica slows down
  • Next by Date: Re: Re: Mathematica language issues
  • Previous by thread: Re: Re: Re: Mathematica slows down
  • Next by thread: Laplace Transformation vs. erf