[Date Index]
[Thread Index]
[Author Index]
Re: Seaching in Pi a sequence. Looking for a faster method
*To*: mathgroup at smc.vnet.net
*Subject*: [mg119593] Re: Seaching in Pi a sequence. Looking for a faster method
*From*: Anthony Hodsdon <ajhodsd at hotmail.com>
*Date*: Sat, 11 Jun 2011 06:49:35 -0400 (EDT)
*References*: <201106101038.GAA19889@smc.vnet.net> <05cf01cc27fd$271fb3e0$755f1ba0$@hotmail.com>
Actually, come to think of it, I think the biggest benefit of the string
approach is the reduction in memory used:
In[72]:= ToString[N[Pi - 3, 10^7]] // ByteCount
Out[72]= 10000048
In[75]:= Split[RealDigits[Pi - 3, 10, 10^7][[1]]] // ByteCount
Out[75]= 751990872
--Anthony
-----Original Message-----
From: Anthony Hodsdon [mailto:ajhodsd at hotmail.com]
Sent: Friday, June 10, 2011 11:02 PM
To: 'Guillermo Sanchez'; 'mathgroup at smc.vnet.net'
Subject: [mg119593] Re: Seaching in Pi a sequence. Looking for a faster
method
This sounds like a job for string search:
piesimo2[n_, m_, r_] :=
Transpose[
StringPosition[StringDrop[ToString[N[Pi, n]], 2],
ToString[m*(10^r - 1)/9]]][[1]]
In[44]:= piesimo2[10^7, 9, 7] // Timing
Out[44]= {19.063, {1722776, 3389380, 4313727, 5466169}}
Not bad, considering "stringifying" pi to begin with seems to take most of
the time:
In[49]:= ToString[N[Pi, 10^7]]; // Timing
Out[49]= {18.19, Null}
Mathematica can do the actual search very quickly using a linear time (in
terms of n+r) algorithm (see, for instance,
http://en.wikipedia.org/wiki/String_searching_algorithm).
--Anthony
-----Original Message-----
From: Guillermo Sanchez [mailto:guillermo.sanchez at hotmail.com]
Sent: Friday, June 10, 2011 3:38 AM
To: mathgroup at smc.vnet.net
Subject: [mg119593] Seaching in Pi a sequence. Looking for a faster method
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: Is there ToNumber?**
Next by Date:
**Re: How to make the same two expressions**
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**
| |