En un equipo puedo tener números enteros de tamaño arbitrario gracias a GMP, por lo que se representa en base 2 en la memoria.
Me pregunto si es posible en teoría a utilizar menos memoria si almacenar solamente factores primeros y su exponente, creo que es inútil para la mayoría números, pero me pregunto si funciona para una minoría muy pequeña de números con las factores primeros grandes.
¿Cómo puedo demostrarme equivocado?
No, no es posible. En general, no existe ningún algoritmo que comprime todos los $n$ cadena de bits, o reduce la longitud de una cadena aleatoria de bits (en espera).
Su algoritmo puede comprimir algunos números, pero luego se va a utilizar más memoria para almacenar los demás. Si sus datos son aleatorios, no hay ningún beneficio en el uso de su esquema de compresión.
En realidad, el hecho de que ningún esquema de compresión que existe puede ser usado para demostrar que existen infinitos números primos - de lo contrario, si hay sólo un número finito de números primos de su esquema de compresión sería muy eficiente!
Hay excelentes notas de la conferencia en la Complejidad de Kolmogorov por Alexander Shen que discutir "incompressability"; en particular, Shen escribe acerca de su algoritmo de compresión en la Sección 18.
Algo que implica de que la respuesta podría ser sí en algunas circunstancias (me especializo en precisión!) es que se puede hacer para resolver sistemas de ecuaciones lineales con coeficientes enteros grandes resolviendo el sistema de modulo de un número de números primos (o relativamente prime valores como $2^n-1$ para $n$) apropiado y combinación de los resultados usando el Teorema chino del resto. Tienes que tener suficiente moduli el su producto es mayor que cualquiera de los resultados.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
