Inverse BBP algorithm. (Pi)

[Kharakov]

I would like to an inverse BBP algorithm so I can calculate where and if the words "Kharakov was here" appear in the base 37 expansion of pi (37 for space character).

Ok. I just want to make one up for fun. I haven't looked into it too much and I'm thinking maybe the spigot algorithm isn't invertible.

Anyways. Have at it. I'll be back in a few. Might be around more. Looks like I'll be off the street and back in a place where I'll have access to a computer in the next month or so. . Which means you guys get to see me post again. Lol...

 

[steve_bank]

I'd have to look up inverse BBP algorithm but the sub string search itself is straightforward.

Searching for a substring in a string s a common sw language function.

1convert the number to a string, in this case a segment of pi and compare ASCII chracters.

string1[8]= kharakov"
string2[n_digits] = "pi314159..."

Sequentially compare string1 character by character with a moving 8 character window through stribg2. If the number of matches equals 8 it is there.

 

[Bomb#20]

I would like to an inverse BBP algorithm so I can calculate where and if the words "Kharakov was here" appear in the base 37 expansion of pi (37 for space character).

Back of the envelope, I think you're going to need to try about 10²⁷ positions to have a decent chance of finding it.

 

[Swammerdami]

Those responding to Kharakov may be ignoring what the "BBP algorithm" is. Normally, to find the millionth digit of pi [call it f_B(1000000)], you first calculate the first 999,999 digits — in other words, you just approximate pi very closely.

The  Bailey–Borwein–Plouffe formula bypasses that work and presents the n'th digit of pi directly! It sounds like magic, but the basic idea is simple. There are many many series expansions for pi; Plouffe et al just needed an expansion where the k'th term in the series is multiplied by B^-k where B is the base (i.e. B=10 if you want pi's decimal expansion).

The original Plouffe formula worked for B=16 (pi's hexadecimal expansion). Since then I think series have been developed for other B; don't know about B=37.

But Kharakov wants to invert this BBP function; instead of evaluating f_B(1000000) to tell us pi's millionth digit, he wants f_B^-1('K') to tell us where the K's are in pi's base-37 expansion. That would be hugely more difficult than BBP itself, and of course f_B^-1() is a multi-function

 

[Bomb#20]

... and of course f_B^-1() is a multi-function

That's the issue. Assuming we can find an inverse BBP algorithm for base 37, we plug in "K" and it returns, not just the place in the sequence where "Kharakov was here" starts, but everywhere in the sequence where there's a "K". Then we'll have to look at about 10²⁷ of the returned locations in order to find one that's followed by "harakov was here".

 

[Swammerdami]

Reading pi's entrails by first rendering it in base 37 is rather an arbitrary decision anyway.

Since any such encoding would be arbitrary, why not improve the rendered text, e.g. by treating pi's bits as an arithmetic entropy code that produces text with the same tetraglyph statistics as Shakespeare's Sonnets? You might get this:

Which dare both fords to him when your pleave crue
The unking milege it dothey work oncell.

Muse,
The fair; myself all cap'd thou arer in mell,
In power carv'd, and.

Since I love by in knowin adverath dears do noth negle plemembling,
Gively knife
Askance will wateristol'n I call me: if in thou lock toilst shall be;
Such then of your profan'd;
Alth men's with all more.

Therittle his leasure:
But yet not,
Save intage old, more time breature!
Is pass besmellow seem to many againstantinuteously woeful pity,
If the of ther so best mind,
Which in my appy poil madderough thee.

Which be skill thy pace.

So flowe.
To hone:
Yet gone being of left, nor face hen too may may
And far glance wasteel 'hue?

This was generated with the same software I mentioned elsethread, but with pi's bits substituted for a PRNG. (The heart of the generator was shown in a Code Snippets thread.)

 

[Jokodo]

I would like to an inverse BBP algorithm so I can calculate where and if the words "Kharakov was here" appear in the base 37 expansion of pi (37 for space character).

Ok. I just want to make one up for fun. I haven't looked into it too much and I'm thinking maybe the spigot algorithm isn't invertible.

Anyways. Have at it. I'll be back in a few. Might be around more. Looks like I'll be off the street and back in a place where I'll have access to a computer in the next month or so. . Which means you guys get to see me post again. Lol...

You could speed it up by using base 11 (or 10 if you don't care about capitalization), with the digits mapped to all and only those characters you need for your target string, i.e. [' ', 'A', 'E', 'H', 'K', 'O', 'R', 'S', 'V', 'W'] or [' ', 'a', 'e', 'h', 'k', 'K', 'o', 'r', 's', 'v', 'w']

 

[steve_bank]

The question is more general. Assuming all pi generation algorithms are the same, what is the probability of an arbitray sequence?

There must be files of i online.

Start off with the occurrence of any individual digit, then two digits, and so on. Once you do that you can estimate a probility of finding an encoded text sequence.

Then get a cheap used computer, a UPS backup, start the algorithm, and take a long vacation while it runs.

Adding... looks lie there is a .pi file extension for the outputs of pi calculators.

 

[Swammerdami]

The question is more general. Assuming all pi generation algorithms are the same, what is the probability of an arbitray sequence?

Mr. Bomb (or his envelope's back) already addressed this in #3.

Given a random sequence of symbols uniform on a B-sized alphabet, you will match a given M-length target once every B^M symbols on average.

In OP's task B=37, M=17; so B^M = 37^17 = ^{_{456487940826035155404146917}} ≈ 10^26.66

Oops; there's that pesky triple-6 Number of the Beast again. Blame OP for that, not me.