Il y a eu un milliard d'itérations de défis Fibonacci sur ce site Web, alors laissez pimenter les choses avec un défi Fibonacci d'un milliard d'itérations!

Votre défi est de générer les 1000 premiers chiffres décimaux du millionième millionième nombre de Fibonacci avec un programme aussi bref que possible. Cela peut ensuite éventuellement être suivi de toute sortie supplémentaire de votre choix, y compris, sans toutefois s'y limiter, le reste des chiffres.

J'utilise la convention qui fib 0 = 0, fib 1 = 1.

Votre programme doit être assez rapide pour que vous puissiez l'exécuter et en vérifier l'exactitude. Pour cela, voici les 1000 premiers chiffres:

7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799

Python 2 + sympy, 72 octets

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

Essayez-le en ligne!

-10 octets en supprimant le terme pratiquement-0 grâce à Jeff Dege
-1 octet (1000 -> 1e3 grâce à Zacharý)
-2 octets en supprimant la variable inutile grâce à Erik the Outgolfer
-2 octets en passant à Python 2 grâce à Zacharý
-3 octets en 11 'les -11remerciements à ThePirateBay -3 octets en échangeant strdes backticks grâce à notjagan

bat désormais la solution haskell non intégrée de OP!

Python 2 , 106 octets

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

Essayez-le en ligne!

Aucune bibliothèque, juste arithmétique entière. Fonctionne presque instantanément.

Le noyau est l'identité diviser pour régner:

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

Cela nous permet de mettre (a,b) = (f(n),f(n+1))à jour pour doubler n -> 2*n. Puisque nous voulons obtenir n=10**9, cela ne prend que des log_2(10**9)=30itérations. Nous construisons nen 10**9faisant de manière répétée n->2*n+cpour chaque chiffre cde son développement binaire. Quand c==1, la valeur doublée est augmentée 2*n -> 2*n+1avec un décalage de Fibonacci en une étape(a,b)=(b+a,b)

Pour que les valeurs restent a,bgérables, nous ne stockons que leurs premiers 1006chiffres par division du sol 10jusqu'à ce qu'ils soient en dessous 2**3340 ~ 1e1006.

Code machine x86 32 bits (avec appels système Linux): 106 105 octets

changelog: enregistre un octet dans la version rapide, car une constante par un ne change pas le résultat pour Fib (1G).

Ou 102 octets pour une version de 18% plus lente (sur Skylake) (en utilisant mov/ sub/ cmcau lieu de lea/ cmpdans la boucle interne, pour générer le report et l’emballage à la 10**9place de 2**32). Ou 101 octets pour une version ~ 5.3x plus lente avec une branche dans la gestion du report dans la boucle la plus interne. (J'ai mesuré un taux de pronostic erroné de branche de 25,4%!)

Ou 104/101 octets si un zéro est autorisé. (Il faut 1 octet supplémentaire pour que 1 code soit ignoré, ce qui est nécessaire pour Fib (10 ** 9)).

Malheureusement, le mode NASM de TIO semble ignorer -felf32dans les drapeaux du compilateur. Voici quand même un lien avec mon code source complet, avec tout le fouillis d'idées expérimentales dans les commentaires.

Ceci est un programme complet . Il imprime les 1000 premiers chiffres de Fib (10 ** 9) suivis de quelques chiffres supplémentaires (les derniers étant erronés), suivis de quelques octets parasites (sans nouvelle ligne). La plupart des déchets sont non-ASCII, vous voudrez peut-être passer à travers cat -v. Cela ne casse pas mon émulateur de terminal (KDE konsole), cependant. Les "octets de mémoire" stockent Fib (999999999). J'avais déjà -1024dans un registre, il était donc moins cher d'imprimer 1024 octets que la taille appropriée.

Je ne compte que le code machine (taille du segment de texte de mon exécutable statique), pas le fluff qui en fait un exécutable ELF. (De très petits exécutables ELF sont possibles , mais je ne voulais pas m'en soucier). Il s'est avéré que l'utilisation de la mémoire de pile au lieu de BSS était plus courte, je peux donc justifier de ne rien compter d'autre dans le binaire, car je ne dépend d'aucune métadonnée. (Produire un binaire statique épuré de la manière habituelle rend un exécutable ELF de 340 octets.)

Vous pouvez créer une fonction à partir de ce code que vous pourriez appeler à partir de C. Cela coûterait quelques octets pour sauvegarder / restaurer le pointeur de pile (peut-être dans un registre MMX) et un autre temps système, mais également pour économiser des octets en retournant avec la chaîne en mémoire, au lieu de faire un write(1,buf,len)appel système. Je pense que jouer au golf dans le code machine devrait me faire perdre un peu de temps ici, car personne d’autre n’a même posté de réponse dans une langue qui ne possède pas une précision étendue native, mais je pense qu’une version fonctionnelle de cela devrait être inférieure à 120 octets sans avoir à re-jouer au golf dans son ensemble. chose.

Algorithme:

force brute a+=b; swap(a,b), tronquée au besoin pour ne conserver que le premier> = 1017 chiffres décimaux. Il fonctionne en 1min13s sur mon ordinateur (ou 322,47 milliards de cycles d'horloge + - 0,05%) (et pourrait être quelques% plus rapide avec quelques octets de taille de code supplémentaires, ou jusqu'à 62s avec une taille de code beaucoup plus grande à partir du déroulement de la boucle. Non mathématiques intelligentes, faisant juste le même travail avec moins de frais généraux). Il est basé sur l'implémentation Python de @ AndersKaseorg , qui s'exécute en 12 min 35 s sur mon ordinateur (Skylake i7-6700k à 4,4 GHz). Aucune des versions ne contient de cache L1D manquant, mon DDR4-2666 n'a donc aucune importance.

À la différence de Python, je stocke les nombres à précision étendue dans un format qui permet de tronquer les chiffres décimaux gratuitement . Je stocke des groupes de 9 chiffres décimaux par entier de 32 bits, de sorte qu'un décalage de pointeur ignore les 9 chiffres les plus bas. Il s’agit bien d’un milliard de base, ce qui représente une puissance de 10. (C’est une pure coïncidence que ce défi nécessite le milliardième chiffre de Fibonacci, mais il m’économise quelques octets au lieu de deux constantes distinctes.)

Selon la terminologie GMP , chaque bloc de 32 bits d’un nombre à précision étendue est appelé un "membre". L'exécution lors de l'ajout doit être générée manuellement avec une comparaison avec 1e9, mais est ensuite utilisée normalement comme entrée de l' ADCinstruction habituelle pour le membre suivant. (Je dois aussi [0..999999999]retourner manuellement à la plage plutôt qu'à 2 ^ 32 ~ = 4.295e9. Je le fais sans branche avec lea+ cmov, en utilisant le résultat de report de la comparaison.)

Lorsque le dernier membre produit un report non nul, les deux itérations suivantes de la boucle externe lisent un membre plus haut que la normale, mais écrivent toujours au même endroit. Cela revient à faire un memcpy(a, a+4, 114*4)virage à droite d'un membre, mais dans le cadre des deux boucles d'addition suivantes. Cela se produit chaque ~ 18 itérations.

Des astuces pour gagner en taille et en performance:

• Les trucs habituels comme lea ebx, [eax-4 + 1]au lieu de mov ebx, 1, quand je le sais eax=4. Et utiliser loopdans des endroits où LOOPla lenteur n'a qu'un impact minime.

• Découpez gratuitement un membre en décalant les pointeurs à partir desquels nous lisons, tout en écrivant au début du tampon dans la adcboucle interne. Nous lisons depuis [edi+edx]et écrivons à [edi]. Nous pouvons donc obtenir edx=0ou 4obtenir un décalage lecture-écriture pour la destination. Nous devons faire cela pour 2 itérations successives, en compensant d'abord les deux, puis en ne compensant que le dst. Nous détectons le 2e cas en regardant esp&4avant de réinitialiser les pointeurs au début des tampons (en utilisant &= -1024, car les tampons sont alignés). Voir les commentaires dans le code.

• L'environnement de démarrage de processus Linux (pour un exécutable statique) contient la plupart des registres, et la mémoire de pile en dessous de esp/ rspest mise à zéro. Mon programme en profite. Dans une version appelable de cette fonction (où une pile non allouée pourrait être sale), je pourrais utiliser BSS pour la mémoire mise à zéro (au prix de peut-être 4 octets supplémentaires pour configurer les pointeurs). La réduction à zéro edxprendrait 2 octets. L’ABI System V x86-64 ne garantit aucun de ces éléments, mais son implémentation en fait zéro (pour éviter les fuites d’informations hors du noyau). Dans un processus lié dynamiquement, /lib/ld.sos'exécute avant _startet laisse des registres différents de zéro (et probablement de la mémoire en mémoire sous le pointeur de pile).

• Je garde -1024en ebxpour une utilisation en dehors des boucles. Utiliser blcomme un compteur pour les boucles internes, se terminant par zéro (qui est l’octet de poids faible de -1024, restaurant ainsi la constante pour une utilisation en dehors de la boucle). Intel Haswell et les versions ultérieures ne prévoient pas de pénalité pour la fusion de registres partiels pour les registres low8 (et ne les renomment même pas séparément) . Il existe donc une dépendance sur le registre complet, comme sur AMD (ce n’est pas un problème ici). Cela serait horrible sur Nehalem et plus tôt, cependant, qui ont des blocages de registres partiels lors de la fusion. Il y a d'autres endroits où j'écris des regs partiels, puis je lis les regs complets sans xor-zeroing ou unmovzx, généralement parce que je sais que certains codes antérieurs ont mis à zéro les octets supérieurs, et encore une fois, c’est bien sur AMD et la famille Intel SnB, mais lent sur Intel avant Sandybridge.

  J'utilise 1024comme nombre d'octets pour écrire dans stdout ( sub edx, ebx), de sorte que mon programme imprime des octets parasites après les chiffres de Fibonacci, car ils mov edx, 1000coûtent plus d'octets.

• (non utilisé) adc ebx,ebxavec EBX = 0 pour obtenir EBX = CF, en économisant 1 octet contre setc bl.

• dec/ à l' jnzintérieur d'une adcboucle préserve CF sans provoquer de adcblocage d'indicateurs partiels lors de la lecture d'indicateurs sur Intel Sandybridge et versions ultérieures. C'est mauvais sur les anciens processeurs , mais autant que je sache, sur Skylake. Ou au pire, un extra uop.

• Utilisez la mémoire ci-dessous espcomme une zone rouge géante . Comme il s’agit d’un programme complet pour Linux, je sais que je n’ai installé aucun gestionnaire de signaux, et que rien d’autre ne videra la mémoire de pile d’espace utilisateur de manière asynchrone. Cela peut ne pas être le cas sur d'autres systèmes d'exploitation.

• Tirez parti du moteur de pile pour économiser la bande passante des problèmes uop en utilisant pop eax(1 uop + synchronisation ponctuelle occasionnelle) au lieu de lodsd(2 uops sur Haswell / Skylake, 3 sur IvB et plus tôt selon les tableaux d'instructions d'Agner Fog )). IIRC, le temps d'exécution est passé d'environ 83 secondes à 73 secondes. Je pourrais probablement obtenir la même vitesse d'utilisation movd'un mode d'adressage indexé, comme dans le mov eax, [edi+ebp]cas où ebple décalage entre les tampons src et dst est maintenu. (Cela compliquerait le code en dehors de la boucle interne, car il faudrait annuler le registre de décalage dans le cadre de l'échange de src et de dst pour les itérations de Fibonacci.) Voir la section "performance" ci-dessous pour plus d'informations.

• Commencez la séquence en donnant à la première itération un report (un octet stc), au lieu de stocker un 1en mémoire n'importe où. Beaucoup d'autres choses spécifiques à un problème documentées dans les commentaires.

Liste NASM (code machine + source) , générée avec nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Ensuite, j'ai enlevé à la main quelques blocs d'éléments commentés, afin que la numérotation des lignes comporte des espaces.) Pour effacer les colonnes de tête afin de pouvoir l'insérer dans YASM ou NASM, utilisez 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

Il y a probablement de la place pour jouer au golf encore quelques octets, mais j'ai déjà passé au moins 12 heures à ce sujet pendant 2 jours. Je ne veux pas sacrifier la vitesse, même si elle est beaucoup plus rapide et qu'il est possible de la réduire à un coût aussi rapide . Une partie de ma raison d’afficher montre à quelle vitesse je peux créer une version brute-force asm. Si quelqu'un veut vraiment opter pour une taille minimale, mais peut-être 10 fois plus lente (par exemple, un chiffre par octet), n'hésitez pas à copier ceci comme point de départ.

Le fichier exécutable résultant (from yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) est 340B (stripped):

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

Performance

La adcboucle interne correspond à 10 Uops à domaine fondu sur Skylake (+1 pile de synchronisation tous les 128 octets environ). Elle peut ainsi émettre au moins 2,5 cycles sur Skylake avec un débit frontal optimal (en ignorant les uops de synchronisation de pile). . La latence du chemin critique est de 2 cycles, pour la chaîne de dépendance acheminée par la boucle de l'itération adc-> cmp-> suivante adc;

adc eax, [edi + edx]est 2 uops de domaine non-fusionné pour les ports d’exécution: charge + ALU. Il micro-fusionnent dans les décodeurs (1 uop à domaine fondu), mais non laminés à l'étape d'émission en 2 uops à domaine fondu, en raison du mode d'adressage indexé, même sur Haswell / Skylake . Je pensais qu'il resterait micro-fusionné, comme le add eax, [edi + edx]fait le reste , mais peut-être que conserver les modes d'adressage indexés micro-fusionnés ne fonctionne pas pour les Uops qui ont déjà 3 entrées (drapeaux, mémoire et destination). Quand je l'ai écrit, je pensais qu'il n'y aurait pas d'inconvénient en termes de performances, mais je me suis trompé. Cette façon de gérer la troncature ralentit la boucle interne à chaque fois, qu’il s’agisse de edx0 ou de 4.

Il serait plus rapide de gérer le décalage lecture-écriture pour le dst en décalant ediet en utilisant edxpour ajuster le magasin. Donc adc eax, [edi]/ ... / mov [edi+edx], eax/ lea edi, [edi+4]au lieu de stosd. Haswell et plus tard peuvent garder un magasin indexé micro-fusionné. (Sandybridge / IvB le désamorcerait aussi.)

Sur Intel Haswell et les versions antérieures, adcet cmovcsont 2 uops chacun, avec une latence 2c . ( adc eax, [edi+edx]est toujours non-laminé sur Haswell, et est émis en tant que 3 uops à domaine fondu). Broadwell et les versions ultérieures autorisent les uops à 3 entrées pour plus que juste FMA (Haswell), en faisant adcet cmovc(et quelques autres choses) des instructions en mono-uop, comme si elles utilisaient la DMLA depuis longtemps. (C’est une des raisons pour lesquelles AMD s’est bien débrouillé avec les tests de performance GMP de précision étendue depuis longtemps.) Quoi qu’il en soit, la boucle interne de Haswell devrait être de 12 uops (+1 en synchronisation de pile à l’occasion), avec un goulot d’étranglement frontal de ~ 3c par iter dans le meilleur des cas, en ignorant les uops de synchronisation de pile.

L'utilisation popsans équilibrage à l' pushintérieur d'une boucle signifie que la boucle ne peut pas être exécutée à partir du LSD (détecteur de flux de boucle) et doit être relue à chaque fois à partir du cache uop dans l'IDQ. Au contraire, c’est une bonne chose sur Skylake, puisqu’une boucle de 9 ou 10 UOP n’émet pas de façon optimale à 4 UPS à chaque cycle . Cela fait probablement partie des raisons pour lesquelles remplacer lodsdpar poptellement aidé. (Le LSD ne peut pas verrouiller les uops car cela ne laisserait pas de place pour insérer une pile de synchronisation .) (BTW, une mise à jour au microcode désactive complètement le LSD sur Skylake et Skylake-X afin de corriger un erratum. ci-dessus avant d’obtenir cette mise à jour.)

Je l’ai profilée sur Haswell et ai constaté qu’elle fonctionnait en 381,31 milliards de cycles d’horloge (quelle que soit la fréquence du processeur, car elle utilise uniquement le cache L1D, pas la mémoire). Le débit de sortie front-end était de 3,72 UOP par domaine fondu, contre 3,70 pour Skylake. (Mais bien sûr, le nombre d’instructions par cycle est passé de 2,87 à 2,42, parce que adcet cmovsont 2 oups sur Haswell.)

pushremplacer stosdne vous aiderait probablement pas autant, car adc [esp + edx]cela déclencherait une synchronisation de pile à chaque fois. Et cela coûterait un octet, la stdsituation lodsdva dans l'autre sens. ( mov [edi], eax/ lea edi, [edi+4]remplacer stosdest une victoire, passant de 32,909Mcycles pour 100Miters à 31,954Mcycles pour 100Miters. Il semble que stosddécodage en 3 uops, avec les adresses de magasin / données de magasin non micro-fusionnées, donc push+ pile-sync uops pourrait encore être plus rapide que stosd)

La performance réelle de ~ 322,47 milliards de cycles pour les itérations 1G de 114 membres équivaut à 2,824 cycles par itération de la boucle interne , pour la version rapide 105B sur Skylake. (Voir la ocperf.pysortie ci-dessous). C'est plus lent que prévu par l'analyse statique, mais j'ignorais les frais généraux de la boucle externe et de toutes les opérations de synchronisation de pile.

Perf corrige brancheset branch-missesmontre que la boucle interne se trompe une fois par boucle externe (à la dernière itération, si elle n’est pas prise). Cela représente également une partie du temps supplémentaire.

Je pourrais économiser du code en faisant en sorte que la boucle la plus interne ait une latence de 3 cycles pour le chemin critique, en utilisant mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) au lieu de lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B ). Le cmov/ stosdest hors du chemin critique. (L'incrémentation-edi de stosdpeut être exécutée séparément du magasin, chaque itération bifurque ainsi d'une chaîne de dépendance courte.) Il enregistrait un autre 1B en modifiant l'instruction d'initialisation ebp de lea ebp, [ecx-1]en mov ebp,eax, mais j'ai découvert qu'avoir la mauvaiseebpn'a pas changé le résultat. Cela laisserait un membre exactement = 1000000000 au lieu d’emballer et de produire un report, mais cette erreur se propage plus lentement que nous grandissons, de sorte que cela ne change pas les 1k premiers chiffres du résultat final. De plus, je pense que l'erreur peut se corriger d'elle-même lorsque nous ajoutons, car il y a de la place dans un membre pour la retenir sans débordement. Même 1G + 1G ne dépasse pas un entier de 32 bits, il finira par percoler vers le haut ou être tronqué.

La version de latence 3c est 1 uop supplémentaire, ainsi le front-end peut la publier à un cycle par 2,75c sur Skylake, à peine légèrement plus rapide que le back-end ne peut l'exécuter. (Sur Haswell, ce sera 13 uops au total puisqu'il utilise toujours adcet cmov, et un goulot d'étranglement sur le front-end à 3,25 centimes par iter).

En pratique, Skylake ralentit le facteur 1,18 (3,34 cycles par membre) au lieu de 3 / 2,5 = 1,2 que je prédisais pour remplacer le goulot d'étranglement du front-end par le goulot d'étranglement dû au fait de regarder la boucle interne sans synchronisation de pile. uops. Comme les piles de synchronisation de pile ne font que mal à la version rapide (goulot d’étranglement au lieu de la latence), il n’en faut pas beaucoup pour l’expliquer. par exemple 3 / 2,54 = 1,18.

Un autre facteur est que la version de latence 3c peut détecter l’erreur lorsqu’elle quitte la boucle interne alors que le chemin critique est en cours d’exécution (car le serveur frontal peut avoir une longueur d’avance sur le back-end, ce qui permet à une exécution hors d’ordre d’exécuter la boucle. ainsi, la peine effective d’erreur de pronostic est plus faible. La perte de ces cycles frontaux permet au back-end de se rattraper.

Si ce n'était pas le cas, nous pourrions peut-être accélérer la cmcversion 3c en utilisant une branche dans la boucle externe au lieu du traitement sans branche du décalage carry_out -> edx et esp. Une prédiction de branche + une exécution spéculative pour une dépendance de contrôle au lieu d'une dépendance de données pourrait permettre à la prochaine itération de démarrer l'exécution de la adcboucle alors que des uops de la boucle interne précédente étaient encore en vol. Dans la version sans embranchement, les adresses de charge de la boucle interne ont une dépendance de données sur CF à partir adcdu dernier membre.

Les goulots d'étranglement de la version de boucle interne de latence 2c sur le front-end, donc le back-end continue à peu près. Si le code de la boucle externe était à latence élevée, le serveur frontal pourrait aller de l'avant en émettant des uops dès la prochaine itération de la boucle interne. (Mais dans ce cas, la boucle externe contient beaucoup d' ILP et aucune charge de latence élevée. Par conséquent, le back-end n'a pas beaucoup de retard leurs entrées deviennent prêtes).

### 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 %)est l'écart-type sur les 4 exécutions pour ce compte. Intéressant qu'il exécute un tel nombre rond d'instructions. Ces 924 milliards ne sont pas une coïncidence. Je suppose que la boucle externe exécute un total de 924 instructions.

uops_issuedest un compte de domaine fondu (pertinent pour la bande passante d'émission front-end), alors qu'il uops_executeds'agit d'un compte de domaine non fusionné (nombre d'UP envoyés aux ports d'exécution). La micro-fusion regroupe 2 Uops à domaine non fusionné dans un UOP à domaine fusionné, mais mov-élimination signifie que certains Uops à domaine fusionné ne nécessitent aucun port d'exécution. Voir la question liée pour en savoir plus sur le comptage des uops et des domaines fusionnés et non fusionnés. (Voir également les tableaux d'instructions et le guide uarch d'Agner Fog , ainsi que d'autres liens utiles dans le wiki des balises SO x86 ).

D'une autre série, mesurant différentes choses: les erreurs de cache L1D sont totalement insignifiantes, comme prévu pour la lecture / écriture des deux mêmes tampons 456B. La branche de la boucle interne se trompe une fois par boucle externe (lorsqu'il n'est pas nécessaire de quitter la boucle). (Le temps total est plus long parce que l'ordinateur n'était pas totalement inactif. L'autre cœur logique a probablement été actif de temps en temps, et des interruptions supplémentaires ont eu lieu (la fréquence mesurée par l'utilisateur étant plus basse que 4,400 GHz). Ou plusieurs cœurs étaient actifs la plupart du temps, réduisant le turbo max. Je ne savais pas cpu_clk_unhalted.one_thread_activesi la concurrence HT posait problème.)

     ### 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        

Mon code peut bien fonctionner en moins de cycles sur Ryzen, ce qui peut générer 5 uops par cycle (ou 6 lorsque certaines d'entre elles sont des instructions 2-uop, comme les fichiers AVX 256b sur Ryzen). Je ne suis pas sûr de ce que son front-end ferait avec stosd, qui est de 3 oups sur Ryzen (identique à Intel). Je pense que les autres instructions de la boucle interne ont la même latence que Skylake et que toutes les réponses sont individuelles. (Y compris adc eax, [edi+edx], ce qui est un avantage sur Skylake).

Cela pourrait probablement être beaucoup plus petit, mais peut-être 9 fois plus lent si je stockais les nombres sous la forme d'un chiffre décimal par octet . Générer un report avec cmpet s’ajuster avec cmovfonctionnerait de la même façon, mais réalisez 1 / 9e du travail. Deux chiffres décimaux par octet (base 100, pas un BCD 4 bits avec une vitesse lenteDAA ) fonctionneraient également, et div r8/ add ax, 0x3030convertit un octet 0-99 en deux chiffres ASCII dans l'ordre d'impression. Mais 1 chiffre par octet n'est pas nécessaire div, il suffit de boucler et d'ajouter 0x30. Si je stocke les octets dans l’ordre d’impression, cela rendrait la deuxième boucle très simple.

L'utilisation de 18 ou 19 chiffres décimaux par entier 64 bits (en mode 64 bits) lui permettrait de fonctionner environ deux fois plus vite, mais coûterait une taille de code significative pour tous les préfixes REX et pour les constantes 64 bits. Les membres 32 bits en mode 64 bits empêchent d'utiliser pop eaxau lieu de lodsd. Je pouvais toujours éviter les préfixes REX en utilisant espun registre de travail non-pointeur (en échangeant l'utilisation de esiet esp) au lieu de l'utiliser en r8dtant que 8ème registre.

Si vous créez une version à fonction appelable, la conversion au format 64 bits et son utilisation r8dpeuvent être moins onéreuses que la sauvegarde / restauration rsp. De plus, 64 bits ne peuvent pas utiliser le dec r32codage sur un octet (puisqu'il s'agit d'un préfixe REX). Mais la plupart du temps, j'ai fini par utiliser dec bl2 octets. (Parce que j'ai une constante dans les octets supérieurs de ebxet que je ne l'utilise qu'en dehors des boucles internes, ce qui fonctionne car l'octet de poids faible de la constante est 0x00.)

Version haute performance

Pour obtenir des performances maximales (sans code-golf), vous souhaiterez dérouler la boucle interne de manière à ce qu'elle fonctionne au maximum en 22 itérations, ce qui est un modèle pris / non pris suffisamment court pour que les prédicteurs de branche fonctionnent correctement. Dans mes expériences, mov cl, 22avant une .inner: dec cl/jnz .innerboucle, il y avait très peu de prédictions erronées (comme 0,05%, bien moins d'un par cycle complet de la boucle interne), mais mov cl,23de 0,35 à 0,6 fois par boucle interne. 46est particulièrement mauvais, avec une prévision erronée d’environ 1,28 fois par boucle interne (128 millions de fois pour 100 itérations de boucle externe). 114erroné, exactement une fois par boucle intérieure, comme dans la boucle de Fibonacci.

Je suis devenu curieux et j'ai essayé, déroulant la boucle intérieure de 6 avec un %rep 6(parce que cela divise 114 uniformément). Cela a pour la plupart éliminé les échecs de branche. J'ai fait edxnégatif et utilisé comme compensation pour les movmagasins, donc adc eax,[edi]je pouvais rester micro-fusionné. (Et donc je pourrais éviter stosd). J'ai tiré le leapour mettre à jour edihors du %repbloc, donc il ne fait qu'un pointeur-mise à jour pour 6 magasins.

Je me suis également débarrassé de tout ce qui concerne les registres partiels dans la boucle externe, bien que je ne pense pas que cela soit significatif. Il aurait peut-être été utile que la fin de la boucle externe ne soit pas dépendante de l'ADC final, de sorte que certaines des boucles internes puissent être démarrées. Le code de la boucle extérieure pourrait probablement être optimisé un peu plus, car neg edxc’était la dernière chose que j’ai faite, après avoir remplacé xchgpar seulement 2 movinstructions (puisque j’en avais déjà une) et réorganisé les chaînes dep avec suppression du code 8 bits. enregistrer des choses.

C’est la source NASM de la boucle de Fibonacci. C'est un remplacement instantané de cette section de la version d'origine.

  ;;;; 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

Performance:

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

C'est pour la même Fib (1G), produisant la même sortie en 62,3 secondes au lieu de 73 secondes. (273,146 G, contre 322,467 G. Puisque tout se trouve dans le cache N1, les cycles d’horloge de base sont tout ce que nous devons examiner.)

Notez le uops_issuednombre total beaucoup plus bas , bien en dessous du uops_executednombre. Cela signifie que beaucoup d'entre eux étaient micro-fusionnés: 1 uop dans le domaine fusionné (issue / ROB), mais 2 uops dans le domaine non fusionné (planificateur / unités d'exécution)). Et ces quelques-uns ont été éliminés à l'étape d'émission / de changement de nom (comme la movcopie de registre ou la xorréduction à zéro, qui doivent être émises mais n'ont pas besoin d'une unité d'exécution). Les uops éliminés déséquilibreraient le compte dans l'autre sens.

branch-missesest descendu à ~ 400k, à partir de 1G, donc le déroulement a fonctionné. resource_stalls.anyest important maintenant, ce qui signifie que le front-end n'est plus le goulot d'étranglement: au lieu de cela, le back-end prend du retard et limite le front-end. idq_uops_not_delivered.corene compte que les cycles où le front-end n’a pas livré de bonus, mais que le back-end n’a pas été bloqué. C'est bon et bas, indiquant peu de goulots d'étranglement au début.

Fait amusant: la version en python passe plus de la moitié de son temps à être divisée par 10 au lieu d’ajouter. (Remplacer par a/=10par a>>=64accélère de plus d'un facteur 2, mais modifie le résultat car troncature binaire! = Troncature décimale.)

Ma version asm est bien sûr optimisée spécifiquement pour cette taille de problème, avec la boucle itération-compte codée en dur. Même déplacer un nombre de précision arbitraire le copiera, mais ma version peut simplement lire à partir d'un décalage pour les deux itérations suivantes, même pour ignorer cela.

J'ai profilé la version de python (python2.7 64 bits sur 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

Les nombres entre parenthèses indiquent combien de temps le compteur de perf était échantillonné. Quand on regarde plus de pions que le matériel ne supporte, perf tourne entre les pions différents et extrapole. C'est tout à fait bien pour une longue période de la même tâche.

Si je courais perfaprès avoir paramétré sysctl kernel.perf_event_paranoid = 0(ou en perftant que root), cela se mesurerait 4.400GHz. cycles:une compte pas le temps passé dans les interruptions (ou les appels système), mais uniquement les cycles de l'espace utilisateur. Mon bureau était presque totalement inactif, mais c'est typique.

Haskell, 83 61 octets

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)

Les sorties ( F _1000000000 , F _1000000001 ). Sur mon ordinateur portable, il imprime correctement le paren gauche et les 1000 premiers chiffres en 133 secondes, en utilisant 1,35 Go de mémoire.

Comment ça fonctionne

La récurrence de Fibonacci peut être résolue à l'aide de l'exponentiation matricielle:

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

d'où proviennent ces identités:

[ 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 ; 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} .

La pfonction calcule ( F _{i + j} , F _{i + j + 1} ) donnée ( F _i , F _{i + 1} ) et ( F _j , F _{j + 1} ). En écrivant f npour ( F _i , F _{i + 1} ), nous avons p (f i) (f j)= f (i + j).

Ensuite,

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

et on branche f 1= (1,1).

Mathematica, 15 34 octets

Fibonacci lui-même prend ~ 6s sur mon ordinateur. Et 95 (+/- 5) s pour le frontend pour l'afficher.

Fibonacci@1*^9&

Les 1000 premiers chiffres (34 octets): ⌊Fibonacci@1*^9/1*^208986640⌋&

Plus long mais plus rapide ToString@Fibonacci@1*^9~StringTake~1000&:

Python 2, 70 octets

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

Cela a fonctionné en 18 minutes et 31 secondes sur mon ordinateur portable, produisant les 1000 chiffres corrects suivis de 74100118580(les chiffres suivants corrects sont 74248787892).

Haskell , 78 octets

(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

Essayez-le en ligne!

A pris 48 secondes sur TIO. Même formule récursive que ma réponse Python , mais sans tronquer.

La constante 2143923439est 10**9-1inversée en binaire et avec un extra à la fin. Itérer entre ses chiffres binaires en sens inverse simule l’itération entre les chiffres binaires de 10**9-1. Il semble plus court de coder ceci que de le calculer.

Haskell , 202 184 174 173 170 170 168 164 162 octets

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

Essayez-le en ligne!

Explication

Cela utilise un moyen assez rapide pour calculer les nombres de fibonacci. La fonction lprend deux nombres de Fibonacci et calcule les nombres de Fibonacci 10 plus tard, alors que fprend la n ième et n + 1 ième nombres de Fibonacci et calcule la 2n + 20 e et 2n + 21 ième nombres de Fibonacci. Je les enchaîne plutôt au hasard pour obtenir 1 milliard et saisir les 1000 premiers chiffres.

Haskell, 81 octets

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

Explication

f ncalcule récursivement le nnombre th de fibonacci en utilisant la récurrence de la réponse de xnor avec élimination de la sous-expression commune. Contrairement aux autres solutions publiées, qui utilisent des multiplications O (log (n)), nous avons une récursion O (log (n)) - profondeur avec un facteur de ramification de 2, pour une complexité de multiplications O (n).

Cependant, tout n'est pas perdu! Comme presque tous les appels se trouveront au bas de l’arbre de récursivité, nous pouvons utiliser l’arithmétique native rapide dans la mesure du possible et éviter de nombreuses manipulations d’énormes bignums. Il crache une réponse en quelques minutes sur ma boîte.

T-SQL, 422 414 453 octets (vérifié, en compétition maintenant!)

EDIT 2 : changé en , gagné quelques octets mais vitesse accrue pour compléter à 1 milliard! Terminé en 45 heures 29 minutes , vérifie par rapport à la chaîne donnée et affiche 8 caractères supplémentaires (qui peuvent ou non être corrects en raison d'erreurs d'arrondi).INT BIGINT DECIMAL(37,0)

T-SQL n'a pas de support natif pour les "nombres énormes", il a donc fallu lancer mon propre additionneur de nombres énormes à base de texte en utilisant des chaînes de 1008 caractères:

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 @

Voici la version formatée avec des commentaires:

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 @

En gros, je manipule manuellement des chaînes remplies de zéros de 1008 caractères représentant mes deux variables de Fibonacci, @aet @.

Je les additionne 8 18 36 chiffres à la fois, en enlevant les 36 derniers chiffres, en les convertissant en un type numérique gérable ( DECIMAL(37,0)), en les additionnant, puis en les écrasant dans une autre longue chaîne @c. Je «tourne» ensuite @a, @en déplaçant les 36 derniers chiffres vers l'avant et en répétant le processus. 28 rotations * 36 chiffres couvrent la totalité des 1008. Je dois "porter celui-ci" manuellement.

Une fois que notre nombre commence à dépasser la longueur de ma chaîne, je "décale à gauche" et nous commençons à perdre de la précision, mais l'erreur se situe bien dans mes caractères supplémentaires.

J'ai essayé d'utiliser une table SQL contenant des INT et des BIGINT, avec une logique similaire, et elle était considérablement plus lente. Bizarre.

PARI / GP, 45 octets

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

D'une certaine manière \p1000n'est pas suffisant. Cela ne fonctionne pas avec les systèmes 32 bits. La division finale consiste à éviter le point décimal de la notation scientifique.

Pari / GP , 15 + 5 = 20 octets

fibonacci(10^9)

Exécuter avec l'option de ligne de commande -s1gpour allouer 1 Go de mémoire.

Ruby, 63 octets

mec, je suis mauvais au golf ruby; mais la classe BigInt fait des merveilles pour ce genre de choses. Nous utilisons le même algorithme que Anders Kaseorg.

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