Es gab eine Milliarde Iterationen von Fibonacci-Herausforderungen auf dieser Website. Lassen Sie uns die Dinge mit einer Fibonacci-Herausforderung von einer Milliarde Iterationen aufpeppen!

Ihre Herausforderung besteht darin, die ersten 1000 Dezimalstellen der 1.000.000.000sten Fibonacci-Zahl mit einem möglichst kurzen Programm auszugeben. Darauf kann optional eine zusätzliche Ausgabe Ihrer Wahl folgen, einschließlich, aber nicht beschränkt auf den Rest der Ziffern.

Ich bin mit dem Kongress , dass fib 0 = 0, fib 1 = 1.

Ihr Programm muss schnell genug sein, damit Sie es ausführen und seine Richtigkeit überprüfen können. Zu diesem Zweck sind hier die ersten 1000 Stellen:

7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799

Python 2 + Sympy, 72 Bytes

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

Probieren Sie es online!

-10 Bytes durch Entfernen des praktisch-0-Terms dank Jeff Dege
-1 Bytes (1000 -> 1e3 dank Zacharý)
-2 Bytes durch Entfernen der unnötigen Variablen dank Erik the Outgolfer
-2 Bytes durch Verschieben nach Python 2 dank Zacharý
-3 Bytes durch 11'ing den -11Dank an ThePirateBay -3 Bytes durch Austausch strfür Backticks dank Notjagan

schlägt jetzt OPs ungepostete Haskell-Lösung!

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

Probieren Sie es online!

Keine Bibliotheken, nur ganzzahlige Arithmetik. Läuft fast sofort.

Der Kern ist die Divide-and-Conquer-Identität:

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

Auf diese Weise können wir das Update (a,b) = (f(n),f(n+1))auf das Doppelte durchführen n -> 2*n. Da wir bekommen wollen n=10**9, dauert dies nur log_2(10**9)=30Iterationen. Wir bauen darauf nauf, 10**9indem wir n->2*n+cfür jede Ziffer cihrer binären Expansion wiederholt tun . Wenn c==1wird der doppelte Wert 2*n -> 2*n+1mit einer einstufigen Fibonacci-Verschiebung nach oben verschoben(a,b)=(b+a,b)

Um die Werte a,büberschaubar zu halten , speichern wir nur die ersten 1006Ziffern, indem wir sie durch teilen, 10bis sie darunter liegen 2**3340 ~ 1e1006.

x86-32-Bit-Maschinencode (bei Linux-Systemaufrufen): 106 bis 105 Byte

Changelog: In der schnellen Version wurde ein Byte gespeichert, da eine Off-by-One-Konstante das Ergebnis für Fib (1G) nicht ändert.

Oder 102 Bytes für eine 18% langsamere (bei Skylake) Version (Verwenden von mov/ sub/ cmcanstelle von lea/ cmpin der inneren Schleife, um Übertragen und Umbrechen zu generieren, 10**9anstatt 2**32). Oder 101 Bytes für eine ~ 5,3x langsamere Version mit einer Verzweigung im Carry-Handling in der innersten Schleife. (Ich habe eine Rate von 25,4% für Branchenfehlprognosen gemessen!)

Oder 104/101 Bytes, wenn eine führende Null zulässig ist. (Es dauert 1 zusätzliches Byte, um eine Stelle der Ausgabe mit festem Code zu überspringen, was für Fib (10 ** 9) erforderlich ist.)

Leider scheint der NASM-Modus von TIO -felf32in den Compiler-Flags zu ignorieren . Hier ist sowieso ein Link mit meinem vollständigen Quellcode, mit all dem Durcheinander an experimentellen Ideen in Kommentaren.

Dies ist ein vollständiges Programm . Es werden die ersten 1000 Stellen von Fib (10 ** 9) gedruckt, gefolgt von einigen zusätzlichen Stellen (von denen die letzten falsch sind), gefolgt von einigen Müllbytes (ohne Zeilenvorschub). Der größte Teil des Mülls ist kein ASCII-Speicher, daher möchten Sie möglicherweise eine Pipe-Funktion ausführen cat -v. Mein Terminalemulator (KDE konsole) wird dadurch jedoch nicht beschädigt. Die "Garbage Bytes" speichern Fib (999999999). Ich hatte bereits -1024in einem Register, so war es billiger, 1024 Bytes als die richtige Größe zu drucken.

Ich zähle nur den Maschinencode (Größe des Textsegments meiner statischen ausführbaren Datei) und nicht die Flusen, die sie zu einer ausführbaren ELF-Datei machen. ( Sehr kleine ELF-Programme sind möglich , aber ich wollte mich nicht darum kümmern). Es stellte sich heraus, dass es kürzer war, Stack-Speicher anstelle von BSS zu verwenden, sodass ich irgendwie rechtfertigen kann, nichts anderes in der Binärdatei zu zählen, da ich nicht von Metadaten abhängig bin. (Die normale Erzeugung einer statischen Binärdatei macht eine ELF mit 340 Byte ausführbar.)

Sie könnten aus diesem Code eine Funktion machen, die Sie von C aus aufrufen könnten. Das Speichern / Wiederherstellen des Stapelzeigers (möglicherweise in einem MMX-Register) und eines anderen Overheads würde einige Bytes kosten, aber auch Bytes, indem Sie mit der Zeichenfolge zurückkehren im Speicher, anstatt einen write(1,buf,len)Systemaufruf zu tätigen. Ich denke, das Golfen mit Maschinencode sollte hier ein wenig nachlassen, da noch niemand eine Antwort in einer Sprache ohne native Extended-Precision gepostet hat, aber ich denke, eine Funktionsversion davon sollte immer noch unter 120 Bytes sein, ohne das Ganze erneut zu golfen Ding.

Algorithmus:

Brute Force a+=b; swap(a,b), die nach Bedarf abgeschnitten wird, um nur die führenden Dezimalstellen> = 1017 beizubehalten. Es läuft in 1min13s auf meinem Computer (oder 322,47 Milliarden Taktzyklen + - 0,05%) (und könnte mit ein paar zusätzlichen Bytes Codegröße ein paar% schneller sein, oder bis zu 62s mit viel größerer Codegröße durch das Abrollen der Schleife. Nr kluge Mathematik, die gleiche Arbeit mit weniger Aufwand machen). Es basiert auf der Python-Implementierung von @ AndersKaseorg , die in 12 Minuten auf meinem Computer ausgeführt wird (4,4 GHz Skylake i7-6700k). Keine der beiden Versionen hat L1D-Cache-Fehler, daher spielt mein DDR4-2666 keine Rolle.

Im Gegensatz zu Python speichere ich die Zahlen mit erweiterter Genauigkeit in einem Format, das das Abschneiden von Dezimalstellen freigibt . Ich speichere Gruppen mit 9 Dezimalstellen pro 32-Bit-Ganzzahl, sodass ein Zeiger-Offset die niedrigen 9 Stellen verwirft. Dies ist effektiv die Basis 1 Milliarde, was einer Potenz von 10 entspricht. (Es ist reiner Zufall, dass diese Herausforderung die 1 Milliarde Fibonacci-Zahl benötigt, aber es erspart mir ein paar Bytes gegenüber zwei separaten Konstanten.)

Gemäß der GMP- Terminologie wird jeder 32-Bit-Block einer Zahl mit erweiterter Genauigkeit als "Glied" bezeichnet. Die Ausführung während des Hinzufügens muss manuell mit einem Vergleich gegen 1e9 erzeugt werden, wird dann aber normalerweise als Eingabe für die übliche ADCAnweisung für die nächste Gliedmaße verwendet. (Ich muss auch manuell auf den [0..999999999]Bereich umbrechen, anstatt auf 2 ^ 32 ~ = 4.295e9. Ich mache dies ohne Verzweigung mit lea+ cmov, wobei ich das Ergebnis des Vergleichs verwende.)

Wenn das letzte Glied einen Übertrag ungleich Null erzeugt, werden die nächsten zwei Iterationen der äußeren Schleife von einem Glied höher als normal gelesen, aber immer noch an dieselbe Stelle geschrieben. Dies entspricht einer memcpy(a, a+4, 114*4)Verschiebung um 1 Glied nach rechts, wird jedoch als Teil der nächsten beiden Additionsschleifen ausgeführt. Dies geschieht alle ~ 18 Iterationen.

Hacks für Größenersparnis und Leistung:

• Das übliche Zeug wie lea ebx, [eax-4 + 1]statt mov ebx, 1, wenn ich das weiß eax=4. Und loopan Orten, an denen LOOPLangsamkeit nur einen geringen Einfluss hat.

• Kürzen Sie kostenlos um 1 Glied, indem Sie die Zeiger, von denen wir lesen, versetzen, während Sie weiterhin an den Anfang des Puffers in der adcinneren Schleife schreiben . Wir lesen aus [edi+edx]und schreiben an [edi]. So können wir einen Lese-Schreib-Offset für das Ziel erhalten edx=0oder 4erhalten. Wir müssen dies für 2 aufeinanderfolgende Iterationen tun, indem wir zuerst beide und dann nur den dst versetzen. Wir erkennen den 2. Fall, indem wir esp&4vor dem Zurücksetzen der Zeiger auf die Vorderseite der Puffer (mit &= -1024, weil die Puffer ausgerichtet sind) schauen . Siehe Kommentare im Code.

• Die Linux-Prozessstartumgebung (für eine statische ausführbare Datei) setzt die meisten Register auf Null , und der Stapelspeicher unter esp/ rspwird auf Null gesetzt. Mein Programm nutzt dies aus. In einer Version mit aufrufbaren Funktionen (bei der der nicht zugewiesene Stapel möglicherweise fehlerhaft ist) könnte ich BSS für die Nullsetzung des Speichers verwenden (auf Kosten von möglicherweise 4 weiteren Bytes zum Einrichten von Zeigern). Das Nullsetzen edxwürde 2 Bytes dauern. Die x86-64-System-V-ABI garantiert keines davon, aber die Linux-Implementierung macht null (um Informationslecks aus dem Kernel zu vermeiden). Wird in einem dynamisch verknüpften Prozess /lib/ld.sozuvor ausgeführt _startund hinterlässt Register ungleich Null (und möglicherweise Speicherabfall unterhalb des Stapelzeigers).

• Ich halte -1024in ebxfür den Einsatz außerhalb von Schleifen. Verwendung blals Zähler für innere Schleifen, die auf Null enden (das ist das niedrige Byte von -1024, wodurch die Konstante für die Verwendung außerhalb der Schleife wiederhergestellt wird). Intel Haswell und neuere Versionen haben keine Nachteile für das Zusammenführen von Teilregistern für Low8-Register (und benennen sie auch nicht separat um). Daher besteht eine Abhängigkeit vom vollständigen Register wie bei AMD (hier kein Problem). Dies wäre jedoch für Nehalem und frühere Versionen schrecklich, da diese beim Zusammenführen teilweise Registerstände aufweisen. Es gibt andere Stellen, an denen ich xorTeilregs schreibe und dann die vollständige Reg ohne -Zeroing oder a lesemovzxIn der Regel, weil ich weiß, dass vorheriger Code die oberen Bytes auf Null gesetzt hat, und das ist bei AMD und der Intel SnB-Familie in Ordnung, bei Intel vor Sandybridge jedoch langsam.

  Ich benutze 1024als Anzahl der Bytes, um in stdout ( sub edx, ebx) zu schreiben , also druckt mein Programm einige Müllbytes nach den Fibonacci-Ziffern, weil es mov edx, 1000mehr Bytes kostet.

• (nicht verwendet) adc ebx,ebxmit EBX = 0, um EBX = CF zu erhalten und 1 Byte gegenüber setc bl.

• dec/ jnzinside Eine adcSchleife bewahrt CF, ohne dass es beim adcLesen von Flags auf Intel Sandybridge und höher zu einem partiellen Flag- Stillstand kommt. Es ist schlecht auf früheren CPUs , aber AFAIK kostenlos auf Skylake. Oder im schlimmsten Fall eine Extragebühr.

• Verwenden Sie den folgenden Speicher espals riesige rote Zone . Da es sich um ein vollständiges Linux-Programm handelt, habe ich keine Signal-Handler installiert, und nichts anderes wird den Stapelspeicher des Benutzerraums asynchron belasten. Dies ist bei anderen Betriebssystemen möglicherweise nicht der Fall.

• Nutzen Sie die Stack-Engine , um die Bandbreite des UOP-Problems zu verringern, indem Sie pop eax(1 UOP + gelegentliches Stack-Sync-UOP) anstelle von lodsd(2 UOP bei Haswell / Skylake, 3 bei IvB und früher gemäß den Anweisungen von Agner Fog ) verwenden. IIRC, dies verringerte die Laufzeit von ungefähr 83 Sekunden auf 73. Ich könnte wahrscheinlich die gleiche Geschwindigkeit erzielen, wenn ich einen movmit einem Index versehenen Adressierungsmodus verwende, etwa mov eax, [edi+ebp]wenn ebpder Versatz zwischen src- und dst-Puffern gehalten wird. (Dies würde den Code außerhalb der inneren Schleife komplexer machen und das Offset-Register als Teil des Austauschs von src und dst für Fibonacci-Iterationen negieren.) Weitere Informationen finden Sie im Abschnitt "Leistung" weiter unten.

• Starten Sie die Sequenz, indem Sie der ersten Iteration einen Übertrag (ein Byte stc) zuweisen , anstatt sie 1irgendwo im Speicher abzulegen. Viele andere problemspezifische Dinge sind in Kommentaren dokumentiert.

NASM-Auflistung (Maschinencode + Quelle) , generiert mit nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Dann habe ich einige kommentierte Blöcke von Hand entfernt, damit die Zeilennummerierung Lücken aufweist.) Verwenden Sie, um die führenden Spalten auszublenden, damit Sie sie in YASM oder NASM einspeisen können 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

Es gibt wahrscheinlich Platz, um ein paar Bytes mehr Golf zu spielen, aber ich habe bereits über 2 Tage mindestens 12 Stunden damit verbracht. Ich möchte nicht auf Geschwindigkeit verzichten, obwohl es viel mehr als schnell genug ist und es Raum gibt, es auf eine Weise zu verkleinern, die Geschwindigkeit kostet . Ein Grund für mein Posting ist, zu zeigen, wie schnell ich eine Brute-Force-Asm-Version erstellen kann. Wenn jemand wirklich die Mindestgröße anstreben möchte, aber vielleicht 10x langsamer (z. B. 1 Ziffer pro Byte), können Sie dies als Ausgangspunkt kopieren.

Die resultierende ausführbare Datei (von yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) ist 340B (entfernt):

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

Performance

Die innere adcSchleife besteht aus 10 Fused-Domain-Uops in Skylake (+1 Stack-Sync-Uop alle ~ 128 Bytes), sodass sie in Skylake mit optimalem Front-End-Durchsatz alle ~ 2,5 Zyklen ausgegeben werden kann (ohne Berücksichtigung der Stack-Sync-Uops). . Die Wartezeit auf dem kritischen Pfad beträgt 2 Zyklen für die durch die Schleife übertragene Abhängigkeitskette der adc-> cmp-> nächsten Iteration adc, sodass der Engpass das Front-End-Problemlimit von ~ 2,5 Zyklen pro Iteration sein sollte.

adc eax, [edi + edx]Es gibt 2 nicht fusionierte Domänen-Uops für die Ausführungsports: load + ALU. Er ist in den Decodern mit Mikrosicherungen versehen (1 UOP für verschmolzene Domänen), wird jedoch in der Ausgabephase aufgrund des indizierten Adressierungsmodus sogar in Haswell / Skylake auf 2 UOP für verschmolzene Domänen unlaminiert . Ich dachte, es würde mit add eax, [edi + edx]Mikrosicherungen verbunden bleiben , aber vielleicht funktioniert das Beibehalten der mit Mikrosicherungen verbundenen indizierten Adressierungsmodi nicht für Benutzeroberflächen, die bereits 3 Eingänge haben (Flags, Speicher und Ziel). Als ich es schrieb, dachte ich, es hätte keine Nachteile, aber ich habe mich geirrt. Diese Art der Behandlung von Kürzungen verlangsamt die innere Schleife jedes Mal, egal ob edx0 oder 4.

Es wäre schneller, den Lese-Schreib-Versatz für das dst zu handhaben, ediindem edxder Speicher versetzt und mit eingestellt wird . Also adc eax, [edi]/ ... / mov [edi+edx], eax/ lea edi, [edi+4]statt stosd. Haswell und später können einen indizierten Speicher mit einer Fusionssicherung versehen. (Sandybridge / IvB würden es auch unlaminieren.)

Auf Intel Haswell und früher adcund cmovcsind 2 Uops jeweils mit 2c Latenz . ( adc eax, [edi+edx]ist noch nicht auf Haswell laminiert und wird als 3 Fused-Domain-Ups ausgegeben). Broadwell und später erlauben 3-Input-Uops für mehr als nur FMA (Haswell), Erstellen adcund cmovc(und ein paar andere Dinge) Single-Uop-Anweisungen, wie sie schon lange bei AMD sind. (Dies ist einer der Gründe, warum AMD bei GMP-Benchmarks mit erweiterter Genauigkeit seit langem gute Ergebnisse erzielt.) Auf jeden Fall sollte die innere Schleife von Haswell 12 Uops (gelegentlich +1 Stack-Sync-Uops) mit einem Front-End-Engpass von ~ 3c pro Uops umfassen Im besten Fall ignorieren Sie Stack-Sync-Uops.

Die Verwendung popohne Ausgleich pushinnerhalb einer Schleife bedeutet, dass die Schleife nicht vom LSD (Loop Stream Detector) ausgeführt werden kann und jedes Mal neu aus dem UOP-Cache in den IDQ gelesen werden muss. Wenn überhaupt, ist es eine gute Sache bei Skylake, da eine 9- oder 10-Up-Schleife bei 4 Ups pro Zyklus nicht optimal funktioniert . Dies ist wahrscheinlich ein Grund, warum das Ersetzen lodsddurch popso viel geholfen hat. (Das LSD kann die Uops nicht sperren, da sonst kein Platz für ein Stack-Sync-Uop vorhanden ist .) ( Übrigens deaktiviert ein Mikrocode-Update das LSD vollständig auf Skylake und Skylake-X, um einen Fehler zu beheben. Ich habe das gemessen vor dem Update.)

Ich habe es auf Haswell profiliert und festgestellt, dass es in 381,31 Milliarden Taktzyklen läuft (unabhängig von der CPU-Frequenz, da es nur L1D-Cache verwendet, keinen Speicher). Der Durchsatz für Front-End-Probleme betrug 3,72 Fused-Domain-Ups pro Uhr gegenüber 3,70 für Skylake. (Aber natürlich waren die Instruktionen pro Zyklus von 2,87 auf 2,42 gesunken , weil adcund cmov2 Ups auf Haswell sind.)

pushzu ersetzen stosdwürde wahrscheinlich nicht so viel helfen, da adc [esp + edx]jedes Mal ein Stack-Sync-Up ausgelöst würde. Und würde ein Byte kosten, stddamit lodsdgeht die andere Richtung. ( mov [edi], eax/ lea edi, [edi+4]zu ersetzen stosdist ein Gewinn, der von 32.909Mcycles für 100M-Iter auf 31.954Mcycles für 100M-Iter steigt. Es scheint, dass die stosdDecodierung als 3 Uops erfolgt, wobei die Store-Adresse / Store-Daten-Uops nicht mikroverschmolzen sind, also push+ Stack-Sync uops könnte noch schneller sein als stosd)

Die tatsächliche Leistung von ~ 322,47 Milliarden Zyklen für 1G-Iterationen von 114 Gliedmaßen entspricht 2,824 Zyklen pro Iteration der inneren Schleife für die schnelle 105B-Version auf Skylake. (Siehe ocperf.pyAusgabe unten). Das ist langsamer als ich es aus der statischen Analyse vorhergesagt habe, aber ich habe den Overhead der äußeren Schleife und alle Stack-Sync-Ups ignoriert.

Perf-Zähler für branchesund branch-misseszeigen, dass die innere Schleife einmal pro äußere Schleife falsch voraussagt (bei der letzten Iteration, wenn sie nicht ausgeführt wird). Das macht auch einen Teil der Verlängerung aus.

Ich könnte Codegröße sparen, indem die innerste Schleife eine Latenzzeit von 3 Zyklen für den kritischen Pfad aufweist, indem ich mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) anstelle von lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B) verwende ). Das cmov/ stosdist aus dem kritischen Pfad. (Die inkrementelle Bearbeitung von stosdkann separat vom Speicher ausgeführt werden, sodass jede Iteration eine kurze Abhängigkeitskette ableitet.) Es wurde verwendet, um weitere 1B zu sparen, indem der Befehl ebp init von lea ebp, [ecx-1]auf geändert wurde mov ebp,eax, aber ich habe festgestellt, dass die falsche Anweisung vorliegtebphat das Ergebnis nicht verändert. Dies würde eine Gliedmaße genau == 1000000000 sein lassen, anstatt einen Übertrag einzuwickeln und zu erzeugen, aber dieser Fehler breitet sich langsamer aus, als wir Fib () wachsen. Dies ändert also nicht die führenden 1k-Stellen des Endergebnisses. Ich denke auch, dass sich der Fehler von selbst korrigieren kann, wenn wir ihn nur hinzufügen, da in einem Glied Platz ist, um ihn ohne Überlauf zu halten. Sogar 1G + 1G überläuft eine 32-Bit-Ganzzahl nicht, so dass sie irgendwann nach oben sickert oder abgeschnitten wird.

Die 3c-Latenz-Version kostet 1 zusätzlichen UOP, sodass das Front-End sie bei Skylake einmal pro 2,75c-Zyklen ausgeben kann, was nur geringfügig schneller ist, als das Back-End sie ausführen kann. (Auf Haswell werden es insgesamt 13 Uops sein, da es immer noch adcund verwendet cmov, und ein Engpass auf dem Front-End bei 3,25 c pro Iter).

In der Praxis läuft es auf Skylake um einen Faktor von 1,18 langsamer (3,34 Zyklen pro Glied) als 3 / 2,5 = 1,2, was ich vorhergesagt habe, um den Front-End-Engpass durch den Latenz-Engpass zu ersetzen, indem ich nur die innere Schleife ohne Stack-Sync betrachtete uops. Da die Stack-Sync-Ups nur der schnellen Version schaden (Engpass am Front-End anstelle von Latenz), ist es nicht sehr schwierig, dies zu erklären. zB 3 / 2,54 = 1,18.

Ein weiterer Faktor ist, dass die 3c-Latenz-Version möglicherweise den Fehler beim Verlassen der inneren Schleife erkennt, während der kritische Pfad noch ausgeführt wird (da das Front-End vor dem Back-End stehen kann und die Ausführung der Schleife außerhalb der Reihenfolge ausgeführt wird). counter uops), so dass die effektive Strafe für falsche Voraussagen geringer ist. Der Verlust dieser Front-End-Zyklen lässt das Back-End aufholen.

Wäre dies nicht cmcder Fall , könnten wir die 3c- Version möglicherweise beschleunigen, indem wir eine Verzweigung in der äußeren Schleife anstelle der verzweigungslosen Behandlung der Verschiebungen carry_out -> edx und esp verwenden. Die Verzweigungsvorhersage und die spekulative Ausführung für eine Steuerungsabhängigkeit anstelle einer Datenabhängigkeit können dazu führen, dass die nächste Iteration die adcSchleife ausführt, während sich die Uops der vorherigen inneren Schleife noch im Flug befinden. In der verzweigungslosen Version haben die Ladeadressen in der inneren Schleife eine Datenabhängigkeit von CF vom letzten adcder letzten Glieder.

Die 2c-Latenz-Inner-Loop-Version hat Engpässe im Front-End, sodass das Back-End so ziemlich mithält. Wenn der Code für die äußere Schleife eine hohe Latenz aufweist, kann das Front-End ab der nächsten Iteration der inneren Schleife Uops ausgeben. (Aber in diesem Fall hat das Outer-Loop-Material viel ILP und kein Material mit hoher Latenz, sodass das Back-End nicht viel Nachholbedarf hat, wenn es im Out-of-Order-Scheduler as durch Uops kaut ihre Eingaben werden fertig).

### 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 %)ist die Standardabweichung über die 4 Läufe für diese Zählung. Interessant, dass es so eine runde Anzahl von Anweisungen ausführt. Diese 924 Milliarden sind kein Zufall. Ich vermute, dass die äußere Schleife insgesamt 924 Anweisungen ausführt.

uops_issueduops_executedHierbei handelt es sich um eine Fused-Domain-Anzahl (relevant für die Bandbreite des Front-End-Problems), während es sich um eine Nicht-Fused-Domain-Anzahl handelt (Anzahl der an Ausführungsports gesendeten Uops). Micro-Fusion packt 2 nicht fusionierte Domänen-Uops in ein nicht fusioniertes Domänen-Uop, aber Mov-Elimination bedeutet, dass einige nicht fusionierte Domänen-Uops keine Ausführungsports benötigen. In der verknüpften Frage finden Sie weitere Informationen zum Zählen von "Uops" und "Fused" und "Unfused" -Domain. (Siehe auch die Anweisungstabellen und das Handbuch von Agner Fog sowie andere nützliche Links im SO x86-Tag-Wiki. )

Aus einem anderen Lauf, der verschiedene Dinge misst: L1D-Cache-Fehlschläge sind völlig unbedeutend, wie erwartet, um dieselben zwei 456B-Puffer zu lesen / schreiben. Der innere Schleifenzweig sagt einmal pro äußerer Schleife etwas falsch voraus (wenn es nicht erforderlich ist, die Schleife zu verlassen). (Die Gesamtzeit ist höher, da der Computer nicht vollständig im Leerlauf war. Wahrscheinlich war der andere logische Kern einige Zeit aktiv und es wurde mehr Zeit für Interrupts aufgewendet (da die vom Benutzer gemessene Frequenz weiter unter 4,400 GHz lag). Oder mehrere Kerne waren die meiste Zeit aktiv und senkten den maximalen Turbo. Ich habe nicht verfolgt cpu_clk_unhalted.one_thread_active, ob die HT-Konkurrenz ein Problem war.)

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

Mein Code kann auf Ryzen in weniger Zyklen ausgeführt werden, wodurch 5 Uops pro Zyklus ausgegeben werden können (oder 6, wenn es sich bei einigen von ihnen um 2-Uops-Anweisungen handelt, wie z. B. AVX 256b-Dateien auf Ryzen). Ich bin mir nicht sicher, was das Front-End damit stosdanfangen würde , das sind 3 Ups auf Ryzen (genau wie Intel). Ich denke, die anderen Anweisungen in der inneren Schleife sind die gleiche Latenz wie Skylake und alle Single-UOP. (Einschließlich adc eax, [edi+edx], was ein Vorteil gegenüber Skylake ist).

Dies könnte wahrscheinlich deutlich kleiner sein, aber vielleicht 9x langsamer, wenn ich die Zahlen als 1 Dezimalstelle pro Byte gespeichert habe . Das Erzeugen von Carry-Outs cmpund das Anpassen von Carry-Outs mit cmovwürde genauso funktionieren, aber 1/9 der Arbeit erledigen. 2 Dezimalstellen pro Byte (Base-100, nicht 4-Bit-BCD mit einer langsamenDAA ) würden ebenfalls funktionieren, und div r8/ add ax, 0x3030wandelt ein 0-99-Byte in der Druckreihenfolge in zwei ASCII-Stellen um. Eine Ziffer pro Byte ist jedoch nicht erforderlich. Sie divmüssen lediglich eine Schleife ausführen und 0x30 hinzufügen. Wenn ich die Bytes in Druckreihenfolge speichere, würde das die 2. Schleife wirklich einfach machen.

Die Verwendung von 18 oder 19 Dezimalstellen pro 64-Bit-Ganzzahl (im 64-Bit-Modus) würde die Geschwindigkeit etwa verdoppeln, jedoch die Codegröße für alle REX-Präfixe und für 64-Bit-Konstanten erheblich beeinträchtigen. 32-Bit-Zweige im 64-Bit-Modus verhindern die Verwendung von pop eaxanstelle von lodsd. Ich könnte immer noch REX-Präfixe vermeiden, indem ich espein Nicht-Zeiger-Scratch-Register verwende (wobei die Verwendung von esiund vertauscht wird esp), anstatt es r8dals 8. Register zu verwenden.

Wenn Sie eine Callable-Function-Version r8derstellen , ist die Konvertierung in 64-Bit und die Verwendung möglicherweise billiger als das Speichern / Wiederherstellen rsp. 64-Bit kann die Ein-Byte- dec r32Codierung auch nicht verwenden (da es sich um ein REX-Präfix handelt). Aber meistens habe ich dec bl2 Bytes benutzt. (Weil ich eine Konstante in den oberen Bytes von habe ebxund sie nur außerhalb der inneren Schleifen verwende, was funktioniert, weil das untere Byte der Konstante ist 0x00.)

Hochleistungsversion

Für maximale Leistung (nicht Code-Golf) sollten Sie die innere Schleife ausrollen, damit sie höchstens 22 Iterationen durchläuft. Dies ist ein kurz genug gewähltes / nicht gewähltes Muster, damit die Verzweigungsvorhersagen gut abschneiden können. In meinen Experimenten hat mov cl, 22eine .inner: dec cl/jnz .innerSchleife nur sehr wenige falsche Vorhersagen (wie 0,05%, weit weniger als eine pro vollem Lauf der inneren Schleife), aber mov cl,23falsche Vorhersagen vom 0,35- bis 0,6-fachen pro innerer Schleife. 46ist besonders schlimm, da es ~ 1,28-mal pro innerer Schleife falsch vorhersagt (128-mal für 100-mal äußere Schleifeniterationen). 114genau einmal pro innerer Schleife falsch vorhergesagt, so wie ich es als Teil der Fibonacci-Schleife fand.

Ich wurde neugierig und versuchte es, indem ich die innere Schleife mit einem 6 abrollte %rep 6(weil das 114 gleichmäßig teilt). Damit wurden Branch-Misses größtenteils beseitigt. Ich habe ein edxNegativ gemacht und es als Offset für movLäden verwendet, damit adc eax,[edi]es mit dem Mikro verschmolzen bleibt. (Und so konnte ich es vermeiden stosd). Ich habe das leazu aktualisierende ediElement aus dem %repBlock gezogen, sodass es nur ein Zeiger-Update pro 6 Speicher ausführt .

Ich habe auch all das Teilregister-Zeug in der äußeren Schleife losgeworden, obwohl ich denke, dass das nicht signifikant war. Möglicherweise hat es etwas geholfen, dass CF am Ende der äußeren Schleife nicht vom endgültigen ADC abhängt, sodass einige der Uops der inneren Schleife gestartet werden können. Der Outer-Loop-Code könnte wahrscheinlich ein bisschen weiter optimiert werden, da neg edxich das letzte Mal nach dem Ersetzen xchgdurch nur 2 movAnweisungen (da ich bereits 1 hatte) und dem Neuanordnen der Dep-Ketten und dem Löschen der 8-Bit-Anweisungen tat Zeug registrieren.

Dies ist die NASM-Quelle nur der Fibonacci-Schleife. Es ist ein direkter Ersatz für diesen Abschnitt der Originalversion.

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

Das ist für die gleiche Fib (1G), was die gleiche Ausgabe in 62,3 Sekunden anstelle von 73 Sekunden ergibt. (273.146G Zyklen gegenüber 322.467G. Da im L1-Cache alles zutrifft, müssen wir uns nur die Kerntaktzyklen ansehen.)

Beachten Sie die viel niedrigere Gesamtanzahl uops_issued, die deutlich unter der uops_executedAnzahl liegt. Das bedeutet, dass viele von ihnen mikrofusioniert waren: 1 UOP in der fusionierten Domäne (Issue / ROB), aber 2 UOP in der nicht fusionierten Domäne (Scheduler / Ausführungseinheiten). Und diese wenigen wurden in der Phase der Ausgabe / Umbenennung beseitigt (wie movdas Kopieren von Registern oderxor Ausgabe- -Nullsetzen, die ausgegeben werden müssen, aber keine Ausführungseinheit benötigen). Eliminierte Ups würden die Zählung auf die andere Weise aus dem Gleichgewicht bringen.

branch-missesist auf ~ 400k gesunken, von 1G, also hat das Abrollen funktioniert. resource_stalls.anyDies bedeutet, dass das Front-End nicht mehr der Engpass ist, sondern dass das Back-End in Verzug gerät und das Front-End einschränkt. idq_uops_not_delivered.coreZählt nur Zyklen, in denen das Front-End keine Ups lieferte, das Back-End jedoch nicht blockiert war. Das ist nett und niedrig, was auf wenige Front-End-Engpässe hindeutet.

Witzige Tatsache: Die Python-Version verbringt mehr als die Hälfte ihrer Zeit damit, durch 10 zu dividieren, anstatt sie zu addieren. (Ersetzen der a/=10mita>>=64 Geschwindigkeit um mehr als den Faktor 2 erhöht, das Ergebnis wird jedoch geändert, da binäre Kürzung! = Dezimaltrennung.)

Meine asm-Version ist natürlich speziell für diese Problemgröße optimiert, wobei die Anzahl der Schleifeniterationen fest codiert ist. Selbst das Verschieben einer Zahl mit willkürlicher Genauigkeit kopiert sie, aber meine Version kann nur von einem Versatz für die nächsten zwei Iterationen lesen, um auch das zu überspringen.

Ich habe die Python-Version (64-Bit-Python2.7 unter Arch Linux) profiliert :

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

Die Zahlen in (parens) geben an, wie oft der Perf-Counter abgetastet wurde. Wenn Sie mehr Zähler als die von HW unterstützten anzeigen, wechselt perf zwischen verschiedenen Zählern und Extrapolaten. Das ist völlig in Ordnung für einen langen Zeitraum der gleichen Aufgabe.

Wenn ich perfnach dem Setzen von sysctl kernel.perf_event_paranoid = 0(oder perfals root) lief, würde es messen 4.400GHz. cycles:uZählt nicht die Zeit, die in Interrupts (oder Systemaufrufen) verbracht wurde, sondern nur Benutzerbereichszyklen. Mein Desktop war fast leer, aber das ist typisch.

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)

Ausgänge ( F _1000000000 , F _1000000001 ). Auf meinem Laptop werden der linke Teil und die ersten 1000 Stellen innerhalb von 133 Sekunden mit 1,35 GB Speicher korrekt gedruckt.

Wie es funktioniert

Das Fibonacci-Rezidiv kann durch Matrixexponentiation gelöst werden:

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

von denen leiten wir diese Identitäten ab:

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

Die pFunktion berechnet ( F _{i + j} , F _{i + j + 1} ) gegeben ( F _i , F _{i + 1} ) und ( F _j , F _{j + 1} ). Wenn wir f nfür ( F _i , F _{i + 1} ) schreiben , haben wir p (f i) (f j)= f (i + j).

Dann,

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

und wir stecken ein f 1= (1,1).

Mathematica, 15 34 Bytes

Fibonacci selbst dauert ~ 6s auf meinem Computer. Und 95 (+/- 5) s für das Frontend, um es anzuzeigen.

Fibonacci@1*^9&

Die ersten 1000 Stellen (34 Bytes): ⌊Fibonacci@1*^9/1*^208986640⌋&

Länger aber schneller 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

Dies lief in 18 Minuten und 31 Sekunden auf meinem Laptop und ergab die richtigen 1000 Ziffern, gefolgt von 74100118580(die richtigen folgenden Ziffern sind 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

Probieren Sie es online!

Hat 48 Sekunden mit TIO gedauert. Dieselbe rekursive Formel wie meine Python-Antwort , jedoch ohne Kürzung.

Die Konstante 2143923439ist 10**9-1binär umgekehrt und mit einer zusätzlichen 1 am Ende. Das umgekehrte Durchlaufen der Binärziffern simuliert das Durchlaufen der Binärziffern von 10**9-1. Es scheint kürzer zu sein, dies fest zu codieren, als es zu berechnen.

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)

Probieren Sie es online!

Erläuterung

Dies verwendet eine relativ schnelle Methode zur Berechnung von Fibonacci-Zahlen. Die Funktion lnimmt zwei Fibonacci-Zahlen und berechnet die Fibonacci-Zahlen 10 später, während sie fdie n- ten und n + 1- ten Fibonacci-Zahlen und die 2n + 20- ten und 2n + 21- ten Fibonacci-Zahlen berechnet. Ich kette sie ziemlich willkürlich an, um 1 Milliarde zu bekommen und die ersten 1000 Ziffern zu bekommen.

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

Erläuterung

f nBerechnet rekursiv die nth Fibonacci-Zahl unter Verwendung der Wiederholung aus der Antwort von xnor mit Eliminierung von gemeinsamen Unterausdrücken. Im Gegensatz zu den anderen Lösungen, die O (log (n)) -Multiplikationen verwenden, haben wir eine O (log (n)) - Tiefenrekursion mit einem Verzweigungsfaktor von 2 für eine Komplexität von O (n) -Multiplikationen.

Es ist jedoch nicht alles verloren! Da sich fast alle Aufrufe in der Nähe des unteren Randes des Rekursionsbaums befinden, können wir, wo immer möglich, eine schnelle native Arithmetik verwenden und viele Manipulationen an riesigen Bignums vermeiden. Es spuckt in ein paar Minuten eine Antwort auf meine Box aus.

T-SQL, 422 414 453 Bytes (Verifiziert, jetzt im Wettbewerb!)

BEARBEITUNG 2 : Geändert zu : Erhielt ein paar Bytes, erhöhte aber die Geschwindigkeit auf 1 Milliarde! Wird in 45 Stunden und 29 Minuten ausgeführt , überprüft die Eingabe anhand der angegebenen Zeichenfolge und zeigt zusätzliche 8 Zeichen an (was aufgrund von Rundungsfehlern möglicherweise nicht richtig ist).INT BIGINT DECIMAL(37,0)

T-SQL hat keine native Unterstützung für "Riesen-Zahlen" und musste daher meinen eigenen textbasierten Riesen-Zahlen-Addierer mit 1008-Zeichen-Strings rollen:

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 @

Hier ist die formatierte Version mit Kommentaren:

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 @

Grundsätzlich bearbeite ich 1008 Zeichen lange, mit Nullen gefüllte Zeichenfolgen, die meine beiden Fibonacci-Variablen darstellen, @aund @.

Ich füge sie 8 bis 18 mal 36 Ziffern gleichzeitig hinzu, indem ich die letzten 36 Ziffern entferne, in einen überschaubaren numerischen Typ ( DECIMAL(37,0)) umwandle, sie addiere und dann wieder in eine andere lange Zeichenkette zerschmettere @c. Ich "drehe" dann @aund @indem ich die letzten 36 Stellen nach vorne schiebe und den Vorgang wiederhole. 28 Umdrehungen * 36 Stellen decken alle 1008 ab. Ich muss die "eine" manuell tragen.

Sobald unsere Zahl meine Stringlänge überschreitet, "verschiebe" ich mich nach links und wir verlieren etwas an Präzision, aber der Fehler liegt gut in meinen zusätzlichen Zeichen.

Ich habe versucht, eine SQL-Tabelle voller INTs und BIGINTs mit ähnlicher Logik zu verwenden, und sie war dramatisch langsamer. Seltsam.

PARI / GP, 45 Bytes

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

Irgendwie reicht \p1000das nicht. Dies funktioniert nicht mit 32-Bit-Systemen. Die letzte Unterteilung besteht darin, den Dezimalpunkt in der wissenschaftlichen Notation zu vermeiden.

Pari / GP , 15 + 5 = 20 Bytes

fibonacci(10^9)

Führen Sie den Befehl mit der Befehlszeilenoption aus -s1g, um 1 GB Speicher zuzuweisen.

Ruby, 63 Bytes

Mann, ich bin schlecht darin, Rubin zu spielen; Aber die BigInt-Klasse tut Wunder für solche Sachen. Wir verwenden den gleichen Algorithmus wie Anders Kaseorg.

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