Calcular dígitos de Pi

15

Esta es una tarea algo diferente. Calcule 1024 dígitos hexadecimales de π, comenzando en el lugar hexadecimal número 1024.

Formalmente: su programa debería completarse en menos de 1 minuto y producir el siguiente resultado:

25d479d8f6e8def7e3fe501ab6794c3b976ce0bd04c006bac1a94fb6409f60c45e5c9ec2196a246368fb6faf3e6c53b51339b2eb3b52ec6f6dfc511f9b30952ccc814544af5ebd09bee3d004de334afd660f2807192e4bb3c0cba85745c8740fd20b5f39b9d3fbdb5579c0bd1a60320ad6a100c6402c7279679f25fefb1fa3cc8ea5e9f8db3222f83c7516dffd616b152f501ec8ad0552ab323db5fafd23876053317b483e00df829e5c57bbca6f8ca01a87562edf1769dbd542a8f6287effc3ac6732c68c4f5573695b27b0bbca58c8e1ffa35db8f011a010fa3d98fd2183b84afcb56c2dd1d35b9a53e479b6f84565d28e49bc4bfb9790e1ddf2daa4cb7e3362fb1341cee4c6e8ef20cada36774c01d07e9efe2bf11fb495dbda4dae909198eaad8e716b93d5a0d08ed1d0afc725e08e3c5b2f8e7594b78ff6e2fbf2122b648888b812900df01c4fad5ea0688fc31cd1cff191b3a8c1ad2f2f2218be0e1777ea752dfe8b021fa1e5a0cc0fb56f74e818acf3d6ce89e299b4a84fe0fd13e0b77cc43b81d2ada8d9165fa2668095770593cc7314211a1477e6ad206577b5fa86c75442f5fb9d35cfebcdaf0c7b3e89a0d6411bd3ae1e7e4900250e2d2071b35e226800bb57b8e0af2464369bf009b91e5563911d59dfa6aa78c14389d95a537f207d5ba202e5b9c5832603766295cfa911c8197a72e72a341134834472

El programa con la menor duración gana. Tienes que calcular todos los dígitos en tiempo de ejecución. No tiene que implementar el algoritmo que calcula π; Si su idioma ya proporciona esa funcionalidad, puede usarla.

FUZxxl
fuente
Ja, debería ser fácil. (+1, aún) Apuesto a que puedo ejecutarlo en menos de unos segundos.
Mateen Ulhaq
@muntoo: ¿Y? ¿Dónde está tu solución?
FUZxxl
Olvidé hacerlo. :) Por cierto, velocidad! = Código-golf.
Mateen Ulhaq
@muntoo: lo sé. Pero también creo que 5 días es un buen momento para una tarea tan fácil.
FUZxxl

Respuestas:

13

Sage, 29 char

Esto no es técnicamente trampa, ya que los dígitos se calculan en tiempo de ejecución. Dicho eso, sigue siendo barato como el infierno.

hex(floor(pi*2^8192))[1025:]
boothby
fuente
1
Definitivamente no es trampa.
FUZxxl
11
Mmmm, piso pi.
breadbox
13

Utilidades de Shell: 48

curl -sL ow.ly/5u3hc|grep -Eom 1 '[a-f0-9]{1024}'

  • Toda la salida se "calcula" en tiempo de ejecución. (gracias a OP publicar la solución)
  • Corre en menos de un minuto. (puede depender de la velocidad de su conexión a internet)
usuario2074
fuente
Por lo general, rechazo ese tipo de soluciones, porque son un abuso común de las reglas y ya no son divertidas. Pero solo porque eres tan astuto para tomar la solución de referencia proporcionada y escribir Todos los resultados se "calculan" en tiempo de ejecución. (gracias a que OP publicó la solución) , le doy un
voto positivo
Versión de golf: curl -sL ow.ly/shKGY|grep -Po \\w{99,}(37). Trabaja en Dash. Bash necesitaría un byte adicional.
Dennis
6

J, 156, 140, 137 127

d=:3 :'1|+/4 _2 _1 _1*+/(y&(16^-)%1 4 5 6+8*])"0 i.y+9'
,1([:}.'0123456789abcdef'{~[:|.[:<.[:(],~16*1|{.)^:8 d)"0\1024x+8*i.128

Usando la fórmula BBP.

No no funcionar en menos de un minuto (pero tenemos una respuesta J: p)

Ejemplo para los primeros 104 dígitos de π (esto corre rápido):

,1([:}.'0123456789abcdef'{~[:|.[:<.[:(],~16*1|{.)^:8 d)"0\8*i.13x

243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89
452821e638d01377be5466cf34e90c6cc0ac29b7
Eelvex
fuente
¿Por qué no usa #: para convertir los números a hexadecimales?
FUZxxl
No estoy seguro de lo que quieres decir. #:no generará dígitos hexadecimales.
Eelvex
En mi humilde opinión, es más fácil usar #: y una reforma para generar dígitos hexadecimales que su enfoque actual.
FUZxxl
¿Quieres decir algo así (... 16 #:) Pi? Creo que no tenemos suficientes dígitos, así que tenemos que generarlos de todos modos.
Eelvex
1
Por cierto, descubrí que existe el verbo hfdpara convertir números a hexadecimales.
FUZxxl
5

JavaScript, 536

(Saltos de línea e indentación solo para legibilidad)

var d='0123456789abcdef',p='',o='',l=3e3,c=0,e='length';d=d+d;
function $(n,r){return n[e]<=r?0:d.indexOf(n[r])}
function g(a,b){for(i=0,t='',s=16;i<l;i++,t+=d[~~(s/b)],s=(s%b)*16);
for(;a--;t=_(t,t,1));return t}
function _(a,b,s){for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i>=0;r=(s?
  function(k){c=k>15;return d[k]}($(a,i)+$(b,i)+c):
  function(k){c=k<0;return d[k+16]}($(a,i)-$(b,i)-c))+r,i--);return r}
for(i=0;i<l;i++,p+='2');
for(j=1;j<l;p=_(p,(o+='0')+_(_(_(g(2,8*j+1),g(1,8*j+4)),g(0,8*j+5)),g(0,8*j+6)),1),j++);
console.log(p.slice(1024,2048))

Tarda unos 25 segundos, en Google Chrome 14 en mi computadora portátil con Intel i5 core. ¿Alguien más puede jugar golf este código? No puedo jugar bien al golf .. :(

Debajo está no golfizado. Solo eliminé todos los comentarios y cambié el loop por golf.

No mencione sobre for(;s>=b;s-=b);s*=16;. Lo cambié a s=(s%b)*16. :PAG

/**
Calculate PI-3 to 3000 (3e3) digits.
a : a
b : b
c : carry
d : digits
e : length
f : get from d
g : calculate (2^a)/b.
i,j, : for looping
l : length to calculate
p : pi
r,t : return value
*/
var d='0123456789abcdef',p='',o='',l=3e3,c=0,e='length';
d=d+d;//for carring

function $(n,r){return n[e]<=r?0:d.indexOf(n[r])}
/*
Calculate (2^a)/b. Assume that 2^a < b.
*/
function g(a,b){
    for(i=0,t='',s=16;i<l;i++){t+=d[~~(s/b)];for(;s>=b;s-=b);s*=16;}
    for(;a--;t=_(t,t,1));return t}
/*
Calculate a±b. (+ when s=1, - when s=0) When calculating minus, assume that 1>b>a>0.
*/
function _(a,b,s){
    for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i>=0;
        r=(s?function(k){c=k>15;return d[k]}($(a,i)+$(b,i)+c):
            function(k){c=k<0;return d[k+16]}($(a,i)-$(b,i)-c))+r,i--);return r;
}
/*
Using BBP formula. Calc when j=0...
4/1 - 2/4 - 1/5 - 1/6 = 3.22222222.... (b16)
*/
for(i=0;i<l;i++,p+='2');
//Calc when j>0
for(j=1;j<l;p=_(p,(o+='0')+_(_(_(g(2,8*j+1),g(1,8*j+4)),g(0,8*j+5)),g(0,8*j+6)),1),j++);
console.log(p.slice(1024,2048));

EDITAR: Se eliminó la función totalmente no utilizada. (¿Por qué me quedé con eso?: /)

PD. Primeros 100 dígitos de PI

243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89452821e638d01377be5466cf34e90c6cc0ab

JiminP
fuente
@FUZxxl: ¿No fue suficiente el código no golfizado? .. :(
JiminP
Era de hecho. Pero en mi humilde opinión, se ve mejor, si utiliza el formato de código en lugar de utilizar la sintaxis de retroceso. Como escribí, siéntete libre de volver si no te gusta.
FUZxxl
d='0123456789abcdef',l=3e3,p=Array(l+1).join(2),o='',c=0,e='length';d+=d;function _(a,b,s){for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i+1;r=d[Z=F(b,i,1)+c,k=F(a,i,1)+(s?Z:16-Z),c=s?k>15:k<16,k]+r,i--);return r}function F(a,b,f){if(f)f=a[e]>b?d.indexOf(a[b]):0;else{for(i=0,f='',s=16;i++<l;f+=d[~~(s/b)],s=(s%b)*16);while(a--)f=_(f,f,1)}return f}for(j=0;++j<l;p=_(p,(o+='0')+_(_(_(F(2,z=8*j+1),F(1,z+3)),F(0,z+4)),F(0,z+5)),1));console.log(p.slice(1024,2048))
Peter Taylor
Eso es realmente todas las micro optimizaciones, aunque algunas de ellas parecen bastante grandes. El mayor ahorro proviene de la eliminación de las dos funciones anónimas _a favor del ,operador. La más complicada es la fusión de $y gen una función, con un argumento opcional para seleccionar entre ellas. functiony returnambos son bastante caros, por lo que un if(f)...elsepar de ellos ,1es una compensación razonable.
Peter Taylor
4

PHP 116 114 bytes

<?for(;$g?$d=0|($$g=$g--/2*$d+($$g?:2)%$g*$f)/$g--:4613^printf($i++>257?'%04x':'',$e+$d/$f=4*$g=16384)^$e=$d%$f;);

Esta solución calcula todos los pi hasta 2048 dígitos hexadecimales, cuatro dígitos hexadecimales a la vez, y genera la última mitad de ellos. El tiempo de ejecución es inferior a 5 segundos. La fórmula utilizada para el cálculo es la siguiente:

pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + 5/11*(2 + 6/13*(2 + 7/15*(2 + ... )))))))

La precisión se obtiene almacenando los restos en una matriz y continuando cada una de las 2 ^ 14 divisiones de forma incremental.

Python 64 bytes

x=p=16385
while~-p:x=p/2*x/p+2*2**8192;p-=2
print('%x'%x)[1025:]

El mismo método que el anterior. Se ejecuta en aproximadamente 0.2s.

O como una línea en 73 bytes :

print('%x'%reduce(lambda x,p:p/2*x/p+2*2**8192,range(16387,1,-2)))[1025:]
primo
fuente
3

PARI / GP-2.4, 141

forstep(d=1024,2047,8,y=frac(apply(x->sum(k=0,d+30,16^(d-k)/(8*k+x)),[1,4,5,6])*[4,-2,-1,-1]~);for(i=0,7,y=16*frac(y);printf("%X",floor(y))))

Usando la fórmula de Bailey – Borwein – Plouffe (por supuesto).

Se ejecuta en menos de un minuto.

Eelvex
fuente
3

Código C:

long ki,k,e,d=1024;
int  dig,tD=0,c,Co=0,j,js[4]  ={1,4,5,6};
double res=0.0,tres=0.0,gT,ans[4] ={0.0};
while(tD < 1024)
{while(Co<4){ j= js[Co],gT=0.0,ki= 0;
 for(; ki < d+1;ki++){ k = 8*ki+j,e= d-ki,c=1; while(e--) c = 16*c % k; gT+=((double)(c)/(double)k);}
 ans[Co] = (gT - (int)gT),++Co;}
 double gA = 4*ans[0]-2*ans[1]-ans[2]-ans[3];
 gA = (gA<0) ? gA + -1*(int)gA +1 : gA -(int)gA;
 dig=0;while(dig++ < 6 && tD++ < 1024) gA *=16, printf("%X",gA),gA -= (int)gA;
 d+=6,Co = 0;}

tiempo de ejecución = 8.06 segundos en un Intel Quad Core

johnnyR
fuente
Este es el código de golf. Intente comprimir su código tanto como sea posible utilizando nombres de variables cortos y evitando espacios en blanco. Por ejemplo, podría guardar muchos caracteres utilizando en printf("%X",(int)gA)lugar de esa larga lista.
FUZxxl
1

PARI / GP - 40 bytes

Esta versión 'engaña' al usar \xpara mostrar los dígitos hexadecimales del resultado.

\p8197
x=Pi<<4^6;x-=x\1;x=(x<<4^6)\1
\xx

Esta versión tarda 87 bytes para convertir a hexadecimal de la manera habitual.

\p8197
x=Pi<<4^6;x-=x\1;concat([Vec("0123456789abcdef")[n+1]|n<-digits((x<<4^6)\1,16)])

Ambas versiones se ejecutan en una pequeña fracción de segundo.

Charles
fuente
1

Perl - 59

use ntheory"Pi";say substr int(Pi(3000)<<8192)->as_hex,1027

Menos de 0.1s.

DanaJ
fuente
0

Shell 68

herramientas: bc -l, tr, corte

echo "scale=2468;obase=16;4*a(1)"|bc -l|tr -d '\\\n'|cut -c1027-2051

Shell 64, herramientas: bc -l, tr, tail, difiere en el redondeo del último lugar

echo "scale=2466;obase=16;4*a(1)"|bc -l|tr -d '\\\n'|tail -c1024

Puede considerarse trampa, ya que el conocimiento de cómo calcular PI está en 4 * a (1), y que 1 tiene que usar scale = 2466 se investigó de forma iterativa.

Gracias a breadbox por la idea de usar cortar.

usuario desconocido
fuente
No veo cómo podría considerarse trampa; los dígitos se calculan en tiempo de ejecución. Aunque debo tener en cuenta que cuando lo ejecuto, la salida difiere en el último dígito (7 en lugar de A). Por cierto, creo que puede reemplazar el ddcomando con tail -c1024para guardar algunos caracteres.
breadbox
Sí, también observé la diferencia (y paso media hora en eso :)). Si le digo a bc que use una escala de x dígitos, se redondea a ese dígito en modo decimal y luego realiza la conversión hexadecimal. Entonces, si tomo un dígito más, produce un 69, no un 7. Sin embargo, el estilo de redondeo o el truncamiento no se especificaron en la pregunta. Y gracias por la idea de la cola. :)
usuario desconocido
La pregunta especifica: terminar y producir una salida idéntica a la especificada.
FUZxxl
@FUZxxl: "debería ...", no "debe ..." - Pensé que debería ser una ayuda verificar, si la conversión hexadecimal está funcionando bien, y el recuento de caracteres a omitir, no como parte de la especificación , para cumplir con el último dígito de 1024. Pero cedí y agregué 16 caracteres para reemplazar uno.
usuario desconocido
1
Dado que la oración comienza con la palabra "Formalmente", estaría de acuerdo en que el OP probablemente lo quiso decir en el sentido RFC de la palabra. Además, aún puede mejorar su nueva solución reemplazando el uso de ddcon cut -c1027-2051. (El shell tiene muchas herramientas para manipular secuencias de texto.)
breadbox