На этом сайте было миллиард итераций задач Фибоначчи, поэтому давайте добавим, что задача Фибоначчи состоит из миллиарда итераций!

Ваша задача - вывести первые 1000 десятичных цифр из 1 000 000 000-го числа Фибоначчи с как можно более короткой программой. Это может затем произвольно сопровождаться любым дополнительным выводом по вашему выбору, включая, но не ограничиваясь, остальные цифры.

Я использую конвенции , что fib 0 = 0, fib 1 = 1.

Ваша программа должна быть достаточно быстрой, чтобы вы могли запустить ее и проверить ее правильность. Для этого вот первые 1000 цифр:

7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799

Python 2 + sympy, 72 байта

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

Попробуйте онлайн!

-10 байт, удаляя термин «практически 0» благодаря Джеффу Деге,
-1 байт (1000 -> 1e3 благодаря Захари)
-2 байт, удаляя ненужную переменную, благодаря Эрику Аутгольферу
-2 байта, переходя на Python 2 благодаря Захари
-3 байта за 11 ' -11благодарности ThePirateBay -3 байта путем замены strбэкстиков благодаря notjagan

теперь превосходит неопубликованное решение OP на Haskell!

Python 2 , 106 байт

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

Попробуйте онлайн!

Нет библиотек, только целочисленная арифметика. Запускается практически мгновенно.

Основой является тождество «разделяй и властвуй»:

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

Это позволяет нам обновляться (a,b) = (f(n),f(n+1))в два раза n -> 2*n. Поскольку мы хотим получить n=10**9, это занимает только log_2(10**9)=30итерации. Мы строим nдо 10**9, неоднократно делая n->2*n+cдля каждой цифры cсвоего двоичного расширения. Когда c==1удвоенное значение сдвигается вверх 2*n -> 2*n+1с одношаговым сдвигом Фибоначчи(a,b)=(b+a,b)

Чтобы сохранить a,bуправляемые значения , мы храним только их первые 1006цифры путем деления на полы 10до тех пор, пока они не станут меньше 2**3340 ~ 1e1006.

32-разрядный машинный код x86 (с системными вызовами Linux): 106 105 байт

changelog: сохранил байт в быстрой версии, поскольку постоянная константа не меняет результат для Fib (1G).

Или 102 байта для 18% более медленной (на Skylake) версии (используя mov/ sub/ cmcвместо lea/ cmpво внутреннем цикле, чтобы генерировать вынос и обертывание 10**9вместо 2**32). Или 101 байт для ~ 5,3x более медленной версии с ветвью в обработке переноса в самом внутреннем цикле. (Я измерил 25,4% ошибок в ветвях!)

Или 104/101 байт, если разрешен начальный ноль. (Требуется 1 дополнительный байт для жесткого кодирования, пропуская 1 цифру вывода, что и требуется для Fib (10 ** 9)).

К сожалению, режим NASM в TIO игнорируется -felf32флагами компилятора. В любом случае, вот ссылка на мой полный исходный код со всеми путаницами экспериментальных идей в комментариях.

Это полная программа . Он печатает первые 1000 цифр Fib (10 ** 9), за которыми следуют несколько дополнительных цифр (последние несколько из которых неправильные), за которыми следуют некоторые байты мусора (не включая символ новой строки). Большая часть мусора не ASCII, так что вы можете захотеть пройти через cat -v. Это не нарушает мой эмулятор терминала (KDE konsole). «Мусорные байты» хранят Fib (999999999). У меня уже был -1024в реестре, так что было дешевле печатать 1024 байта, чем правильный размер.

Я считаю только машинный код (размер текстового сегмента моего статического исполняемого файла), а не пух, который делает его исполняемым ELF. ( Возможны очень маленькие исполняемые файлы ELF , но я не хотел беспокоиться об этом). Оказалось, что использовать стековую память вместо BSS короче, поэтому я могу оправдать то, что в двоичном коде я ничего не считаю, поскольку не зависим от метаданных. (При обычном преобразовании статического двоичного файла получается исполняемый файл ELF размером 340 байт.)

Из этого кода вы могли бы сделать функцию, которую вы могли бы вызывать из C. Для сохранения / восстановления указателя стека (возможно, в регистре MMX) и некоторых других служебных расходов потребовалось бы несколько байтов, а также для сохранения байтов путем возврата со строкой в памяти вместо write(1,buf,len)системного вызова. Я думаю, что игра в гольф в машинном коде должна немного ослабить меня, поскольку никто другой даже не опубликовал ответ на каком-либо языке без встроенной расширенной точности, но я думаю, что функциональная версия этого файла все равно должна иметь размер менее 120 байт без повторной обработки всего вещь.

Алгоритм:

грубая сила a+=b; swap(a,b), усеченная по мере необходимости, чтобы сохранить только первые> = 1017 десятичных цифр. Он запускается за 1 мин 13 с на моем компьютере (или 322,47 млрд тактовых циклов + - 0,05%) (и может быть на несколько% быстрее с несколькими дополнительными байтами размера кода или до 62 с гораздо большим размером кода при развертывании цикла. Нет умная математика, просто делаю ту же работу с меньшими накладными расходами). Он основан на реализации Python @ AndersKaseorg , которая работает на моем компьютере за 12 минут 35 секунд (4,4 ГГц Skylake i7-6700k). Ни в одной версии нет ошибок кэша L1D, поэтому мой DDR4-2666 не имеет значения.

В отличие от Python, я храню числа с расширенной точностью в формате, который освобождает усечение десятичных цифр . Я храню группы из 9 десятичных цифр на 32-разрядное целое число, поэтому смещение указателя отбрасывает младшие 9 цифр. Фактически это базовый 1 миллиард, то есть степень 10. (Это чистое совпадение, что для этого вызова требуется 1-миллиардное число Фибоначчи, но оно спасает меня пару байтов против двух отдельных констант.)

Следуя терминологии GMP , каждый 32-разрядный фрагмент номера с расширенной точностью называется «конечностью». Выполнение при добавлении должно быть сгенерировано вручную со сравнением с 1e9, но затем обычно используется в качестве входных данных для обычной ADCинструкции для следующего лимба. (Я также должен вручную переносить в [0..999999999]диапазон, а не в 2 ^ 32 ~ = 4.295e9. Я делаю это без lea+ ветвлений cmov, используя результат выполнения сравнения.)

Когда последняя ветвь производит ненулевое выполнение, следующие две итерации внешнего цикла читаются на 1 конечность выше, чем обычно, но все еще записывают в то же место. Это похоже на выполнение memcpy(a, a+4, 114*4)сдвига вправо на 1 конечность, но в рамках следующих двух циклов сложения. Это происходит каждые ~ 18 итераций.

Хаки для экономии размера и производительности:

• Обычные вещи вроде lea ebx, [eax-4 + 1]вместо того mov ebx, 1, когда я это знаю eax=4. И использование loopв местах, где LOOPмедлительность оказывает лишь незначительное влияние.

• Обрежьте на 1 конечность бесплатно, сместив указатели, с которых мы читаем, при этом продолжая запись в начало буфера во adcвнутреннем цикле. Мы читаем [edi+edx]и пишем [edi]. Таким образом, мы можем получить edx=0или 4получить смещение чтения-записи для места назначения. Мы должны сделать это для двух последовательных итераций, сначала смещая обе, а затем смещая только dst. Мы обнаруживаем 2-й случай, посмотрев esp&4перед сбросом указателей на переднюю часть буферов (используя &= -1024, потому что буферы выровнены). Смотрите комментарии в коде.

• Среда запуска процессов в Linux (для статического исполняемого файла) обнуляет большинство регистров, а память стека ниже esp/ rspобнуляется. Моя программа использует это преимущество. В этой версии с вызываемой функцией (где нераспределенный стек может быть грязным), я мог бы использовать BSS для обнуленной памяти (по стоимости, возможно, еще 4 байта для установки указателей). Обнуление edxзаняло бы 2 байта. ABI System V x86-64 не гарантирует ни того, ни другого, но реализация Linux делает его нулевым (чтобы избежать утечки информации из ядра). В динамически связанном процессе /lib/ld.soвыполняется до _startи оставляет регистры ненулевыми (и, вероятно, мусор в памяти ниже указателя стека).

• Я держу -1024в ebxдля использования снаружи петель. Используйте blв качестве счетчика для внутренних циклов, заканчивающихся нулем (который является младшим байтом -1024, таким образом, восстанавливая константу для использования вне цикла). В Intel Haswell и более поздних версиях нет штрафов за частичное объединение регистров для регистров low8 (и фактически даже не переименовывают их отдельно) , поэтому существует зависимость от полного регистра, как у AMD (здесь нет проблем). Это было бы ужасно для Nehalem и более ранних, хотя, у которых есть срывы частичного регистра при слиянии. Есть и другие места, где я пишу частичные регистры, а затем читаю полный xorрегистр без нуля илиmovzxобычно потому, что я знаю, что какой-то предыдущий код обнулял верхние байты, и опять же, это нормально для AMD и семейства Intel SnB, но медленно для Intel до Sandybridge.

  Я использую 1024в качестве количества байтов для записи в stdout ( sub edx, ebx), поэтому моя программа печатает некоторые байты мусора после цифр Фибоначчи, потому что mov edx, 1000стоит больше байтов.

• (не используется) adc ebx,ebxс EBX = 0, чтобы получить EBX = CF, экономя 1 байт против setc bl.

• dec/ jnzвнутри adcцикла сохраняет CF, не вызывая частичного adcостанова флага, когда читает флаги на Intel Sandybridge и позже. Это плохо на более ранних процессорах , но AFAIK бесплатно на Skylake. Или, в худшем случае, лишний уп.

• Используйте память ниже espкак гигантскую красную зону . Поскольку это полноценная программа для Linux, я знаю, что не установил никаких обработчиков сигналов, и что ничто другое не будет асинхронно захламлять память стека пространства пользователя. Это может быть не так в других ОС.

• Воспользуйтесь механизмом стека, чтобы сэкономить пропускную способность проблемы uop, используя pop eax(1 моп + случайный стековый синхронизатор мопов) вместо lodsd(2 моп на Haswell / Skylake, 3 на IvB и более ранние в соответствии с таблицами инструкций Agner Fog )). Во IIRC это время работы сократилось с 83 секунд до 73. Вероятно, я мог бы получить ту же скорость при использовании a movс индексным режимом адресации, например, mov eax, [edi+ebp]где ebpхранится смещение между буферами src и dst. (Это сделало бы код вне внутреннего цикла более сложным, так как пришлось бы отменять регистр смещения как часть обмена src и dst для итераций Фибоначчи.) Подробнее см. В разделе «производительность» ниже.

• начните последовательность, предоставив первой итерации перенос (один байт stc) вместо сохранения 1в памяти где-либо. Множество других проблемных вещей, задокументированных в комментариях.

Список NASM (машинный код + источник) , сгенерированный с помощью nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Затем я удалил некоторые блоки комментариев, чтобы нумерация строк имела пропуски.) Чтобы удалить ведущие столбцы, чтобы вы могли передать их в YASM или NASM, используйте 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

Возможно, из этого есть место для игры в гольф, но я уже потратил на это как минимум 12 часов за 2 дня. Я не хочу жертвовать скоростью, даже если она более чем достаточно быстра и есть место, чтобы уменьшить ее так, чтобы это стоило скорости . Одна из причин, по которой я пишу, - это то, как быстро я могу сделать асим-версию методом грубой силы. Если кто-то действительно хочет использовать минимальный размер, но, возможно, в 10 раз медленнее (например, 1 цифра на байт), не стесняйтесь скопировать его в качестве отправной точки.

Результирующий исполняемый файл (из yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) - 340B (лишенный):

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

Представление

Внутренний adcцикл - 10 мопов с плавкой областью на Skylake (+1 мера синхронизации стека каждые ~ 128 байт), поэтому он может выдавать один раз за ~ 2,5 цикла на Skylake с оптимальной пропускной способностью внешнего интерфейса (игнорируя моты стековой синхронизации) , Задержка критического пути составляет 2 цикла для цепочки зависимостей, переносимой в цикле следующей итерации adc-> cmp-> adc, поэтому узким местом должно быть ограничение исходной задачи ~ 2,5 цикла на итерацию.

adc eax, [edi + edx]2 неопубликованных мопа для портов выполнения: нагрузка + ALU. Микроплавкие предохранители в декодерах (1 моп в слитых доменах), но на стадии выдачи не расслаиваются до 2 мопов в слитых доменах из-за режима индексированной адресации даже в Haswell / Skylake . Я думал, что он останется с микросинтеграцией, как и add eax, [edi + edx]делает, но, возможно, сохранение индексированных режимов адресации с микроплавлением не работает для мопов, у которых уже есть 3 входа (флаги, память и место назначения). Когда я писал это, я думал, что у него не будет снижения производительности, но я ошибался. Этот способ обработки усечения замедляет внутренний цикл каждый раз, будь то edx0 или 4.

Было бы быстрее обрабатывать смещение чтения-записи для dst путем смещения ediи использования edxдля настройки хранилища. Итак adc eax, [edi]/ ... / mov [edi+edx], eax/ lea edi, [edi+4]вместо stosd. Haswell и более поздние могут хранить индексированный магазин в микроплавлении. (Sandybridge / IvB тоже не расслаивается.)

На Intel Haswell и ранее, adcи cmovc2 микрооперации каждая, 2с латентности . ( adc eax, [edi+edx]все еще не ламинирован на Haswell и выпускается как 3 мопа слитых доменов). Broadwell и более поздние версии допускают 3-х входные мопы для большего, чем просто FMA (Haswell), делая adcи cmovc(и пару других) однопроцессных инструкций, как это было в AMD в течение долгого времени. (Это одна из причин, по которой AMD долгое время преуспевала в тестах GMP с расширенной точностью.) В любом случае, внутренний цикл Haswell должен составлять 12 мопов (иногда - +1 стек-синхронизация мопов), с внешним узким местом ~ 3c в в лучшем случае, игнорируя стековые синхронизации

Использование popбез балансировки pushвнутри цикла означает, что цикл не может выполняться из LSD (детектора потока цикла) , и его необходимо каждый раз перечитывать из кэша UOP в IDQ. Во всяком случае, это хорошая вещь на Skylake, так как цикл 9 или 10 моп не дает оптимальной выдачи при 4 моп в каждом цикле . Это, вероятно, часть того, почему замена lodsdна popтак сильно помогла. (ЛСД не может заблокировать мопы, потому что это не оставит места для вставки мера стековой синхронизации .) (Кстати, обновление микрокода полностью отключает ЛСД на Skylake и Skylake-X, чтобы исправить ошибку. Я измерил выше, прежде чем получить это обновление.)

Я профилировал его на Haswell и обнаружил, что он работает с 381,31 млрд тактов (независимо от частоты процессора, поскольку он использует только кэш L1D, а не память). Пропускная способность переднего плана составляла 3,72 мопов слитых доменов за такт против 3,70 для Skylake. (Но, конечно , инструкции за цикл снизился до 2,42 с 2,87, потому что adcи cmov2 микрооперации на Haswell.)

pushзамена, stosdвероятно, не очень поможет, потому adc [esp + edx]что каждый раз будет запускать синхронизацию стека. И будет стоить байт, stdтак что lodsdидет в другом направлении. ( mov [edi], eax/ lea edi, [edi+4]заменить stosd- это выигрыш: от 32 909 циклов для 100M итеров до 31 954 циклов для 100 миллионов итеров. Кажется, что stosdдекодируется как 3 мопа, а маны store-address / store-data не микросопряжены, поэтому push+ синхронизация стека мопс все равно может быть быстрее чем stosd)

Фактическая производительность ~ 322,47 миллиардов циклов для 1G итераций 114 конечностей составляет 2,824 цикла на итерацию внутреннего цикла для быстрой версии 105B на Skylake. (Смотрите ocperf.pyвывод ниже). Это медленнее, чем я предполагал из статического анализа, но я игнорировал издержки внешнего цикла и любые операции синхронизации стека.

Perf подсчитывает branchesи branch-missesпоказывает, что внутренний цикл неверно предсказывает один раз за внешний цикл (на последней итерации, когда она не берется). Это также составляет часть дополнительного времени.

Я мог бы сохранить размер кода, установив для самого внутреннего цикла 3-тактовую задержку для критического пути, используя mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) вместо lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B ). cmov/ stosdВыключен критический путь. (Операция increment-ediop of stosdможет запускаться отдельно от хранилища, поэтому каждая итерация разветвляется на короткую цепочку зависимостей.) Раньше она сохраняла еще 1B, изменяя инструкцию ebp init с lea ebp, [ecx-1]на mov ebp,eax, но я обнаружил, что неправильноebpне изменил результат. Это позволило бы конечности быть точно == 1000000000 вместо переноса и создания переноса, но эта ошибка распространяется медленнее, чем рост Fib (), так что это не приводит к изменению первых 1k цифр конечного результата. Кроме того, я думаю, что ошибка может исправить себя, когда мы просто добавляем, так как в конечности есть место, чтобы держать ее без переполнения. Даже 1G + 1G не переполняет 32-разрядное целое число, поэтому оно в конечном итоге будет просачиваться вверх или обрезаться.

Версия с задержкой 3c составляет 1 дополнительный такт, поэтому интерфейс может выдавать ее один раз в 2,75 циклов на Skylake, лишь немного быстрее, чем сервер может его запустить. (На Haswell это будет всего 13 мопов, так как он все еще использует adcи cmov, и узкое место на входе составляет 3.25c на итера).

На практике он работает в 1,18 раза медленнее на Skylake (3,34 цикла на конечность), чем на 3 / 2,5 = 1,2, который я предсказал для замены входного узкого места узким местом с задержкой от простого просмотра внутреннего цикла без синхронизации стека микрооперации. Поскольку стековые синхронизации синхронизируют только быструю версию (узкое место во внешнем интерфейсе вместо задержки), объяснение этого не займет много времени. например, 3 / 2,54 = 1,18.

Еще один фактор заключается в том, что версия с задержкой 3c может обнаруживать ошибочный прогноз при выходе из внутреннего цикла, в то время как критический путь все еще выполняется (потому что внешний интерфейс может опередить серверную часть, позволяя незапланированному выполнению запустить цикл. counter uops), поэтому эффективный штраф за неправильный прогноз ниже. Потеря этих циклов переднего плана позволяет фону наверстать упущенное.

Если бы не это, мы могли бы ускорить cmcверсию 3c , используя ветвь во внешнем цикле вместо обработки без ветвей смещений carry_out -> edx и esp. Предсказание ветвлений + спекулятивное выполнение для управляющей зависимости вместо зависимости от данных может позволить следующей итерации запустить adcцикл, пока мопы из предыдущего внутреннего цикла все еще находились в полете. В версии без ответвлений адреса загрузки во внутреннем цикле зависят от данных CF последней adcиз последней ветви.

Версия с внутренним контуром с задержкой 2c является узким местом на передней части, так что внутренняя часть в значительной степени не отстает. Если бы во внешнем цикле был код с высокой задержкой, внешний интерфейс мог бы выполнить выдачу мопов из следующей итерации внутреннего цикла. (Но в этом случае во внешнем цикле много ILP и нет элементов с высокой задержкой, поэтому бэк-энду не нужно сильно догонять, когда он начинает жевать мопы в планировщике вне очереди, как их входы становятся готовыми).

### 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 %)стандартное отклонение для 4 прогонов для этого количества. Интересно, что запускается такое круглое количество инструкций. Эти 924 миллиарда не случайность. Я предполагаю, что внешний цикл выполняет 924 инструкции.

uops_issued- это число слитых доменов (относится к полосе пропускания uops_executedвнешней проблемы), а число неиспользуемых доменов (количество мопов, отправленных на порты выполнения). Micro-fusion упаковывает 2 мопа с неиспользованным доменом в один моп с объединенным доменом, но удаление с помощью mov означает, что некоторым мопам с плавким доменом не требуются порты выполнения См. Связанный вопрос для получения дополнительной информации о подсчете мопов и слитых и не слитых доменов. (Также смотрите таблицы инструкций Agner Fog и руководство по uarch и другие полезные ссылки в вики-тэге SO x86 ).

С другой стороны, измеряя разные вещи: пропуски L1D-кэша совершенно незначительны, как и ожидалось для чтения / записи тех же двух буферов 456B. Ветвь внутренней петли неверно предсказывает один раз за внешнюю петлю (когда не требуется выходить из петли). (Общее время выше, потому что компьютер не был полностью бездействующим. Возможно, какое-то время другое логическое ядро ​​было активным, и в прерываниях было потрачено больше времени (поскольку частота, измеренная в пространстве пользователя, была ниже 4,400 ГГц). Или несколько ядер были активны большую часть времени, снижая максимальный турбо. Я не отслеживал, cpu_clk_unhalted.one_thread_activeбыло ли соревнование HT проблемой.)

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

Мой код вполне может выполняться за меньшее количество циклов на Ryzen, который может выдавать 5 мопов за цикл (или 6, когда некоторые из них представляют собой 2-х тактные инструкции, такие как AVX 256b на Ryzen). Я не уверен, что его интерфейс будет делать с stosd3 мопами на Ryzen (так же, как Intel). Я думаю, что другие инструкции во внутреннем цикле имеют ту же задержку, что и Skylake, и все одиночные операции. (В том числе adc eax, [edi+edx], что является преимуществом перед Skylake).

Вероятно, это может быть значительно меньше, но, возможно, в 9 раз медленнее, если я сохраню числа как 1 десятичную цифру на байт . Генерация выполнения с cmpнастройкой cmovи работа с ними будет работать одинаково, но выполнять 1/9 работы. 2 десятичных знака на байт (base-100, а не 4-битный BCD с медленнымDAA ) также будут работать, и div r8/ / add ax, 0x3030превращает 0-99 байт в две ASCII-цифры в порядке печати. Но 1 цифра на байт совсем не нужна div, просто зацикливание и добавление 0x30. Если я сохраню байты в порядке печати, это сделает 2-й цикл действительно простым.

Использование 18 или 19 десятичных цифр на 64-разрядное целое число (в 64-разрядном режиме) позволило бы запустить его примерно в два раза быстрее, но стоило бы значительного размера кода для всех префиксов REX и для 64-разрядных констант. 32-битные конечности в 64-битном режиме не позволяют использовать pop eaxвместо lodsd. Я мог бы по-прежнему избегать использования префиксов REX, используя espрегистр нуля без указателя (обмениваясь использованием esiи esp), вместо использования r8dв качестве восьмого регистра.

При создании версии с вызываемой функцией преобразование в 64-битную версию и ее использование r8dможет оказаться дешевле, чем сохранение / восстановление rsp. 64-битный также не может использовать однобайтовую dec r32кодировку (так как это префикс REX). Но в основном я использовал dec bl2 байта. (Потому что у меня есть константа в старших байтах ebx, и я использую ее только вне внутренних циклов, что работает, потому что младший байт константы есть 0x00.)

Высокопроизводительная версия

Для достижения максимальной производительности (не код-гольф) вам нужно развернуть внутренний цикл, чтобы он выполнялся не более 22 итераций, что является достаточно коротким шаблоном «взят / не принят», чтобы предсказатели ветвлений работали хорошо. В моих экспериментах mov cl, 22перед .inner: dec cl/jnz .innerциклом было очень мало ошибочных прогнозов (например, 0,05%, намного меньше, чем один за полный цикл внутреннего цикла), но mov cl,23ошибочно прогнозировалось от 0,35 до 0,6 раза за внутренний цикл. 46особенно плохо, неправильно прогнозирует ~ 1,28 раза за внутренний цикл (128M раз за 100M итераций внешнего цикла). 114ошибочно прогнозируется ровно один раз для каждого внутреннего цикла, как я обнаружил в рамках цикла Фибоначчи.

Мне стало любопытно, и я попробовал это, развернув внутренний цикл на 6 с %rep 6(потому что это делит 114 равномерно). Это в основном устраняет промахи веток. Я сделал edxотрицательный результат и использовал его как офсет для movмагазинов, так что adc eax,[edi]смог остаться в микрослиянии. (И чтобы я мог избежать stosd). Я вытащил leaдля обновления ediиз %repблока, так что он делает только одно обновление указателя на 6 магазинов.

Я также избавился от всей частичной регистрации во внешнем цикле, хотя я не думаю, что это было важно. Возможно, это немного помогло иметь CF в конце внешнего цикла, не зависящего от конечного АЦП, так что некоторые из внутренних циклов цикла могут начаться. Код внешнего цикла, вероятно, можно было бы оптимизировать немного больше, поскольку это neg edxбыло последнее, что я сделал после замены xchgвсего лишь двумя movинструкциями (так как у меня уже было 1) и перестановки цепочек dep вместе с удалением 8-битного зарегистрировать вещи.

Это источник NASM только петли Фибоначчи. Это вставная замена для этого раздела оригинальной версии.

  ;;;; Main loop, optimized for performance, not code-size
%assign unrollfac 6
    mov    bl, limbcount/unrollfac  ; and at the end of the outer loop
    align 32
.fibonacci:
limbcount equ 114             ; 112 = 1006 decimal digits / 9 digits per limb.  Not enough for 1000 correct digits, but 114 is.
                              ; 113 would be enough, but we depend on limbcount being even to avoid a sub
;    align 8
.digits_add:

%assign i 0
%rep unrollfac
    ;lodsd                       ; Skylake: 2 uops.  Or  pop rax  with rsp instead of rsi
;    mov    eax, [esp]
;    lea    esp, [esp+4]   ; adjust ESP without affecting CF.  Alternative, load relative to edi and negate an offset?  Or add esp,4 after adc before cmp
    pop    eax
    adc    eax, [edi+i*4]    ; read from a potentially-offset location (but still store to the front)
 ;; jz .out   ;; Nope, a zero digit in the result doesn't mean the end!  (Although it might in base 10**9 for this problem)

    lea    esi, [eax - 1000000000]
    cmp    ebp, eax                ; sets CF when (base-1) < eax.  i.e. when eax>=base
    cmovc  eax, esi                ; eax %= base, keeping it in the [0..base) range
%if 0
    stosd
%else
  mov    [edi+i*4+edx], eax
%endif
%assign i i+1
%endrep
  lea   edi, [edi+4*unrollfac]

    dec    bl                      ; preserves CF.  The resulting partial-flag merge on ADC would be slow on pre-SnB CPUs
    jnz .digits_add
    ; bl=0, ebx=-1024
    ; esi has its high bit set opposite to CF
.end_innerloop:
    ;; after a non-zero carry-out (CF=1): right-shift both buffers by 1 limb, over the course of the next two iterations
    ;; next iteration with r8 = 1 and rsi+=4:  read offset from both, write normal.  ends with CF=0
    ;; following iter with r8 = 1 and rsi+=0:  read offset from dest, write normal.  ends with CF=0
    ;; following iter with r8 = 0 and rsi+=0:  i.e. back to normal, until next carry-out (possible a few iters later)

    ;; rdi = bufX + 4*limbcount
    ;; rsi = bufY + 4*limbcount + 4*carry_last_time

;    setc   [rdi]
;    mov    dl, dh               ; edx=0.  2c latency on SKL, but DH has been ready for a long time
;    adc    edx,edx    ; edx = CF.  1B shorter than setc dl, but requires edx=0 to start
    setc   al
    movzx  edx, al
    mov    [edi], edx ; store the carry-out into an extra limb beyond limbcount
    shl    edx, 2
    ;; Branching to handle the truncation would break the data-dependency (of pointers) on carry-out from this iteration
    ;;  and let the next iteration start, but we bottleneck on the front-end (9 uops)
    ;;  not the loop-carried dependency of the inner loop (2 cycles for adc->cmp -> flag input of adc next iter)
    ;; Since the pattern isn't perfectly regular, branch mispredicts would hurt us

    ; keep -1024 in ebx.  Using bl for the limb counter leaves bl zero here, so it's back to -1024 (or -2048 or whatever)
    mov    eax, esp
    and    esp, 4               ; only works if limbcount is even, otherwise we'd need to subtract limbcount first.

    and    edi, ebx  ; -1024    ; revert to start of buffer, regardless of offset
    add    edi, edx             ; read offset in next iter's src
    ;; maybe   or edi,edx / and edi, 4 | -1024?  Still 2 uops for the same work
    ;;  setc dil?

    ;; after adjusting src, so this only affects read-offset in the dst, not src.
    or     edx, esp             ; also set r8d if we had a source offset last time, to handle the 2nd buffer
    mov    esp, edi

;    xchg   edi, esp   ; Fibonacci: dst and src swap
    and    eax, ebx  ; -1024

    ;; mov    edi, eax
    ;; add    edi, edx
    lea    edi, [eax+edx]
    neg    edx            ; negated read-write offset used with store instead of load, so adc can micro-fuse

    mov    bl, limbcount/unrollfac
    ;; Last instruction must leave CF clear for next iter
;    loop .fibonacci  ; Maybe 0.01% slower than dec/jnz overall
;    dec ecx
    sub ecx, 1                  ; clear any flag dependencies.  No faster than dec, at least when CF doesn't depend on edx
    jnz .fibonacci

Представление:

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

Это для того же Fibre (1G), производящего тот же результат за 62,3 секунды вместо 73 секунд. (273,146G циклов против 322,467G. Поскольку все попадает в кэш L1, тактовые частоты ядра - это действительно все, на что мы должны смотреть.)

Обратите внимание на гораздо более низкое общее uops_issuedколичество, значительно ниже uops_executedколичества. Это означает, что многие из них были микросинхронизированы: 1 моп в объединенном домене (выпуск / ROB), но 2 моп в незадействованном домене (планировщик / исполнительные блоки)). И некоторые из них были устранены на этапе выпуска / переименования (например, movкопирование регистра или xor-зеро, которые должны быть выданы, но не нуждаются в исполнительном модуле). Исключенные мопы нарушат баланс в другом направлении.

branch-missesдо ~ 400k, с 1G, поэтому развертывание сработало. resource_stalls.anyтеперь важно, что означает, что передний конец больше не является узким местом: вместо этого задний конец отстает и ограничивает передний конец. idq_uops_not_delivered.coreучитывает только циклы, в которых интерфейс не доставлял мопы, но сервер не остановился. Это хорошо и низко, указывая на несколько узких мест переднего плана.

Забавный факт: версия на python тратит больше половины своего времени на деление на 10, а не на добавление. (Замена a/=10с a>>=64ускоряет его более чем в 2 раза, но меняет результат, потому что двоичное усечение! = Десятичное усечение.)

Моя версия asm, конечно, оптимизирована специально для этого размера проблемы, с жестко запрограммированными счетчиками итераций цикла. Даже смещение числа произвольной точности скопирует его, но моя версия может просто прочитать смещение за следующие две итерации, чтобы пропустить даже это.

Я профилировал версию python (64-битный python2.7 на 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

Числа в (parens) показывают, сколько времени отбор проб осуществлялся с помощью счетчика перфорирования. При просмотре большего количества счетчиков, чем поддерживает HW, перфоманс переключается между различными счетчиками и экстраполирует. Это вполне нормально для длительного выполнения одной и той же задачи.

Если бы я запускал perfпосле установки sysctl kernel.perf_event_paranoid = 0(или запуска perfот имени root), он бы измерял 4.400GHz. cycles:uне учитывает время, потраченное на прерывания (или системные вызовы), только циклы пользовательского пространства. Мой рабочий стол почти полностью простаивал, но это типично.

Haskell, 83 61 байт

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)

Выходы ( F _1000000000 , F _1000000001 ). На моем ноутбуке он правильно печатает левую пареню и первые 1000 цифр в течение 133 секунд, используя 1,35 ГБ памяти.

Как это устроено

Рецидив Фибоначчи может быть решен с использованием матричного возведения в степень:

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

из которого мы получаем эти идентичности:

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

В pфункции вычисляет ( Р _{я + J} , Р _{я + J + 1} ) с учетом ( Р _я , Р _{я + 1} ) и ( F _J , F _{J + 1} ). Пишем f nдля ( F _i , F _{i + 1} ), имеем p (f i) (f j)= f (i + j).

Затем,

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

и мы подключаем f 1= (1,1).

Математика, 15 34 байтов

Fibonacci само по себе занимает ~ 6с на моем компьютере. И 95 (+/- 5) с для внешнего интерфейса, чтобы отобразить его.

Fibonacci@1*^9&

Первые 1000 цифр (34 байта): ⌊Fibonacci@1*^9/1*^208986640⌋&

Дольше, но быстрее ToString@Fibonacci@1*^9~StringTake~1000&:

Python 2, 70 байт

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

На моем ноутбуке это заняло 18 минут и 31 секунду, после чего были введены правильные 1000 цифр 74100118580(правильные следующие цифры 74248787892).

Haskell , 78 байт

(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

Попробуйте онлайн!

На TIO ушло 48 секунд. Та же самая рекурсивная формула, что и в моем Python-ответе , но без усечения.

Константа 2143923439в 10**9-1обратном порядке в двоичном виде и с дополнительным 1 в конце. Итерация по двоичным цифрам в обратном порядке имитирует итерацию по двоичным цифрам 10**9-1. Кажется, короче жестко закодировать это, чем вычислить.

Haskell , 202 184 174 173 170 168 164 162 байта

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

Попробуйте онлайн!

объяснение

Это использует довольно быстрый способ для вычисления чисел Фибоначчи. Функция lберет два числа Фибоначчи и вычисляет числа Фибоначчи 10 позже, а fберет n- е и n + 1- е числа Фибоначчи и вычисляет 2n + 20- е и 2n + 21- е числа Фибоначчи. Я цепляю их довольно случайно, чтобы получить 1 миллиард и получить первые 1000 цифр.

Haskell, 81 байт

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

объяснение

f nРекурсивно вычисляет число nФибоначчи, используя рекурсию из ответа xnor с устранением общего подвыражения. В отличие от других опубликованных решений, которые используют умножения O (log (n)), мы имеем рекурсию глубины O (log (n)) - с коэффициентом ветвления 2 для сложности умножений O (n).

Однако еще не все потеряно! Поскольку почти все вызовы будут находиться в нижней части дерева рекурсии, мы можем по возможности использовать быструю встроенную арифметику и избегать множества манипуляций с огромными бигнумами. Через пару минут он выкладывает ответ на мой ящик.

T-SQL, 422 414 453 байта (проверено, теперь конкурирует!)

РЕДАКТИРОВАТЬ 2 : Изменено , получил несколько байтов, но увеличил скорость достаточно, чтобы завершить до 1 миллиарда! Завершено за 45 часов 29 минут , проверяет соответствие данной строке и отображает дополнительные 8 символов (что может быть или не быть правильным из-за ошибок округления).INT BIGINT DECIMAL(37,0)

T-SQL не имеет встроенной поддержки «огромного числа», поэтому пришлось свернуть мой собственный текстовый сумматор огромных чисел, используя строки из 1008 символов:

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 @

Вот отформатированная версия с комментариями:

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 @

По сути, я вручную манипулирую 1008-символьными строками, заполненными нулями, представляющими две мои переменные Фибоначчи, @aи @.

Я добавляю их по 8 18 36 цифр за раз, убирая последние 36 цифр, преобразовывая их в управляемый числовой тип ( DECIMAL(37,0)), добавляя их, а затем разбивая обратно в другую длинную строку @c. Я тогда «поворот» @aи @перемещая последние 36 цифр к фронту, и повторяя процесс. 28 вращений * 36 цифр охватывает все 1008. Я должен «нести один» вручную.

Как только наше число начинает превышать мою длину строки, я «сдвигаюсь влево», и мы начинаем терять некоторую точность, но ошибка вполне в моих дополнительных символах.

Я попытался использовать таблицу SQL, полную INT и BIGINT, с похожей логикой, и она была значительно медленнее. Weird.

PARI / GP, 45 байт

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

Как-то \p1000не достаточно. Это не работает с 32-битными системами. Последнее разделение состоит в том, чтобы избежать десятичной точки в научной нотации.

Пари / ГП , 15 + 5 = 20 байт

fibonacci(10^9)

Запустите с параметром командной строки, -s1gчтобы выделить 1 Гбайт памяти.

Рубин, 63 байта

чувак, я плохо играю в гольф-рубин; но класс BigInt делает чудеса для такого рода вещей. Мы используем тот же алгоритм, что и Anders Kaseorg.

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