Houve um bilhão de iterações de desafios de Fibonacci neste site, então vamos apimentar as coisas com um desafio de Fibonacci de um bilhão de iterações!

Seu desafio é gerar os primeiros 1000 dígitos decimais do número de 1.000.000.000.000 de Fibonacci com o menor programa possível. Opcionalmente, isso pode ser seguido por qualquer saída adicional de sua escolha, incluindo mas não se limitando ao restante dos dígitos.

Eu estou usando a convenção de que fib 0 = 0, fib 1 = 1.

Seu programa deve ser rápido o suficiente para você executá-lo e verificar sua correção. Para esse fim, aqui estão os primeiros 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:]

Experimente online!

-10 bytes removendo o termo praticamente 0, graças a Jeff Dege
-1 byte (1000 -> 1e3 graças a Zacharý)
-2 bytes removendo a variável desnecessária graças a Erik the Outgolfer
-2 bytes movendo-se para Python 2 graças a Zacharý
-3 bytes por 11'ing os -11agradecimentos a ThePirateBay -3 bytes trocando strpor backticks graças a notjagan

agora supera a solução haskell não publicada do 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

Experimente online!

Sem bibliotecas, apenas aritmética inteira. É executado quase instantaneamente.

O núcleo é a identidade de dividir e conquistar:

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

Isso nos permite atualizar (a,b) = (f(n),f(n+1))para o dobro n -> 2*n. Como queremos obter n=10**9, são necessárias apenas log_2(10**9)=30iterações. Nós construímos naté 10**9por repetidamente fazer n->2*n+cpara cada dígito cde sua expansão binário. Quando c==1, o valor dobrado é aumentado 2*n -> 2*n+1com um deslocamento de Fibonacci em uma etapa(a,b)=(b+a,b)

Para manter os valores a,bgerenciáveis, armazenamos apenas os primeiros 1006dígitos dividindo o piso 10até que eles estejam abaixo 2**3340 ~ 1e1006.

código de máquina x86 de 32 bits (com chamadas do sistema Linux): 106 105 bytes

changelog: salvou um byte na versão rápida porque uma constante off-by-one não altera o resultado para Fib (1G).

Ou 102 bytes para uma versão 18% mais lenta (no Skylake) (usando mov/ sub/ em cmcvez de lea/ cmpno loop interno, para gerar execução e empacotamento em 10**9vez de 2**32). Ou 101 bytes para uma versão mais lenta ~ 5.3x com uma ramificação no processamento de transporte no loop mais interno. (Avaliei uma taxa de desvio de agência de 25,4%!)

Ou 104/101 bytes, se um zero inicial for permitido. (É necessário 1 byte extra para o código físico pular 1 dígito da saída, que é o que é necessário para a Fib (10 ** 9)).

Infelizmente, o modo NASM do TIO parece ignorar -felf32nos sinalizadores do compilador. Aqui está um link de qualquer maneira com meu código fonte completo, com toda a bagunça de idéias experimentais nos comentários.

Este é um programa completo . Ele imprime os primeiros 1000 dígitos de Fib (10 ** 9), seguidos de alguns dígitos extras (os últimos estão errados), seguidos de alguns bytes de lixo (sem incluir uma nova linha). A maior parte do lixo não é ASCII, portanto, você pode querer passar por ele cat -v. konsolePorém, não quebra meu emulador de terminal (KDE ). Os "bytes de lixo" estão armazenando Fib (999999999). Eu já tinha -1024um registro, por isso era mais barato imprimir 1024 bytes do que o tamanho adequado.

Estou contando apenas o código da máquina (tamanho do segmento de texto do meu executável estático), não o buço que o torna um executável ELF. ( Executáveis ​​ELF muito pequenos são possíveis , mas eu não queria me preocupar com isso). Acabou sendo mais curto usar a pilha de memória em vez do BSS, para que eu possa justificar não contar mais nada no binário, pois não dependo de nenhum metadado. (Produzir um binário estático sem strip da maneira normal torna um ELF de 340 bytes executável.)

Você poderia criar uma função desse código que poderia chamar de C. Custaria alguns bytes para salvar / restaurar o ponteiro da pilha (talvez em um registro MMX) e outras sobrecargas, mas também salvar bytes retornando com a string na memória, em vez de fazer uma write(1,buf,len)chamada do sistema. Eu acho que jogar golfe em código de máquina deve me dar alguma folga aqui, já que ninguém mais postou uma resposta em qualquer idioma sem precisão estendida nativa, mas acho que uma versão funcional disso ainda deve ter menos de 120 bytes sem jogar novamente todo o golfe coisa.

Algoritmo:

força bruta a+=b; swap(a,b), truncando conforme necessário para manter apenas os dígitos decimais iniciais> = 1017. Ele roda em 1min13s no meu computador (ou 322,47 bilhões de ciclos de clock + - 0,05%) (e pode ser um pouco mais rápido com alguns bytes extras de tamanho de código ou até 62s com tamanho de código muito maior desde o desenrolamento do loop. matemática inteligente, apenas fazendo o mesmo trabalho com menos sobrecarga). É baseado na implementação Python do @ AndersKaseorg , que é executada em 12min35s no meu computador (Skylake 4.4GHz i7-6700k). Nenhuma versão tem nenhum cache L1D em falta, portanto meu DDR4-2666 não importa.

Diferentemente do Python, eu armazeno os números de precisão estendida em um formato que libera truncado os dígitos decimais . Eu armazeno grupos de 9 dígitos decimais por número inteiro de 32 bits, para que um deslocamento de ponteiro descarte os 9 dígitos baixos. Isso é efetivamente base de 1 bilhão, o que é uma potência de 10. (É pura coincidência que esse desafio precise do número de bilionésimo de Fibonacci, mas me poupa alguns bytes versus duas constantes separadas).

Seguindo a terminologia GMP , cada parte de 32 bits de um número de precisão estendida é chamada de "membro". A execução durante a adição deve ser gerada manualmente com uma comparação com 1e9, mas é usada normalmente como uma entrada para as ADCinstruções usuais do próximo membro. (Também tenho que quebrar manualmente para o [0..999999999]intervalo, em vez de 2 ^ 32 ~ = 4.295e9. Faço isso sem ramificações com lea+ cmov, usando o resultado de execução da comparação.)

Quando o último membro produz uma execução diferente de zero, as duas próximas iterações do loop externo são lidas a partir de 1 membro mais alto que o normal, mas ainda gravam no mesmo local. É como fazer um memcpy(a, a+4, 114*4)deslocamento à direita de 1 membro, mas feito como parte dos próximos dois loops de adição. Isso acontece a cada ~ 18 iterações.

Hacks para economia de tamanho e desempenho:

• As coisas de sempre, como em lea ebx, [eax-4 + 1]vez de mov ebx, 1, quando eu sei disso eax=4. E usar loopem lugares onde LOOPa lentidão tem apenas um pequeno impacto.

• Trunque por 1 membro gratuitamente, deslocando os ponteiros dos quais lemos, enquanto ainda escreve no início do buffer no adcloop interno. Lemos [edi+edx]e escrevemos para [edi]. Para que possamos obter edx=0ou 4obter um deslocamento de leitura e gravação para o destino. Precisamos fazer isso por 2 iterações sucessivas, primeiro compensando as duas e depois apenas compensando o dst. Detectamos o segundo caso examinando esp&4antes de redefinir os ponteiros para a frente dos buffers (usando &= -1024porque os buffers estão alinhados). Veja os comentários no código.

• O ambiente de inicialização do processo Linux (para um executável estático) zera a maioria dos registros e a memória da pilha abaixo esp/ rspé zerada. Meu programa tira proveito disso. Em uma versão com função de chamada disso (onde a pilha não alocada pode estar suja), eu poderia usar o BSS para memória zerada (ao custo de talvez mais 4 bytes para configurar os ponteiros). A zeragem edxlevaria 2 bytes. A ABI do System V x86-64 não garante nenhum deles, mas a implementação do Linux é zero (para evitar vazamentos de informações do kernel). Em um processo vinculado dinamicamente, /lib/ld.soé executado antes _starte deixa os registros diferentes de zero (e provavelmente lixo na memória abaixo do ponteiro da pilha).

• Eu continuo -1024em ebxpara uso fora de loops. Use blcomo um contador para loops internos, terminando em zero (que é o byte baixo de -1024, restaurando assim a constante para uso fora do loop). A Intel Haswell e mais tarde não têm multas parciais de mesclagem de registros para registros low8 (e, na verdade, nem os renomeiam separadamente) ; portanto, há uma dependência no registro completo, como na AMD (não é um problema aqui). Isso seria horrível para Nehalem e versões anteriores, porém, que têm paradas parciais de registro durante a fusão. Em outros lugares, escrevo regs parciais e leio o reg completo sem xor-zero ou ummovzx, geralmente porque sei que algum código anterior zerou os bytes superiores e, novamente, isso é bom na família AMD e Intel SnB, mas lento na Intel pré-Sandybridge.

  Como uso 1024o número de bytes para gravar em stdout ( sub edx, ebx), meu programa imprime alguns bytes de lixo após os dígitos de Fibonacci, porque mov edx, 1000custa mais bytes.

• (não utilizado) adc ebx,ebxcom EBX = 0 para obter EBX = CF, economizando um byte vs setc bl.

• dec/ jnzdentro de um adcloop preserva o CF sem causar uma parada parcial do sinalizador quando adclê sinalizadores no Intel Sandybridge e posterior. É ruim em CPUs anteriores , mas o AFAIK é gratuito no Skylake. Ou, na pior das hipóteses, um golpe extra.

• Use a memória abaixo espcomo uma zona vermelha gigante . Como esse é um programa completo do Linux, sei que não instalei nenhum manipulador de sinal e que nada mais assobiará de forma assíncrona a memória da pilha de espaço do usuário. Pode não ser o caso em outros sistemas operacionais.

• Tire proveito do mecanismo de pilha para economizar largura de banda de problemas de uop usando pop eax(1 uop + ocasional de sincronização de pilha) em vez de lodsd(2 uops em Haswell / Skylake, 3 em IvB e versões anteriores de acordo com as tabelas de instruções de Agner Fog )). IIRC, isso diminuiu o tempo de execução de 83 segundos para 73. Provavelmente, eu poderia obter a mesma velocidade usando um movcom um modo de endereçamento indexado, como mov eax, [edi+ebp]onde ebpmantém o deslocamento entre os buffers src e dst. (Isso tornaria o código fora do loop interno mais complexo, tendo que negar o registro de deslocamento como parte da troca de src e dst pelas iterações de Fibonacci.) Consulte a seção "desempenho" abaixo para obter mais informações.

• inicie a sequência fornecendo à primeira iteração uma carga (um byte stc), em vez de armazenar uma 1na memória em qualquer lugar. Muitas outras coisas específicas do problema estão documentadas nos comentários.

Listagem NASM (código de máquina + fonte) , gerada com nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Em seguida, removi manualmente alguns blocos de material comentado, para que a numeração das linhas tenha lacunas.) Para remover as colunas principais para que você possa alimentá-lo no YASM ou 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

Provavelmente há espaço para jogar mais alguns bytes com isso, mas eu já passei pelo menos 12 horas nisso em 2 dias. Eu não quero sacrificar a velocidade, mesmo que seja muito mais do que rápido o suficiente e haja espaço para diminuí-la de maneiras que custam velocidade . Parte do meu motivo para publicar está mostrando a rapidez com que posso criar uma versão asm de força bruta. Se alguém quiser realmente optar pelo tamanho mínimo, mas talvez 10 vezes mais lento (por exemplo, 1 dígito por byte), fique à vontade para copiar isso como ponto de partida.

O executável resultante (de yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) é 340B (despojado):

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

atuação

O adcloop interno é de 10 uops de domínio fundido no Skylake (+1 de sincronização de pilha a cada ~ 128 bytes), para que ele possa emitir um por ~ 2,5 ciclos no Skylake com taxa de transferência de front-end ideal (ignorando os uops de sincronização de pilha) . A latência-caminho crítico é de 2 ciclos, por o adc-> cmp-> de iteração seguinte adccadeia de dependência realizadas em malha, de modo que o gargalo deve ser o limite de emissão de front-end ~ 2,5 ciclos por iteração.

adc eax, [edi + edx]são 2 uops de domínio não utilizado para as portas de execução: load + ALU. Ele se funde nos decodificadores (1 uop de domínio fundido), mas não é laminado no estágio de edição para 2 uops de domínio fundido, devido ao modo de endereçamento indexado, mesmo em Haswell / Skylake . Eu pensei que ele ficaria micro-fundido, como add eax, [edi + edx]acontece, mas talvez manter os modos de endereçamento indexado micro-fundidos não funcione para uops que já possuem 3 entradas (sinalizadores, memória e destino). Quando escrevi, estava pensando que não teria uma desvantagem no desempenho, mas estava errado. Essa maneira de lidar com o truncamento diminui o loop interno todas as vezes, seja edx0 ou 4.

Seria mais rápido lidar com o deslocamento de leitura e gravação para o dst, deslocando edie usando edxpara ajustar o armazenamento. Então adc eax, [edi]/ ... / mov [edi+edx], eax/ em lea edi, [edi+4]vez de stosd. Haswell e mais tarde podem manter uma loja indexada micro-fundida. (Sandybridge / IvB também a lamina.)

No Intel Haswell e anteriores, adce cmovcsão 2 UOPs cada, com latência 2c . ( adc eax, [edi+edx]ainda não é laminado em Haswell e é emitido como três uops de domínio fundido). Broadwell e mais tarde permitem uops de 3 entradas para mais do que apenas FMA (Haswell), fazendo adce cmovc(e algumas outras coisas) instruções de uop, como se estivessem na AMD há muito tempo. (Essa é uma das razões pelas quais a AMD se sai bem nos benchmarks GMP de precisão estendida há muito tempo.) De qualquer forma, o loop interno de Haswell deve ser de 12 uops (ocasionalmente, com +1 de sincronização de pilha), com um gargalo de front-end de ~ 3 c por melhor exemplo, ignorando os uops de sincronização de pilha.

Usar popsem balancear pushdentro de um loop significa que o loop não pode ser executado a partir do LSD (detector de fluxo de loop) e deve ser relido do cache uop para o IDQ todas as vezes. Se alguma coisa, é uma coisa boa no Skylake, já que um loop de 9 ou 10 uop ​​não emite de maneira ideal a 4 uops a cada ciclo . Isso provavelmente é parte do motivo pelo qual a substituição lodsdpor popajudou tanto. (O LSD não pode bloquear os uops porque isso não deixaria espaço para inserir um uop de sincronização de pilha .) (BTW, uma atualização de microcódigo desativa o LSD inteiramente no Skylake e Skylake-X para corrigir uma errata. acima antes de obter essa atualização.)

Eu criei um perfil no Haswell e descobri que ele roda 381,31 bilhões de ciclos de clock (independentemente da frequência da CPU, pois ele usa apenas o cache L1D, não a memória). A taxa de transferência do problema de front-end foi de 3,72 ups de domínio fundido por relógio, contra 3,70 no Skylake. (Mas é claro instruções por ciclo foi reduzido para 2,42 de 2,87, porque adce cmovsão 2 UOPs sobre Haswell.)

pushsubstituir stosdprovavelmente não ajudaria tanto, porque adc [esp + edx]provocaria uma sincronização de pilha sempre. E custaria um byte, por stdisso lodsdvai na outra direção. ( mov [edi], eax/ lea edi, [edi+4]substituir stosdé uma vitória, passando de 32.909Motos para iteradores de 100M para 31.954Motos para iteradores de 100M. Parece que stosddecodifica como 3 uops, com os uops de endereço da loja / dados da loja não microfundidos, então push+ sincronização de pilha uops ainda pode ser mais rápido que stosd)

O desempenho real de ~ 322,47 bilhões de ciclos para iterações 1G de 114 membros funciona para 2.824 ciclos por iteração do loop interno , para a versão rápida 105B no Skylake. (Veja a ocperf.pysaída abaixo). Isso é mais lento do que eu previa na análise estática, mas estava ignorando a sobrecarga do loop externo e quaisquer uops de sincronização de pilha.

Os contadores de perf branchese branch-missesmostram que o loop interno é imprevisível uma vez por loop externo (na última iteração, quando não é utilizado). Isso também é responsável por parte do tempo extra.

Eu poderia salvar o tamanho do código fazendo com que o loop mais interno tivesse latência de 3 ciclos para o caminho crítico, usando mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) em vez de lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B ) O cmov/ stosdestá fora do caminho crítico. (A edição de incremento stosdpode ser executada separadamente do armazenamento, de modo que cada iteração cria uma cadeia de dependência curta.) Ele costumava salvar outro 1B alterando a instrução init do ebp de lea ebp, [ecx-1]para mov ebp,eax, mas descobri que ter o erro erradoebpnão mudou o resultado. Isso permitiria que um membro fosse exatamente == 1000000000 em vez de agrupar e produzir um carry, mas esse erro se propaga mais lentamente do que o crescimento de Fib (), portanto, isso não altera os dígitos de 1k iniciais do resultado final. Além disso, acho que esse erro pode se corrigir quando estamos apenas adicionando, já que há espaço em um membro para mantê-lo sem excesso. Mesmo 1G + 1G não transborda um número inteiro de 32 bits; portanto, ele eventualmente percorre para cima ou é truncado.

A versão de latência 3c é 1 uop extra, portanto, o front-end pode emiti-lo em um por 2,75 c ciclos no Skylake, apenas um pouco mais rápido que o back-end pode executá-lo. (No Haswell, serão 13 uops no total, pois ainda usa adcand cmov, e gargalo no front-end a 3,25 c por iter).

Na prática, ele executa um fator 1,18 mais lento no Skylake (3,34 ciclos por membro), em vez de 3 / 2,5 = 1,2 que eu previ para substituir o gargalo do front-end pelo gargalo de latência, apenas olhando para o loop interno sem a sincronização de pilha uops. Como os uops de sincronização de pilha prejudicam apenas a versão rápida (gargalo no front-end em vez de latência), não é preciso muito para explicar. por exemplo, 3 / 2,54 = 1,18.

Outro fator é que a versão de latência 3c pode detectar a imprevisibilidade ao deixar o loop interno enquanto o caminho crítico ainda está em execução (porque o front-end pode ficar à frente do back-end, permitindo que a execução fora de ordem execute o loop- contra-ataques), portanto, a penalidade efetiva de imprevisibilidade é menor. Perder esses ciclos de front-end permite que o back-end o atualize.

Se não fosse por isso, talvez pudéssemos acelerar a cmcversão 3c usando uma ramificação no loop externo em vez de manipular sem ramificações as compensações carry_out -> edx e esp. Previsão de ramificação + execução especulativa para uma dependência de controle em vez de uma dependência de dados pode permitir que a próxima iteração comece a executar o adcloop enquanto os uops do loop interno anterior ainda estavam em andamento. Na versão sem ramificação, os endereços de carregamento no loop interno têm uma dependência de dados do CF do adcúltimo membro da última.

A versão de loop interno de latência 2c afunila no front-end, portanto o back-end praticamente se mantém. Se o código do loop externo tiver alta latência, o front-end poderá avançar emitindo uops a partir da próxima iteração do loop interno. (Mas, neste caso, o material do loop externo possui bastante ILP e não possui alta latência, portanto o back-end não tem muito o que fazer quando começa a mastigar os uops no planejador fora de ordem, como suas entradas ficam prontas).

### 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 %)é o desvio padrão nas 4 execuções para essa contagem. Interessante que ele execute um número tão redondo de instruções. Esses 924 bilhões não são uma coincidência. Eu acho que o loop externo executa um total de 924 instruções.

uops_issuedé uma contagem de domínio fundido (relevante para a largura de banda do problema de front-end), enquanto uops_executedé uma contagem de domínio não fundido (número de uops enviados para portas de execução). A microfusão une 2 uops de domínio não fundido em um uop de domínio fundido, mas a eliminação de movimentos significa que alguns uops de domínio fundido não precisam de nenhuma porta de execução. Consulte a pergunta vinculada para obter mais informações sobre a contagem de uops e domínio fundido versus domínio não fundido. (Consulte também as tabelas de instruções e o guia do uarch do Agner Fog e outros links úteis no wiki de tags do SO x86 ).

De outra execução, medindo coisas diferentes: as falhas no cache L1D são totalmente insignificantes, conforme o esperado para a leitura / gravação dos mesmos dois buffers 456B. A ramificação do loop interno é imprevisível uma vez por loop externo (quando não é necessário sair do loop). (O tempo total é maior porque o computador não estava totalmente ocioso. Provavelmente o outro núcleo lógico estava ativo algumas vezes e passava mais tempo em interrupções (uma vez que a frequência medida pelo espaço do usuário estava abaixo de 4.400 GHz). Ou vários núcleos estavam ativos a maior parte do tempo, diminuindo o máximo de turbo. Não rastreei cpu_clk_unhalted.one_thread_activepara ver se a competição por HT era um 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        

Meu código pode rodar em menos ciclos no Ryzen, que pode emitir 5 uops por ciclo (ou 6 quando alguns deles são instruções de 2 uop, como o AVX 256b no Ryzen). Não tenho certeza do que o seu front-end faria stosd, que são 3 uops na Ryzen (o mesmo que a Intel). Eu acho que as outras instruções no loop interno são a mesma latência que a Skylake e todas são únicas. (Incluindo adc eax, [edi+edx], o que é uma vantagem sobre a Skylake).

Provavelmente isso poderia ser significativamente menor, mas talvez 9x mais lento, se eu armazenasse os números como 1 dígito decimal por byte . Gerar execução cmpe ajuste com cmovfuncionaria da mesma forma, mas executaria 1/9 da obra. 2 dígitos decimais por byte (base-100, não BCD de 4 bits com lentidãoDAA ) também funcionariam e div r8/ add ax, 0x3030transforma um byte de 0-99 em dois dígitos ASCII na ordem de impressão. Mas um dígito por byte não precisa div, basta repetir e adicionar 0x30. Se eu armazenar os bytes na ordem de impressão, isso tornaria o segundo loop realmente simples.

Usar 18 ou 19 dígitos decimais por número inteiro de 64 bits (no modo de 64 bits) faria com que fosse executado duas vezes mais rápido, mas custaria um tamanho de código significativo para todos os prefixos REX e constantes de 64 bits. Membros de 32 bits no modo de 64 bits evitam o uso em pop eaxvez de lodsd. Ainda pude evitar os prefixos REX usando espcomo um registro de rascunho que não é um ponteiro (trocando o uso de esie esp), em vez de usar r8dcomo um oitavo registro.

Se estiver criando uma versão de função que pode chamar, converter para 64 bits e usá-lo r8dpode ser mais barato do que salvar / restaurar rsp. 64 bits também não podem usar a dec r32codificação de um byte (já que é um prefixo REX). Mas na maioria das vezes acabei usando dec bl2 bytes. (Porque eu tenho uma constante nos bytes superiores de ebxe a uso apenas fora dos loops internos, o que funciona porque o byte baixo da constante é 0x00.)

Versão de alto desempenho

Para obter o desempenho máximo (não código-golfe), você deseja desenrolar o loop interno para que ele execute no máximo 22 iterações, que é um padrão de tomada / não-tomada suficientemente curto para que os preditores de ramificações funcionem bem. Nas minhas experiências, mov cl, 22antes de um .inner: dec cl/jnz .innerloop ter muito poucos erros de previsão (como 0,05%, muito menos de um por execução completa do loop interno), mas mov cl,23erros de previsão de 0,35 a 0,6 vezes por loop interno. 46é particularmente ruim, imprevisível ~ 1,28 vezes por loop interno (128M vezes para iterações de loop externo 100M). 114imprevisível exatamente uma vez por loop interno, o mesmo que encontrei como parte do loop de Fibonacci.

Fiquei curioso e tentei, desenrolando o loop interno por 6 com um %rep 6(porque isso divide 114 uniformemente). Isso eliminou principalmente erros de ramificação. Fiz edxnegativo e usei-o como compensação para as movlojas, para que adc eax,[edi]pudesse ficar micro-fundido. (E assim eu poderia evitar stosd). Puxei o leapara atualizar edifora do %repbloco, então ele faz apenas uma atualização de ponteiro por 6 lojas.

Também me livrei de todas as coisas de registro parcial no loop externo, embora não ache isso significativo. Pode ter ajudado um pouco a CF no final do loop externo, não dependente do ADC final; portanto, alguns dos uops do loop interno podem começar. O código do loop externo provavelmente poderia ser otimizado um pouco mais, já que neg edxfoi a última coisa que fiz, depois de substituir xchgpor apenas 2 movinstruções (já que eu ainda tinha 1) e reorganizar as cadeias de dep e eliminar os 8 bits registrar coisas.

Esta é a fonte NASM apenas do loop Fibonacci. É um substituto para essa seção da versão 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

Atuação:

 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% )

Isso é para o mesmo Fib (1G), produzindo a mesma saída em 62,3 segundos em vez de 73 segundos. (Ciclos 273.146G, vs. 322.467G. Como tudo ocorre no cache L1, os ciclos de clock do núcleo são realmente tudo o que precisamos examinar.)

Observe a uops_issuedcontagem total muito mais baixa , bem abaixo da uops_executedcontagem. Isso significa que muitos deles foram micro-fundidos: 1 uop no domínio fundido (problema / ROB), mas 2 uops no domínio não fundido (unidades de agendador / execução)). E que poucos foram eliminados no estágio de emissão / renomeação (como movcópia de registro ou xorzeros, que precisam ser emitidos, mas não precisam de uma unidade de execução). Uops eliminados desequilibrariam a contagem para o outro lado.

branch-missescaiu para ~ 400k, de 1G, então desenrolar funcionou. resource_stalls.anyé significativo agora, o que significa que o front-end não é mais o gargalo: em vez disso, o back-end está ficando para trás e limitando o front-end. idq_uops_not_delivered.coreconta apenas ciclos em que o front-end não deu uops, mas o back-end não foi interrompido. Isso é bom e baixo, indicando alguns gargalos no front-end.

Curiosidade: a versão python gasta mais da metade do tempo dividindo por 10 em vez de adicionar. (Substituir o a/=10com a>>=64acelera mais de um fator de 2, mas altera o resultado porque truncamento binário! = Truncamento decimal.)

É claro que minha versão asm é otimizada especificamente para esse tamanho de problema, com a iteração de loop - contagens codificadas. Mesmo mudar um número de precisão arbitrária o copiará, mas minha versão pode apenas ler de um deslocamento para as próximas duas iterações para pular até isso.

Eu criei um perfil da versão python (python2.7 de 64 bits no 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

Os números em (parens) são quanto tempo esse contador de amostras estava sendo amostrado. Ao olhar para mais contadores do que o HW suporta, o perf gira entre diferentes contadores e extrapola. Isso é ótimo para uma longa execução da mesma tarefa.

Se eu corresse perfdepois de definir o sysctl kernel.perf_event_paranoid = 0(ou executando perfcomo root), ele seria medido 4.400GHz. cycles:unão conta o tempo gasto em interrupções (ou chamadas do sistema), apenas ciclos de espaço do usuário. Minha área de trabalho estava quase totalmente ociosa, mas isso é 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)

Saídas ( F _1000000000 , F _1000000001 ). No meu laptop, ele imprime corretamente o ponto esquerdo e os primeiros 1000 dígitos em 133 segundos, usando 1,35 GiB de memória.

Como funciona

A recorrência de Fibonacci pode ser resolvida usando exponenciação de matriz:

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

a partir do qual derivamos essas identidades:

[ M _{i + j - 1} , M _{i + j} ; M _{i + j} , M _{i + j + 1} ] = [ F _{i - 1} , F _I ; F _i , F _{i + 1} ] ⋅ [ F _{j - 1} , F _j ; F _j , F _{j + 1} ],
F _{i + j} = F _{i+ 1} F _{j + 1} - F _{i - 1} F _{j - 1} = F _{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} .

A pfunção calcula ( F _{i + j} , F _{i + j + 1} ) dados ( F _i , F _{i + 1} ) e ( F _j , F _{j + 1} ). Escrevendo f npara ( F _i , F _{i + 1} ), temos p (f i) (f j)= f (i + j).

Então,

(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),

e nós conectamos f 1= (1,1).

Mathematica, 15 34 bytes

Fibonacci em si leva ~ 6s no meu computador. E 95 (+/- 5) s para o frontend exibi-lo.

Fibonacci@1*^9&

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

Mais longo, mas mais 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

Isso funcionou em 18 minutos e 31 segundos no meu laptop, produzindo os 1000 dígitos corretos seguidos por 74100118580(os seguintes dígitos corretos são 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

Experimente online!

Levou 48 segundos no TIO. A mesma fórmula recursiva da minha resposta em Python , mas sem truncar.

A constante 2143923439é 10**9-1, invertida em binário e com 1 extra no final. Iterar através de seus dígitos binários no sentido inverso simula a iteração através dos dígitos binários de 10**9-1. Parece mais curto codificar isso do que calculá-lo.

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)

Experimente online!

Explicação

Isso usa uma maneira bastante rápida de calcular os números de fibonacci. A função lleva dois números de Fibonacci e calcula os números de Fibonacci 10 posterior, enquanto que fleva a n th e n + 1 th números de Fibonacci e calcula a 2n + 20 ° e 2n + 21 números th Fibonacci. Eu os encadeio aleatoriamente para obter 1 bilhão e pegar os primeiros 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

Explicação

f ncalcula recursivamente o nnúmero de fibonacci usando a recorrência da resposta do xnor com a eliminação da subexpressão comum. Diferentemente das outras soluções postadas, que usam multiplicações de O (log (n)), temos uma recursão de profundidade de O (log (n)) com um fator de ramificação de 2, para uma complexidade de multiplicações de O (n).

No entanto, nem tudo está perdido! Como quase todas as chamadas estarão próximas à parte inferior da árvore de recursão, podemos usar aritmética nativa rápida sempre que possível e evitar muita manipulação de bignums enormes. Ele cospe uma resposta em alguns minutos na minha caixa.

T-SQL, 422 414 453 bytes (Verificado, agora competindo!)

EDIT 2 : Alterado para , ganhou alguns bytes, mas aumentou a velocidade suficiente para completar para 1 bilhão! Concluído em 45 horas e 29 minutos , verifica a sequência especificada e exibe 8 caracteres adicionais (que podem ou não estar corretos devido a erros de arredondamento).INT BIGINT DECIMAL(37,0)

O T-SQL não tem suporte nativo para "grande número", então tive que rolar meu próprio somador de grande número baseado em texto usando cadeias 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 @

Aqui está a versão formatada com comentários:

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 @

Basicamente, estou manipulando manualmente seqüências de 1008 caracteres preenchidas com zero, representando minhas duas variáveis ​​Fibonacci, @ae @.

Eu os adiciono 8 18 36 dígitos por vez, removendo os últimos 36 dígitos, convertendo para um tipo numérico gerenciável ( DECIMAL(37,0)), somando-os e depois esmagando-o novamente em outra sequência longa @c. Eu então "giro" @ae @movendo os últimos 36 dígitos para a frente e repetindo o processo. 28 rotações * 36 dígitos cobrem todos os 1008. Eu tenho que "carregar esse" manualmente.

Quando nosso número começa a exceder o comprimento da minha string, eu "desligo para a esquerda" e começamos a perder alguma precisão, mas o erro está dentro dos meus caracteres extras.

Tentei usar uma tabela SQL cheia de INTs e BIGINTs, com lógica semelhante, e foi muito mais lenta. Esquisito.

PARI / GP, 45 bytes

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

De alguma forma, \p1000não é suficiente. Isso não funciona com sistemas de 32 bits. A divisão final é evitar o ponto decimal na notação científica.

Pari / GP , 15 + 5 = 20 bytes

fibonacci(10^9)

Execute com a opção de linha de comando -s1gpara alocar 1 Gbytes de memória.

Ruby, 63 bytes

cara, sou ruim em jogar rubi; mas a classe BigInt faz maravilhas para esse tipo de coisa. Usamos o mesmo algoritmo que Anders Kaseorg.

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