El objetivo es simple: calcular la función totient para tantos números como sea posible en 10 segundos y sumar los números.
Debe imprimir su resultado al final y realmente debe calcularlo. No se permite la función totient automatizada, pero las bibliotecas bignum sí. Debe comenzar en 1 y contar todos los enteros consecutivamente. Usted está no permite omitir los números.
Su puntaje es cuántos números puede calcular su programa en su máquina / cuántos puede calcular mi programa en su máquina . Mi código es un programa simple en C ++ (optimizaciones desactivadas), espero que pueda ejecutarlo.
¡Propiedades importantes que podrías usar!
- Si
gcd(m,n) = 1, phi(mn) = phi(m) * phi(n)
- si
p
es primo,phi(p) = p - 1
(parap < 10^20
) - si
n
es parphi(2n) = 2 phi(n)
- otros listados en el primer enlace
Mi código
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
while (b != 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}
int phi(int n)
{
int x = 0;
for (int i=1; i<=n; i++)
{
if (gcd(n, i) == 1)
x++;
}
return x;
}
int main()
{
unsigned int sum = 0;
for (int i=1; i<19000; i++) // Change this so it runs in 10 seconds
{
sum += phi(i);
}
cout << sum << endl;
return 0;
}
fastest-code
qwr
fuente
fuente
1, 3, 5, 2, 4
o algo así?Respuestas:
Nimrod: ~ 38,667 (580,000,000 / 15,000)
Esta respuesta utiliza un enfoque bastante simple. El código emplea un tamiz simple de números primos que almacena el primo de la potencia prima más pequeña en cada ranura para números compuestos (cero para primos), luego usa programación dinámica para construir la función totient sobre el mismo rango, luego suma los resultados. El programa pasa prácticamente todo su tiempo construyendo el tamiz, luego calcula la función totient en una fracción del tiempo. Parece que se trata de construir un tamiz eficiente (con el ligero giro de que uno también tiene que poder extraer un factor primo para los números compuestos del resultado y mantener el uso de la memoria en un nivel razonable).
Actualización: rendimiento mejorado al reducir la huella de memoria y mejorar el comportamiento de la memoria caché. Es posible exprimir un 5% -10% más de rendimiento, pero el aumento en la complejidad del código no vale la pena. En última instancia, este algoritmo ejerce principalmente el cuello de botella de von Neumann de la CPU, y hay muy pocos ajustes algorítmicos que puedan solucionarlo.
También actualicé el divisor de rendimiento ya que el código C ++ no estaba destinado a ser compilado con todas las optimizaciones y nadie más lo hizo. :)
Actualización 2: operación de tamizado optimizada para un mejor acceso a la memoria. Ahora maneja primos pequeños a granel a través de memcpy () (~ 5% de aceleración) y omite múltiplos de 2, 3 y 5 cuando tamiza primos más grandes (~ 10% de aceleración).
Código C ++: 9.9 segundos (con g ++ 4.9)
Código Nimrod: 9.9 segundos (con -d: release, gcc 4.9 backend)
fuente
Java, puntaje ~ 24,000 (360,000,000 / 15,000)
El siguiente código de Java hace el cálculo de la función totient y el tamiz principal juntos. Tenga en cuenta que, dependiendo de su máquina, debe aumentar el tamaño de almacenamiento dinámico inicial / máximo (en mi portátil bastante lento tuve que subir
-Xmx3g -Xms3g
).fuente
Nimrod: ~ 2,333,333 (42,000,000,000 / 18,000)
Esto utiliza un enfoque completamente diferente de mi respuesta anterior. Ver comentarios para más detalles. El
longint
módulo se puede encontrar aquí .fuente
2*sqrt(n)
), Lo que hace una puntuación mucho más baja.C #: 49,000 (980,000,000 / 20,000)
/codegolf//a/26800 "Código de Howard".
Pero modificado, los valores de phi se calculan para enteros impares.
Nueva puntuación: 61,000 (1,220,000,000 / 20,000)
En "App.config" tuve que agregar "gcAllowVeryLargeObjects enabled = true".
fuente
Python 3: ~ 24000 (335,000,000 / 14,000)
Mi versión es un puerto Python del algoritmo de Howard . Mi función original era una modificación de un algoritmo introducido en este blog .
Estoy usando los módulos Numpy y Numba para acelerar el tiempo de ejecución. Tenga en cuenta que normalmente no necesita declarar los tipos de variables locales (cuando usa Numba), pero en este caso quería reducir el tiempo de ejecución tanto como sea posible.
Editar: combina las funciones constructsieve y summaryum en una sola función.
C ++: 9.99s (n = 14,000); Python 3: 9.94s (n = 335,000,000)
fuente
Aquí está mi implementación de Python que parece capaz de producir ~ 60000 números en 10 segundos. Estoy factorizando números usando el algoritmo pollard rho y usando la prueba de primalidad Rabin miller.
fuente
φ (2 n ) = 2 n - 1
Σ φ (2 i ) = 2 i - 1 para i de 1 a n
Primero, algo para encontrar tiempos:
Para el código de referencia, para mí, eso es:
Ahora, Haskell:
Hace algo con 2525224 dígitos en 0.718 segundos. Y ahora solo estoy notando el comentario de @ Howard.
fuente
Matlab: 1464 = 26355867/18000
No puedo probar su código, así que dividí entre 18000, ya que representa la computadora más rápida de las personas que lo probaron. Llegué a la partitura usando esta propiedad:
Principalmente me gusta que es un trazador de líneas:
fuente
phi(p)
con todos los no primosp
?Python 2.7: 10.999 (165975/15090)
Pypy 2.3.1: 28.496 (430000/15090)
Algunos métodos interesantes que uso:
Prueba de pseudoprime fuerte de Rabin-Miller : una prueba de primalidad que proporciona un algoritmo probabilístico eficiente para determinar si un número dado es primo
Fórmula del producto de Euler : el producto está sobre los distintos números primos que dividen n
Código:
fuente