Ada satu miliar iterasi tantangan Fibonacci di situs web ini, jadi mari kita tambahkan semuanya dengan tantangan Fibonacci dari satu miliar iterasi!

Tantangan Anda adalah menghasilkan 1000 digit desimal pertama dari angka Fibonacci 1.000.000.000 dengan program sesingkat mungkin. Ini kemudian secara opsional dapat diikuti oleh output tambahan apa pun yang Anda pilih, termasuk tetapi tidak terbatas pada digit lainnya.

Saya menggunakan konvensi yang fib 0 = 0, fib 1 = 1.

Program Anda harus cukup cepat untuk menjalankannya dan memverifikasi kebenarannya. Untuk tujuan ini, berikut adalah 1000 digit pertama:

7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799

Python 2 + sympy, 72 byte

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

Cobalah online!

-10 byte dengan menghapus istilah-0 praktis berkat Jeff Dege
-1 byte (1000 -> 1e3 berkat Zacharý)
-2 byte dengan menghapus variabel yang tidak perlu berkat Erik the Outgolfer
-2 byte dengan pindah ke Python 2 berkat Zacharý
-3 bytes dengan mengucapkan -11terima kasih kepada ThePirateBay -3 bytes dengan menukar strbacktick berkat notjagan

sekarang mengalahkan solusi haskell OP yang belum diposkan!

Python 2 , 106 byte

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

Cobalah online!

Tidak ada perpustakaan, hanya aritmatika integer. Berjalan hampir seketika.

Inti adalah identitas divide-and-conquer:

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

Ini memungkinkan kami memperbarui (a,b) = (f(n),f(n+1))menjadi dua kali lipat n -> 2*n. Karena kami ingin mendapatkan n=10**9, ini hanya membutuhkan log_2(10**9)=30iterasi. Kami membangun nhingga 10**9dengan berulang kali melakukan n->2*n+cuntuk setiap digit cekspansi biner. Ketika c==1, nilai berlipat digeser ke atas 2*n -> 2*n+1dengan pergeseran Fibonacci satu langkah(a,b)=(b+a,b)

Agar nilai-nilai a,bdapat dikelola, kami hanya menyimpan 1006digit pertama mereka dengan membagi lantai 10sampai mereka berada di bawah 2**3340 ~ 1e1006.

x86 kode mesin 32-bit (dengan panggilan sistem Linux): 106 105 byte

changelog: menyimpan byte dalam versi cepat karena konstanta off-by-one tidak mengubah hasil untuk Fib (1G).

Atau 102 byte untuk versi 18% lebih lambat (pada Skylake) (menggunakan mov/ sub/ cmcbukannya lea/ cmpdi loop dalam, untuk menghasilkan carry-out dan pembungkus di 10**9bukan 2**32). Atau 101 byte untuk versi yang lebih lambat ~ 5.3x dengan cabang dalam carry-handling di loop paling dalam. (Saya mengukur tingkat mispredict cabang 25,4%!)

Atau 104/101 byte jika nol di depan diizinkan. (Dibutuhkan 1 byte tambahan untuk hard-code melewatkan 1 digit dari output, yang merupakan apa yang diperlukan untuk Fib (10 ** 9)).

Sayangnya, mode NASM TIO tampaknya diabaikan -felf32dalam flag-flag compiler. Berikut adalah tautan dengan kode sumber lengkap saya, dengan semua kekacauan gagasan eksperimental dalam komentar.

Ini adalah program yang lengkap . Mencetak 1000 digit pertama Fib (10 ** 9) diikuti oleh beberapa digit tambahan (beberapa yang terakhir salah) diikuti oleh beberapa bytes sampah (tidak termasuk baris baru). Sebagian besar sampah adalah non-ASCII, jadi Anda mungkin ingin menyalurkannya cat -v. Tapi itu tidak merusak emulator terminal saya (KDE konsole). "Sampah byte" menyimpan Fib (999999999). Saya sudah punya -1024di register, jadi lebih murah untuk mencetak 1024 byte daripada ukuran yang tepat.

Saya menghitung hanya kode mesin (ukuran segmen teks dari executable statis saya), bukan fluff yang membuatnya menjadi executable ELF. ( Executable ELF sangat kecil adalah mungkin , tapi saya tidak mau repot dengan itu). Ternyata lebih pendek menggunakan memori stack daripada BSS, jadi saya bisa membenarkan tidak menghitung apa pun dalam biner karena saya tidak bergantung pada metadata. (Memproduksi biner statis yang dilucuti dengan cara biasa membuat ELF 340 byte dapat dieksekusi.)

Anda dapat membuat fungsi dari kode ini yang dapat Anda panggil dari C. Dibutuhkan beberapa byte untuk menyimpan / mengembalikan stack pointer (mungkin dalam register MMX) dan beberapa overhead lainnya, tetapi juga menyimpan byte dengan kembali dengan string. dalam memori, alih-alih melakukan write(1,buf,len)panggilan sistem. Saya pikir golf dalam kode mesin harus memberi saya sedikit kelonggaran di sini, karena tidak ada orang lain yang bahkan memposting jawaban dalam bahasa apa pun tanpa ketelitian asli yang diperluas, tetapi saya pikir versi fungsi ini masih harus di bawah 120 byte tanpa golf ulang keseluruhan benda.

Algoritma:

brute force a+=b; swap(a,b), memotong seperlunya untuk menjaga hanya angka desimal terdepan> = 1017. Ini berjalan dalam 1 menit 13 detik di komputer saya (atau 322,47 miliar siklus clock + - 0,05%) (dan bisa beberapa% lebih cepat dengan beberapa byte tambahan ukuran kode, atau turun ke 62an dengan ukuran kode yang jauh lebih besar dari loop membuka gulungan. Tidak matematika pintar, hanya melakukan pekerjaan yang sama dengan overhead yang lebih sedikit). Ini didasarkan pada implementasi Python @ AndersKaseorg , yang berjalan dalam 12 menit 35 pada komputer saya (4.4GHz Skylake i7-6700k). Tidak ada versi yang memiliki cache L1D meleset, jadi DDR4-2666 saya tidak masalah.

Tidak seperti Python, saya menyimpan angka presisi yang diperluas dalam format yang membuat pemotongan angka desimal gratis . Saya menyimpan grup dengan 9 angka desimal per bilangan bulat 32-bit, jadi offset pointer membuang angka 9 yang rendah. Ini secara efektif basis 1-miliar, yang merupakan kekuatan 10. (Ini kebetulan murni bahwa tantangan ini membutuhkan angka Fibonacci 1 miliar, tapi itu menyelamatkan saya beberapa byte vs dua konstanta terpisah.)

Mengikuti terminologi GMP , setiap potongan 32-bit dari nomor dengan ketepatan yang diperluas disebut "ekstremitas". Melakukan sambil menambahkan harus dihasilkan secara manual dengan membandingkan terhadap 1e9, tetapi kemudian digunakan secara normal sebagai input ke ADCinstruksi biasa untuk anggota tubuh berikutnya. (Saya juga harus membungkus secara manual ke [0..999999999]rentang, daripada pada 2 ^ 32 ~ = 4.295e9. Saya melakukan ini tanpa cabang dengan lea+ cmov, menggunakan hasil carry-out dari perbandingan.)

Ketika tungkai terakhir menghasilkan non-zero carry-out, dua iterasi berikutnya dari loop luar membaca dari 1 tungkai lebih tinggi dari biasanya, tetapi masih menulis ke tempat yang sama. Ini seperti melakukan memcpy(a, a+4, 114*4)pergeseran ke kanan sebanyak 1 ekstremitas, tetapi dilakukan sebagai bagian dari dua loop tambahan berikutnya. Ini terjadi setiap ~ 18 iterasi.

Hacks untuk penghematan ukuran dan kinerja:

• Hal-hal yang biasa saya sukai lea ebx, [eax-4 + 1]alih - alih mov ebx, 1, ketika saya tahu itu eax=4. Dan menggunakan loopdi tempat-tempat di mana LOOPkelambatan hanya memiliki dampak kecil.

• Potong dengan 1 anggota badan secara gratis dengan mengimbangi pointer yang kita baca, sambil tetap menulis ke awal buffer di adcloop dalam. Kami membaca dari [edi+edx], dan menulis ke [edi]. Jadi kita bisa mendapatkan edx=0atau 4mendapatkan offset baca-tulis untuk tujuan. Kita perlu melakukan ini untuk 2 iterasi berturut-turut, pertama mengimbangi keduanya, kemudian hanya mengimbangi dulu. Kami mendeteksi kasing ke-2 dengan melihat esp&4sebelum menyetel ulang pointer ke bagian depan buffer (menggunakan &= -1024, karena buffer disejajarkan). Lihat komentar dalam kode.

• Lingkungan proses-startup Linux (untuk eksekusi statis) nol paling banyak register, dan tumpukan-memori di bawah esp/ rspadalah nol. Program saya memanfaatkan ini. Dalam versi fungsi-terpanggil dari ini (di mana tumpukan yang tidak terisi dapat menjadi kotor), saya bisa menggunakan BSS untuk memusatkan memori (dengan biaya mungkin 4 byte lebih untuk mengatur pointer). Zeroing edxakan membutuhkan 2 byte. System V ABI x86-64 tidak menjamin salah satu dari ini, tetapi implementasi Linux tidak nol (untuk menghindari kebocoran informasi dari kernel). Dalam proses yang terhubung secara dinamis, /lib/ld.sojalankan sebelumnya _start, dan biarkan register tidak nol (dan mungkin sampah di memori di bawah stack pointer).

• Aku tetap -1024di ebxuntuk digunakan di luar loop. Gunakan blsebagai penghitung untuk loop dalam, berakhir dengan nol (yang merupakan byte rendah -1024, sehingga mengembalikan konstanta untuk digunakan di luar loop). Intel Haswell dan kemudian tidak memiliki hukuman penggabungan sebagian daftar untuk register low8 (dan bahkan tidak mengubah nama mereka secara terpisah) , jadi ada ketergantungan pada register lengkap, seperti pada AMD (tidak masalah di sini). Namun hal ini akan sangat mengerikan di Nehalem dan sebelumnya, yang memiliki warung-warung pendaftaran sebagian saat penggabungan. Ada tempat-tempat lain di mana saya menulis reg sebagian dan kemudian membaca reg penuh tanpa- xornol atau amovzx, biasanya karena saya tahu bahwa beberapa kode sebelumnya memusatkan byte atas, dan sekali lagi itu baik-baik saja pada AMD dan Intel SnB-family, tetapi lambat pada Intel pra-Sandybridge.

  Saya menggunakan 1024jumlah byte untuk menulis ke stdout ( sub edx, ebx), jadi program saya mencetak beberapa byte sampah setelah digit Fibonacci, karena mov edx, 1000biaya lebih banyak byte.

• (tidak digunakan) adc ebx,ebxdengan EBX = 0 untuk mendapatkan EBX = CF, menyimpan 1 byte vs setc bl.

• dec/ jnzdi dalam satu adcloop mempertahankan CF tanpa menyebabkan parsial-bendera terhenti ketika adcmembaca bendera di Intel Sandybridge dan kemudian. Ini buruk pada CPU sebelumnya , tetapi AFAIK gratis di Skylake. Atau paling buruk, uop ekstra.

• Gunakan memori di bawah ini espsebagai zona merah raksasa . Karena ini adalah program Linux yang lengkap, saya tahu saya tidak menginstal penangan sinyal apa pun, dan tidak ada yang lain yang secara tidak sinkron akan menumpuk memori ruang pengguna. Ini mungkin tidak terjadi pada OS lain.

• Manfaatkan mesin stack untuk menghemat bandwidth masalah uop dengan menggunakan pop eax(1 uop + stack-sync uop sesekali) alih-alih lodsd(2 uops di Haswell / Skylake, 3 di IvB dan sebelumnya menurut tabel instruksi Agner Fog )). IIRC, ini menurunkan run-time dari sekitar 83 detik menjadi 73. Saya mungkin bisa mendapatkan kecepatan yang sama dari menggunakan movdengan mode pengalamatan terindeks, seperti di mov eax, [edi+ebp]mana ebpmemegang offset antara buffer src dan dst. (Ini akan membuat kode di luar loop dalam lebih kompleks, harus meniadakan register offset sebagai bagian dari swapping src dan dst untuk iterasi Fibonacci.) Lihat bagian "kinerja" di bawah ini untuk informasi lebih lanjut.

• mulai urutan dengan memberikan iterasi pertama carry-in (satu byte stc), alih-alih menyimpan 1dalam memori di mana saja. Banyak hal khusus masalah lain yang didokumentasikan dalam komentar.

Daftar NASM (kode mesin + sumber) , dibuat dengan nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Kemudian saya menghapus beberapa blok dari hal-hal yang dikomentari, sehingga penomoran baris memiliki celah.) Untuk menghapus kolom terkemuka sehingga Anda dapat memasukkannya ke YASM atau NASM, gunakan 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

Mungkin ada ruang untuk bermain golf beberapa byte lagi dari ini, tapi saya sudah menghabiskan setidaknya 12 jam untuk ini selama 2 hari. Saya tidak ingin mengorbankan kecepatan, meskipun cara itu lebih dari cukup cepat dan ada ruang untuk membuatnya lebih kecil dengan biaya kecepatan . Bagian dari alasan saya untuk memposting adalah menunjukkan seberapa cepat saya dapat membuat versi asm brute-force. Jika ada yang ingin benar-benar menggunakan ukuran minimum tetapi mungkin 10x lebih lambat (mis. 1 digit per byte), jangan ragu untuk menyalin ini sebagai titik awal.

Eksekusi yang dihasilkan (dari yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) adalah 340B (dilucuti):

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

Performa

adcLoop dalam adalah 10 uop ​​domain-menyatu pada Skylake (+1 stack-sync uop setiap ~ 128 byte), sehingga ia dapat mengeluarkan satu siklus per 2.5 siklus pada Skylake dengan throughput front-end yang optimal (mengabaikan uop stack-sync) . Latensi jalur kritis adalah 2 siklus, untuk adc-> cmp-> adcrantai ketergantungan loop berikutnya yang diangkut iterasi , sehingga bottleneck harus menjadi batas masalah front-end ~ 2,5 siklus per iterasi.

adc eax, [edi + edx]adalah 2 domain yang tidak digunakan untuk port eksekusi: load + ALU. Ini micro-sekering dalam decoder (1 domain-leburan-uop), tetapi un-laminasi dalam tahap masalah ke 2-domain-leburan-uops, karena mode pengalamatan diindeks, bahkan pada Haswell / Skylake . Saya pikir itu akan tetap micro-fused, seperti add eax, [edi + edx]halnya, tetapi mungkin menjaga mode pengalamatan terindeks micro-fused tidak bekerja untuk uops yang sudah memiliki 3 input (flag, memori, dan tujuan). Ketika saya menulisnya, saya berpikir itu tidak akan memiliki penurunan kinerja, tetapi saya salah. Cara penanganan pemotongan ini memperlambat loop dalam setiap kali, apakah edx0 atau 4.

Akan lebih cepat untuk menangani offset baca-tulis untuk dst dengan mengimbangi edidan menggunakan edxuntuk menyesuaikan toko. Jadi adc eax, [edi]/ ... mov [edi+edx], eax// lea edi, [edi+4]bukan stosd. Haswell dan yang lebih baru dapat menyimpan toko yang diindeks dengan mikro. (Sandybridge / IvB akan menghapus laminasi juga.)

Pada Intel Haswell dan sebelumnya, adcdan cmovcmasing-masing 2 uops, dengan latensi 2c . ( adc eax, [edi+edx]masih belum dilaminasi di Haswell, dan diterbitkan sebagai 3 domain-fuse uops). Broadwell dan kemudian memungkinkan 3-input uops untuk lebih dari sekedar FMA (Haswell), membuat adcdan cmovc(dan beberapa hal lainnya) instruksi single-uop, seperti mereka telah menggunakan AMD untuk waktu yang lama. (Ini adalah salah satu alasan AMD melakukannya dengan baik dalam tolok ukur GMP presisi panjang untuk waktu yang lama.) Bagaimanapun, loop internal Haswell harus 12 uops (kadang-kadang 1 stack-sync uop), dengan bottleneck front-end ~ 3c per iter kasus terbaik, abaikan tumpukan-sinkronisasi uops.

Menggunakan poptanpa menyeimbangkan pushdi dalam loop berarti loop tidak dapat berjalan dari LSD (loop stream detector) , dan harus dibaca kembali dari cache uop ke IDQ setiap waktu. Jika ada, itu adalah hal yang baik pada Skylake, karena loop 9 atau 10 uop ​​tidak cukup masalah secara optimal pada 4 uops setiap siklus . Ini mungkin bagian dari mengapa mengganti lodsddengan popsangat membantu. (LSD tidak dapat mengunci uops karena itu tidak akan meninggalkan ruang untuk memasukkan tumpukan-sinkronisasi uop .) (BTW, pembaruan mikrokode menonaktifkan LSD sepenuhnya pada Skylake dan Skylake-X untuk memperbaiki erratum. Saya mengukur di atas sebelum mendapatkan pembaruan itu.)

Saya memprofilkannya di Haswell, dan menemukan bahwa itu berjalan dalam 381,31 miliar siklus clock (terlepas dari frekuensi CPU, karena hanya menggunakan cache L1D, bukan memori). Throughput masalah front-end adalah 3,72 domain-leburan uops per jam, vs 3,70 untuk Skylake. (Tapi tentu saja instruksi per siklus turun ke 2,42 dari 2,87, karena adcdan cmov2 uops di Haswell.)

pushuntuk mengganti stosdmungkin tidak akan banyak membantu, karena adc [esp + edx]akan memicu tumpukan-sinkronisasi uop setiap kali. Dan akan memakan biaya satu byte untuk stdseterusnya lodsdke arah lain. ( mov [edi], eax/ lea edi, [edi+4]untuk menggantikan stosdadalah kemenangan, pergi dari 32.909Mesin untuk 100M iter ke 31.954Mesel untuk iters 100M. Tampaknya diterjemahkan stosdsebagai 3 uops, dengan uup store-address / store-data bukan micro-fused, jadi push+ stack-sync mungkin masih lebih cepat dari stosd)

Kinerja aktual ~ 322,47 miliar siklus untuk iterasi 1G dari 114 anggota badan bekerja hingga 2,824 siklus per iterasi loop dalam , untuk versi 105B cepat di Skylake. (Lihat ocperf.pyoutput di bawah). Itu lebih lambat dari yang saya perkirakan dari analisis statis, tetapi saya mengabaikan overhead loop luar dan setiap tumpukan-sinkronisasi uops

Perf counters untuk branchesdan branch-missesmenunjukkan bahwa loop dalam mispredicts sekali per loop luar (pada iterasi terakhir, ketika itu tidak diambil). Itu juga merupakan bagian dari waktu tambahan.

Saya bisa menyimpan ukuran kode dengan membuat loop paling dalam memiliki latensi 3 siklus untuk jalur kritis, menggunakan mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) alih-alih lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B ). The cmov/ stosdoff jalur kritis. (Penambahan-edi uop dari stosddapat berjalan secara terpisah dari toko, sehingga setiap iterasi memotong rantai ketergantungan pendek.) Dulu menyimpan 1B lain dengan mengubah instruksi ebp init dari lea ebp, [ecx-1]menjadi mov ebp,eax, tetapi saya menemukan bahwa memiliki kesalahanebptidak mengubah hasilnya. Ini akan membuat anggota badan menjadi persis == 1000000000 alih-alih membungkus dan memproduksi carry, tetapi kesalahan ini menyebar lebih lambat dari yang kita Fib () tumbuhkan, jadi ini terjadi tidak mengubah digit 1k terkemuka dari hasil akhir. Juga, saya pikir kesalahan itu dapat memperbaiki dirinya sendiri ketika kami baru saja menambahkan, karena ada ruang dalam dahan untuk menahannya tanpa meluap. Bahkan 1G + 1G tidak melimpahi integer 32-bit, sehingga akhirnya akan meresap ke atas atau terpotong.

Versi latensi 3c adalah 1 ekstra uop, sehingga front-end dapat mengeluarkannya pada satu siklus per 2,75c pada Skylake, hanya sedikit lebih cepat daripada back-end yang dapat menjalankannya. (Di Haswell, itu akan menjadi total 13 uops karena masih menggunakan adcdan cmov, dan bottleneck di front-end di 3,25c per iter).

Dalam praktiknya menjalankan faktor 1,18 lebih lambat pada Skylake (3,34 siklus per tungkai), daripada 3 / 2,5 = 1,2 yang saya prediksi untuk mengganti bottleneck front-end dengan bottleneck latency dari hanya melihat loop dalam tanpa melihat stack-sync uops. Karena stack-sync uops hanya merusak versi cepat (bottlenecked di front-end, bukan latency), tidak perlu banyak menjelaskannya. misal 3 / 2.54 = 1.18.

Faktor lain adalah bahwa versi latensi 3c dapat mendeteksi kesalahan perkiraan saat meninggalkan loop dalam saat jalur kritis masih mengeksekusi (karena front-end dapat maju dari back-end, membiarkan eksekusi out-of-order menjalankan loop- balik), sehingga hukuman salah saji efektif lebih rendah. Kehilangan siklus front-end tersebut memungkinkan back-end mengejar ketinggalan.

Jika bukan karena itu, kita mungkin bisa mempercepat cmcversi 3c dengan menggunakan cabang di lingkaran luar alih-alih penanganan tanpa cabang dari carry bawa -> edx dan offset. Prediksi cabang + eksekusi spekulatif untuk dependensi kontrol alih-alih ketergantungan data dapat membuat iterasi berikutnya mulai menjalankan adcloop sementara uops dari loop dalam sebelumnya masih dalam penerbangan. Dalam versi branchless, alamat muat di loop dalam memiliki ketergantungan data pada CF dari yang terakhir adcdari anggota gerak terakhir.

Bottleneck versi loop dalam latensi 2c di front-end, sehingga back-end cukup banyak terus. Jika kode loop luar adalah latensi tinggi, front-end dapat melanjutkan mengeluarkan uops dari iterasi berikutnya dari loop dalam. (Tetapi dalam hal ini hal-hal loop luar memiliki banyak ILP dan tidak ada hal latensi tinggi, sehingga back-end tidak memiliki banyak hal yang harus dilakukan ketika mulai mengunyah uops dalam penjadwalan out-of-order sebagai input mereka menjadi siap).

### 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 %)adalah standar-deviasi selama 4 berjalan untuk hitungan itu. Menarik bahwa ia menjalankan sejumlah instruksi. 924 miliar itu bukan kebetulan. Saya kira loop luar menjalankan total 924 instruksi.

uops_issuedadalah jumlah domain-menyatu (relevan untuk bandwidth masalah front-end), sementara itu uops_executedadalah jumlah-domain yang tidak digunakan (jumlah uops yang dikirim ke port eksekusi). Paket micro-fusion 2 uops domain yang tidak digunakan menjadi satu uop domain-menyatu, tetapi eliminasi gerak berarti bahwa beberapa uops domain-fusi tidak memerlukan port eksekusi. Lihat pertanyaan terkait untuk lebih lanjut tentang menghitung uops dan domain menyatu vs tidak terpakai. (Juga lihat tabel instruksi Agner Fog dan panduan uarch , dan tautan bermanfaat lainnya dalam wiki tag SO x86 ).

Dari proses lain mengukur hal-hal yang berbeda: L1D cache misses sama sekali tidak signifikan, seperti yang diharapkan untuk membaca / menulis dua buffer 456B yang sama. Cabang loop-dalam salah memperkirakan satu kali per loop luar (ketika tidak diambil untuk meninggalkan loop). (Total waktu lebih tinggi karena komputer tidak sepenuhnya menganggur. Mungkin inti logis lainnya aktif beberapa saat, dan lebih banyak waktu dihabiskan dalam interupsi (karena frekuensi ruang-pengguna diukur lebih jauh di bawah 4,400GHz). Atau beberapa core aktif lebih banyak waktu, menurunkan max turbo. Saya tidak melacak cpu_clk_unhalted.one_thread_activeuntuk melihat apakah persaingan HT adalah masalah.)

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

Kode saya mungkin berjalan dalam siklus yang lebih sedikit di Ryzen, yang dapat mengeluarkan 5 uops per siklus (atau 6 ketika beberapa dari mereka adalah instruksi 2-uop, seperti hal-hal AVX 256b pada Ryzen). Saya tidak yakin apa yang akan dilakukan front-end-nya stosd, yaitu 3 uops di Ryzen (sama dengan Intel). Saya pikir instruksi lain di loop dalam adalah latensi yang sama dengan Skylake dan semua single-uop. (Termasuk adc eax, [edi+edx], yang merupakan keunggulan dibandingkan Skylake).

Ini mungkin bisa secara signifikan lebih kecil, tapi mungkin 9x lebih lambat, jika saya menyimpan angka sebagai 1 angka desimal per byte . Menghasilkan barang bawaan dengan cmpdan menyesuaikan dengan cmovakan bekerja sama, tetapi melakukan 1/9 pekerjaan. 2 digit desimal per byte (basis-100, bukan BCD 4-bit dengan lambatDAA ) juga akan berfungsi, dan div r8/ add ax, 0x3030mengubah 0-99 byte menjadi dua digit ASCII dalam urutan pencetakan. Tapi 1 digit per byte tidak perlu divsama sekali, hanya mengulang dan menambahkan 0x30. Jika saya menyimpan byte dalam urutan pencetakan, itu akan membuat loop ke-2 sangat sederhana.

Menggunakan 18 atau 19 angka desimal per bilangan bulat 64-bit (dalam mode 64-bit) akan membuatnya berjalan sekitar dua kali lebih cepat, tetapi biaya ukuran kode yang signifikan untuk semua awalan REX, dan untuk konstanta 64-bit. 32-bit anggota badan dalam mode 64-bit mencegah menggunakan pop eaxbukan lodsd. Saya masih bisa menghindari awalan REX dengan menggunakan espsebagai register awal non-pointer (menukar penggunaan esidan esp), daripada menggunakan r8dsebagai register ke-8.

Jika membuat versi fungsi-panggilan, konversi ke 64-bit dan menggunakan r8dmungkin lebih murah daripada menyimpan / mengembalikan rsp. 64-bit juga tidak dapat menggunakan dec r32pengodean satu byte (karena ini adalah awalan REX). Tapi kebanyakan saya akhirnya menggunakan dec blyang 2 byte. (Karena saya memiliki konstanta dalam byte atas ebx, dan hanya menggunakannya di luar loop batin, yang berfungsi karena byte rendah dari konstanta adalah 0x00.)

Versi kinerja tinggi

Untuk kinerja maksimum (bukan kode-golf), Anda ingin membuka gulungan lingkaran dalam sehingga menjalankan paling banyak 22 iterasi, yang merupakan pola pengambilan / tidak-ambil yang cukup singkat untuk dilakukan oleh prediktor cabang dengan baik. Dalam eksperimen saya, mov cl, 22sebelum satu .inner: dec cl/jnz .innerloop memiliki sangat sedikit mispredict (seperti 0,05%, jauh lebih sedikit dari satu per putaran penuh dari loop dalam), tetapi mov cl,23mispredict mulai dari 0,35 hingga 0,6 kali per loop dalam. 46sangat buruk, mispredicting ~ 1,28 kali per loop dalam (128M kali untuk iterasi loop luar 100M). 114mispredicted tepat sekali per loop dalam, sama seperti yang saya temukan sebagai bagian dari loop Fibonacci.

Saya jadi penasaran dan mencobanya, membuka gulungan lingkaran dalam dengan 6 %rep 6(karena itu membagi 114 secara merata). Itu sebagian besar menghilangkan kesalahan cabang. Saya membuat edxnegatif dan menggunakannya sebagai offset untuk movtoko, jadi adc eax,[edi]bisa tetap menyatu secara mikro. (Dan supaya aku bisa menghindari stosd). Saya menarik leauntuk memperbarui edikeluar dari %repblok, jadi itu hanya melakukan satu pointer-pembaruan per 6 toko.

Saya juga menyingkirkan semua hal-hal register parsial di loop luar, meskipun saya tidak berpikir itu penting. Mungkin sedikit membantu memiliki CF di ujung loop luar tidak tergantung pada ADC akhir, sehingga beberapa loop dalam loop dapat dimulai. Kode loop luar mungkin dapat dioptimalkan sedikit lebih, karena neg edxadalah hal terakhir yang saya lakukan, setelah mengganti xchgdengan hanya 2 movinstruksi (karena saya sudah memiliki 1), dan mengatur ulang rantai dep bersama dengan menjatuhkan 8-bit daftar barang.

Ini adalah sumber NASM dari hanya loop Fibonacci. Ini pengganti drop-in untuk bagian versi asli.

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

Kinerja:

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

Itu untuk Fib yang sama (1G), menghasilkan output yang sama dalam 62,3 detik, bukan 73 detik. (273.146G siklus, vs. 322.467G. Karena semuanya menyentuh dalam cache L1, siklus clock inti benar-benar yang perlu kita lihat.)

Perhatikan jumlah total jauh lebih uops_issuedrendah, jauh di bawah uops_executedjumlah. Itu berarti banyak dari mereka adalah mikro-menyatu: 1 uop dalam domain menyatu (masalah / ROB), tetapi 2 uops dalam domain yang tidak digunakan (penjadwal / unit eksekusi)). Dan itu sedikit yang dihilangkan pada tahap masalah / ganti nama (seperti movregister copying, atau xor-zeroing, yang perlu dikeluarkan tetapi tidak memerlukan unit eksekusi). Uops yang dieliminasi akan mengacaukan hitungan dengan cara lain.

branch-missesturun ke ~ 400k, dari 1G, jadi membuka gulungan bekerja. resource_stalls.anysignifikan sekarang, yang berarti front-end bukan hambatan lagi: sebaliknya back-end semakin di belakang dan membatasi front-end. idq_uops_not_delivered.corehanya menghitung siklus di mana front-end tidak mengirimkan up, tetapi back-end tidak terhenti. Itu bagus dan rendah, menunjukkan beberapa kemacetan front-end.

Fakta menyenangkan: versi python menghabiskan lebih dari setengah waktunya untuk membagi dengan 10 daripada menambahkan. (Mengganti a/=10dengan a>>=64mempercepatnya lebih dari faktor 2, tetapi mengubah hasilnya karena pemotongan biner! = Pemotongan desimal.)

Versi asm saya tentu saja dioptimalkan secara khusus untuk ukuran masalah ini, dengan loop iteration-menghitung hard coded. Bahkan menggeser angka presisi yang sewenang-wenang akan menyalinnya, tetapi versi saya hanya bisa membaca dari offset untuk dua iterasi berikutnya untuk melewati bahkan itu.

Saya membuat profil versi python (64-bit python2.7 di 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

Angka dalam (parens) adalah berapa kali penghitung perf sedang disampel. Ketika melihat lebih banyak penghitung daripada dukungan HW, perf berputar antara penghitung berbeda dan ekstrapolasi. Itu benar-benar baik untuk jangka panjang dari tugas yang sama.

Jika saya berlari perfsetelah mengatur sysctl kernel.perf_event_paranoid = 0(atau menjalankan perfsebagai root), itu akan mengukur 4.400GHz. cycles:utidak menghitung waktu yang dihabiskan dalam interupsi (atau panggilan sistem), hanya siklus ruang pengguna. Desktop saya hampir sepenuhnya idle, tetapi ini tipikal.

Haskell, 83 61 byte

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)

Output ( F _1000000000 , F _1000000001 ). Di laptop saya, ia mencetak dengan benar paren kiri dan 1000 digit pertama dalam 133 detik, menggunakan memori 1,35 GiB.

Bagaimana itu bekerja

Perulangan Fibonacci dapat diselesaikan dengan menggunakan matriks eksponensial:

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

dari mana kita memperoleh identitas ini:

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

The pToedjoe menghitung fungsi ( F _{i + j} , F _{i + j + 1} ) diberikan ( F _i , F _{i + 1} ) dan ( F _j , F _{j + 1} ). Menulis f nuntuk ( F _i , F _{i +1} ), kami memiliki p (f i) (f j)= f (i + j).

Kemudian,

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

dan kami pasang f 1= (1,1).

Mathematica, 15 34 byte

Fibonacci itu sendiri mengambil ~ 6s di komputer saya. Dan 95 (+/- 5) untuk tampilan depan untuk itu.

Fibonacci@1*^9&

1000 digit pertama (34 byte): ⌊Fibonacci@1*^9/1*^208986640⌋&

Lebih lama tetapi lebih cepat ToString@Fibonacci@1*^9~StringTake~1000&:

Python 2, 70 byte

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

Ini berjalan dalam 18 menit dan 31 detik pada laptop saya, menghasilkan 1000 digit yang benar diikuti oleh 74100118580(digit berikut yang benar adalah 74248787892).

Haskell , 78 byte

(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

Cobalah online!

Butuh 48 detik di TIO. Rumus rekursif yang sama dengan jawaban Python saya , tetapi tanpa memotong.

Konstanta 2143923439adalah 10**9-1, dibalik dalam biner, dan dengan tambahan 1 di akhir. Iterasi melalui digit biner secara terbalik mensimulasikan iterasi melalui digit biner 10**9-1. Tampaknya lebih pendek untuk meng-hardcode ini daripada menghitungnya.

Haskell , 202 184 174 173 170 168 164 162 byte

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

Cobalah online!

Penjelasan

Ini menggunakan cara yang agak cepat untuk menghitung angka fibonacci. Fungsi lmengambil dua fibonacci angka dan menghitung angka fibonacci 10 kemudian, sementara fmengambil n th dan n + 1 th angka fibonacci dan menghitung 2n + 20 th dan 2n + 21 nomor th fibonacci. Saya rantai mereka agak sembarangan untuk mendapatkan 1 miliar dan ambil 1000 digit pertama.

Haskell, 81 byte

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

Penjelasan

f nsecara rekursif menghitung angka nfibonacci menggunakan rekurensi dari jawaban xnor dengan eliminasi common-subexpression. Tidak seperti solusi lain yang telah diposting, yang menggunakan O (log (n)) multiplikasi, kami memiliki rekursi kedalaman O (log (n)) dengan faktor percabangan 2, untuk kompleksitas O (n) multiplikasi.

Namun, semuanya tidak hilang! Karena hampir semua panggilan akan berada di dekat bagian bawah pohon rekursi, kita dapat menggunakan aritmatika asli cepat jika mungkin dan menghindari banyak manipulasi bignum besar. Itu mengeluarkan jawaban dalam beberapa menit di kotak saya.

T-SQL, 422 414 453 byte (Terverifikasi, sekarang bersaing!)

EDIT 2 : Diubah menjadi , Memperoleh beberapa byte tetapi meningkatkan kecepatan yang cukup untuk menyelesaikan hingga 1 miliar! Selesai dalam 45 jam 29 menit , memverifikasi terhadap string yang diberikan, dan menampilkan 8 karakter tambahan (yang mungkin atau mungkin tidak benar karena kesalahan pembulatan).INT BIGINT DECIMAL(37,0)

T-SQL tidak memiliki dukungan asli "angka besar", jadi saya harus menggulung penambah angka besar berbasis teks saya sendiri menggunakan string 1008-karakter:

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 @

Inilah versi yang diformat dengan komentar:

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 @

Pada dasarnya saya secara manual memanipulasi 1008 karakter string berisi nol yang mewakili dua variabel Fibonacci saya, @adan @.

Saya menambahkannya 8 18 36 digit sekaligus, dengan menanggalkan 36 digit terakhir, mengonversinya menjadi tipe numerik yang dapat diatur ( DECIMAL(37,0)), menambahkannya, lalu menghancurkannya kembali menjadi string panjang lainnya @c. Saya kemudian "memutar" @adan @dengan memindahkan 36 digit terakhir ke depan, dan mengulangi prosesnya. 28 rotasi * 36 digit mencakup semua 1008. Saya harus "membawa satu" secara manual.

Setelah nomor kami mulai melebihi panjang string saya, saya "bergeser ke kiri" dan kami mulai kehilangan beberapa ketepatan, tetapi kesalahannya masih dalam karakter tambahan saya.

Saya mencoba menggunakan tabel SQL yang penuh dengan INT dan BIGINT, dengan logika yang sama, dan secara dramatis lebih lambat. Aneh.

PARI / GP, 45 byte

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

Entah bagaimana \p1000tidak cukup. Ini tidak bekerja dengan sistem 32 bit. Pembagian akhir adalah untuk menghindari titik desimal dalam notasi ilmiah.

Pari / GP , 15 + 5 = 20 byte

fibonacci(10^9)

Jalankan dengan opsi baris perintah -s1guntuk mengalokasikan 1 Gbytes memori.

Ruby, 63 byte

***, aku buruk dalam golf ruby; tapi kelas BigInt melakukan keajaiban untuk hal semacam ini. Kami menggunakan algoritma yang sama dengan Anders Kaseorg.

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