Cómo encontrar la secuencia de dígitos de pi?

Question

Vi este proyecto en github https://github.com/philipl/pifs, donde están tratando de comprimir los archivos en el pi número después de la coma decimal. Supongo que esto tiene sentido porque al parecer cada secuencia finita de dígitos que existen en las interminables números decimales de pi. Pero estoy tratando de entender a 1 paso de su proceso.

Así que en primer lugar de lo que yo entiendo, si usted desea comprimir un archivo, que es realmente representados en una secuencia de números como dicen 471947...2846 (de alguna manera, obtenido de la base 16). A continuación, se asume que la secuencia está en algún lugar en pi.

De alguna manera, a continuación, mirar hacia arriba, donde se inicia la secuencia en pi. Este es el paso que no entiendo cómo lo hacen. Pero el uso de una fórmula llamada Bailey–Borwein–Plouffe fórmula para hacerlo.

Por lo que la compresión es, en realidad, dos números de $<A,B>$, donde a es el índice del número de inicio de la pi, y B es la longitud necesaria.

Para ello, tan solo es un bucle, el bucle a través de todos los índices de Una, y repita B veces, y usar esa fórmula, para obtener el valor de los dígitos de pi, a continuación, volver a convertir binario, y usted tiene el archivo original de nuevo.

Pero es que el primer paso para encontrar que el primer inicio índice utilizando la fórmula no entiendo cómo se hace eso. Seguro que no la fuerza bruta y probar cada combinación de una forma lineal.

¿Alguien sabe?

Gracias

Answer 1

El proyecto en el que has encontrado es un (deliberada!) broma.

Es cierto que $\pi$ es la sospecha de ser normal en todas las bases, lo que implicaría que cada secuencia finita de dígitos hexadecimales aparece en algún lugar (de hecho, en muchas ocasiones) en la expansión hexadecimal de $\pi$.

Pero esto no puede ser utilizado para la compresión -- el problema es que el número de $A$ que te dice donde encontrar el archivo en $\pi$ - en la gran mayoría de los casos, ser tan grande que el almacenamiento de $A$ ocupa más espacio que se necesitaría para almacenar el archivo original.

El BBP fórmula no es especialmente adecuado para encontrar una secuencia particular en $\pi$, excepto por ensayo y error, o por empezar en algún lugar de $\pi$ y mantener la producción de dígitos hasta que al azar venir a través de la secuencia que usted está buscando. Así que en un principio, el objetivo del proyecto sería totalmente imposible ... sólo la localización de un diez bytes del archivo tomaría vidas. (Es decir, un múltiplo de la vida del universo).

El trampolín es en esta parte de la descripción:

Ahora, todos sabemos que se puede tomar un tiempo para encontrar una larga secuencia de dígitos en $\pi$, por lo que, por razones prácticas, debemos romper los archivos en partes más pequeñas que pueden ser más fácil de encontrar.

En esta implementación, para maximizar el rendimiento, consideramos que cada individuo bytes del archivo por separado, y la busque en $\pi$.

Así que en realidad no "comprimir" nada-sólo se almacena, para cada byte en el archivo, una posición en la $\pi$ donde bytes en particular se puede encontrar. (Y encontrar a esa corta un segmento es sin duda es factible por fuerza bruta). Pero el almacenamiento de una posición lleva más de un byte. Así que todo es sólo una simple sustitución de código, con una particularmente ineficaz aplicación.

(Y luego hay algunos más bromeando, diciendo que los índices no se cuentan como espacio utilizado porque son "metadatos".)

Answer 2

El Bailey-Borwein-Plouffle fórmula no permiten encontrar una secuencia de dígitos en $\pi$. Como la página de la Wikipedia, dice, le permite encontrar los dígitos hexadecimales de partida como un lugar deseado sin calcular las anteriores. Así que si quieres los dígitos de $\pi$, empezando en la milmillonésima parte, esta es tu amigo. Este sería utilizado en el descifrado de paso.

No está demostrado que cada dígito de la secuencia aparece en $\pi$, pero es probable. Yo no soy consciente de ninguna manera, además de la fuerza bruta para encontrar fueron una determinada secuencia se produce. El problema con la idea es que el índice para el archivo es probable que sea tan largo como el archivo. Sí, en lugar de almacenar el archivo se almacena el índice, pero es igual de grande y difícil de usar. Supongamos que usted tiene un archivo que es $1000$ hex dígitos de largo. Hay $16^{1000}$ secuencias de $1000$ dígitos hexadecimales, por lo que sería de esperar que la cadena a ocurrir en algún lugar alrededor de la posición $16^{1000}$, que se lleva a $1000$ dígitos hexadecimales a la tienda. En esta página usted puede buscar en la primera $200,000,000$ dígitos decimales de $\pi$ para una cadena deseada. Si usted busca $12345678$, informa que se produce en la posición $186557266$, $9$ dígitos en lugar de $8$

Answer 3

De alguna manera, a continuación, mirar hacia arriba, donde se inicia la secuencia en pi. Este es el paso no entiendo cómo lo hacen. Pero el uso de una fórmula llamada [Bailey–Borwein–Plouffe][1] la fórmula para hacerlo.

Sí, que es un fantástico descubrimiento, permite calcular el $k$-ésimo dígito detrás del periodo sin necesidad de conocer el antes de dígitos.

Esto beneficiaría el proceso de decodificación.

Que es el grano de la verdad detrás de este proyecto.

Sin embargo

Dijeron que el 100% de compresión era imposible? Usted está mirando!

y

Así que he mirado mi bytes en π, pero ¿cómo puedo recordar dónde están?

Bueno, obviamente has conseguido anotar en algún lugar; usted podría utilizar un pedazo de papel, pero recuerda todo lo que el espacio de almacenamiento que nos salvó por mover nuestros datos en π? ¿Por qué no guardamos nuestras ubicaciones de archivo de allí!?! Aún mejor, la ubicación de los archivos en π es metadatos y como todos nosotros conocer los metadatos se está volviendo más y más importante en todo lo que hacemos. No se siento muy bien de haber generado tanta metadatos? ¿Por qué perder tiempo con la vieja usanza de los datos cuando se puede tratar sólo con los metadatos, y mucha de ella!

que es, obviamente, un engaño.

Aquí es probable que el índice o el índice combinado y de longitud como resultado un gran número entero, probablemente mucho mayor que el del archivo original. No es una característica deseable para un esquema de compresión.