Ha habido mil millones de iteraciones de desafíos de Fibonacci en este sitio web, ¡así que vamos a darle vida a un desafío de Fibonacci de mil millones de iteraciones!

Su desafío es generar los primeros 1000 dígitos decimales del número 1,000,000,000 de Fibonacci con el programa más corto posible. Luego, opcionalmente, esto puede ser seguido por cualquier salida adicional de su elección, que incluye pero no se limita al resto de los dígitos.

Estoy utilizando la convención de que fib 0 = 0, fib 1 = 1.

Su programa debe ser lo suficientemente rápido para que pueda ejecutarlo y verificar su corrección. Para este propósito, aquí están los primeros 1000 dígitos:

7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799

Python 2 + sympy, 72 bytes

from sympy import*
n=sqrt(5)
print'7'+`((.5+n/2)**1e9/n).evalf(1e3)`[2:]

Pruébalo en línea!

-10 bytes eliminando el término prácticamente-0 gracias a Jeff Dege
-1 byte (1000 -> 1e3 gracias a Zacharý)
-2 bytes eliminando la variable innecesaria gracias a Erik the Outgolfer
-2 bytes moviéndose a Python 2 gracias a Zacharý
-3 bytes por 11 ' -11gracias a ThePirateBay -3 bytes cambiando strpor backticks gracias a notjagan

¡ahora supera la solución haskell sin publicar de OP!

Python 2 , 106 bytes

a,b=0,1
for c in bin(10**9):
 a,b=2*a*b-a*a,a*a+b*b
 if'1'==c:a,b=b,a+b
 while a>>3340:a/=10;b/=10
print a

Pruébalo en línea!

No hay bibliotecas, solo aritmética de enteros. Corre casi al instante.

El núcleo es la identidad de divide y vencerás:

f(2*n)   = 2*f(n)*f(n+1) - f(n)^2
f(2*n+1) = f(n)^2 + f(n+1)^2

Esto nos permite actualizar (a,b) = (f(n),f(n+1))a doble n -> 2*n. Como queremos obtener n=10**9, esto solo requiere log_2(10**9)=30iteraciones. Construimos nhasta 10**9haciendo repetidamente n->2*n+cpara cada dígito cde su expansión binaria. Cuando c==1, el valor duplicado se desplaza hacia arriba 2*n -> 2*n+1con un cambio de Fibonacci de un paso(a,b)=(b+a,b)

Para mantener los valores a,bmanejables, almacenamos solo sus primeros 1006dígitos dividiendo el piso entre 10hasta que estén debajo 2**3340 ~ 1e1006.

Código de máquina x86 de 32 bits (con llamadas al sistema Linux): 106 105 bytes

registro de cambios: guardó un byte en la versión rápida porque una constante off-by-one no cambia el resultado para Fib (1G).

O 102 bytes para una versión un 18% más lenta (en Skylake) (usando mov/ sub/ en cmclugar de lea/ cmpen el bucle interno, para generar la ejecución y el ajuste en 10**9lugar de 2**32). O 101 bytes para una versión más lenta ~ 5.3x con una rama en el manejo de acarreo en el bucle más interno. (¡Medí una tasa de predicción errónea de sucursal del 25.4%!)

O 104/101 bytes si se permite un cero inicial. (Se necesita 1 byte adicional para que el código duro omita 1 dígito de la salida, que es lo que se necesita para Fib (10 ** 9)).

Desafortunadamente, el modo NASM de TIO parece ignorarse -felf32en los indicadores del compilador. Aquí hay un enlace de todos modos con mi código fuente completo, con todo el lío de ideas experimentales en los comentarios.

Este es un programa completo . Imprime los primeros 1000 dígitos de Fib (10 ** 9) seguidos de algunos dígitos adicionales (los últimos de los cuales son incorrectos) seguidos de algunos bytes basura (sin incluir una nueva línea). La mayor parte de la basura no es ASCII, por lo que es posible que desee canalizar cat -v. Sin embargo, no rompe mi emulador de terminal (KDE konsole). Los "bytes basura" están almacenando Fib (999999999). Ya tenía -1024en un registro, por lo que era más barato imprimir 1024 bytes que el tamaño adecuado.

Estoy contando solo el código de máquina (tamaño del segmento de texto de mi ejecutable estático), no la pelusa que lo convierte en un ejecutable ELF. ( Son posibles ejecutables ELF muy pequeños , pero no quería molestarme con eso). Resultó ser más corto usar memoria de pila en lugar de BSS, por lo que puedo justificar no contar nada más en el binario ya que no dependo de ningún metadato. (La producción de un binario estático despojado de la forma normal hace que un ELF de 340 bytes sea ejecutable).

Podría hacer una función de este código que podría llamar desde C. Costaría unos pocos bytes guardar / restaurar el puntero de la pila (tal vez en un registro MMX) y alguna otra sobrecarga, pero también guardar bytes al regresar con la cadena en memoria, en lugar de hacer una write(1,buf,len)llamada al sistema. Creo que jugar golf en código de máquina debería ganarme un poco de holgura aquí, ya que nadie más ha publicado una respuesta en ningún idioma sin precisión extendida nativa, pero creo que una versión funcional de esto aún debería tener menos de 120 bytes sin volver a jugar golf todo cosa.

Algoritmo:

fuerza bruta a+=b; swap(a,b), truncada según sea necesario para mantener solo los primeros> = 1017 dígitos decimales. Se ejecuta en 1min13s en mi computadora (o 322.47 mil millones de ciclos de reloj + - 0.05%) (y podría ser un poco más rápido con unos pocos bytes adicionales de tamaño de código, o hasta 62s con un tamaño de código mucho mayor desde el desenrollado del bucle. No matemática inteligente, solo haciendo el mismo trabajo con menos gastos generales). Se basa en la implementación de Python de @ AndersKaseorg , que se ejecuta en 12min35s en mi computadora (4.4GHz Skylake i7-6700k). Ninguna de las versiones tiene errores de caché L1D, por lo que mi DDR4-2666 no importa.

A diferencia de Python, almaceno los números de precisión extendida en un formato que libera los dígitos decimales truncados . Almaceno grupos de 9 dígitos decimales por entero de 32 bits, por lo que un desplazamiento del puntero descarta los 9 dígitos bajos. Esto es efectivamente una base de mil millones, que es una potencia de 10. (Es pura coincidencia que este desafío necesite el número mil millonésimo de Fibonacci, pero me ahorra un par de bytes frente a dos constantes separadas).

Siguiendo la terminología de GMP , cada fragmento de 32 bits de un número de precisión extendida se denomina "extremidad". La ejecución mientras se agrega debe generarse manualmente con una comparación con 1e9, pero luego se usa normalmente como una entrada a la ADCinstrucción habitual para la siguiente extremidad. (También tengo que ajustar manualmente al [0..999999999]rango, en lugar de 2 ^ 32 ~ = 4.295e9. Hago esto sin ramificaciones con lea+ cmov, usando el resultado de la comparación).

Cuando la última rama produce una ejecución distinta de cero, las siguientes dos iteraciones del bucle externo leen desde una rama más alta de lo normal, pero aún escriben en el mismo lugar. Esto es como hacer un memcpy(a, a+4, 114*4)desplazamiento hacia la derecha en una extremidad, pero como parte de los siguientes dos bucles de adición. Esto sucede cada ~ 18 iteraciones.

Hacks para ahorrar tamaño y rendimiento:

• Las cosas habituales como en lea ebx, [eax-4 + 1]lugar de mov ebx, 1, cuando lo sé eax=4. Y usar loopen lugares donde LOOPla lentitud solo tiene un pequeño impacto.

• Truncar por 1 miembro de forma gratuita mediante la compensación de los punteros que leemos, mientras sigue escribiendo al inicio del búfer en el adcbucle interno. Leemos [edi+edx]y escribimos a [edi]. Entonces podemos obtener edx=0u 4obtener un desplazamiento de lectura y escritura para el destino. Necesitamos hacer esto para 2 iteraciones sucesivas, primero compensando ambas, luego solo compensando el dst. Detectamos el segundo caso al mirar esp&4antes de restablecer los punteros al frente de los buffers (usando &= -1024, porque los buffers están alineados). Ver comentarios en el código.

• El entorno de inicio de proceso de Linux (para un ejecutable estático) pone a cero la mayoría de los registros, y la memoria de pila debajo de esp/ rspse pone a cero. Mi programa se aprovecha de esto. En una versión de función invocable de esto (donde la pila no asignada podría estar sucia), podría usar BSS para memoria puesta a cero (al costo de quizás 4 bytes más para configurar punteros). La reducción a cero edxtomaría 2 bytes. El x86-64 System V ABI no garantiza ninguno de estos, pero la implementación de Linux hace cero (para evitar filtraciones de información del núcleo). En un proceso vinculado dinámicamente, se /lib/ld.soejecuta antes _starty deja registros distintos de cero (y probablemente basura en la memoria debajo del puntero de la pila).

• Me mantengo -1024en ebxuso fuera de los bucles. Úselo blcomo un contador para los bucles internos, que termina en cero (que es el byte bajo de -1024, restaurando así la constante para su uso fuera del bucle). Intel Haswell y versiones posteriores no tienen penalizaciones por fusión de registros parciales para registros low8 (y de hecho ni siquiera los renombran por separado) , por lo que hay una dependencia en el registro completo, como en AMD (no es un problema aquí). Sin embargo, esto sería horrible en Nehalem y anteriores, que tienen puestos de registro parcial al fusionarse. Hay otros lugares donde escribo registros parciales y luego leo el registro completo sin xorponer a cero omovzx, generalmente porque sé que algún código anterior puso a cero los bytes superiores, y nuevamente está bien en AMD e Intel SnB-family, pero lento en Intel pre-Sandybridge.

  Lo uso 1024como el número de bytes para escribir en stdout ( sub edx, ebx), por lo que mi programa imprime algunos bytes de basura después de los dígitos de Fibonacci, porque mov edx, 1000cuesta más bytes.

• (no se utiliza) adc ebx,ebxcon EBX = 0 para obtener EBX = CF, el ahorro de 1 byte vs setc bl.

• dec/ jnzdentro de un adcbucle conserva CF sin causar un bloqueo parcial de bandera cuando adclee banderas en Intel Sandybridge y posteriores. Es malo en CPU anteriores , pero AFAIK gratis en Skylake. O, en el peor de los casos, un impulso adicional.

• Use la memoria a continuación espcomo una zona roja gigante . Dado que este es un programa completo de Linux, sé que no instalé ningún controlador de señal y que nada más bloqueará asincrónicamente la memoria de la pila de espacio de usuario. Este puede no ser el caso en otros sistemas operativos.

• Aproveche el motor de pila para ahorrar ancho de banda de emisión de uop usando pop eax(1 uop + uop de sincronización de pila ocasional) en lugar de lodsd(2 uops en Haswell / Skylake, 3 en IvB y anteriores según las tablas de instrucciones de Agner Fog )). IIRC, esto redujo el tiempo de ejecución de aproximadamente 83 segundos a 73. Probablemente podría obtener la misma velocidad al usar un movmodo de direccionamiento indexado, como mov eax, [edi+ebp]donde se ebpmantiene el desplazamiento entre las memorias intermedias src y dst. (Haría que el código fuera del bucle interno fuera más complejo, ya que tendría que negar el registro de desplazamiento como parte del intercambio de src y dst para las iteraciones de Fibonacci). Consulte la sección "rendimiento" a continuación para obtener más información.

• comience la secuencia dando a la primera iteración un arrastre (un byte stc), en lugar de almacenar un 1en memoria en cualquier lugar. Muchas otras cosas específicas del problema documentadas en los comentarios.

Listado NASM (código máquina + fuente) , generado con nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Luego, eliminé a mano algunos bloques de material comentado, por lo que la numeración de las líneas tiene huecos). Para eliminar las columnas iniciales y poder introducirlas en YASM o NASM, use cut -b 27- <fibonacci-1G.lst > fibonacci-1G.asm.

  1          machine      global _start
  2          code         _start:
  3 address

  4 00000000 B900CA9A3B       mov    ecx, 1000000000       ; Fib(ecx) loop counter
  5                       ;    lea    ebp, [ecx-1]          ;  base-1 in the base(pointer) register ;)
  6 00000005 89CD             mov    ebp, ecx    ; not wrapping on limb==1000000000 doesn't change the result.
  7                                              ; It's either self-correcting after the next add, or shifted out the bottom faster than Fib() grows.
  8                       
 42                       
 43                       ;    mov    esp, buf1
 44                       
 45                       ;    mov    esi, buf1   ; ungolfed: static buffers instead of the stack
 46                       ;    mov    edi, buf2

 47 00000007 BB00FCFFFF       mov    ebx, -1024
 48 0000000C 21DC             and    esp, ebx    ; alignment necessary for convenient pointer-reset
 49                       ;    sar    ebx, 1
 50 0000000E 01DC             add    esp, ebx     ; lea    edi, [esp + ebx].  Can't skip this: ASLR or large environment can put ESP near the bottom of a 1024-byte block to start with
 51 00000010 8D3C1C           lea    edi, [esp + ebx*1]
 52                           ;xchg   esp, edi   ; This is slightly faster.  IDK why.
 53                       
 54                           ; It's ok for EDI to be below ESP by multiple 4k pages.  On Linux, IIRC the main stack automatically extends up to ulimit -s, even if you haven't adjusted ESP.  (Earlier I used -4096 instead of -1024)
 55                           ; After an even number of swaps, EDI will be pointing to the lower-addressed buffer
 56                           ; This allows a small buffer size without having the string step on the number.
 57
 58                       ; registers that are zero at process startup, which we depend on:
 59                       ;    xor   edx, edx
 60                       ;;  we also depend on memory far below initial ESP being zeroed.
 61
 62 00000013 F9               stc    ; starting conditions: both buffers zeroed, but carry-in = 1
 63                       ; starting Fib(0,1)->0,1,1,2,3 vs. Fib(1,0)->1,0,1,1,2 starting "backwards" puts us 1 count behind
 66
 67                       ;;; register usage:
 68                       ;;; eax, esi: scratch for the adc inner loop, and outer loop
 69                       ;;; ebx: -1024.  Low byte is used as the inner-loop limb counter (ending at zero, restoring the low byte of -1024)
 70                       ;;; ecx: outer-loop Fibonacci iteration counter
 71                       ;;; edx: dst read-write offset (for "right shifting" to discard the least-significant limb)
 72                       ;;; edi: dst pointer
 73                       ;;; esp: src pointer
 74                       ;;; ebp: base-1 = 999999999.  Actually still happens to work with ebp=1000000000.
 75
 76                       .fibonacci:
 77                       limbcount equ 114             ; 112 = 1006 decimal digits / 9 digits per limb.  Not enough for 1000 correct digits, but 114 is.
 78                                                     ; 113 would be enough, but we depend on limbcount being even to avoid a sub
 79 00000014 B372             mov    bl, limbcount
 80                       .digits_add:
 81                           ;lodsd                       ; Skylake: 2 uops.  Or  pop rax  with rsp instead of rsi
 82                       ;    mov    eax, [esp]
 83                       ;    lea    esp, [esp+4]   ; adjust ESP without affecting CF.  Alternative, load relative to edi and negate an offset?  Or add esp,4 after adc before cmp
 84 00000016 58               pop    eax
 85 00000017 130417           adc    eax, [edi + edx*1]    ; read from a potentially-offset location (but still store to the front)
 86                        ;; jz .out   ;; Nope, a zero digit in the result doesn't mean the end!  (Although it might in base 10**9 for this problem)
 87
 88                       %if 0   ;; slower version
                          ;; could be even smaller (and 5.3x slower) with a branch on CF: 25% mispredict rate
 89                           mov  esi, eax
 90                           sub  eax, ebp  ; 1000000000 ; sets CF opposite what we need for next iteration
 91                           cmovc eax, esi
 92                           cmc                         ; 1 extra cycle of latency for the loop-carried dependency. 38,075Mc for 100M iters (with stosd).
 93                                                       ; not much worse: the 2c version bottlenecks on the front-end bottleneck
 94                       %else   ;; faster version
 95 0000001A 8DB0003665C4     lea    esi, [eax - 1000000000]
 96 00000020 39C5             cmp    ebp, eax                ; sets CF when (base-1) < eax.  i.e. when eax>=base
 97 00000022 0F42C6           cmovc  eax, esi                ; eax %= base, keeping it in the [0..base) range
 98                       %endif
 99                       
100                       %if 1
101 00000025 AB               stosd                          ; Skylake: 3 uops.  Like add + non-micro-fused store.  32,909Mcycles for 100M iters (with lea/cmp, not sub/cmc)
102                       %else
103                         mov    [edi], eax                ; 31,954Mcycles for 100M iters: faster than STOSD
104                         lea   edi, [edi+4]               ; Replacing this with ADD EDI,4 before the CMP is much slower: 35,083Mcycles for 100M iters
105                       %endif
106                       
107 00000026 FECB             dec    bl                      ; preserves CF.  The resulting partial-flag merge on ADC would be slow on pre-SnB CPUs
108 00000028 75EC             jnz .digits_add
109                           ; bl=0, ebx=-1024
110                           ; esi has its high bit set opposite to CF
111                       .end_innerloop:
112                           ;; after a non-zero carry-out (CF=1): right-shift both buffers by 1 limb, over the course of the next two iterations
113                           ;; next iteration with r8 = 1 and rsi+=4:  read offset from both, write normal.  ends with CF=0
114                           ;; following iter with r8 = 1 and rsi+=0:  read offset from dest, write normal.  ends with CF=0
115                           ;; following iter with r8 = 0 and rsi+=0:  i.e. back to normal, until next carry-out (possible a few iters later)
116                       
117                           ;; rdi = bufX + 4*limbcount
118                           ;; rsi = bufY + 4*limbcount + 4*carry_last_time
119                       
120                       ;    setc   [rdi]
123 0000002A 0F92C2           setc   dl
124 0000002D 8917             mov    [edi], edx ; store the carry-out into an extra limb beyond limbcount
125 0000002F C1E202           shl    edx, 2

139                           ; keep -1024 in ebx.  Using bl for the limb counter leaves bl zero here, so it's back to -1024 (or -2048 or whatever)
142 00000032 89E0             mov    eax, esp   ; test/setnz could work, but only saves a byte if we can somehow avoid the  or dl,al
143 00000034 2404             and    al, 4      ; only works if limbcount is even, otherwise we'd need to subtract limbcount first.

148 00000036 87FC             xchg   edi, esp   ; Fibonacci: dst and src swap
149 00000038 21DC             and    esp, ebx  ; -1024  ; revert to start of buffer, regardless of offset
150 0000003A 21DF             and    edi, ebx  ; -1024
151                       
152 0000003C 01D4             add    esp, edx             ; read offset in src

155                           ;; after adjusting src, so this only affects read-offset in the dst, not src.
156 0000003E 08C2             or    dl, al              ; also set r8d if we had a source offset last time, to handle the 2nd buffer
157                           ;; clears CF for next iter

165 00000040 E2D2             loop .fibonacci  ; Maybe 0.01% slower than dec/jnz overall

169                       to_string:

175                       stringdigits equ 9*limbcount  ; + 18
176                       ;;; edi and esp are pointing to the start of buffers, esp to the one most recently written
177                       ;;;  edi = esp +/- 2048, which is far enough away even in the worst case where they're growing towards each other
178                       ;;;  update: only 1024 apart, so this only works for even iteration-counts, to prevent overlap

180                           ; ecx = 0 from the end of the fib loop
181                           ;and   ebp, 10     ; works because the low byte of 999999999 is 0xff
182 00000042 8D690A           lea    ebp, [ecx+10]         ;mov    ebp, 10
183 00000045 B172             mov    cl, (stringdigits+8)/9
184                       .toascii:  ; slow but only used once, so we don't need a multiplicative inverse to speed up div by 10
185                           ;add   eax, [rsi]    ; eax has the carry from last limb:  0..3  (base 4 * 10**9)
186 00000047 58               pop    eax                  ; lodsd
187 00000048 B309             mov    bl, 9
188                       .toascii_digit:
189 0000004A 99               cdq                         ; edx=0 because eax can't have the high bit set
190 0000004B F7F5             div    ebp                  ; edx=remainder = low digit = 0..9.  eax/=10

197 0000004D 80C230           add    dl, '0'
198                                              ; stosb  ; clobber [rdi], then  inc rdi
199 00000050 4F               dec    edi         ; store digits in MSD-first printing order, working backwards from the end of the string
200 00000051 8817             mov    [edi], dl
201                       
202 00000053 FECB             dec    bl
203 00000055 75F3             jnz  .toascii_digit
204                       
205 00000057 E2EE             loop .toascii
206                       
207                           ; Upper bytes of eax=0 here.  Also AL I think, but that isn't useful
208                           ; ebx = -1024
209 00000059 29DA             sub  edx, ebx   ; edx = 1024 + 0..9 (leading digit).  +0 in the Fib(10**9) case
210                       
211 0000005B B004             mov   al, 4                 ; SYS_write
212 0000005D 8D58FD           lea  ebx, [eax-4 + 1]       ; fd=1
213                           ;mov  ecx, edi               ; buf
214 00000060 8D4F01           lea  ecx, [edi+1]           ; Hard-code for Fib(10**9), which has one leading zero in the highest limb.
215                       ;    shr  edx, 1 ;    for use with edx=2048
216                       ;    mov  edx, 100
217                       ;    mov byte  [ecx+edx-1], 0xa;'\n'  ; count+=1 for newline
218 00000063 CD80             int  0x80                   ; write(1, buf+1, 1024)
219                       
220 00000065 89D8             mov  eax, ebx ; SYS_exit=1
221 00000067 CD80             int  0x80     ; exit(ebx=1)
222                       
  # next byte is 0x69, so size = 0x69 = 105 bytes

Probablemente haya espacio para jugar más bytes, pero ya he pasado al menos 12 horas en esto durante 2 días. No quiero sacrificar la velocidad, a pesar de que es mucho más que lo suficientemente rápido y hay espacio para hacerlo más pequeño en formas que cuestan velocidad . Parte de mi razón para publicar es mostrar qué tan rápido puedo hacer una versión asm de fuerza bruta. Si alguien quiere realmente un tamaño mínimo pero tal vez 10 veces más lento (por ejemplo, 1 dígito por byte), siéntase libre de copiar esto como punto de partida.

El ejecutable resultante (desde yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) es 340B (despojado):

size fibonacci-1G
 text    data     bss     dec     hex filename
  105       0       0     105      69 fibonacci-1G

Actuación

El adcbucle interno es de 10 uops de dominio fusionado en Skylake (+1 uop de sincronización de pila cada ~ 128 bytes), por lo que puede emitirse a uno por cada ~ 2.5 ciclos en Skylake con un rendimiento óptimo de front-end (ignorando los uops de sincronización de pila) . La latencia de la ruta crítica es de 2 ciclos, para la cadena de dependencia transportada en bucle de la siguiente iteración adc-> cmp-> adc, por lo que el cuello de botella debe ser el límite de emisión inicial de ~ 2.5 ciclos por iteración.

adc eax, [edi + edx]son 2 uops de dominio sin fusionar para los puertos de ejecución: carga + ALU. Se micro fusiona en los decodificadores (1 uop de dominio fusionado), pero se deslamina en la etapa de emisión a 2 uops de dominio fusionado, debido al modo de direccionamiento indexado, incluso en Haswell / Skylake . Pensé que permanecería micro fusionada, como lo add eax, [edi + edx]hace, pero tal vez mantener los modos de direccionamiento indexados micro fusionados no funciona para los uops que ya tienen 3 entradas (banderas, memoria y destino). Cuando lo escribí, pensaba que no tendría un rendimiento negativo, pero estaba equivocado. Esta forma de manejar el truncamiento ralentiza el ciclo interno cada vez, ya edxsea ​​0 o 4.

Sería más rápido manejar el desplazamiento de lectura-escritura para el dst al compensar ediy usar edxpara ajustar la tienda. Entonces adc eax, [edi]/ ... / mov [edi+edx], eax/ en lea edi, [edi+4]lugar de stosd. Haswell y más adelante pueden mantener una tienda indexada micro fusionada. (Sandybridge / IvB también lo deslaminaría).

En Intel Haswell y versiones anteriores, adcy cmovcson 2 uops cada uno, con latencia 2c . ( adc eax, [edi+edx]todavía no está laminado en Haswell y emite como 3 uops de dominio fusionado). Broadwell y versiones posteriores permiten uops de 3 entradas para más que solo FMA (Haswell), haciendo adcy cmovc(y un par de cosas más) instrucciones de un solo uop, como si hubieran estado en AMD durante mucho tiempo. (Esta es una de las razones por las que AMD ha funcionado bien en los puntos de referencia GMP de precisión extendida durante mucho tiempo). De todos modos, el bucle interno de Haswell debe ser de 12 uops (ocasionalmente +1 stack-sync uop), con un cuello de botella frontal de ~ 3c por Es el mejor de los casos, ignorando la sincronización de la pila.

El uso popsin un equilibrio pushdentro de un bucle significa que el bucle no puede ejecutarse desde el LSD (detector de flujo de bucle) , y debe volver a leerse desde la caché uop al IDQ cada vez. En todo caso, es algo bueno en Skylake, ya que un ciclo de 9 u 10 uop ​​no se emite de manera óptima a 4 uops en cada ciclo . Probablemente esto sea parte de por qué reemplazar tanto lodsdcon popayudado. (El LSD no puede bloquear los uops porque eso no dejaría espacio para insertar un uop de sincronización de pila .) (Por cierto, una actualización de microcódigo deshabilita el LSD por completo en Skylake y Skylake-X para corregir una errata. Medí el anterior antes de obtener esa actualización.)

Lo perfilé en Haswell y descubrí que se ejecuta en 381.31 mil millones de ciclos de reloj (independientemente de la frecuencia de la CPU, ya que solo usa caché L1D, no memoria). El rendimiento de problemas de front-end fue de 3.72 uops de dominio fusionado por reloj, frente a 3.70 para Skylake. (Pero, por supuesto, las instrucciones por ciclo se redujeron a 2.42 desde 2.87, porque adcy cmovson 2 uops en Haswell).

pushreemplazarlo stosdprobablemente no ayudaría tanto, ya adc [esp + edx]que desencadenaría una uop de sincronización de pila cada vez. Y costaría un byte por stdlo que lodsdva en la otra dirección. ( mov [edi], eax/ lea edi, [edi+4]reemplazar stosdes una victoria, pasando de 32,909Mcycles por 100M iters a 31,954Mcycles por 100M iters. Parece que stosddecodifica como 3 uops, con la dirección de la tienda / datos de la tienda uops no micro-fusionados, entonces push+ stack-sync Uops aún podría ser más rápido que stosd)

El rendimiento real de ~ 322.47 mil millones de ciclos para iteraciones 1G de 114 extremidades equivale a 2.824 ciclos por iteración del bucle interno , para la versión rápida 105B en Skylake. (Ver ocperf.pysalida a continuación). Eso es más lento de lo que predije del análisis estático, pero estaba ignorando la sobrecarga del bucle externo y cualquier uops de sincronización de pila.

Los contadores de rendimiento branchesy branch-missesmuestran que el bucle interno predice erróneamente una vez por bucle externo (en la última iteración, cuando no se toma). Eso también representa parte del tiempo extra.

Podría guardar el tamaño del código haciendo que el bucle más interno tenga una latencia de 3 ciclos para la ruta crítica, usando mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) en lugar de lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B ) El cmov/ stosdestá fuera de la ruta crítica. (El increment-edi uop de stosdpuede ejecutarse por separado de la tienda, por lo que cada iteración se bifurca en una cadena de dependencia corta). Solía ​​guardar otro 1B cambiando la instrucción de inicio ebp de lea ebp, [ecx-1]a mov ebp,eax, pero descubrí que tener el errorebpNo cambió el resultado. Esto permitiría que una extremidad sea exactamente == 1000000000 en lugar de envolver y producir un acarreo, pero este error se propaga más lentamente de lo que crece Fib (), por lo que esto no cambia los primeros dígitos de 1k del resultado final. Además, creo que ese error puede corregirse solo cuando solo estamos agregando, ya que hay espacio en una extremidad para sostenerlo sin desbordamiento. Incluso 1G + 1G no desborda un número entero de 32 bits, por lo que eventualmente se filtrará hacia arriba o se truncará.

La versión de latencia 3c es 1 uop adicional, por lo que el front-end puede emitirlo en uno por 2.75c ciclos en Skylake, solo un poco más rápido que el back-end puede ejecutarlo. (En Haswell, será un total de 13 uops ya que todavía usa adcy cmov, y un cuello de botella en el front-end a 3.25c por iter).

En la práctica, funciona un factor de 1.18 más lento en Skylake (3.34 ciclos por extremidad), en lugar de 3 / 2.5 = 1.2 que predije para reemplazar el cuello de botella frontal con el cuello de botella de latencia simplemente mirando el bucle interno sin sincronización de pila uops Dado que los Uops de sincronización de pila solo dañan la versión rápida (cuello de botella en el front-end en lugar de latencia), no se necesita mucho para explicarlo. por ejemplo, 3 / 2.54 = 1.18.

Otro factor es que la versión de latencia 3c puede detectar la predicción errónea al abandonar el bucle interno mientras la ruta crítica aún se está ejecutando (porque el front-end puede adelantarse al back-end, permitiendo que la ejecución fuera de orden ejecute el bucle- counter uops), por lo que la penalización efectiva del error de predicción es menor. La pérdida de esos ciclos de front-end permite que el back-end se ponga al día.

Si no fuera por eso, tal vez podríamos acelerar la cmcversión 3c mediante el uso de una bifurcación en el bucle externo en lugar del manejo sin bifurcación de las compensaciones carry_out -> edx y esp. La predicción de bifurcación + la ejecución especulativa para una dependencia de control en lugar de una dependencia de datos podría permitir que la siguiente iteración comience a ejecutar el adcbucle mientras los uops del bucle interno anterior todavía están en vuelo. En la versión sin ramificación, las direcciones de carga en el bucle interno tienen una dependencia de datos en CF desde el último adcde la última rama.

Los cuellos de botella de la versión de bucle interno de latencia 2c en el extremo frontal, por lo que el extremo posterior prácticamente se mantiene. Si el código del bucle externo era de alta latencia, el front-end podría avanzar emitiendo uops desde la próxima iteración del bucle interno. (Pero en este caso, el material del bucle externo tiene un montón de ILP y nada de alta latencia, por lo que el back-end no tiene mucho que hacer cuando comienza a masticar uops en el programador fuera de servicio como sus entradas se vuelven listas).

### Output from a profiled run
$ asm-link -m32 fibonacci-1G.asm && (size fibonacci-1G; echo disas fibonacci-1G) && ocperf.py stat -etask-clock,context-switches:u,cpu-migrations:u,page-faults:u,cycles,instructions,uops_issued.any,uops_executed.thread,uops_executed.stall_cycles -r4  ./fibonacci-1G
+ yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm
+ ld -melf_i386 -o fibonacci-1G fibonacci-1G.o
   text    data     bss     dec     hex filename
    106       0       0     106      6a fibonacci-1G
disas fibonacci-1G
perf stat -etask-clock,context-switches:u,cpu-migrations:u,page-faults:u,cycles,instructions,cpu/event=0xe,umask=0x1,name=uops_issued_any/,cpu/event=0xb1,umask=0x1,name=uops_executed_thread/,cpu/event=0xb1,umask=0x1,inv=1,cmask=1,name=uops_executed_stall_cycles/ -r4 ./fibonacci-1G
79523178745546834678293851961971481892555421852343989134530399373432466861825193700509996261365567793324820357232224512262917144562756482594995306121113012554998796395160534597890187005674399468448430345998024199240437534019501148301072342650378414269803983873607842842319964573407827842007677609077777031831857446565362535115028517159633510239906992325954713226703655064824359665868860486271597169163514487885274274355081139091679639073803982428480339801102763705442642850327443647811984518254621305295296333398134831057713701281118511282471363114142083189838025269079177870948022177508596851163638833748474280367371478820799566888075091583722494514375193201625820020005307983098872612570282019075093705542329311070849768547158335856239104506794491200115647629256491445095319046849844170025120865040207790125013561778741996050855583171909053951344689194433130268248133632341904943755992625530254665288381226394336004838495350706477119867692795685487968552076848977417717843758594964253843558791057997424878788358402439890396,�X\�;3�I;ro~.�'��R!q��%��X'B ��      8w��▒Ǫ�
 ... repeated 3 more times, for the 3 more runs we're averaging over
  Note the trailing garbage after the trailing digits.

 Performance counter stats for './fibonacci-1G' (4 runs):

      73438.538349      task-clock:u (msec)       #    1.000 CPUs utilized            ( +-  0.05% )
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
                 2      page-faults:u             #    0.000 K/sec                    ( +- 11.55% )
   322,467,902,120      cycles:u                  #    4.391 GHz                      ( +-  0.05% )
   924,000,029,608      instructions:u            #    2.87  insn per cycle           ( +-  0.00% )
 1,191,553,612,474      uops_issued_any:u         # 16225.181 M/sec                   ( +-  0.00% )
 1,173,953,974,712      uops_executed_thread:u    # 15985.530 M/sec                   ( +-  0.00% )
     6,011,337,533      uops_executed_stall_cycles:u #   81.855 M/sec                    ( +-  1.27% )

      73.436831004 seconds time elapsed                                          ( +-  0.05% )

( +- x %)es la desviación estándar en las 4 carreras para ese recuento. Es interesante que ejecute un número tan redondo de instrucciones. Que 924 mil millones no es una coincidencia. Supongo que el bucle externo ejecuta un total de 924 instrucciones.

uops_issuedes un recuento de dominio fusionado (relevante para el ancho de banda del problema de front-end), mientras que uops_executedes un recuento de dominio no fusionado (número de uops enviados a puertos de ejecución). Micro-fusion empaqueta 2 uops de dominio no fusionado en un uop de dominio fusionado, pero la eliminación de movimiento significa que algunos uops de dominio fusionado no necesitan ningún puerto de ejecución. Consulte la pregunta vinculada para obtener más información sobre el conteo de uops y el dominio fusionado frente al no fusionado. (Consulte también las tablas de instrucciones de Agner Fog y la guía de uarch , y otros enlaces útiles en el wiki de etiquetas SO x86 ).

De otra ejecución que mide cosas diferentes: los errores de caché L1D son totalmente insignificantes, como se esperaba para leer / escribir los mismos dos buffers 456B. La rama del bucle interno predice erróneamente una vez por bucle externo (cuando no se toma para abandonar el bucle). (El tiempo total es mayor porque la computadora no estaba totalmente inactiva. Probablemente el otro núcleo lógico estuvo activo parte del tiempo, y se dedicó más tiempo a las interrupciones (ya que la frecuencia medida por el espacio del usuario estaba más abajo de 4.400 GHz). O múltiples núcleos estuvieron activos la mayor parte del tiempo, bajando el turbo máximo. No rastreé cpu_clk_unhalted.one_thread_activepara ver si la competencia HT era un problema).

     ### Another run of the same 105/106B "main" version to check other perf counters
      74510.119941      task-clock:u (msec)       #    1.000 CPUs utilized          
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
                 2      page-faults:u             #    0.000 K/sec                  
   324,455,912,026      cycles:u                  #    4.355 GHz                    
   924,000,036,632      instructions:u            #    2.85  insn per cycle         
   228,005,015,542      L1-dcache-loads:u         # 3069.535 M/sec
           277,081      L1-dcache-load-misses:u   #    0.00% of all L1-dcache hits
                 0      ld_blocks_partial_address_alias:u #    0.000 K/sec                  
   115,000,030,234      branches:u                # 1543.415 M/sec                  
     1,000,017,804      branch-misses:u           #    0.87% of all branches        

Es posible que mi código se ejecute en menos ciclos en Ryzen, que puede emitir 5 uops por ciclo (o 6 cuando algunos de ellos son instrucciones de 2 uop, como AVX 256b en Ryzen). No estoy seguro de qué haría su front-end stosd, que es 3 uops en Ryzen (igual que Intel). Creo que las otras instrucciones en el bucle interno son la misma latencia que Skylake y todas de un solo uop. (Incluyendo adc eax, [edi+edx], lo cual es una ventaja sobre Skylake).

Esto probablemente podría ser significativamente más pequeño, pero quizás 9 veces más lento si almacenara los números como 1 dígito decimal por byte . Generar llevar a cabo con cmpy ajustar con cmovfuncionaría igual, pero hacer 1/9 del trabajo. También funcionarían 2 dígitos decimales por byte (base-100, no BCD de 4 bits con un lentoDAA ), y div r8/ add ax, 0x3030convierte un byte 0-99 en dos dígitos ASCII en orden de impresión. Pero 1 dígito por byte no necesita divnada, solo se repite y se agrega 0x30. Si guardo los bytes en orden de impresión, eso haría que el segundo ciclo sea realmente simple.

El uso de 18 o 19 dígitos decimales por entero de 64 bits (en modo de 64 bits) haría que se ejecute aproximadamente el doble de rápido, pero con un tamaño de código significativo para todos los prefijos REX y para las constantes de 64 bits. Las extremidades de 32 bits en modo de 64 bits evitan el uso en pop eaxlugar de lodsd. Todavía podría evitar los prefijos REX al usar espcomo un registro de scratch sin puntero (intercambiando el uso de esiy esp), en lugar de usar r8dcomo un octavo registro.

Si realiza una versión de función invocable, la conversión a 64 bits y el uso r8dpueden ser más baratos que guardar / restaurar rsp. 64 bits tampoco puede usar la dec r32codificación de un byte (ya que es un prefijo REX). Pero principalmente terminé usando dec bl2 bytes. (Porque tengo una constante en los bytes superiores de ebx, y solo la uso fuera de los bucles internos, lo que funciona porque el byte bajo de la constante es 0x00).

Versión de alto rendimiento

Para obtener el máximo rendimiento (no el código de golf), desearía desenrollar el bucle interno para que se ejecute a lo sumo 22 iteraciones, que es un patrón suficientemente corto tomado / no tomado para que los predictores de ramificación funcionen bien. En mis experimentos, mov cl, 22antes de un .inner: dec cl/jnz .innerciclo tenía muy pocas predicciones erróneas (como 0.05%, mucho menos de una por ciclo completo del ciclo interno), pero mov cl,23predecía incorrectamente de 0.35 a 0.6 veces por ciclo interno. 46es particularmente malo, prediciendo erróneamente ~ 1.28 veces por bucle interno (128M veces para iteraciones de bucle externo de 100M). 114pronosticó mal exactamente una vez por bucle interno, igual que encontré como parte del bucle Fibonacci.

Me dio curiosidad y lo intenté, desenrollando el bucle interno por 6 con un %rep 6(porque eso divide 114 de manera uniforme). Eso eliminó principalmente las fallas en las ramas. Lo hice edxnegativo y lo usé como compensación para las movtiendas, por lo que adc eax,[edi]podría quedar micro-fusionado. (Y así podría evitar stosd). Saqué la leaactualización edidel %repbloque, por lo que solo hace una actualización de puntero por cada 6 tiendas.

También me deshice de todas las cosas de registro parcial en el bucle externo, aunque no creo que haya sido significativo. Puede haber ayudado un poco tener CF al final del bucle externo que no depende del ADC final, por lo que algunos de los uops del bucle interno pueden comenzar. El código del bucle externo probablemente podría optimizarse un poco más, ya que neg edxfue lo último que hice, después de reemplazarlo xchgcon solo 2 movinstrucciones (ya que todavía tenía 1), y reorganizar las cadenas dep junto con soltar los 8 bits registrar cosas

Esta es la fuente NASM de solo el bucle Fibonacci. Es un reemplazo directo para esa sección de la versión original.

  ;;;; Main loop, optimized for performance, not code-size
%assign unrollfac 6
    mov    bl, limbcount/unrollfac  ; and at the end of the outer loop
    align 32
.fibonacci:
limbcount equ 114             ; 112 = 1006 decimal digits / 9 digits per limb.  Not enough for 1000 correct digits, but 114 is.
                              ; 113 would be enough, but we depend on limbcount being even to avoid a sub
;    align 8
.digits_add:

%assign i 0
%rep unrollfac
    ;lodsd                       ; Skylake: 2 uops.  Or  pop rax  with rsp instead of rsi
;    mov    eax, [esp]
;    lea    esp, [esp+4]   ; adjust ESP without affecting CF.  Alternative, load relative to edi and negate an offset?  Or add esp,4 after adc before cmp
    pop    eax
    adc    eax, [edi+i*4]    ; read from a potentially-offset location (but still store to the front)
 ;; jz .out   ;; Nope, a zero digit in the result doesn't mean the end!  (Although it might in base 10**9 for this problem)

    lea    esi, [eax - 1000000000]
    cmp    ebp, eax                ; sets CF when (base-1) < eax.  i.e. when eax>=base
    cmovc  eax, esi                ; eax %= base, keeping it in the [0..base) range
%if 0
    stosd
%else
  mov    [edi+i*4+edx], eax
%endif
%assign i i+1
%endrep
  lea   edi, [edi+4*unrollfac]

    dec    bl                      ; preserves CF.  The resulting partial-flag merge on ADC would be slow on pre-SnB CPUs
    jnz .digits_add
    ; bl=0, ebx=-1024
    ; esi has its high bit set opposite to CF
.end_innerloop:
    ;; after a non-zero carry-out (CF=1): right-shift both buffers by 1 limb, over the course of the next two iterations
    ;; next iteration with r8 = 1 and rsi+=4:  read offset from both, write normal.  ends with CF=0
    ;; following iter with r8 = 1 and rsi+=0:  read offset from dest, write normal.  ends with CF=0
    ;; following iter with r8 = 0 and rsi+=0:  i.e. back to normal, until next carry-out (possible a few iters later)

    ;; rdi = bufX + 4*limbcount
    ;; rsi = bufY + 4*limbcount + 4*carry_last_time

;    setc   [rdi]
;    mov    dl, dh               ; edx=0.  2c latency on SKL, but DH has been ready for a long time
;    adc    edx,edx    ; edx = CF.  1B shorter than setc dl, but requires edx=0 to start
    setc   al
    movzx  edx, al
    mov    [edi], edx ; store the carry-out into an extra limb beyond limbcount
    shl    edx, 2
    ;; Branching to handle the truncation would break the data-dependency (of pointers) on carry-out from this iteration
    ;;  and let the next iteration start, but we bottleneck on the front-end (9 uops)
    ;;  not the loop-carried dependency of the inner loop (2 cycles for adc->cmp -> flag input of adc next iter)
    ;; Since the pattern isn't perfectly regular, branch mispredicts would hurt us

    ; keep -1024 in ebx.  Using bl for the limb counter leaves bl zero here, so it's back to -1024 (or -2048 or whatever)
    mov    eax, esp
    and    esp, 4               ; only works if limbcount is even, otherwise we'd need to subtract limbcount first.

    and    edi, ebx  ; -1024    ; revert to start of buffer, regardless of offset
    add    edi, edx             ; read offset in next iter's src
    ;; maybe   or edi,edx / and edi, 4 | -1024?  Still 2 uops for the same work
    ;;  setc dil?

    ;; after adjusting src, so this only affects read-offset in the dst, not src.
    or     edx, esp             ; also set r8d if we had a source offset last time, to handle the 2nd buffer
    mov    esp, edi

;    xchg   edi, esp   ; Fibonacci: dst and src swap
    and    eax, ebx  ; -1024

    ;; mov    edi, eax
    ;; add    edi, edx
    lea    edi, [eax+edx]
    neg    edx            ; negated read-write offset used with store instead of load, so adc can micro-fuse

    mov    bl, limbcount/unrollfac
    ;; Last instruction must leave CF clear for next iter
;    loop .fibonacci  ; Maybe 0.01% slower than dec/jnz overall
;    dec ecx
    sub ecx, 1                  ; clear any flag dependencies.  No faster than dec, at least when CF doesn't depend on edx
    jnz .fibonacci

Actuación:

 Performance counter stats for './fibonacci-1G-performance' (3 runs):

      62280.632258      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.07% )
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
                 3      page-faults:u             #    0.000 K/sec                    ( +- 12.50% )
   273,146,159,432      cycles                    #    4.386 GHz                      ( +-  0.07% )
   757,088,570,818      instructions              #    2.77  insn per cycle           ( +-  0.00% )
   740,135,435,806      uops_issued_any           # 11883.878 M/sec                   ( +-  0.00% )
   966,140,990,513      uops_executed_thread      # 15512.704 M/sec                   ( +-  0.00% )
    75,953,944,528      resource_stalls_any       # 1219.544 M/sec                    ( +-  0.23% )
       741,572,966      idq_uops_not_delivered_core #   11.907 M/sec                    ( +- 54.22% )

      62.279833889 seconds time elapsed                                          ( +-  0.07% )

Eso es para el mismo Fib (1G), produciendo la misma salida en 62.3 segundos en lugar de 73 segundos. (273.146G ciclos, frente a 322.467G. Dado que todo golpea en la memoria caché L1, los ciclos de reloj de núcleo son realmente todo lo que necesitamos ver).

Tenga en cuenta el uops_issuedrecuento total mucho más bajo , muy por debajo del uops_executedrecuento. Eso significa que muchos de ellos estaban micro fusionados: 1 uop en el dominio fusionado (problema / ROB), pero 2 uops en el dominio no fusionado (planificador / unidades de ejecución)). Y esos pocos fueron eliminados en la etapa de emisión / cambio de nombre (como la movcopia del registro o la xorpuesta a cero, que deben emitirse pero no necesitan una unidad de ejecución). Uops eliminados desequilibrarían el conteo de la otra manera.

branch-missesse redujo a ~ 400k, desde 1G, por lo que desenrollado funcionó. resource_stalls.anyahora es significativo, lo que significa que el front-end ya no es el cuello de botella: en cambio, el back-end se está quedando atrás y limita el front-end. idq_uops_not_delivered.coresolo cuenta los ciclos donde el front-end no entregó uops, pero el back-end no se detuvo. Eso es bueno y bajo, lo que indica pocos cuellos de botella en el front-end.

Dato curioso: la versión de Python pasa más de la mitad de su tiempo dividiendo por 10 en lugar de sumar. (Reemplazar el a/=10con a>>=64acelera en más de un factor de 2, pero cambia el resultado porque el truncamiento binario = truncamiento decimal).

Por supuesto, mi versión asm está optimizada específicamente para este tamaño de problema, con el recuento de iteraciones de bucle codificado. Incluso cambiar un número de precisión arbitraria lo copiará, pero mi versión solo puede leer desde un desplazamiento durante las próximas dos iteraciones para omitir incluso eso.

Perfilé la versión de python (python2.7 de 64 bits en Arch Linux):

ocperf.py stat -etask-clock,context-switches:u,cpu-migrations:u,page-faults:u,cycles,instructions,uops_issued.any,uops_executed.thread,arith.divider_active,branches,branch-misses,L1-dcache-loads,L1-dcache-load-misses python2.7 ./fibonacci-1G.anders-brute-force.py
795231787455468346782938519619714818925554218523439891345303993734324668618251937005099962613655677933248203572322245122629171445627564825949953061211130125549987963951605345978901870056743994684484303459980241992404375340195011483010723426503784142698039838736078428423199645734078278420076776090777770318318574465653625351150285171596335102399069923259547132267036550648243596658688604862715971691635144878852742743550811390916796390738039824284803398011027637054426428503274436478119845182546213052952963333981348310577137012811185112824713631141420831898380252690791778709480221775085968511636388337484742803673714788207995668880750915837224945143751932016258200200053079830988726125702820190750937055423293110708497685471583358562391045067944912001156476292564914450953190468498441700251208650402077901250135617787419960508555831719090539513446891944331302682481336323419049437559926255302546652883812263943360048384953507064771198676927956854879685520768489774177178437585949642538435587910579974100118580

 Performance counter stats for 'python2.7 ./fibonacci-1G.anders-brute-force.py':

     755380.697069      task-clock:u (msec)       #    1.000 CPUs utilized          
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
               793      page-faults:u             #    0.001 K/sec                  
 3,314,554,673,632      cycles:u                  #    4.388 GHz                      (55.56%)
 4,850,161,993,949      instructions:u            #    1.46  insn per cycle           (66.67%)
 6,741,894,323,711      uops_issued_any:u         # 8925.161 M/sec                    (66.67%)
 7,052,005,073,018      uops_executed_thread:u    # 9335.697 M/sec                    (66.67%)
   425,094,740,110      arith_divider_active:u    #  562.756 M/sec                    (66.67%)
   807,102,521,665      branches:u                # 1068.471 M/sec                    (66.67%)
     4,460,765,466      branch-misses:u           #    0.55% of all branches          (44.44%)
 1,317,454,116,902      L1-dcache-loads:u         # 1744.093 M/sec                    (44.44%)
        36,822,513      L1-dcache-load-misses:u   #    0.00% of all L1-dcache hits    (44.44%)

     755.355560032 seconds time elapsed

Los números en (parens) son la cantidad de tiempo que se muestreó el contador de rendimiento. Al mirar más contadores de los que admite el HW, el rendimiento gira entre diferentes contadores y extrapolatos. Eso está totalmente bien para una larga ejecución de la misma tarea.

Si ejecuté perfdespués de configurar sysctl kernel.perf_event_paranoid = 0(o ejecutar perfcomo root), mediría 4.400GHz. cycles:uno cuenta el tiempo dedicado a las interrupciones (o llamadas del sistema), solo los ciclos de espacio de usuario. Mi escritorio estaba casi totalmente inactivo, pero esto es típico.

Haskell, 83 61 bytes

p(a,b)(c,d)=(a*d+b*c-a*c,a*c+b*d)
t g=g.g.g
t(t$t=<<t.p)(1,1)

Salidas ( F _1000000000 , F _1000000001 ). En mi computadora portátil, imprime correctamente el paréntesis izquierdo y los primeros 1000 dígitos en 133 segundos, usando 1.35 GiB de memoria.

Cómo funciona

La recurrencia de Fibonacci se puede resolver utilizando la exponenciación de la matriz:

[ F _{i - 1} , F _i ; F _i , F _{i + 1} ] = [0, 1; 1, 1] ⁱ ,

de donde derivamos estas identidades:

[ F _{i + j - 1} , F _{i + j} ; F _{i + j} , F _{i + j + 1} ] = [ F _{i - 1} , F _i ; F _i , F _{i + 1} ] ⋅ [ F _{j - 1} , F _j ; _{+ 1} F _{j + 1} - F _{i - 1} F _{j - 1} = FF _j , F _{j + 1} ],
F _{i + j} = F _{i i + 1} F _{j + 1} - ( F _{i + 1} - F _i ) ( F _{j + 1} - F _j ),
F _{i + j + 1} = F _i F _j + F _{i + 1} F _{j + 1} .

La pfunción calcula ( F _{i + j} , F _{i + j + 1} ) dada ( F _i , F _{i + 1} ) y ( F _j , F _{j + 1} ). Escribiendo f npara ( F _i , F _{i + 1} ), tenemos p (f i) (f j)= f (i + j).

Entonces,

(t=<<t.p) (f i)
= t ((t.p) (f i)) (f i)
= t (p (f i).p (f i).p (f i)) (f i)
= (p (f i).p (f i).p (f i).p (f i).p (f i).p (f i).p (f i).p (f i).p (f i)) (f i)
= f (10 * i),

(t$t=<<t.p) (f i)
= ((t=<<t.p).(t=<<t.p).(t=<<t.p)) (f i)
= f (10^3 * i),

t(t$t=<<t.p) (f i)
= ((t$t=<<t.p).(t$t=<<t.p).(t$t=<<t.p)) (f i)
= f (10^9 * i),

y nos conectamos f 1= (1,1).

Mathematica, 15 34 bytes

Fibonacci en sí toma ~ 6s en mi computadora. Y 95 (+/- 5) s para que frontend lo muestre.

Fibonacci@1*^9&

Los primeros 1000 dígitos (34 bytes): ⌊Fibonacci@1*^9/1*^208986640⌋&

Más largo pero más rápido ToString@Fibonacci@1*^9~StringTake~1000&:

Python 2, 70 bytes

a,b=0,1
i=1e9
while i:
 a,b=b,a+b;i-=1
 if a>>3360:a/=10;b/=10
print a

Esto se ejecutó en 18 minutos y 31 segundos en mi computadora portátil, produciendo los 1000 dígitos correctos seguidos de 74100118580(los siguientes dígitos correctos son 74248787892).

Haskell , 78 bytes

(a%b)n|n<1=b|odd n=b%(a+b)$n-1|r<-2*a*b-a*a=r%(a*a+b*b)$div n 2
1%0$2143923439

Pruébalo en línea!

Tomó 48 segundos en TIO. Misma fórmula recursiva que mi respuesta de Python , pero sin truncar.

La constante 2143923439es 10**9-1, invertida en binario, y con un 1 extra al final. Iterar a través de sus dígitos binarios en reversa simula iterar a través de los dígitos binarios de 10**9-1. Parece más corto codificar esto que calcularlo.

Haskell , 202 184 174 173 170 168 164 162 bytes

(a,b)!(c,d)=a*c+b*d
l x=((34,55)!x,(55,89)!x)
f(a,b)|x<-l(a,b)=(x!l(b-a,a),x!x)
r=l.f
k=f.f.f
j=f.r.r.r.r
main=print$take 1000$show$fst$f$r$k$k$r$k$j$f$r$j$r(0,1)

Pruébalo en línea!

Explicación

Esto utiliza una forma bastante rápida para calcular los números de fibonacci. La función ltoma dos Fibonacci números y calcula los números de Fibonacci 10 más tarde, mientras ftoma la n º y n + 1 th números de Fibonacci y calcula el 2n + 20 ° y 2n + 21 números º de Fibonacci. Los encadené de manera bastante casual para obtener mil millones y obtener los primeros 1000 dígitos.

Haskell, 81 bytes

f n|n<3=1|even n=fk*(2*f(k+1)-fk)|1>0=f(k+1)^2+fk^2 where k=n`div`2;fk=f k
f$10^9

Explicación

f ncalcula recursivamente el nnúmero de fibonacci th utilizando la recurrencia de la respuesta de xnor con eliminación de subexpresión común. A diferencia de las otras soluciones que se han publicado, que usan multiplicaciones de O (log (n)), tenemos una recursión de profundidad O (log (n)) con un factor de ramificación de 2, para una complejidad de multiplicaciones de O (n).

¡Sin embargo, no todo está perdido! Debido a que casi todas las llamadas estarán cerca de la parte inferior del árbol de recursión, podemos usar aritmética nativa rápida siempre que sea posible y evitar mucha manipulación de bignums enormes. Escupe una respuesta en un par de minutos en mi caja.

T-SQL, 422 414 453 bytes (verificado, ahora compitiendo)

EDIT 2 : ¡Cambió a , ganó algunos bytes pero aumentó la velocidad lo suficiente como para completar hasta mil millones! Completado en 45 horas y 29 minutos , verifica la cadena dada y muestra 8 caracteres adicionales (que pueden ser correctos o no debido a errores de redondeo).INT BIGINT DECIMAL(37,0)

T-SQL no tiene soporte nativo de "gran número", así que tuve que rodar mi propio sumador de gran número basado en texto usando cadenas de 1008 caracteres:

DECLARE @a char(1008)=REPLICATE('0',1008),@ char(1008)=REPLICATE('0',1007)+'1',@c varchar(max),@x bigint=1,@y int,@t varchar(37),@f int=0o:SELECT @x+=1,@c='',@y=1i:SELECT @t=CONVERT(DECIMAL(37,0),RIGHT(@a,36))+CONVERT(DECIMAL(37,0),RIGHT(@,36))+@f,@a=RIGHT(@a,36)+@a,@=RIGHT(@,36)+@,@c=RIGHT(REPLICATE('0',36)+@t,36)+@c,@y+=1IF LEN(@t)>36SET @f=1 ELSE SET @f=0IF @y<29GOTO i
IF @f=1SELECT @a='0'+@,@='1'+@c ELSE SELECT @a=@,@=@c
If @x<1e9 GOTO o
PRINT @

Aquí está la versión formateada con comentarios:

DECLARE @a char(1008)=REPLICATE('0',1008)       --fib(a), have to manually fill
       ,@ char(1008)=REPLICATE('0',1007)+'1'    --fib(b), shortened variable
       ,@c varchar(max), @x bigint=1, @y int, @t varchar(37), @f int=0
o:  --outer loop
    SELECT @x+=1, @c='', @y=1
    i:  --inner loop
        SELECT @t=CONVERT(DECIMAL(37,0),RIGHT(@a,36))      --adds last chunk of string
                 +CONVERT(DECIMAL(37,0),RIGHT(@,36)) + @f
              ,@a=RIGHT(@a,36)+@a                          --"rotates" the strings
              ,@=RIGHT(@,36)+@
              ,@c=RIGHT(REPLICATE('0',36)+@t,36)+@c        --combines result
              ,@y+=1
        IF LEN(@t)>36 SET @f=1 ELSE SET @f=0               --flag for carrying the 1
     IF @y<29 GOTO i                                       --28 * 36 digits = 1008 places
     IF @f=1 SELECT @a='0'+@, @='1'+@c                     --manually carries the 1
        ELSE SELECT @a=@, @=@c
If @x<1e9 GOTO o
PRINT @

Básicamente estoy manipulando manualmente cadenas de relleno de cero de 1008 caracteres que representan mis dos variables de Fibonacci, @ay @.

Los agrego 8 18 36 dígitos a la vez, quitando los últimos 36 dígitos, convirtiéndolos en un tipo numérico manejable ( DECIMAL(37,0)), agregándolos y luego rompiéndolos en otra cadena larga @c. Luego "giro" @ay @moviendo los últimos 36 dígitos al frente, y repitiendo el proceso. 28 rotaciones * 36 dígitos cubre todos los 1008. Tengo que "cargar el" manualmente.

Una vez que nuestro número comienza a exceder la longitud de mi cadena, "cambio a la izquierda" y comenzamos a perder algo de precisión, pero el error está dentro de mis caracteres adicionales.

Intenté usar una tabla SQL llena de INTs y BIGINTs, con lógica similar, y fue dramáticamente más lenta. Extraño.

PARI / GP, 45 bytes

\p1100
s=sqrt(5)
((1+s)/2)^1e9/s/1e208986640

De alguna manera \p1000no es suficiente. Esto no funciona con sistemas de 32 bits. La división final es evitar el punto decimal en notación científica.

Pari / GP , 15 + 5 = 20 bytes

fibonacci(10^9)

Ejecute con la opción de línea de comando -s1gpara asignar 1 Gbytes de memoria.

Ruby, 63 bytes

hombre, soy malo jugando al golf rubí; pero la clase BigInt hace maravillas para este tipo de cosas. Usamos el mismo algoritmo que Anders Kaseorg.

require 'matrix'
m=Matrix
puts m[[1,1],[1,0]]**10**9*m[[1],[1]]