Este desafío es escribir código rápido que pueda realizar una suma infinita computacionalmente difícil.
Entrada
Una matriz n
by con entradas enteras que son más pequeñas que en valor absoluto. Al realizar la prueba, me complace proporcionar información a su código en cualquier formato sensible que su código desee. El valor predeterminado será una línea por fila de la matriz, separada por espacios y proporcionada en la entrada estándar.n
P
100
P
será positivo definitivo que implica que siempre será simétrico. Aparte de eso, realmente no necesita saber qué significa positivo definido para responder al desafío. Sin embargo, significa que en realidad habrá una respuesta a la suma definida a continuación.
Sin embargo, debe saber qué es un producto de matriz-vector .
Salida
Su código debe calcular la suma infinita:
dentro de más o menos 0.0001 de la respuesta correcta. Aquí Z
está el conjunto de enteros y también Z^n
todos los vectores posibles con n
elementos enteros y e
es la famosa constante matemática que equivale aproximadamente a 2.71828. Tenga en cuenta que el valor en el exponente es simplemente un número. Vea a continuación un ejemplo explícito.
¿Cómo se relaciona esto con la función Theta de Riemann?
En la notación de este documento sobre la aproximación de la función Theta de Riemann que estamos tratando de calcular . Nuestro problema es un caso especial por al menos dos razones.
- Establecemos el parámetro inicial llamado
z
en el documento vinculado a 0. - Creamos la matriz
P
de tal manera que el tamaño mínimo de un valor propio sea1
. (Vea a continuación cómo se crea la matriz).
Ejemplos
P = [[ 5., 2., 0., 0.],
[ 2., 5., 2., -2.],
[ 0., 2., 5., 0.],
[ 0., -2., 0., 5.]]
Output: 1.07551411208
Con más detalle, veamos solo un término en la suma de esta P. Tomemos, por ejemplo, solo un término en la suma:
y x^T P x = 30
. Tenga en cuenta que e^(-30)
se trata 10^(-14)
y, por lo tanto, es poco probable que sea importante para obtener la respuesta correcta hasta la tolerancia dada. Recuerde que la suma infinita en realidad usará todos los posibles vectores de longitud 4 donde los elementos son enteros. Acabo de elegir uno para dar un ejemplo explícito.
P = [[ 5., 2., 2., 2.],
[ 2., 5., 4., 4.],
[ 2., 4., 5., 4.],
[ 2., 4., 4., 5.]]
Output = 1.91841190706
P = [[ 6., -3., 3., -3., 3.],
[-3., 6., -5., 5., -5.],
[ 3., -5., 6., -5., 5.],
[-3., 5., -5., 6., -5.],
[ 3., -5., 5., -5., 6.]]
Output = 2.87091065342
P = [[6., -1., -3., 1., 3., -1., -3., 1., 3.],
[-1., 6., -1., -5., 1., 5., -1., -5., 1.],
[-3., -1., 6., 1., -5., -1., 5., 1., -5.],
[1., -5., 1., 6., -1., -5., 1., 5., -1.],
[3., 1., -5., -1., 6., 1., -5., -1., 5.],
[-1., 5., -1., -5., 1., 6., -1., -5., 1.],
[-3., -1., 5., 1., -5., -1., 6., 1., -5.],
[1., -5., 1., 5., -1., -5., 1., 6., -1.],
[3., 1., -5., -1., 5., 1., -5., -1., 6.]]
Output: 8.1443647932
P = [[ 7., 2., 0., 0., 6., 2., 0., 0., 6.],
[ 2., 7., 0., 0., 2., 6., 0., 0., 2.],
[ 0., 0., 7., -2., 0., 0., 6., -2., 0.],
[ 0., 0., -2., 7., 0., 0., -2., 6., 0.],
[ 6., 2., 0., 0., 7., 2., 0., 0., 6.],
[ 2., 6., 0., 0., 2., 7., 0., 0., 2.],
[ 0., 0., 6., -2., 0., 0., 7., -2., 0.],
[ 0., 0., -2., 6., 0., 0., -2., 7., 0.],
[ 6., 2., 0., 0., 6., 2., 0., 0., 7.]]
Output = 3.80639191181
Puntuación
Probaré su código en matrices P elegidas al azar de tamaño creciente.
Su puntaje es simplemente el más grande n
para el que obtengo una respuesta correcta en menos de 30 segundos cuando se promedia más de 5 carreras con matrices elegidas al azar P
de ese tamaño.
¿Qué tal una corbata?
Si hay un empate, el ganador será aquel cuyo código se ejecute más rápido en promedio durante 5 carreras. En el caso de que esos tiempos también sean iguales, el ganador es la primera respuesta.
¿Cómo se creará la entrada aleatoria?
- Sea M una matriz aleatoria de m por n con m <= n y entradas que son -1 o 1. En Python / numpy
M = np.random.choice([0,1], size = (m,n))*2-1
. En la práctica me voy a ponerm
a tratarn/2
. - Sea P la matriz de identidad + M ^ T M. En Python / numpy
P =np.identity(n)+np.dot(M.T,M)
. Ahora estamos garantizados de queP
es definitivo positivo y las entradas están en un rango adecuado.
Tenga en cuenta que esto significa que todos los valores propios de P son al menos 1, lo que hace que el problema sea potencialmente más fácil que el problema general de aproximar la función Theta de Riemann.
Idiomas y bibliotecas
Puede usar cualquier idioma o biblioteca que desee. Sin embargo, para fines de puntuación, ejecutaré su código en mi máquina, así que proporcione instrucciones claras sobre cómo ejecutarlo en Ubuntu.
Mi máquina Los tiempos se ejecutarán en mi máquina. Esta es una instalación estándar de Ubuntu en un procesador AMD FX-8350 de ocho núcleos de 8GB. Esto también significa que necesito poder ejecutar su código.
Respuestas principales
n = 47
en C ++ por Ton Hospeln = 8
en Python por Maltysen
fuente
x
de[-1,0,2,1]
. ¿Puedes dar más detalles sobre esto? (Sugerencia: no soy un gurú de las matemáticas)Respuestas:
C ++
No más acercamiento ingenuo. Solo evalúe dentro del elipsoide.
Utiliza las bibliotecas armadillo, ntl, gsl y pthread. Instalar usando
Compila el programa usando algo como:
En algunos sistemas, es posible que deba agregar
-lgslcblas
después-lgsl
.Ejecute con el tamaño de la matriz seguido de los elementos en STDIN:
matrix.txt
:O para probar una precisión de 1e-5:
infinity.cpp
:fuente
-lgslcblas
bandera para compilar. Increíble respuesta por cierto!Python 3
12 segundos n = 8 en mi computadora, ubuntu 4 core.
Realmente ingenuo, no tengo idea de lo que estoy haciendo.
Esto seguirá aumentando el rango
Z
que usa hasta que obtenga una respuesta lo suficientemente buena. Escribí mi propia matriz de multiplicación, prolly debería usar numpy.fuente