Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2001

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

Search the Archive

RE: Re: Can this be made cleaner and more efficient?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg29096] RE: [mg29066] Re: [mg29022] Can this be made cleaner and more efficient?
  • From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.de>
  • Date: Tue, 29 May 2001 02:57:22 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Anonymous,

using FactorInteger instead of a host of Mod test would be an alternative
(which just springs to my mind, but I'd guess there are more efficient
ways). Compare

In[9]:= SeedRandom[999999]

In[10]:=
Table[Module[{r, d = 5},
        r = Random[Integer, {10^(d - 1), 10^d}];
        While[FactorInteger[r][[1, 1]] < 100, 
          If[++r > 10^d, r = 10^(d - 1) + 1]];
        r], {1000}]; // Timing

Out[10]=
{1.212 Second, Null}

In[11]:=
Table[Module[{r = 3, d = 5},
        While[FactorInteger[r][[1, 1]] < 100, 
          r = Random[Integer, {10^(d - 1), 10^d}]];
        r], {1000}]; // Timing

Out[11]=
{1.643 Second, Null}

In[16]:=
Table[Module[{r = 3, d = 5},
        While[FactorInteger[r, FactorComplete -> False][[1, 1]] < 100, 
          r = Random[Integer, {10^(d - 1), 10^d}]];
        r], {1000}]; // Timing

Out[16]=
{1.452 Second, Null}

with Andrzej's implementations of your algorithm

In[13]:=
Table[RandomOdd3[5], {1000}]; // Timing

Out[13]=
{3.164 Second, Null}

In[15]:=
Table[RandomOdd4[5], {1000}]; // Timing

Out[15]=
{5.919 Second, Null}

RandomOdd4 pays a price for recursion. My first solution however must be
respected with suspicion, since not all numbers with property searched for
are drawn at equal chance. This may be irrelevant or of importance depending
on your application. For the precise meaning of FactorComplete I don't know,
as to it's applicability here this is just a guess.

Browse Help on this and related themes, but I think, "Flip", your problem
posted is a Mathematica question only to a lesser extend. Consult Number
Theory.

-- Hartmut Wolf


> -----Original Message-----
> From: Andrzej Kozlowski [mailto:andrzej at tuins.ac.jp]
To: mathgroup at smc.vnet.net
> Sent: Sunday, May 27, 2001 3:54 AM
> To: mathgroup at smc.vnet.net
> Subject: [mg29096] [mg29066] Re: [mg29022] Can this be made cleaner and more
> efficient?
> 
> 
> You can certainly write simpler code, e.g:
> 
> RandomOdd3[d_] := 
>   Module[{res = Random[Integer, {10^(d - 1), 10^d}],
>       primes = Table[Prime[n], {n, 25}]},
> While[Or @@ Thread[Mod[res, primes] == 0],
>       res = Random[Integer, {10^(d - 1), 10^d}]]; res]
> 
> or:
> 
> RandomOdd4[d_] := 
>   Module[{res = Random[Integer, {10^(d - 1), 10^d}],
>       primes = Table[Prime[n], {n, 25}]},
> If[And @@ Thread[Mod[res, primes] != 0], res, RandomOdd4[d]]]
> 
> However, none of these will be more efficient than yours 
> because they use
> the same algorithm. (In fact they should be somewhat less efficient).
> However, if instead of the first 24 primes you wanted to 
> sieve out the first
> 10000 you might find it rather tedious to write out a version 
> of your code
> ....
> 
> -- 
> Andrzej Kozlowski
> Toyama International University
> JAPAN
> 
> http://platon.c.u-tokyo.ac.jp/andrzej/
> http://sigma.tuins.ac.jp/~andrzej/
> 
> 
> 
> 
> on 01.5.25 2:47 PM, Flip at nospam at newsranger.com wrote:
> 
> > Hi All,
> > 
> > I was wondering if the following module (it is small) can 
> be made simpler and
> > faster ... and thoughts would be appreciated.
> > 
> > RandomOdd2[d_] := Module[{res},
> > res = Random[Integer, {10^(d - 1), 10^d}];
> > While[(
> > 
> > Mod[res, 02] == 0 || Mod[res, 03] == 0 || Mod[res, 05] == 0 ||
> > Mod[res, 07] == 0 || Mod[res, 11] == 0 || Mod[res, 13] == 0 ||
> > Mod[res, 17] == 0 || Mod[res, 19] == 0 || Mod[res, 23] == 0 ||
> > Mod[res, 29] == 0 || Mod[res, 31] == 0 || Mod[res, 37] == 0 ||
> > Mod[res, 41] == 0 || Mod[res, 43] == 0 || Mod[res, 47] == 0 ||
> > Mod[res, 53] == 0 || Mod[res, 59] == 0 || Mod[res, 61] == 0 ||
> > Mod[res, 71] == 0 || Mod[res, 73] == 0 || Mod[res, 79] == 0 ||
> > Mod[res, 83] == 0 || Mod[res, 89] == 0 || Mod[res, 97] == 0),
> > res = Random[Integer, {10^(d - 1), 10^d}]];
> > res]
> > 
> > It is basically sieving out the first 24 primes (primes <= 
> 100) from the
> > result.
> > 
> > Thank you ... Flip
> > 
> > 
> > 
> 
> 



  • Prev by Date: Re: Re: Why can't Nsolve find a solution to this ?
  • Next by Date: AW: Re: Why can't Nsolve find a solution to this ?
  • Previous by thread: Re: Can this be made cleaner and more efficient?
  • Next by thread: RV: Returning List Position w/o brackets