Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.soft-sys.math.mathematica > #3097 > unrolled thread

Re: Seaching in Pi a sequence. Looking for a faster method

Back to article view | Back to comp.soft-sys.math.mathematica

Contents

  Re: Seaching in Pi a sequence. Looking for a faster method Dana DeLouis <dana.del@gmail.com> - 2011-06-15 11:19 +0000
    Re: Seaching in Pi a sequence. Looking for a faster method rafapa <rafapa@us.es> - 2011-06-16 08:02 +0000

#3097 — Re: Seaching in Pi a sequence. Looking for a faster method

Hi.  Just something a little different.
Given piesimo[10^7, 9, 7], You are looking for a specific digit (9) repeated a number of times (7).

Here's what we have so far.

Our String:
pi=StringDrop[ToString[N[Pi,10^7]],2];

Function:
piesimoS[m_String]:=First/@StringPosition[pi,m]

Check Timing:

piesimoS["9999999"]//Timing
{0.2513,{1722776,3389380,4313727,5466169}}

This idea finds all sequences of the digit 9 repeated 7 or more times.

DigitSequence[pi,9,7]//Timing
{0.08725,{{7,1722776},{7,3389380},{7,4313727},{7,5466169}}}

It appears to be about 3 times faster.
That code returned the length of the sequence, and the starting position.

(* s - String, d - digit to check, start - Minimum length *)

DigitSequence[s_,d_,start_]:=Module[
{re,z,t},
z=StringReplace["n{s,}",{"n"->ToString[d],"s"->ToString[start]}];
re=RegularExpression[z];
t=StringPosition[s,re,Overlaps->False];
t=t/.{x_Integer,y_Integer}:>{y-x+1,x};
SortBy[SortBy[t,Last],First]
]


If you only wanted a specific length, then change rule to "n{s,s}"

If you didn't know how many consecutive 9's there are in a string, then this finds 6 or more:

DigitSequence[pi,9,6]//Timing
{0.08989,
{{6,762},{6,193034},{6,1985813},{6,2878443},{6,3062881},
{6,3529731},{6,6951812},{6,7298585},{6,8498459},{7,1722776},
{7,3389380},{7,4313727},{7,5466169}}}

So, the digit 9 occurs at most 7 times in a row.

This is more in line with your specific length example.
This does not look at overlap:

DigitSequence2[s_,d_,length_]:=Module[
{z,t},
z=StringReplace["n{s,s}",{"n"->ToString[d],"s"->ToString[length]}];
t=StringPosition[s,RegularExpression[z],Overlaps->False];
t/.{x_Integer,y_Integer}:>x
]

DigitSequence2[pi,9,7]//Timing
{0.08325,{1722776,3389380,4313727,5466169}}

= = = = = = = = = =
HTH  : >)
Dana DeLouis
$Version
8.0 for Mac OS X x86 (64-bit) (November 6, 2010)




On Jun 10, 6:38 am, Guillermo Sanchez <guillermo.sanc...@hotmail.com> wrote:
> Dear Group
>
> I have developed this function
>
> piesimo[n_, m_, r_] := Module[{a}, a = Split[RealDigits[Pi - 3, 10, n]
> [[1]]]; Part[Accumulate[Length /@ a], Flatten[Position[a, Table[m,
> {r}]]] - 1] + 1]
>
> n is the digits of Pi, after 3, where to search a sequence of m digit
> r times consecutives.
> For instance:
>
> piesimo[10^7, 9, 7]
>
> Gives that the sequence 9999999 happens in positions:
>
> {1722776, 3389380, 4313727, 5466169}
>
> I know that in this group I will find  faster methods. Any idea?
>
> Guillermo

[toc] | [next] | [standalone]

#3125

On Jun 15, 1:19 pm, Dana DeLouis <dana....@gmail.com> wrote:
> Hi.  Just something a little different.
> Given piesimo[10^7, 9, 7], You are looking for a specific digit (9) repeated a number of times (7).
>
> Here's what we have so far.
>
> Our String:
> pi=StringDrop[ToString[N[Pi,10^7]],2];
>
> Function:
> piesimoS[m_String]:=First/@StringPosition[pi,m]
>
> Check Timing:
>
> piesimoS["9999999"]//Timing
> {0.2513,{1722776,3389380,4313727,5466169}}
>
> This idea finds all sequences of the digit 9 repeated 7 or more times.
>
> DigitSequence[pi,9,7]//Timing
> {0.08725,{{7,1722776},{7,3389380},{7,4313727},{7,5466169}}}
>
> It appears to be about 3 times faster.
> That code returned the length of the sequence, and the starting position.
>
> (* s - String, d - digit to check, start - Minimum length *)
>
> DigitSequence[s_,d_,start_]:=Module[
> {re,z,t},
> z=StringReplace["n{s,}",{"n"->ToString[d],"s"->ToString[start]}];
> re=RegularExpression[z];
> t=StringPosition[s,re,Overlaps->False];
> t=t/.{x_Integer,y_Integer}:>{y-x+1,x};
> SortBy[SortBy[t,Last],First]
> ]
>
> If you only wanted a specific length, then change rule to "n{s,s}"
>
> If you didn't know how many consecutive 9's there are in a string, then this finds 6 or more:
>
> DigitSequence[pi,9,6]//Timing
> {0.08989,
> {{6,762},{6,193034},{6,1985813},{6,2878443},{6,3062881},
> {6,3529731},{6,6951812},{6,7298585},{6,8498459},{7,1722776},
> {7,3389380},{7,4313727},{7,5466169}}}
>
> So, the digit 9 occurs at most 7 times in a row.
>
> This is more in line with your specific length example.
> This does not look at overlap:
>
> DigitSequence2[s_,d_,length_]:=Module[
> {z,t},
> z=StringReplace["n{s,s}",{"n"->ToString[d],"s"->ToString[length]}];
> t=StringPosition[s,RegularExpression[z],Overlaps->False];
> t/.{x_Integer,y_Integer}:>x
> ]
>
> DigitSequence2[pi,9,7]//Timing
> {0.08325,{1722776,3389380,4313727,5466169}}
>
> = = = = = = = = = =
> HTH  : >)
> Dana DeLouis
> $Version
> 8.0 for Mac OS X x86 (64-bit) (November 6, 2010)
>
> On Jun 10, 6:38 am, Guillermo Sanchez <guillermo.sanc...@hotmail.com> wrote:
>
>
>
>
>
>
>
> > Dear Group
>
> > I have developed this function
>
> > piesimo[n_, m_, r_] := Module[{a}, a = Split[RealDigits[Pi - 3, 10, n]
> > [[1]]]; Part[Accumulate[Length /@ a], Flatten[Position[a, Table[m,
> > {r}]]] - 1] + 1]
>
> > n is the digits of Pi, after 3, where to search a sequence of m digit
> > r times consecutives.
> > For instance:
>
> > piesimo[10^7, 9, 7]
>
> > Gives that the sequence 9999999 happens in positions:
>
> > {1722776, 3389380, 4313727, 5466169}
>
> > I know that in this group I will find  faster methods. Any idea?
>
> > Guillermo

Well,
it looks like the increased speed is due to the use of
RegularExpression. I modified piesimoS is:

piesimoSR[m_String] :=
 First /@ StringPosition[pi, RegularExpression[m], Overlaps -> False]


 DigitSequence[pi, 9, 7] // Timing

 {0.076988, {{7, 1722776}, {7, 3389380}, {7, 4313727}, {7,
   5466169}}}

 piesimoS["9999999"] // Timing

 {0.204969, {1722776, 3389380, 4313727, 5466169}}

piesimoSR["9999999"] // Timing

 {0.072989, {1722776, 3389380, 4313727, 5466169}}

[toc] | [prev] | [standalone]

Back to top | Article view | comp.soft-sys.math.mathematica

csiph-web