[Date Index]
[Thread Index]
[Author Index]
Re: Seaching in Pi a sequence. Looking for a faster method
*To*: mathgroup at smc.vnet.net
*Subject*: [mg119651] Re: Seaching in Pi a sequence. Looking for a faster method
*From*: Anthony Hodsdon <ajhodsd at hotmail.com>
*Date*: Thu, 16 Jun 2011 04:00:32 -0400 (EDT)
*References*: <201106151119.HAA22777@smc.vnet.net>
Very interesting! I'm surprised that the regular expression path is actually
faster than the simple string. I guess Mathematica doesn't bother to
preprocess the string to use a more efficient searching algorithm like KMP
or Boyer-Moore.
It looks like you get the same optimization by making a regular expression
out of the explicit string:
In[91]:= piesimoSPlus[m_String] :=
First /@ StringPosition[pi, RegularExpression[m]]
In[92]:= piesimoSPlus["9999999"] // Timing
Out[92]= {0.234, {1722776, 3389380, 4313727, 5466169}}
In[82]:= piesimoS["9999999"] // Timing
Out[82]= {0.53, {1722776, 3389380, 4313727, 5466169}}
In[84]:= DigitSequence[pi, 9, 7] // Timing
Out[84]= {0.28, {{7, 1722776}, {7, 3389380}, {7, 4313727}, {7,
5466169}}}
--Anthony
-----Original Message-----
From: Dana DeLouis [mailto:dana.del at gmail.com]
Sent: Wednesday, June 15, 2011 4:20 AM
To: mathgroup at smc.vnet.net
Subject: [mg119651] 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... at 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
Prev by Date:
**Re: Seaching in Pi a sequence. Looking for a faster method**
Next by Date:
**Re: How to extract a pattern**
Previous by thread:
**Re: Seaching in Pi a sequence. Looking for a faster method**
Next by thread:
**Re: Seaching in Pi a sequence. Looking for a faster method**
| |