Na tej stronie było miliard iteracji wyzwań Fibonacciego, więc pozwól nam urozmaicić wyzwanie wyzwaniem Fibonacciego o miliard iteracji!

Twoim wyzwaniem jest wyprowadzenie pierwszych 1000 cyfr dziesiętnych z 1 000 000 000. liczby Fibonacciego przy użyciu możliwie najkrótszego programu. Po tym opcjonalnie może nastąpić dowolne dodatkowe wyjście, które wybierzesz, w tym między innymi pozostałe cyfry.

Używam Konwencji, które fib 0 = 0, fib 1 = 1.

Twój program musi być wystarczająco szybki, abyś mógł go uruchomić i zweryfikować jego poprawność. W tym celu podajemy pierwsze 1000 cyfr:

7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799

Python 2 + sympy, 72 bajty

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

Wypróbuj online!

-10 bajtów poprzez usunięcie praktycznie-0 terminu dzięki Jeffowi Dege
-1 bajtów (1000 -> 1e3 dzięki Zacharýowi)
-2 bajtów poprzez usunięcie niepotrzebnej zmiennej dzięki Erikowi Outgolfer
-2 bajtów poprzez przejście do Pythona 2 dzięki Zacharýowi
-3 bajty przez 11 ' -11dzięki ThePirateBay -3 bajty przez zamianę strna backtyki dzięki notjagan

teraz pokonuje nieopublikowane rozwiązanie haskell OP!

Python 2 , 106 bajtów

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

Wypróbuj online!

Bez bibliotek, tylko arytmetyka liczb całkowitych. Działa prawie natychmiast.

Rdzeń stanowi tożsamość dziel i zwyciężaj:

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

To pozwala nam zaktualizować (a,b) = (f(n),f(n+1))dwukrotnie n -> 2*n. Ponieważ chcemy to zrobić n=10**9, zajmuje to tylko log_2(10**9)=30iteracje. Budujemy nnawet 10**9kilkakrotnie robi n->2*n+cdla każdej cyfry cjej ekspansji binarnym. Kiedy c==1podwojoną wartość przesuwa się 2*n -> 2*n+1o jednoetapowe przesunięcie Fibonacciego(a,b)=(b+a,b)

Aby zachować wartości a,b, którymi zarządzamy, przechowujemy tylko ich pierwsze 1006cyfry, dzieląc piętro, 10dopóki nie spadną 2**3340 ~ 1e1006.

x86 32-bitowy kod maszynowy (z wywołaniami systemowymi Linux): 106 105 bajtów

dziennik zmian: zapisano bajt w szybkiej wersji, ponieważ stała off-by-one nie zmienia wyniku dla Fib (1G).

Lub 102 bajty dla wersji wolniejszej o 18% (w Skylake) (używając mov/ sub/ cmczamiast lea/ cmpw wewnętrznej pętli, aby wygenerować wykonanie i zawijanie 10**9zamiast 2**32). Lub 101 bajtów dla wolniejszej wersji ~ 5,3x z odgałęzieniem w obsłudze przenoszenia w najbardziej wewnętrznej pętli. (Zmierzyłem 25,4% wskaźnika nieprzewidzianych oddziałów!)

Lub 104/101 bajtów, jeśli dozwolone jest zero wiodące. (Potrzebny jest 1 dodatkowy bajt, aby pominąć 1 cyfrę kodu wyjściowego, co jest potrzebne w przypadku Fib (10 ** 9)).

Niestety tryb NASM TIO wydaje się ignorować -felf32flagi kompilatora. Oto i tak link do mojego pełnego kodu źródłowego, z całym bałaganem eksperymentalnych pomysłów w komentarzach.

To jest kompletny program . Drukuje pierwsze 1000 cyfr Fib (10 ** 9), a następnie kilka dodatkowych cyfr (kilka ostatnich jest niepoprawnych), a następnie kilka bajtów śmieci (bez nowego wiersza). Większość śmieci nie jest ASCII, więc możesz chcieć przepłynąć cat -v. konsoleJednak nie psuje mojego emulatora terminali (KDE ). „Bajty śmieci” przechowują Fib (999999999). Miałem już -1024w rejestrze, więc taniej było wydrukować 1024 bajty niż odpowiedni rozmiar.

Liczę tylko kod maszynowy (rozmiar segmentu tekstowego mojego statycznego pliku wykonywalnego), a nie puch, który sprawia, że ​​jest to plik wykonywalny ELF. ( Możliwe są bardzo małe pliki wykonywalne ELF , ale nie chciałem się tym przejmować). Okazało się, że użycie pamięci stosu zamiast BSS jest krótsze, więc mogę uzasadnić, że nie liczę niczego innego w pliku binarnym, ponieważ nie zależę od żadnych metadanych. (Generowanie statycznego pliku binarnego z rozkładem w normalny sposób powoduje, że 340-bajtowy plik ELF jest wykonywalny.)

Z tego kodu można utworzyć funkcję, którą można wywołać z C. Zapisanie / przywrócenie wskaźnika stosu (być może w rejestrze MMX) może kosztować kilka bajtów, a także inne koszty ogólne, ale także zaoszczędzić bajty, zwracając ciąg znaków w pamięci zamiast write(1,buf,len)wywoływać system. Myślę, że golf w kodzie maszynowym powinien dać mi trochę luzu, ponieważ nikt inny nawet nie opublikował odpowiedzi w żadnym języku bez natywnej rozszerzonej precyzji, ale myślę, że wersja funkcji tego powinna nadal mieć mniej niż 120 bajtów bez ponownego gry w golfa rzecz.

Algorytm:

brutalna siła a+=b; swap(a,b), w razie potrzeby obcinana, aby zachować tylko wiodące> = 1017 cyfr dziesiętnych. Działa w ciągu 1 minuty 13 sekund na moim komputerze (lub 322,47 miliarda cykli zegara + - 0,05%) (i może być kilka% szybszy z kilkoma dodatkowymi bajtami rozmiaru kodu lub do 62 sekund przy znacznie większym rozmiarze kodu z rozwijania pętli. Nie sprytna matematyka, wykonująca tę samą pracę przy mniejszym obciążeniu). Opiera się na implementacji Pythona @ AndersKaseorg , która działa w 12min35s na moim komputerze (4.4GHz Skylake i7-6700k). Żadna wersja nie ma żadnych braków pamięci podręcznej L1D, więc moja pamięć DDR4-2666 nie ma znaczenia.

W przeciwieństwie do Pythona przechowuję liczby o rozszerzonej precyzji w formacie, który sprawia, że ​​obcięcie cyfr dziesiętnych jest bezpłatne . Przechowuję grupy 9 cyfr dziesiętnych na 32-bitową liczbę całkowitą, więc przesunięcie wskaźnika odrzuca niskie 9 cyfr. To faktycznie podstawa 1 miliarda, czyli potęga 10. (To czysty zbieg okoliczności, że to wyzwanie wymaga 1 miliardowej liczby Fibonacciego, ale oszczędza mi to kilka bajtów w porównaniu do dwóch oddzielnych stałych).

Zgodnie z terminologią GMP każdy 32-bitowy fragment liczby o rozszerzonej precyzji jest nazywany „kończyną”. Wykonanie podczas dodawania musi zostać wygenerowane ręcznie za pomocą porównania z 1e9, ale następnie jest normalnie wykorzystywane jako dane wejściowe do zwykłej ADCinstrukcji dla następnej kończyny. (Muszę również ręcznie zawinąć do [0..999999999]zakresu, a nie przy 2 ^ 32 ~ = 4,295e9. Robię to bez rozgałęzień za pomocą lea+ cmov, używając wyniku przeprowadzania porównania.)

Kiedy ostatnia kończyna wykonuje niezerowe wykonanie, kolejne dwie iteracje zewnętrznej pętli odczytują z 1 kończyny wyżej niż normalnie, ale nadal piszą w tym samym miejscu. To jest jak memcpy(a, a+4, 114*4)przesunięcie w prawo o 1 kończynę, ale odbywa się to w ramach dwóch następnych pętli dodawania. Dzieje się tak co ~ 18 iteracji.

Hacki dla oszczędności rozmiaru i wydajności:

• Zwykłe rzeczy jak lea ebx, [eax-4 + 1]zamiast mov ebx, 1, kiedy to wiem eax=4. A używanie loopw miejscach, w których LOOPpowolność ma niewielki wpływ.

• Obetnij o 1 kończynę za darmo, przesuwając wskaźniki, z których czytamy, jednocześnie zapisując do początku bufora w adcpętli wewnętrznej. Czytamy [edi+edx]i piszemy do [edi]. Możemy więc uzyskać edx=0lub 4uzyskać przesunięcie odczytu-zapisu dla miejsca docelowego. Musimy to zrobić dla 2 kolejnych iteracji, najpierw kompensując oba, a następnie tylko kompensując dst. Drugi przypadek wykrywamy, sprawdzając esp&4przed zresetowaniem wskaźników z przodu buforów (używając &= -1024, ponieważ bufory są wyrównane). Zobacz komentarze w kodzie.

• Środowisko uruchamiania procesu Linux (dla statycznego pliku wykonywalnego) zeruje większość rejestrów, a pamięć stosu poniżej esp/ rspjest zerowana. Mój program to wykorzystuje. W wersji tego z funkcją wywoływania (gdzie nieprzydzielony stos może być brudny), mógłbym użyć BSS do zerowania pamięci (kosztem może 4 dodatkowych bajtów do ustawienia wskaźników). Zerowanie edxzajmie 2 bajty. X86-64 System V ABI nie gwarantuje żadnego z nich, ale jego implementacja w Linuksie jest zerowa (aby uniknąć wycieku informacji z jądra). W dynamicznie połączonym procesie /lib/ld.sodziała wcześniej _starti pozostawia rejestry niezerowe (i prawdopodobnie śmieci w pamięci poniżej wskaźnika stosu).

• Trzymam -1024się ebxdo stosowania na zewnątrz pętli. Użyj bljako licznik dla wewnętrznych pętli, kończących się na zero (co jest niskim bajtem -1024, przywracając w ten sposób stałą do użycia poza pętlą). Intel Haswell, a później nie ma częściowych kar za łączenie rejestrów za niskie rejestry (a nawet nie zmienia ich osobno) , więc istnieje zależność od pełnego rejestru, jak na AMD (tutaj nie ma problemu). Byłoby to okropne w przypadku Nehalem i wcześniejszych, które mają częściowe rejestracje podczas łączenia. Są inne miejsca, w których piszę częściowe regi, a następnie czytam pełny reg bez xorzerowania lub amovzx, zwykle dlatego, że wiem, że jakiś poprzedni kod zerował górne bajty, i znowu jest to w porządku w przypadku AMD i rodziny Intel SnB, ale powolne w przypadku Intel przed Sandybridge.

  Używam 1024jako liczby bajtów do zapisu do stdout ( sub edx, ebx), więc mój program drukuje niektóre bajty śmieci po cyfrach Fibonacciego, ponieważ mov edx, 1000kosztuje więcej bajtów.

• (nie używane) adc ebx,ebxz EBX = 0, aby uzyskać EBX = CF, oszczędzając 1 bajt vs setc bl.

• dec/ jnzwewnątrz adcpętli zachowuje CF bez powodowania przeciągnięcia częściowej flagi podczas adcodczytywania flag na Intel Sandybridge i nowszych. Jest zły na wcześniejszych procesorach , ale AFAIK za darmo na Skylake. Lub, w najgorszym wypadku, dodatkowa zaleta.

• Użyj pamięci poniżej espjako gigantycznej czerwonej strefy . Ponieważ jest to kompletny program dla systemu Linux, wiem, że nie zainstalowałem żadnych programów obsługi sygnałów i że nic innego nie asynchronicznie zablokuje pamięci stosu przestrzeni użytkownika. Może się tak nie zdarzyć w przypadku innych systemów operacyjnych.

• Skorzystaj z silnika stosu, aby zaoszczędzić przepustowość problemową UOP, używając pop eax(1 uop + okazjonalne synchronizowanie stosu uop) zamiast lodsd(2 uops na Haswell / Skylake, 3 na IvB i wcześniejszych zgodnie z tabelami instrukcji Agner Fog ). IIRC, skróciło to czas działania z około 83 sekund do 73. Prawdopodobnie mógłbym uzyskać taką samą prędkość z używania movz trybem adresowania indeksowanego, tak jak mov eax, [edi+ebp]gdzie ebpzachowuje przesunięcie między buforami src i dst. (Sprawiłoby to, że kod poza pętlą wewnętrzną byłby bardziej złożony, ponieważ musiałby zanegować rejestr przesunięcia w ramach zamiany src i dst dla iteracji Fibonacciego.) Więcej informacji w sekcji „wydajność” poniżej.

• rozpocznij sekwencję, nadając pierwszej iteracji przeniesienie (jeden bajt stc), zamiast zapisywać 1gdziekolwiek w pamięci. Wiele innych specyficznych dla problemu rzeczy udokumentowanych w komentarzach.

Lista NASM (kod maszynowy + źródło) , wygenerowana z nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Następnie ręcznie usunąłem kilka bloków komentowanych rzeczy, więc numeracja linii ma luki.) Aby usunąć główne kolumny i wprowadzić je do YASM lub NASM, użyj 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

Prawdopodobnie jest jeszcze miejsce na grę w golfa, ale spędziłem na tym co najmniej 12 godzin w ciągu 2 dni. Nie chcę poświęcać prędkości, mimo że jest ona o wiele bardziej niż wystarczająco szybka i jest miejsce na jej zmniejszenie w sposób, który kosztuje prędkość . Częścią mojego powodu publikowania postów jest pokazanie, jak szybko mogę stworzyć wersję asm brutalnej siły. Jeśli ktoś naprawdę chce wybrać rozmiar minimalny, ale może 10-krotnie wolniejszy (np. 1 cyfra na bajt), możesz skopiować go jako punkt wyjścia.

Wynikowy plik wykonywalny (z yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) to 340B (pozbawiony):

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

Występ

adcPętla wewnętrzna to 10 skoków domeny połączonej w Skylake (+1 skok synchronizacji stosu co ~ 128 bajtów), więc może wydawać jeden na ~ 2,5 cykli w Skylake z optymalną wydajnością front-end (ignorując wzrost synchronizacji stosu) . Opóźnienie krytycznego ścieżka 2 cykli, gdyż adc-> cmp-> kolejnej iteracji w adcpętli prowadzi łańcuch zależność, a więc szyjka powinny być ograniczenie problem czołowy wynosi około 2,5 cykli na iteracji.

adc eax, [edi + edx]to 2 nieuprawnione nieuprawnione domeny dla portów wykonania: load + ALU. Mikro-topi się w dekoderach (1 UOP w domenie z fuzją), ale un-laminuje na etapie wydania do 2 UUP w domenie z fuzji, ze względu na tryb adresowania indeksowanego, nawet w Haswell / Skylake . Myślałem, że pozostanie mikro-skondensowany, podobnie jak add eax, [edi + edx]robi, ale być może utrzymywanie indeksowanych trybów adresowania mikro-skondensowany nie działa dla uops, które mają już 3 wejścia (flagi, pamięć i miejsce docelowe). Kiedy to napisałem, myślałem, że to nie będzie miało negatywnego wyniku, ale się myliłem. Ten sposób obsługi obcinania spowalnia wewnętrzną pętlę za każdym razem, niezależnie od tego, czy edxwynosi 0, czy 4.

Byłoby szybciej obsłużyć przesunięcie odczytu-zapisu dla dst poprzez przesunięcie edii użycie edxdo dostosowania magazynu. Więc adc eax, [edi]/ ... / mov [edi+edx], eax/ lea edi, [edi+4]zamiast stosd. Haswell i później mogą przechowywać indeksowany sklep w postaci mikro-bezpieczników. (Sandybridge / IvB też to rozwiąże).

Na Intel Haswell i wcześniejszych, adci cmovcsą 2 upops każdy, z opóźnieniem 2c . ( adc eax, [edi+edx]wciąż nie jest laminowany na Haswell i wydaje się, że 3 nie działa w domenie połączonej). Broadwell, a później zezwalają na 3-wejściowe uopsy dla więcej niż tylko FMA (Haswell), tworzenia adci cmovc(i kilku innych rzeczy) instrukcji dla pojedynczych uupów, jakby były na AMD od dłuższego czasu. (Jest to jeden z powodów, dla których AMD od dawna dobrze sobie radzi w testach porównawczych GMP o rozszerzonej precyzji.) W każdym razie wewnętrzna pętla Haswella powinna wynosić 12 jednostek (czasami +1 synchronizacja stosów), z wąskim gardłem na poziomie ~ 3 centów za sztukę iter najlepszy przypadek, ignorując ups synchronizacji stosu.

Używanie popbez równoważenia pushwewnątrz pętli oznacza, że ​​pętla nie może uruchomić się z LSD (detektor strumienia pętli) i musi być za każdym razem ponownie odczytywana z pamięci podręcznej uop do IDQ. Jeśli już, to dobrze, że w Skylake jest dobra, ponieważ pętla 9 lub 10 jednostek nie wydaje się optymalnie przy 4 jednostkach każdego cyklu . Jest to prawdopodobnie część tego, dlaczego zastąpienie lodsdprzez poptak bardzo pomogło. (LSD nie może zablokować opcji Uops, ponieważ nie pozostawiłoby to miejsca na wstawienie opcji UOP synchronizacji stosu .) (BTW, aktualizacja mikrokodu wyłącza LSD całkowicie w Skylake i Skylake-X, aby naprawić błąd. Zmierzyłem powyżej przed otrzymaniem tej aktualizacji).

Profilowałem go na Haswell i stwierdziłem, że działa w 381,31 miliarda cykli zegara (niezależnie od częstotliwości procesora, ponieważ używa tylko pamięci podręcznej L1D, a nie pamięci). Przepustowość problemu front-end wyniosła 3,72 Uops-Fused-domena na zegar, w porównaniu do 3,70 dla Skylake. (Ale oczywiście instrukcje na cykl spadła do 2,42 z 2,87, bo adci cmovsą 2 UOPs na Haswell).

pushzastąpienie stosdprawdopodobnie nie pomogłoby tak bardzo, ponieważ adc [esp + edx]uruchamiałoby uop synchronizacji stosu za każdym razem. I kosztowałby bajt, stdwięc lodsdidzie w innym kierunku. ( mov [edi], eax/ lea edi, [edi+4]do zastąpienia stosdto wygrana, przechodząc z 32.909 motocykli dla iterów 100M do 31.954 motocykli dla iterów 100 mln. Wygląda na to, że stosddekoduje się jako 3 uops, przy czym uops-store / store-data uops nie są mikro-stopione, więc push+ synchronizacja stosu Ups może nadal być szybszy niż stosd)

Rzeczywista wydajność ~ 322,47 miliarda cykli dla iteracji 1G 114 kończyn wynosi 2,824 cykli na iterację pętli wewnętrznej , dla szybkiej wersji 105B na Skylake. (Patrz ocperf.pydane wyjściowe poniżej). Jest to wolniejsze niż przewidywałem na podstawie analizy statycznej, ale ignorowałem obciążenie związane z zewnętrzną pętlą i wszelkimi dodatkami synchronizacji stosu.

Perf liczy branchesi branch-missespokazuje, że wewnętrzna pętla błędnie przewiduje raz na zewnętrzną pętlę (podczas ostatniej iteracji, gdy nie jest pobierana). To także stanowi część dodatkowego czasu.

Mógłbym zapisać rozmiar kodu, sprawiając, że najbardziej wewnętrzna pętla ma 3-cyklowe opóźnienie dla ścieżki krytycznej, używając mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) zamiast lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B ). cmov/ stosdJest wyłączony ścieżce krytycznej. (Edycja przyrostowa stosdmoże działać niezależnie od sklepu, więc każda iteracja wyklucza krótki łańcuch zależności). Dawniej zapisywał kolejny 1B, zmieniając instrukcję init ebp z lea ebp, [ecx-1]na mov ebp,eax, ale odkryłem, że źleebpnie zmienił wyniku. Pozwoliłoby to kończynie dokładnie == 1000000000 zamiast owijania i generowania przeniesienia, ale ten błąd propaguje się wolniej niż rośnie Fib (), więc nie zmienia to wiodących cyfr 1k końcowego wyniku. Myślę też, że ten błąd może się poprawić, gdy dodajemy, ponieważ w kończynie jest miejsce, aby go utrzymać bez przepełnienia. Nawet 1G + 1G nie przepełnia 32-bitowej liczby całkowitej, więc ostatecznie przesiąknie w górę lub zostanie obcięta.

Wersja 3c z opóźnieniem ma 1 dodatkowy UOP, więc front-end może wydawać go raz na 2,75c cykli w Skylake, tylko nieco szybciej niż back-end może go uruchomić. (W Haswell będzie to łącznie 13 uops, ponieważ nadal używa adci cmovoraz wąskie gardło w interfejsie na poziomie 3,25 c na iter).

W praktyce działa on o 1,18 wolniej na Skylake (3,34 cykli na kończynę), zamiast 3 / 2,5 = 1,2, które przewidywałem, że zastąpię wąskie gardło z przodu z wąskim gardłem od samego spojrzenia na wewnętrzną pętlę bez synchronizacji stosu ups. Ponieważ uops-sync stosy szkodzą tylko szybkiej wersji (wąskie gardło na froncie zamiast opóźnień), nie trzeba wiele wyjaśniać. np. 3 / 2,54 = 1,18.

Innym czynnikiem jest to, że wersja 3c z opóźnieniem może wykryć nieprzewidywalne wyjście z wewnętrznej pętli, gdy ścieżka krytyczna jest nadal wykonywana (ponieważ front-end może wyprzedzić back-end, pozwalając na wykonanie poza kolejnością, uruchamiając pętlę- counter uops), więc skuteczna kara za niepoprawne przewidywanie jest niższa. Utrata tych cykli front-end pozwala dogonić back-end.

Gdyby tak nie było, moglibyśmy przyspieszyć cmcwersję 3c , używając gałęzi w zewnętrznej pętli zamiast bezgałęziowej obsługi przeniesień carry_out -> edx i esp. Przewidywanie rozgałęzień + wykonywanie spekulatywne dla zależności sterującej zamiast zależności danych może pozwolić następnej iteracji na uruchomienie adcpętli, podczas gdy wzloty z poprzedniej pętli wewnętrznej były nadal w locie. W wersji bez rozgałęzienia adresy obciążenia w pętli wewnętrznej zależą od CF od ostatniej adcostatniej kończyny.

Wąskie gardła w wewnętrznej pętli z opóźnieniem 2c z przodu, więc back-end prawie nadąża. Gdyby kod pętli zewnętrznej miał duże opóźnienie, front-end mógłby wyprzedzić wydawanie wzlotów z następnej iteracji pętli wewnętrznej. (Ale w tym przypadku zewnętrzna pętla ma dużo ILP i nie ma opóźnień, więc back-end nie ma wiele do nadrobienia, gdy zaczyna przeżuwać błędy w harmonogramie poza kolejnością, ponieważ ich dane wejściowe są gotowe).

### 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 %)jest odchyleniem standardowym dla 4 przebiegów dla tej liczby. Ciekawe, że działa tak okrągła liczba instrukcji. 924 miliardów to nie przypadek. Wydaje mi się, że w zewnętrznej pętli działa łącznie 924 instrukcji.

uops_issuedjest liczbą domen połączonych (istotną dla przepustowości problemów frontonu), podczas gdy uops_executedjest liczbą domen nieużywanych (liczba operacji wysyłania do portów wykonawczych). Mikro-fuzja pakuje 2 nieuprawnione domeny w jedną domenę o fuzji domeny, ale mov-eliminacja oznacza, że ​​niektóre uopsy domeny nie wymagają portów wykonawczych. Zobacz połączone pytanie, aby uzyskać więcej informacji na temat liczenia domen upops i fused vs. (Zobacz także tabele instrukcji Agner Fog i przewodnik uarch oraz inne przydatne linki w wiki tagu SO x86 ).

Z innego pomiaru mierzącego różne rzeczy: brak pamięci podręcznej L1D jest całkowicie nieistotny, zgodnie z oczekiwaniami dla odczytu / zapisu tych samych dwóch buforów 456B. Gałąź pętli wewnętrznej błędnie przewiduje raz na pętlę zewnętrzną (gdy nie jest podejmowana, aby opuścić pętlę). (Całkowity czas jest dłuższy, ponieważ komputer nie był całkowicie bezczynny. Prawdopodobnie drugi logiczny rdzeń był aktywny przez pewien czas, a więcej czasu spędzano na przerwaniach (ponieważ częstotliwość mierzona w przestrzeni użytkownika była dalej niższa niż 4.400 GHz). Lub więcej rdzeni było aktywnych przez dłuższy czas, obniżając maksymalne turbo. Nie śledziłem, cpu_clk_unhalted.one_thread_activeczy konkurencja HT jest problemem.)

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

Mój kod może być uruchamiany w mniejszej liczbie cykli na Ryzen, co może powodować 5 uopsów na cykl (lub 6, gdy niektóre z nich to instrukcje 2 uop, takie jak AVX 256b na Ryzen). Nie jestem pewien, co zrobiłby jego front-end stosd, czyli 3 ulepszenia na Ryzen (tak samo jak Intel). Myślę, że pozostałe instrukcje w wewnętrznej pętli mają takie same opóźnienia jak Skylake i wszystkie pojedynczo. (W tym adc eax, [edi+edx], co stanowi przewagę nad Skylake).

Mogłoby to być prawdopodobnie znacznie mniejsze, ale może 9-krotnie wolniejsze, jeśli zapisałem liczby jako 1 cyfrę dziesiętną na bajt . Generowanie wykonania cmpi dostosowywanie za pomocą cmovdziałałoby tak samo, ale wykonaj 1/9 pracy. Działa również 2 cyfry dziesiętne na bajt (base-100, nie 4-bitowy BCD ze spowolnieniemDAA ) i div r8/ add ax, 0x3030zamienia 0-99 bajtów na dwie cyfry ASCII w kolejności drukowania. Ale 1 cyfra na bajt wcale nie potrzebuje div, wystarczy zapętlić i dodać 0x30. Jeśli przechowam bajty w kolejności drukowania, to sprawi, że druga pętla stanie się naprawdę prosta.

Zastosowanie 18 lub 19 cyfr dziesiętnych na 64-bitową liczbę całkowitą (w trybie 64-bitowym) sprawiłoby, że działałby on około dwa razy szybciej, ale kosztował znaczny rozmiar kodu dla wszystkich prefiksów REX i dla 64-bitowych stałych. 32-bitowe kończyny w trybie 64-bitowym uniemożliwiają użycie pop eaxzamiast lodsd. Nadal mogłem uniknąć prefiksów REX, używając espjako rejestru non-point scratch (zamieniając użycie esii esp), zamiast używać r8djako 8. rejestr.

W przypadku wersji z funkcją wywoływania konwersja do wersji 64-bitowej i używanie r8dmoże być tańsze niż zapisywanie / przywracanie rsp. 64-bitowe również nie mogą używać dec r32kodowania jednobajtowego (ponieważ jest to przedrostek REX). Ale głównie skończyło się na dec bltym, że 2 bajty. (Ponieważ mam stałą w górnych bajtach ebxi używam jej tylko poza wewnętrznymi pętlami, co działa, ponieważ niski bajt stałej jest 0x00.)

Wersja o wysokiej wydajności

Aby uzyskać maksymalną wydajność (nie kod-golf), należy rozwinąć wewnętrzną pętlę, aby działała co najwyżej 22 iteracje, co jest wystarczająco krótkim wzorcem wziętym / nie wziętym, aby predyktory gałęzi działały dobrze. W moich eksperymentach, mov cl, 22zanim .inner: dec cl/jnz .innerpętla zawiera bardzo mało nieprzewidywalnych wyników (np. 0,05%, znacznie mniej niż jeden na pełny przebieg wewnętrznej pętli), ale mov cl,23błędnie przewiduje od 0,35 do 0,6 razy na wewnętrzną pętlę. 46jest szczególnie zły, nieprzewidywalny ~ 1,28 razy na pętlę wewnętrzną (128 mln razy dla iteracji 100M pętli zewnętrznej). 114źle przewidziany dokładnie raz na wewnętrzną pętlę, tak samo jak znalazłem jako część pętli Fibonacciego.

Zainteresowałem się i wypróbowałem to, rozwijając wewnętrzną pętlę o 6 za pomocą %rep 6(ponieważ to równomiernie dzieli 114). To w większości wyeliminowało brakujące oddziały. Zrobiłem edxujemny i użyłem go jako offsetu dla movsklepów, więc adc eax,[edi]mogłem pozostać mikro-stopiony. (I tak mogłem uniknąć stosd). Wyciągnąłem leaaktualizację ediz %repbloku, więc wykonuje tylko jedną aktualizację wskaźnika na 6 sklepów.

Pozbyłem się również wszystkich częściowych rejestrów w zewnętrznej pętli, choć nie sądzę, żeby to miało znaczenie. Być może pomógł nieznacznie mieć CF na końcu zewnętrznej pętli, niezależny od ostatecznego ADC, więc niektóre ze zmian w pętli wewnętrznej można zacząć. Kod pętli zewnętrznej można prawdopodobnie zoptymalizować nieco bardziej, ponieważ neg edxbyła to ostatnia rzecz, którą zrobiłem, po zastąpieniu xchgtylko 2 movinstrukcjami (ponieważ wciąż miałem 1) i ponownym rozmieszczeniu łańcuchów dep wraz z upuszczeniem 8-bitów zarejestrować rzeczy.

To jest źródło NASM tylko pętli Fibonacciego. Jest to drop-in zamiennik tej sekcji oryginalnej wersji.

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

Występ:

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

To dotyczy tego samego Fib (1G), wytwarzając tę ​​samą moc wyjściową w 62,3 sekundy zamiast 73 sekund. (273.146G cykli, w porównaniu z 322.467G. Ponieważ wszystko uderza w pamięć podręczną L1, cykle zegara rdzenia to naprawdę wszystko, na co musimy spojrzeć.)

Zwróć uwagę na znacznie niższą całkowitą uops_issuedliczbę, znacznie poniżej uops_executedliczby. Oznacza to, że wiele z nich zostało połączonych w trybie mikro: 1 uop w domenie z fuzją (problem / ROB), ale 2 uop w domenie bez fuzji (harmonogram / jednostki wykonawcze)). I niewielu zostało wyeliminowanych na etapie wydania / zmiany nazwy (np. movKopiowanie rejestru lub xorzerowanie, które wymagają wydania, ale nie potrzebują jednostki wykonawczej). Wyeliminowane ups będą równoważyć liczbę w drugą stronę.

branch-missesspada do ~ 400k, z 1G, więc rozwijanie działało. resource_stalls.anyjest teraz znaczący, co oznacza, że ​​front-end nie jest już wąskim gardłem: zamiast tego back-end jest w tyle i ogranicza front-end. idq_uops_not_delivered.coreliczy tylko cykle, w których front-end nie dostarczał poprawek, ale back-end nie został zablokowany. To miłe i niskie, wskazujące na kilka wąskich gardeł z przodu.

Ciekawostka: wersja Pythona spędza ponad połowę czasu dzieląc przez 10, a nie dodając. (Wymiana a/=10z a>>=64prędkościami go o więcej niż współczynnik 2, ale zmienia wynik bo obcinanie binarnym! = Dziesiętny obcięcie).

Moja wersja asm jest oczywiście zoptymalizowana specjalnie dla tego rozmiaru problemu, a iteracja pętli liczy się na sztywno. Nawet przesunięcie liczby o dowolnej dokładności spowoduje jej skopiowanie, ale moja wersja może po prostu odczytać offset z następnych dwóch iteracji, aby pominąć nawet to.

Profilowałem wersję Pythona (64-bitowy python2.7 na 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

Liczby w (parens) określają, ile czasu próbkowany był licznik perf. Patrząc na więcej liczników niż obsługuje HW, perf obraca się między różnymi licznikami i ekstrapoluje. To całkiem dobrze na długi okres tego samego zadania.

Gdybym uruchomił perfpo ustawieniu sysctl kernel.perf_event_paranoid = 0(lub uruchomieniu perfjako root), to by to zmierzyło 4.400GHz. cycles:unie liczy czasu spędzonego na przerwaniach (lub wywołaniach systemowych), tylko cykle przestrzeni użytkownika. Mój pulpit był prawie całkowicie bezczynny, ale jest to typowe.

Haskell, 83 61 bajtów

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)

Wyjścia ( F _1000000000 , F _1000000001 ). Na moim laptopie poprawnie drukuje lewy paren i pierwsze 1000 cyfr w ciągu 133 sekund, wykorzystując 1,35 GiB pamięci.

Jak to działa

Nawrót Fibonacciego można rozwiązać za pomocą potęgowania macierzy:

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

z którego czerpiemy te tożsamości:

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

W pOblicza funkcyjną ( C _{i + J} , M _{i + j + 1} ), ze względu na ( F _I , M _{i + 1} ) i ( K _J , K _{j + 1} ). Pisząc f ndla ( F _i , F _{i + 1} ), mamy p (f i) (f j)= f (i + j).

Następnie,

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

i podłączamy f 1= (1,1).

Mathematica, 15 34 bajty

Fibonacci sam zajmuje ~ 6s na moim komputerze. I 95 (+/- 5) s dla interfejsu użytkownika, aby go wyświetlić.

Fibonacci@1*^9&

Pierwsze 1000 cyfr (34 bajty): ⌊Fibonacci@1*^9/1*^208986640⌋&

Dłuższy, ale szybszy ToString@Fibonacci@1*^9~StringTake~1000&:

Python 2, 70 bajtów

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

Trwało to przez 18 minut i 31 sekund na moim laptopie, generując prawidłowe 1000 cyfr, a następnie 74100118580(prawidłowe są następujące cyfry 74248787892).

Haskell , 78 bajtów

(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

Wypróbuj online!

Zajęło 48 sekund na TIO. Ta sama rekurencyjna formuła jak moja odpowiedź w języku Python , ale bez obcinania.

Stała 2143923439jest 10**9-1odwrócona binarnie, a na końcu jest dodatkowa 1. Iteracja cyfr binarnych w odwrotnej kolejności symuluje iterację cyfr binarnych z 10**9-1. Wydaje się, że kodowanie tego jest krótsze niż jego obliczenie.

Haskell , 202 184 174 173 170 168 164 162 bajtów

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

Wypróbuj online!

Wyjaśnienie

Wykorzystuje to dość szybki sposób obliczania liczb fibonacciego. Funkcja lprzyjmuje dwie liczby Fibonacciego i oblicza liczby Fibonacciego 10 później, podczas gdy fbierze n- ta i n + 1- tą liczbę Fibonacciego i oblicza 2n + 20- te i 2n + 21- te liczby Fibonacciego. Łączę je raczej przypadkowo, aby zdobyć 1 miliard i zdobyć pierwsze 1000 cyfr.

Haskell, 81 bajtów

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

Wyjaśnienie

f nrekurencyjnie oblicza nliczbę F fibonacciego, używając wzorca z odpowiedzi xnora z eliminacją podwyrażenia wspólnego. W przeciwieństwie do innych opublikowanych rozwiązań, które wykorzystują multiplikacje O (log (n)), mamy rekurencję głębokości O (log (n)) o współczynniku rozgałęzienia 2, dla złożoności mnożenia O (n).

Jednak nie wszystko jest stracone! Ponieważ prawie wszystkie wywołania będą znajdować się w dolnej części drzewa rekurencji, w miarę możliwości możemy użyć szybkiej natywnej arytmetyki i uniknąć mnóstwa manipulacji dużymi bignum. Wyrzuca odpowiedź w ciągu kilku minut na moim pudełku.

T-SQL, 422 414 453 bajtów (zweryfikowany, teraz konkuruje!)

EDYCJA 2 : Zmieniono na , Zyskałem kilka bajtów, ale zwiększyłem prędkość wystarczającą do ukończenia do 1 miliarda! Ukończony w ciągu 45 godzin 29 minut , weryfikuje podany ciąg znaków i wyświetla dodatkowe 8 znaków (które mogą, ale nie muszą być poprawne z powodu błędów zaokrąglania).INT BIGINT DECIMAL(37,0)

T-SQL nie ma natywnej obsługi „ogromnej liczby”, więc musiałem rzucić własny tekstowy sumator dużej liczby przy użyciu ciągów 1008 znaków:

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 @

Oto sformatowana wersja z komentarzami:

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 @

Zasadniczo ręcznie manipuluję ciągami wypełnionymi zerami 1008 znaków reprezentujących moje dwie zmienne Fibonacciego @ai @.

Dodaję je 8 18 36 cyfr na raz, usuwając ostatnie 36 cyfr, konwertując na możliwy do zarządzania typ numeryczny ( DECIMAL(37,0)), dodając je, a następnie rozbijając z powrotem na kolejny długi ciąg @c. Następnie „obracam” @ai @przesuwam ostatnie 36 cyfr do przodu i powtarzam proces. 28 obrotów * 36 cyfr obejmuje wszystkie 1008. Muszę „nosić ten” ręcznie.

Gdy nasza liczba zaczyna przekraczać długość mojego łańcucha, „przesuwam w lewo” i zaczynamy tracić precyzję, ale błąd mieści się w zakresie moich dodatkowych znaków.

Próbowałem użyć tabeli SQL pełnej INT i BIGINT, z podobną logiką, i było to znacznie wolniejsze. Dziwne.

PARI / GP, 45 bajtów

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

Jakoś \p1000nie wystarczy. To nie działa z systemami 32-bitowymi. Ostatecznym podziałem jest unikanie kropki dziesiętnej w notacji naukowej.

Pari / GP , 15 + 5 = 20 bajtów

fibonacci(10^9)

Uruchom z opcją wiersza polecenia, -s1gaby przydzielić 1 GB pamięci.

Ruby, 63 bajty

człowieku, jestem zły w golfie ruby; ale klasa BigInt robi cuda dla tego rodzaju rzeczy. Używamy tego samego algorytmu, co Anders Kaseorg.

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