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
> >
> >
> >
>
>