title: Extreme Fibonacci

text:
# Question
Title: Extreme Fibonacci
There have been a billion iterations of Fibonacci challenges on this website, so lets spice things up with a Fibonacci challenge of a billion iterations!

Your challenge is to output the first 1000 decimal digits of the 1,000,000,000th Fibonacci number with as short a program as possible. This may then optionally be followed by any additional output of your choosing, including but not limited to the rest of the digits.

I am using the convention that `fib 0 = 0`, `fib 1 = 1`.

Your program must be fast enough for you to run it and verify its correctness. For this purpose, here are the first 1000 digits:

```
7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799

```

# Answer
> 13 votes
# Mathematica, 15 ~~34~~ bytes

`Fibonacci` **itself** takes ~6s on my computer. And 95(+/-5)s for frontend to display it.

```
Fibonacci@1*^9&

```

The first 1000 digits (34 bytes): `⌊Fibonacci@1*^9/1*^208986640⌋&`

Longer but faster `ToString@Fibonacci@1*^9~StringTake~1000&`:

# Answer
> 37 votes
# Python 2 \+ sympy, 72 bytes

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

```

Try it online!

-10 bytes by removing the practically-0 term thanks to Jeff Dege
-1 byte (1000 -\> 1e3 thanks to Zacharý)
-2 bytes by removing the unnecessary variable thanks to Erik the Outgolfer
-2 bytes by moving to Python 2 thanks to Zacharý
-3 bytes by 11'ing the `-11` thanks to ThePirateBay -3 bytes by swapping `str` for backticks thanks to notjagan

now beats OP's unposted haskell solution!

# Answer
> 35 votes
# Python 2, 106 bytes

```
a,b=0,1
for c in bin(10**9):
 a,b=2*a*b-a*a,a*a+b*b
 if'1'==c:a,b=b,a+b
 while a>>3340:a/=10;b/=10
print a

```

Try it online!

No libraries, just integer arithmetic. Runs almost instantly.

The core is the divide-and-conquer identity:

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

```

This lets us update `(a,b) = (f(n),f(n+1))` to double `n -> 2*n`. Since we want to get `n=10**9`, this takes only `log_2(10**9)=30` iterations. We build `n` up to `10**9` by repeatedly doing `n->2*n+c` for each digit `c` of its binary expansion. When `c==1`, the doubled value is shifted up `2*n -> 2*n+1` with a one-step Fibonacci shift `(a,b)=(b+a,b)`

To keep the values `a,b` manageable, we store only their first `1006` digits by floor-dividing by `10` until they are under `2**3340 ~ 1e1006`.

# Answer
> 33 votes
# x86 32-bit machine code (with Linux system calls): ~~106~~ 105 bytes

changelog: saved a byte in the fast version because an off-by-one constant doesn't change the result for Fib(1G).

Or 102 bytes for an 18% slower (on Skylake) version (using `mov`/`sub`/`cmc` instead of `lea`/`cmp` in the inner loop, to generate carry-out and wrapping at `10**9` instead of `2**32`). Or 101 bytes for a ~5.3x slower version with a branch in the carry-handling in the inner-most loop. (I measured a 25.4% branch-mispredict rate!)

Or 104/101 bytes if a leading zero is allowed. (It takes 1 extra byte to hard-code skipping 1 digit of the output, which is what happens to be needed for Fib(10\**9)).

Unfortunately, TIO's NASM mode seems to ignore `-felf32` in the compiler flags. Here's a link anyway with my full source code, with all the mess of experimental ideas in comments.

**This is a complete program**. It prints the first 1000 digits of Fib(10\**9) followed by some extra digits (the last few of which are wrong) followed by some garbage bytes (not including a newline). Most of the garbage is non-ASCII, so you may want to pipe through `cat -v`. It doesn't break my terminal emulator (KDE `konsole`), though. The "garbage bytes" are storing Fib(999999999). I already had `-1024` in a register, so it was cheaper to print 1024 bytes than the proper size.

I'm counting just the machine-code (size of the text segment of my static executable), not the fluff that makes it an ELF executable. (Very tiny ELF executables are possible, but I didn't want to bother with that). It turned out to be shorter to use stack memory instead of BSS, so I can kind of justify not counting anything else in the binary since I don't depend on any metadata. (Producing a stripped static binary the normal way makes a 340 byte ELF executable.)

You could make a function out of this code that you could call from C. It would cost a few bytes to save/restore the stack pointer (maybe in an MMX register) and some other overhead, but also save bytes by returning with the string in memory, instead of making a `write(1,buf,len)` system call. I think golfing in machine code should earn me some slack here, since nobody else has even posted an answer in any language without native extended-precision, but I think a function version of this should still be under 120 bytes without re-golfing the whole thing.

---

### Algorithm:

**brute force `a+=b; swap(a,b)`, truncating as needed to keep only the leading \>= 1017 decimal digits. It runs in 1min13s on my computer (or 322.47 billion clock cycles +- 0.05%)** (and could be a few % faster with a few extra bytes of code-size, or down to 62s with much larger code size from loop unrolling. No clever math, just doing the same work with less overhead). It's based on @AndersKaseorg's Python implementation, which runs in 12min35s on my computer (4.4GHz Skylake i7-6700k). Neither version has any L1D cache misses, so my DDR4-2666 doesn't matter.

Unlike Python, **I store the extended-precision numbers in a format that makes truncating decimal digits free**. I store groups of 9 decimal digits per 32-bit integer, so a pointer offset discards the low 9 digits. This is effectively base 1-billion, which is a power of 10. (It's pure coincidence that this challenge needs the 1-billionth Fibonacci number, but it does save me a couple bytes vs. two separate constants.)

Following GMP terminology, each 32-bit chunk of an extended-precision number is called a "limb". Carry-out while adding has to be generated manually with a compare against 1e9, but is then used normally as an input to the usual `ADC` instruction for the next limb. (I also have to manually wrap to the `[0..999999999]` range, rather than at 2^32 ~= 4.295e9. I do this branchlessly with `lea` \+ `cmov`, using the carry-out result from the compare.)

When the last limb produces non-zero carry-out, the next two iterations of the outer loop read from 1 limb higher than normal, but still write to the same place. This is like doing a `memcpy(a, a+4, 114*4)` to right-shift by 1 limb, but done as part of the next two addition loops. This happens every ~18 iterations.

---

Hacks for size-saving and performance:

* The usual stuff like `lea ebx, [eax-4 + 1]` instead of `mov ebx, 1`, when I know that `eax=4`. And using `loop` in places where `LOOP`'s slowness only has a tiny impact.
* Truncate by 1 limb for free by offsetting the pointers that we read from, while still writing to the start of the buffer in the `adc` inner loop. We read from `[edi+edx]`, and write to `[edi]`. So we can get `edx=0` or `4` to get a read-write offset for the destination. We need to do this for 2 successive iterations, first offsetting both, then only offsetting the dst. We detect the 2nd case by looking at `esp&4` before resetting the pointers to the front of the buffers (using `&= -1024`, because the buffers are aligned). See comments in the code.
* The Linux process-startup environment (for a static executable) zeros most registers, and stack-memory below `esp`/`rsp` is zeroed. My program takes advantage of this. In a callable-function version of this (where unallocated stack could be dirty), I could use BSS for zeroed memory (at the cost of maybe 4 more bytes to set up pointers). Zeroing `edx` would take 2 bytes. The x86-64 System V ABI doesn't guarantee either of these, but Linux's implementation of it does zero (to avoid information-leaks out of the kernel). In a dynamically-linked process, `/lib/ld.so` runs before `_start`, and does leave registers non-zero (and probably garbage in memory below the stack pointer).
* I keep `-1024` in `ebx` for use outside of loops. Use `bl` as a counter for inner loops, ending in zero (which is the low byte of `-1024`, thus restoring the constant for use outside the loop). Intel Haswell and later don't have partial-register merging penalties for low8 registers (and in fact don't even rename them separately), so there's a dependency on the full register, like on AMD (not a problem here). This would be horrible on Nehalem and earlier, though, which have partial-register stalls when merging. There are other places where I write partial regs and then read the full reg without `xor`-zeroing or a `movzx`, usually because I know that some previous code zeroed the upper bytes, and again that's fine on AMD and Intel SnB-family, but slow on Intel pre-Sandybridge.

I use `1024` as the number of bytes to write to stdout (`sub edx, ebx`), so my program prints some garbage bytes after the Fibonacci digits, because `mov edx, 1000` costs more bytes.
* (not used) `adc ebx,ebx` with EBX=0 to get EBX=CF, saving 1 byte vs. `setc bl`.
* `dec`/`jnz` inside an `adc` loop preserves CF without causing a partial-flag stall when `adc` reads flags on Intel Sandybridge and later. It's bad on earlier CPUs, but AFAIK free on Skylake. Or at worst, an extra uop.
* Use memory below `esp` as a giant red-zone. Since this is a complete Linux program, I know I didn't install any signal handlers, and that nothing else will asynchronously clobber user-space stack memory. This may not be the case on other OSes.
* Take advantage of the stack-engine to save uop issue bandwidth by using `pop eax` (1 uop + occasional stack-sync uop) instead of `lodsd` (2 uops on Haswell/Skylake, 3 on IvB and earlier according to Agner Fog's instruction tables)). IIRC, this dropped the run-time from about 83 seconds to 73. I could probably get the same speed from using a `mov` with an indexed addressing mode, like `mov eax, [edi+ebp]` where `ebp` holds the offset between src and dst buffers. (It would make the code outside the inner loop more complex, having to negate the offset register as part of swapping src and dst for Fibonacci iterations.) See the "performance" section below for more.
* start the sequence by giving the first iteration a carry-in (one byte `stc`), instead of storing a `1` in memory anywhere. Lots of other problem-specific stuff documented in comments.

**NASM listing (machine-code + source)**, generated with `nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'`. (Then I hand-removed some blocks of commented stuff, so the line numbering has gaps.) To strip out the leading columns so you can feed it into YASM or NASM, use `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

```

There's probably room to golf some more bytes out of this, but I've already spent at least 12 hours on this over 2 days. **I don't want to sacrifice speed, even though it's way more than fast enough and there is room to make it smaller in ways that cost speed**. Part of my reason for posting is showing how fast I can make a brute-force asm version. If anyone wants to really go for minimum-size but maybe 10x slower (e.g. 1 digit per byte), feel free to copy this as a starting point.

The resulting executable (from `yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o`) is 340B (stripped):

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

```

### Performance

The inner `adc` loop is 10 fused-domain uops on Skylake (+1 stack-sync uop every ~128 bytes), so it can issue at one per ~2.5 cycles on Skylake with optimal front-end throughput (ignoring the stack-sync uops). The critical-path latency is 2 cycles, for the `adc`-\>`cmp` -\> next iteration's `adc` loop-carried dependency chain, so the bottleneck should be the front-end issue limit of ~2.5 cycles per iteration.

`adc eax, [edi + edx]` is 2 unfused-domain uops for the execution ports: load + ALU. It micro-fuses in the decoders (1 fused-domain uop), but un-laminates in the issue stage to 2 fused-domain uops, because of the indexed addressing mode, even on Haswell/Skylake. I thought it would stay micro-fused, like `add eax, [edi + edx]` does, but maybe keeping indexed addressing modes micro-fused doesn't work for uops that already have 3 inputs (flags, memory, and destination). When I wrote it, I was thinking it wouldn't have a performance downside, but I was wrong. This way of handling of truncation slows down the inner loop every time, whether `edx` is 0 or 4.

It would be faster to handle the read-write offset for the dst by offsetting `edi` and using `edx` to adjust the store. So `adc eax, [edi]` / ... / `mov [edi+edx], eax` / `lea edi, [edi+4]` instead of `stosd`. Haswell and later can keep an indexed store micro-fused. (Sandybridge/IvB would unlaminate it, too.)

**On Intel Haswell and earlier, `adc` and `cmovc` are 2 uops each, with 2c latency**. (`adc eax, [edi+edx]` is still un-laminated on Haswell, and issues as 3 fused-domain uops). Broadwell and later allow 3-input uops for more than just FMA (Haswell), making `adc` and `cmovc` (and a couple other things) single-uop instructions, like they have been on AMD for a long time. (This is one reason AMD has done well in extended-precision GMP benchmarks for a long time.) Anyway, Haswell's inner loop should be 12 uops (+1 stack-sync uop occasionally), with a front-end bottleneck of ~3c per iter best-case, ignoring stack-sync uops.

**Using `pop` without a balancing `push` inside a loop means the loop can't run from the LSD (loop stream detector)**, and has to be re-read from the uop cache into the IDQ every time. If anything, it's a good thing on Skylake, since a 9 or 10 uop loop doesn't quite issue optimally at 4 uops every cycle. This is probably part of why replacing `lodsd` with `pop` helped so much. (The LSD can't lock down the uops because that wouldn't leave room to insert a stack-sync uop.) (BTW, a microcode update disables the LSD entirely on Skylake and Skylake-X to fix an erratum. I measured the above before getting that update.)

I profiled it on Haswell, and found that it runs in 381.31 billion clock cycles (regardless of CPU frequency, since it only uses L1D cache, not memory). Front-end issue throughput was 3.72 fused-domain uops per clock, vs. 3.70 for Skylake. (But of course instructions per cycle was down to 2.42 from 2.87, because `adc` and `cmov` are 2 uops on Haswell.)

`push` to replace `stosd` probably wouldn't help as much, because `adc [esp + edx]` would trigger a stack-sync uop every time. And would cost a byte for `std` so `lodsd` goes the other direction. (`mov [edi], eax` / `lea edi, [edi+4]` to replace `stosd` is a win, going from 32,909Mcycles for 100M iters to 31,954Mcycles for 100M iters. It seems that `stosd` decodes as 3 uops, with the store-address/store-data uops not micro-fused, so `push` \+ stack-sync uops might still be faster than `stosd`)

**The actual performance of ~322.47 billion cycles for 1G iterations of 114 limbs works out to 2.824 cycles per iteration of the inner loop**, for the fast 105B version on Skylake. (See `ocperf.py` output below). That's slower than I predicted from static analysis, but I was ignoring the overhead of the outer-loop and any stack-sync uops.

Perf counters for `branches` and `branch-misses` show that the inner loop mispredicts once per outer loop (on the last iteration, when it's not taken). That also accounts for part of the extra time.

---

**I could save code-size by making the inner-most loop have 3-cycle latency for the critical path, using `mov esi,eax`/`sub eax,ebp`/`cmovc eax, esi`/`cmc`** (2+2+3+1 = 8B) instead of `lea esi, [eax - 1000000000]`/`cmp ebp,eax`/`cmovc` (6+2+3 = 11B). The `cmov`/`stosd` is off the critical path. (The increment-edi uop of `stosd` can run separately from the store, so each iteration forks off a short dependency chain.) It used to save another 1B by changing the ebp init instruction from `lea ebp, [ecx-1]` to `mov ebp,eax`, but I discovered that having the wrong `ebp` didn't change the result. This would let a limb be exactly == 1000000000 instead of wrapping and producing a carry, but this error propagates slower than we Fib() grows, so this happens not to change the leading 1k digits of the final result. Also, I think that error can correct itself when we're just adding, since there's room in a limb to hold it without overflow. Even 1G + 1G doesn't overflow a 32-bit integer, so it will eventually percolate upwards or be truncated away.

The 3c latency version is 1 extra uop, so the front-end can issue it at one per 2.75c cycles on Skylake, only slightly faster than the back-end can run it. (On Haswell, it will be 13 uops total since it still uses `adc` and `cmov`, and bottleneck on the front-end at 3.25c per iter).

In practice it runs a factor of 1.18 slower on Skylake (3.34 cycles per limb), rather than 3/2.5 = 1.2 that I predicted for replacing the front-end bottleneck with the latency bottleneck from just looking at the inner loop without stack-sync uops. Since the stack-sync uops only hurt the fast version (bottlenecked on the front-end instead of latency), it doesn't take much to explain it. e.g. 3/2.54 = 1.18.

Another factor is that the 3c latency version may detect the mispredict on leaving the inner loop while the critical path is still executing (because the front-end can get ahead of the back-end, letting out-of-order execution run the loop-counter uops), so the effective mispredict penalty is lower. Losing those front-end cycles lets the back-end catch up.

If it wasn't for that, we could maybe speed up the 3c `cmc` version by using a branch in the outer loop instead of branchless handling of the carry\_out -\> edx and esp offsets. Branch-prediction + speculative execution for a control dependency instead of a data dependency could let the next iteration start running the `adc` loop while uops from the previous inner loop were still in flight. In the branchless version, the load addresses in the inner loop have a data dependency on CF from the last `adc` of the last limb.

The 2c latency inner-loop version bottlenecks on the front-end, so the back-end pretty much keeps up. If the outer-loop code was high-latency, the front-end could get ahead issuing uops from the next iteration of the inner loop. (But in this case the outer-loop stuff has plenty of ILP and no high-latency stuff, so the back-end doesn't have much catching up to do when it starts chewing through uops in the out-of-order scheduler as their inputs become ready).

```
### 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 %)` is the standard-deviation over the 4 runs for that count. Interesting that it runs such a round number of instructions. That 924 billion is *not* a coincidence. I guess that the outer loop runs a total of 924 instructions.

`uops_issued` is a fused-domain count (relevant for front-end issue bandwidth), while `uops_executed` is an unfused-domain count (number of uops sent to execution ports). Micro-fusion packs 2 unfused-domain uops into one fused-domain uop, but mov-elimination means that some fused-domain uops don't need any execution ports. See the linked question for more about counting uops and fused vs. unfused domain. (Also see Agner Fog's instruction tables and uarch guide, and other useful links in the SO x86 tag wiki).

From another run measuring different things: L1D cache misses are totally insignificant, as expected for reading/writing the same two 456B buffers. The inner-loop branch mispredicts once per outer loop (when it's not-taken to leave the loop). (The total time is higher because the computer wasn't totally idle. Probably the other logical core was active some of the time, and more time was spent in interrupts (since the user-space-measured frequency was farther below 4.400GHz). Or multiple cores were active more of the time, lowering the max turbo. I didn't track `cpu_clk_unhalted.one_thread_active` to see if HT competition was an issue.)

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

```

My code may well run in fewer cycles on Ryzen, which can issue 5 uops per cycle (or 6 when some of them are 2-uop instructions, like AVX 256b stuff on Ryzen). I'm not sure what its front-end would do with `stosd`, which is 3 uops on Ryzen (same as Intel). I think the other instructions in the inner loop are the same latency as Skylake and all single-uop. (Including `adc eax, [edi+edx]`, which is an advantage over Skylake).

---

**This could probably be significantly smaller, but maybe 9x slower, if I stored the numbers as 1 decimal digit per byte**. Generating carry-out with `cmp` and adjusting with `cmov` would work the same, but do 1/9th the work. 2 decimal digits per byte (base-100, not 4-bit BCD with a slow `DAA`) would also work, and `div r8` / `add ax, 0x3030` turns a 0-99 byte into two ASCII digits in printing order. But 1 digit per byte doesn't need `div` at all, just looping and adding 0x30. If I store the bytes in printing order, that would make the 2nd loop really simple.

---

Using 18 or 19 decimal digits per 64-bit integer (in 64-bit mode) would make it run about twice as fast, but cost significant code-size for all the REX prefixes, and for 64-bit constants. 32-bit limbs in 64-bit mode prevents using `pop eax` instead of `lodsd`. I could still avoid REX prefixes by using `esp` as a non-pointer scratch register (swapping the usage of `esi` and `esp`), instead of using `r8d` as an 8th register.

If making a callable-function version, converting to 64-bit and using `r8d` may be cheaper than saving/restoring `rsp`. 64-bit also can't use the one-byte `dec r32` encoding (since it's a REX prefix). But mostly I ended up using `dec bl` which is 2 bytes. (Because I have a constant in the upper bytes of `ebx`, and only use it outside of inner loops, which works because the low byte of the constant is `0x00`.)

---

### High-performance version

For maximum performance (not code-golf), you'd want to unroll the inner loop so it runs at most 22 iterations, which is a short enough taken/not-taken pattern for the branch-predictors to do well. In my experiments, `mov cl, 22` before a `.inner: dec cl/jnz .inner` loop has very few mispredicts (like 0.05%, far less than one per full run of the inner loop), but `mov cl,23` mispredicts from 0.35 to 0.6 times per inner loop. `46` is particularly bad, mispredicting ~1.28 times per inner-loop (128M times for 100M outer-loop iterations). `114` mispredicted exactly once per inner loop, same as I found as part of the Fibonacci loop.

I got curious and tried it, unrolling the inner loop by 6 with a `%rep 6` (because that divides 114 evenly). That mostly eliminated branch-misses. I made `edx` negative and used it as an offset for `mov` stores, so `adc eax,[edi]` could stay micro-fused. (And so I could avoid `stosd`). I pulled the `lea` to update `edi` out of the `%rep` block, so it only does one pointer-update per 6 stores.

I also got rid of all the partial-register stuff in the outer loop, although I don't think that was significant. It may have helped slightly to have CF at end of the outer loop not dependent on the final ADC, so some of the inner-loop uops can get started. The outer-loop code could probably be optimized a bit more, since `neg edx` was the last thing I did, after replacing `xchg` with just 2 `mov` instructions (since I already still had 1), and re-arranging the dep chains along with dropping the 8-bit register stuff.

This is the NASM source of just the Fibonacci loop. It's a drop-in replacement for that section of the original version.

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

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

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

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

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

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

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

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

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

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

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

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

```

Performance:

```
 Performance counter stats for './fibonacci-1G-performance' (3 runs):

      62280.632258      task-clock (msec)         #    1.000 CPUs utilized            ( +-  0.07% )
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
                 3      page-faults:u             #    0.000 K/sec                    ( +- 12.50% )
   273,146,159,432      cycles                    #    4.386 GHz                      ( +-  0.07% )
   757,088,570,818      instructions              #    2.77  insn per cycle           ( +-  0.00% )
   740,135,435,806      uops_issued_any           # 11883.878 M/sec                   ( +-  0.00% )
   966,140,990,513      uops_executed_thread      # 15512.704 M/sec                   ( +-  0.00% )
    75,953,944,528      resource_stalls_any       # 1219.544 M/sec                    ( +-  0.23% )
       741,572,966      idq_uops_not_delivered_core #   11.907 M/sec                    ( +- 54.22% )

      62.279833889 seconds time elapsed                                          ( +-  0.07% )

```

That's for the same Fib(1G), producing the same output in 62.3 seconds instead of 73 seconds. (273.146G cycles, vs. 322.467G. Since everything hits in L1 cache, core clock cycles is really all we need to look at.)

Note the much lower total `uops_issued` count, well below the `uops_executed` count. That means many of them were micro-fused: 1 uop in the fused domain (issue/ROB), but 2 uops in the unfused domain (scheduler / execution units)). And that few were eliminated in the issue/rename stage (like `mov` register copying, or `xor`-zeroing, which need to issue but don't need an execution unit). Eliminated uops would unbalance the count the other way.

`branch-misses` is down to ~400k, from 1G, so unrolling worked. `resource_stalls.any` is significant now, which means the front-end is not the bottleneck anymore: instead the back-end is getting behind and limiting the front-end. `idq_uops_not_delivered.core` only counts cycles where the front-end didn't deliver uops, but the back-end *wasn't* stalled. That's nice and low, indicating few front-end bottlenecks.

---

Fun fact: the python version spends more than half its time dividing by 10 rather than adding. (Replacing the `a/=10` with `a>>=64` speeds it up by more than a factor of 2, but changes the result because binary truncation != decimal truncation.)

My asm version is of course optimized specifically for this problem-size, with the loop iteration-counts hard coded. Even shifting an arbitrary-precision number will copy it, but my version can just read from an offset for the next two iterations to skip even that.

**I profiled the python version** (64-bit python2.7 on 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

```

Numbers in (parens) are how much of the time that perf counter was being sampled. When looking at more counters than the HW supports, perf rotates between different counters and extrapolates. That's totally fine for a long run of the same task.

If I ran `perf` after setting sysctl `kernel.perf_event_paranoid = 0` (or running `perf` as root), it would measure `4.400GHz`. `cycles:u` doesn't count time spent in interrupts (or system calls), only user-space cycles. My desktop was almost totally idle, but this is typical.

# Answer
> 21 votes
# Haskell, ~~83~~ 61 bytes

```
p(a,b)(c,d)=(a*d+b*c-a*c,a*c+b*d)
t g=g.g.g
t(t$t=<<t.p)(1,1)

```

Outputs (*F*<sub>1000000000</sub>,*F*<sub>1000000001</sub>). On my laptop, it correctly prints the left paren and the first 1000 digits within 133 seconds, using 1.35 GiB of memory.

### How it works

The Fibonacci recurrence can be solved using matrix exponentiation:

\[*F*<sub>*i* − 1</sub>, *F*<sub>*i*</sub>; *F*<sub>*i*</sub>, *F*<sub>*i* \+ 1</sub>\] = \[0, 1; 1, 1\]<sup>*i*</sup>,

from which we derive these identities:

\[*F*<sub>*i* \+ *j* − 1</sub>, *F*<sub>*i* \+ *j*</sub>; *F*<sub>*i* \+ *j*</sub>, *F*<sub>*i* \+ *j* \+ 1</sub>\] = \[*F*<sub>*i* − 1</sub>, *F*<sub>*i*</sub>; *F*<sub>*i*</sub>, *F*<sub>*i* \+ 1</sub>\] ⋅ \[*F*<sub>*j* − 1</sub>, *F*<sub>*j*</sub>; *F*<sub>*j*</sub>, *F*<sub>*j* \+ 1</sub>\],
*F*<sub>*i* \+ *j*</sub> = *F*<sub>*i* \+ 1</sub>*F*<sub>*j* \+ 1</sub>*F*<sub>*i* − 1</sub>*F*<sub>*j* − 1</sub> = *F*<sub>*i* \+ 1</sub>*F*<sub>*j* \+ 1</sub> − (*F*<sub>*i* \+ 1</sub>*F*<sub>*i*</sub>)(*F*<sub>*j* \+ 1</sub>*F*<sub>*j*</sub>),
*F*<sub>*i* \+ *j* \+ 1</sub> = *F*<sub>*i*</sub>*F*<sub>*j*</sub> \+ *F*<sub>*i* \+ 1</sub>*F*<sub>*j* \+ 1</sub>.

The `p` function computes (*F*<sub>*i* \+ *j*</sub>, *F*<sub>*i* \+ *j* \+ 1</sub>) given (*F*<sub>*i*</sub>, *F*<sub>*i* \+ 1</sub>) and (*F*<sub>*j*</sub>, *F*<sub>*j* \+ 1</sub>). Writing `f n` for (*F*<sub>*i*</sub>, *F*<sub>*i* \+ 1</sub>), we have `p (f i) (f j)` = `f (i + j)`.

Then,

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

and we plug in `f 1` = `(1,1)`.

# Answer
> 12 votes
# Python 2, 70 bytes

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

```

This ran in 18 minutes and 31 seconds on my laptop, producing the correct 1000 digits followed by `74100118580` (the correct following digits are `74248787892`).

# Answer
> 10 votes
# Haskell, 78 bytes

```
(a%b)n|n<1=b|odd n=b%(a+b)$n-1|r<-2*a*b-a*a=r%(a*a+b*b)$div n 2
1%0$2143923439

```

Try it online!

Took 48 seconds on TIO. Same recursive formula as my Python answer, but without truncating.

The constant `2143923439` is `10**9-1`, reversed in binary, and with an extra 1 at the end. Iterating through its binary digits in reverse simulates iterating through the binary digits of `10**9-1`. It seems shorter to hardcode this than to compute it.

# Answer
> 9 votes
# Haskell, ~~202~~ ~~184~~ ~~174~~ ~~173~~ ~~170~~ ~~168~~ ~~164~~ 162 bytes

```
(a,b)!(c,d)=a*c+b*d
l x=((34,55)!x,(55,89)!x)
f(a,b)|x<-l(a,b)=(x!l(b-a,a),x!x)
r=l.f
k=f.f.f
j=f.r.r.r.r
main=print$take 1000$show$fst$f$r$k$k$r$k$j$f$r$j$r(0,1)

```

Try it online!

## Explanation

This uses a rather fast way to calculate fibonacci numbers. The function `l` takes two fibonacci numbers and calculates the fibonacci numbers 10 later, while `f` takes the **n**th and **n+1**th fibonacci numbers and calculates the **2n+20**th and **2n+21**th fibonacci numbers. I chain them rather haphazardly to get 1 billion and grab the first 1000 digits.

# Answer
> 9 votes
# T-SQL, ~~422 414~~ 453 bytes (Verified, now competing!)

**EDIT 2**: Changed to ~~`INT BIGINT`~~ `DECIMAL(37,0)`, Gained a few bytes but increased speed enough to complete to 1 billion! Completed in **45 hours 29 minutes**, verifies against the given string, and displays an additional 8 characters (which may or may not be right due to rounding errors).

T-SQL has no native "huge number" support, so had to roll my own text-based huge number adder using 1008-character strings:

```
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 @

```

Here's the formatted version with comments:

```
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 @

```

Basically I'm manually manipulating 1008-character zero-filled strings representing my two Fibonacci variables, `@a` and `@`.

I add them ~~8 18~~ 36 digits at a time, by stripping off the last 36 digits, converting to a manageable numeric type (`DECIMAL(37,0)`), adding them up, then smashing it back into another long string `@c`. I then "rotate" `@a` and `@` by moving the last 36 digits to the front, and repeating the process. 28 rotations * 36 digits covers all 1008. I have to "carry the one" manually.

Once our number starts to exceed my string length, I "shift left" and we start to lose some precision, but the error is well within my extra characters.

I tried using a SQL table full of INTs and BIGINTs, with similar logic, and it was *dramatically* slower. Weird.

# Answer
> 8 votes
# Haskell, 81 bytes

```
f n|n<3=1|even n=fk*(2*f(k+1)-fk)|1>0=f(k+1)^2+fk^2 where k=n`div`2;fk=f k
f$10^9

```

**Explanation**

`f n` recursively computes the `n`th fibonacci number using the recurrence from xnor's answer with common-subexpression elimination. Unlike the other solutions which have been posted, which use O(log(n)) multiplications, we have a O(log(n))-depth recursion with a branching factor of 2, for a complexity of O(n) multiplications.

However, all is not lost! Because almost all calls will be near the bottom of the recursion tree, we can use fast native arithmetic where possible and avoid lots of manipulation of huge bignums. It spits out an answer in a couple of minutes on my machine.

# Answer
> 6 votes
## PARI/GP, 45 bytes

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

```

Somehow `\p1000` isn't enough. This doesn't work with 32 bit systems. The final division is to avoid the decimal point in scientific notation.

# Answer
> 4 votes
# Pari/GP, 15 + 5 = 20 bytes

```
fibonacci(10^9)

```

Run with the command line option `-s1g` to allocate 1 Gbytes of memory.

# Answer
> 2 votes
# Ruby, 63 bytes

man, I'm bad at golfing ruby; but the BigInt class does wonders for this kind of stuff. We use the same algorithm as Anders Kaseorg.

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

```

# Answer
> 2 votes
# x86 .COM, ~~62~~ ~~61~~ ~~56~~ 55 bytes

```
    org $100
    mov di, $8000
    mov ds, di
    mov es, di
    mov cx, di
    xor ax, ax
    xor si, si
    rep stosw
    mov ecx, 1000000000
    ;mov ecx, 6
    stc

lop:
    mov bx, ds
adding:
    lodsb
    adc al, [di]
    aaa
    stosb
    dec bx
    jnz adding

    jnc nocy
    and [si], byte 0
    lodsb
    inc ax
    stosb
nocy:
    loopd lop

    std
    mov si, di
    dec si
delta:
    lodsb
    add al, '0'
    int $29
    loop delta

    ret

```

Should run more than one day, keep 32768 digits of precision of both number

Ran for 165979.100 seconds, result here

# Answer
> 2 votes
# Pyth, 12 bytes

```
A(Z1)V^T9HA(H+HG

```

yuhhhh

# Answer
> 1 votes
`gawk` with `GMP` bigint library -

## *0.012* secs

total for first `1000` digits of `Fib - 1,000,000,000`

```
    # gawk profile, created Tue Nov  7 08:13:56 2023

    # Rule(s)

     1  {
     1      print fib_ultraP(($++_) ^ $++_)

    }

function fib_ultraP(__, ______, _, ___, ____,
                    _____, _______, ________, _________) {

    if ((____ = _ = ! (_______ = length(______ = __)))      ||
        (__ *= _++ < (__ = int(__))) <= (___ = ++_ + _) + _ ||
               (____ = (___ + ___) ^ ___ ^ _ <= __))
        return \
            (____ < _ ? __ + (__ < ++___ ? -(_ <= __) : \
            (___ < __) * _) * _______ : "_ERR_FIBP_OUTPUT_GE_32BITS_")

    ______ += _____ = substr(___ = __ = --_, _______ = --_, _)

    while ((___ += ___) <= ______)_______++

     _________ = _
      ________ = (((_+=(_+=_^=_<_)*_*_)^_)^_)^_
           ___ = ______ + substr(_____,
       (______ = ___) == (_ = _________))
     _________ = ________ * ________

    do {         ____ = (__ + __) * _
                  __ *= __
            if ((___ += ___) < ______ || ___ < (___ -= ______)) {
                    __ -= _ *= -_
                    _ += ____
            } else {
                    _ = __ + _*_
                    __ += ____
            }
            if (____ = _________<_)
                do                  __ = (__ - __%________) /________
                while (_________ < ( _ =  (_ - _%________) /________))

    } while (_______--)

    return \
    substr((_________ = ________ = ___++) \
        ? (__ - __ % (_ = (_ += (_ = ___) * _ * _) ^ (\
            int(log(__) / log(_)) - (___ = _ * _ * _)))) / _ \
        : (_ - _ % (__ = (__ += (__ = ++___) * __ * __) ^ (\
            int(log(_) / log(__)) - (___ = __ * __ * __)))) / __, !!___, ___)
}

 out9: 2.52KiB 0:00:00 [24.7MiB/s] [24.7MiB/s] [  <=> ]

( echo 10 9 | gawk -p- -Mbe ; )  0.00s user 0.00s system 74% cpu 0.012 total

```

---

```
7952317874554683467829385196197148189255542185234398913453039937
3432466861825193700509996261365567793324820357232224512262917144
5627564825949953061211130125549987963951605345978901870056743994
6844843034599802419924043753401950114830107234265037841426980398
3873607842842319964573407827842007677609077777031831857446565362
5351150285171596335102399069923259547132267036550648243596658688
6048627159716916351448788527427435508113909167963907380398242848
0339801102763705442642850327443647811984518254621305295296333398
1348310577137012811185112824713631141420831898380252690791778709
4802217750859685116363883374847428036737147882079956688807509158
3722494514375193201625820020005307983098872612570282019075093705
5423293110708497685471583358562391045067944912001156476292564914
4509531904684984417002512086504020779012501356177874199605085558
3171909053951344689194433130268248133632341904943755992625530254
6652883812263943360048384953507064771198676927956854879685520768
4897741771784375859496425384355879105799

```

---
Tags: code-golf, kolmogorov-complexity, fibonacci, restricted-time
---


title: Decipher a Vigenère ciphertext

text:
# Question
Title: Decipher a Vigenère ciphertext
The Vigenère cipher was a simple polyalphabetic cipher that basically applied one of several Caesar ciphers, according to a key. Basically the letters in the key indicate which shifted alphabet to use. To that end there was a simple tool, called the *Vigenère square:*

Here each row is a separate alphabet, starting with the corresponding letter of the key. The columns then are used to determine the ciphered letter. Decryption works in very much the same fashion, only vice-versa.

Suppose we want to encrypt the string `CODEGOLF`. We also need a key. In this case the key shall be `FOOBAR`. When the key is shorter than the plaintext we extend it by repetition, therefore the actual key we use is `FOOBARFO`. We now look up the first letter of the key, which is `F` to find the alphabet. It starts, perhaps unsurprisingly, with `F`. Now we find the column with the first letter of the plaintext and the resulting letter is `H`. For the second letter we have `O` as the key letter and the plain text letter, resulting in `C`. Continuing that way we finally get `HCRFGFQT`.

**Task**

Your task now is to decipher messages, given a key. However, since we have outgrown the 16th century and have computers we should at least support a slightly larger alphabet:

```
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

```

The construction of the Vigenère square is still very much the same and the cipher still works in the same way. It's just a bit ... unwieldy to give here in full.

**Input**

Input is given on standard input as two separate lines of text, each terminated by a line break. The first line contains the key while the second contains the ciphertext.

**Output**

A single line, containing the deciphered message.

**Winning condition**

Since encryption is sometimes regarded as a weapon, the code should be short to facilitate easy smuggling. The shorter the better, as it reduces the likelihood of discovery.

**Sample input 1**

```
Key
miQ2eEO

```

**Sample output 1**

```
Message

```

**Sample input 2**

```
ThisIsAKey
CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu

```

**Sample output 2**

```
ThisWorksEquallyWellWithNumbers123894576

```

A week has passed. The currently shortest solution has been accepted. For those interested, in our contest we had the following submissions and lengths:

> 130 – Python
> 146 – Haskell
> 195 – C
> 197 – C
> 267 – VB.NET

And our own solutions that weren't ranked with the others:

> 108 – Ruby
> 139 – PowerShell

# Answer
## Golfscript -- 48 chars

```
n%~.,@*\{\(123,97>91,65>+58,48>+:|?@|?\-|=}%\0<+

```

No tricks in this one!
> 10 votes

# Answer
## MS-DOS 16bit .COM file - 87 bytes

Base64 encoded binary (following this link for a decoder)

```
v1cBi8/oQACJ/ovv6DkAi9msitAqF3MDgMI+gMJhgPp6dguA6jqA+lp2A4DqK80hO/d0IkM563TW69YsYXMIBCB9AgQrBBqqtAHNITwNdev+xLIKzSHD

```
> 8 votes

# Answer
## APL (45)

```
∆[⍙⍳⍨¨⌽∘∆¨(⍴⍙←⍞)⍴1-⍨⍞⍳⍨∆←⎕D,⍨⎕A,⍨⎕UCS 96+⍳26]

```

Explanation:

* `∆←⎕D,⍨⎕A,⍨⎕UCS 96+⍳26`: generate the alphabet (numbers (`⎕D`) follow letters (`⎕A`) follow lowercase letters (`⎕UCS 96+⍳26`, the unicode values from 97 to 122).
* `1-⍨⍞⍳⍨∆`: read a line (the key), find the position of each character in the alphabet, and subtract one (arrays are one-based by default, so shifting by those values directly would shift the alphabet one too far).
* `(⍴⍙←⍞)⍴`: read another line (the message), and repeat the indices of the key so that it has the length of the message.
* `⌽∘∆¨`: rotate the alphabet by the indices belonging to the key
* `⍙⍳⍨¨`: look up each character in the message in the corresponding shifted alphabet
* `∆[`...`]`: look up the given indices in the normal alphabet, giving the corresponding characters.
> 8 votes

# Answer
## Ruby - 132 127 122 109 100 characters

```
a,b=*$<
c=*?a..?z,*?A..?Z,*?0..?9
(b.size-1).times{|i|$><<c[c.index(b[i])-c.index(a[i%(a.size-1)])]}

```
> 6 votes

# Answer
## Python - 122 chars

```
from string import*
L=letters+digits
R=raw_input
K,T=R(),R()
F=L.find
print"".join(L[F(i)-F(j)]for i,j in zip(T,K*len(T)))

```
> 5 votes

# Answer
## J, 65 characters

```
v=:4 : 'a{~x(62|[:-/"1 a i.[,.#@[$])y[a=.a.{~62{.;97 65 48+/i.26'

```

Doesn't completely meet the spec since it's defined as a verb rather than taking input, but I'm posting it anyway with the intention of fiddling with it at a later date.

Usage:

```
   'miQ2eEO' v 'Key'
Message
   'CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu' v 'ThisIsAKey'
ThisWorksEquallyWellWithNumbers123894576

```
> 5 votes

# Answer
## Perl, 95 chars

Perl 5.010, run with `perl -E`:

```
%a=map{$_,$n++}@a=(a..z,A..Z,0..9);@k=<>=~/./g;
$_=<>;s/./$a[($a{$&}-$a{$k[$i++%@k]})%62]/ge;say

```
> 4 votes

# Answer
## Python - ~~144~~ ~~143~~ ~~140~~ ~~136~~ 125 characters

Probably not the best, but hey:

```
from string import*
l=letters+digits
r=l.find
q=raw_input
k=q()
print"".join(l[(r(j)-r(k[i%len(k)]))%62]for i,j in enumerate(q()))

```
> 3 votes

# Answer
## Golfscript - 65 chars

Still needs to be golfed more. For now, T is the text, K is the Key, L is the list of letters

```
n%):T,\~*:K;''26,{97+}%+.{32^}%10,{48+}%++:L;T{L\?K(L\?\:K;-L\=}%

```
> 3 votes

# Answer
## K,81 61

```
k:0:0;,/$(m!+(`$'m)!+{(1_x),1#x}\m:,/.Q`a`A`n)[(#v)#k]?'v:0:0

```

.

```
k)k:0:0;,/$(m!+(`$'m)!+{(1_x),1#x}\m:,/.Q`a`A`n)[(#v)#k]?'v:0:0
ThisIsAKey
CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu
"ThisWorksEquallyWellWithNumbers123894576"

```
> 3 votes

# Answer
## Perl, 115 chars

```
$a=join'',@A=(a..z,A..Z,0..9);$_=<>;chop;@K=split//;$_=<>;s/./$A[(index($a,$&)-index($a,$K[$-[0]%@K]))%@A]/ge;print

```
> 2 votes

# Answer
## Golfscript - 92 characters

```
n%~\.,:l;{0\{1$+\)\}%\;}:&;26'a'*&26'A'*&+10'0'*&+\@.,,{.l%3$=4$?\2$=4$?\- 62%3$\>1<}%\;\;\;

```

Probably much longer than it needs to be. Still trying to get my head around GS.

Heres the "ungolfed" and commented version

```
n%~\.,:l;
{0\{1$+\)\}%\;}:&; # This would be sortof an equivalent for range applied to strings
26'a'*&26'A'*&+10'0'*&+\@., # This mess generates the dictionary string,
# l = len(key)
# 0 dictionary (letters + digits)
# 1 key
# 2 text
{
    # 3 index
    .   #+1 Duplicate the index

    # Find the index of the key letter
    l%  #+1 Indice modulo key
    3$  #+2 Duplicate the key
    =   #+1 Get the key letter
    4$? #+1 Search the letters index

    # Find the index of the text letter
    \   #+1 Get the index
    2$  #+2 Get the text
    =   #+1 Get the text letter
    4$? #+0 Search the letters index

    # 3 key index
    # 4 letter index

    \-   #+1 get the index of the new letter

    62% #+1 wrap the index around the dictionary

    3$ #+2 Get the dictionary

    \> #+1 remove the first part of the dict around the target letter

    1< #+1 remove everythin after
}%
\;
\;
\;

```
> 2 votes

# Answer
## VBA, 288

Doesn't quite beat the listed VB.NET score (but I'm getting close):

```
Sub h(k,s)
v=Chr(0)
Z=Split(StrConv("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789",64),v)
a=Split(StrConv(s,64),v):b=Split(StrConv(k,64),v)
For l=0 To Len(s)-1
j=l Mod Len(k)
g=0
For i=0 To 62:g=g+i*((Z(i)=b(j))-(Z(i)=a(l))):Next
x=x &Z(IIf(g<0,g+62,g))
Next
s=x
End Sub

```

**Usage:**

```
Sub test()
k = "ThisIsAKey"
s = "CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu"
h k, s
MsgBox s
End Sub

```

Thanks to Joey for the tip!
> 2 votes

# Answer
**C,186**

A bit late but .. (lines broken to avoid horizontal scrollbar).

```
char a[99],*s,*t;k,j;main(int m,char**v)
{for(;j<26;++j)a[j]=32|(a[j+26]=65+j),
a[52+j]=48+j;while(*v[2])
putchar(a[s=strchr(a,v[1][k++%strlen(v[1])])
,t=strchr(a,*v[2]++),s>t?t-s+62:t-s]);}

```

Nonbroken lines

```
char a[99],*s,*t;k,j;main(int m,char**v){for(;j<26;++j)a[j]=32|(a[j+26]=65+j),a[52+j]=48+j;while(*v[2])putchar(a[s=strchr(a,v[1][k++%strlen(v[1])]),t=strchr(a,*v[2]++),s>t?t-s+62:t-s]);}

```

A discussion about the process of golfing this code can be found here: http://prob-slv.blogspot.com/2013/04/code-golf.html
> 2 votes

# Answer
## JavaScript 248

```
var v= 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
function d(k,c){var a,b,o,x
a=k.charAt(0)
x=v.indexOf(a)
b=v.substr(x)+v.substring(0,x)
o= v.charAt(b.indexOf(c.charAt(0)))
k=k.substr(1)+a
c=c.substr(1)
return (c)?o+d(k,c):o}

```
> 2 votes

# Answer
# Uiua, 42 characters

```
A←⊂/⊂⊞+"aA"⇡26+@0⇡10
&p⊏-∩(⊗∶A)↯△,∶&sc&scA

```

-4 thanks to Unrelated String
> 2 votes

# Answer
## Haskell (169)

```
import List
main=do c<-y;t<-y;putStrLn$map((k!!).(`mod`62))$zipWith(-)(g t)(cycle$g c)
k=['a'..'z']++['A'..'Z']++['0'..'9']
y=getLine
f(Just x)=x
g=map$f.(`elemIndex`k)

```
> 1 votes

# Answer
# J: 91 characters

```
[:{&{.&t({&t"0&(({.t=.1|.^:(i.62)a.{~(97+i.26),(65+i.26),48+i.10)&i.)"0@:$~#)|:@(i."1.,"0)]

```

For example:

```
    g=:[:{&{.&t({&t"0&(({.t=.1|.^:(i.62)a.{~(97+i.26),(65+i.26),48+i.10)&i.)"0@:$~#)|:@(i."1.,"0)]
    'ThisIsAKey' g 'CoqKuGRUw29BiDTQmOpJFpBzlMMLiPb8alGruFbu'
ThisWorksEquallyWellWithNumbers123894576

```
> 1 votes

# Answer
# Scala, 156 bytes

Golfed version. Try it online!

```
(K,T)=>{val L=('a'to'z')++('A'to'Z')++('0'to'9');T.zip(Stream.continually(K).flatten).map{case(i,j)=>L((L.indexOf(i)-L.indexOf(j)+L.size)%L.size)}.mkString}

```

Ungolfed version. Try it online!

```
object Main extends App {
  def transform(K: String, T: String): String = {
    val letters = ('a' to 'z') ++ ('A' to 'Z')
    val digits = '0' to '9'
    val L = letters ++ digits
    (T.zip(Stream.continually(K).flatten))
      .map { case (i, j) =>
        L((L.indexOf(i) - L.indexOf(j) + L.length) % L.length)
      }
      .mkString
  }

  val K = "Key"
  val T = "miQ2eEO"
  val result = transform(K, T)
  println(result)
}

```
> 0 votes

# Answer
# Vyxal `s`, 136 bitsv2, 17 bytes

```
LẎZƛ÷kr₀Ǔ:£~ḟǓ∇_ḟ¥i

```

Try it Online!

Bitstring:

```
0110000111010001100100100100100010010101101010000010110100010111011110111110110000101100000011001010100000111000011100111110110100111001

```

Takes message then key

## Explained

```
LẎZƛ÷kr₀Ǔ:£~ḟǓ∇_ḟ¥i
LẎ                   # Repeat the key to the length of the message
  Z                  # Zip each character in the message to the extended key
   ƛ                 # To each pair:
     kr₀Ǔ            #   Push the string a-zA-Z0-9
         :£          #   and store a copy in the register
    ÷      ~ḟ        #   Find the position of the key character, not popping the alphabet string
             Ǔ       #   Rotate the alphabet string left that many times
    ÷         ∇_     #   Put the message character at the top of the stack, followed by the rotated alphabet
                ḟ    #   Find the index of the message character in that alphabet
                 ¥i  #   And index into the original alphabet string

```

Created with the help of Luminespire.
> 0 votes

---
Tags: code-golf, cipher
---


# Question
Title: How long is my number: Restricted Version
### *Find the original challenge here*

## Challenge

Given an integer, `Z` in the range `-2^31 < Z < 2^31`, output the number of digits in that number (in base 10).

## Rules

You must not use any string functions (in the case of overloading, you must not pass a string into functions which act as both string and integer functions). You are not allowed to store the number as a string.

All mathematical functions are allowed.

You may take input in any base, but the output must be the length of the number in base 10.

Do not count the minus sign for negative numbers. Number will never be a decimal.

Zero is effectively a leading zero, so it can have zero *or* one digit.

## Examples

```
Input > Output

-45 > 2
1254 > 4
107638538 > 9
-20000 > 5
0 > 0 or 1
-18 > 2

```

## Winning

Shortest code in bytes wins.

# Answer
## Mathematica, 13 bytes

```
IntegerLength

```

Well...
> 10 votes

# Answer
# Python 2, 30 bytes

```
f=lambda x:x and-~f(abs(x)/10)

```

Try it online!
> 7 votes

# Answer
# Japt, ~~5~~ 3 bytes

```
ì l

```

Try it online!
> 7 votes

# Answer
## JavaScript (ES6), 19 bytes

```
f=n=>n&&f(n/10|0)+1

console.log(f(-45))       // 2
console.log(f(1254))      // 4
console.log(f(107638538)) // 9
console.log(f(-20000))    // 5
console.log(f(0))         // 0
console.log(f(-18))       // 2
```
> 7 votes

# Answer
My answer from the other challenge still works:

# Brachylog, 1 byte

```
l

```

Try it online!

The `l` builtin is overloaded, but on integers, it takes the number of digits of the integer, ignoring sign.
> 5 votes

# Answer
# Jelly, ~~3~~ 2 bytes

*1 byte saved thanks to Leaky Nun*

```
DL

```

Try it online!

### Explanation

```
 L    Length of
D     Decimal expansion of input argument. Works for negative values too

```
> 4 votes

# Answer
# APL (Dyalog Unicode), 7 bytes

```
⌈10⍟1+|

```

Try it online!

Explanation:

```
⌈10⍟1+|
⌈        ⍝ round up the
 10⍟     ⍝ log10 of...
    1+   ⍝ incremented
      |  ⍝ absolute value of input

```

If format is allowed: 4 bytes - `≢⍕∘|`
> 4 votes

# Answer
# Alice, 16 bytes

```
/O
\I@/Hwa:].$Kq

```

Try it online!

### Explanation

```
/O
\I@/...

```

This is simply a framework for numerical input→mathematical processing→numerical output.

The rest of the code is the real algorithm:

```
Hwa:].$Kq
H            Compute absolute value
 w   .$K     While the result is not zero do:
  a:           divide the number by 10
    ]          move the tape head one cell forward
        q    Get the position of the tape head

```
> 3 votes

# Answer
# Chaincode, 5 bytes

```
pqL_+

```

### Note: This is exactly the same code as that from the other challenge

## Explanation

```
pqL_+ print(
    +   succ(
   _      floor(
  L        log_10(
pq           abs(
               input())))))

```
> 3 votes

# Answer
# dc, 1 byte

```
Z

```

Try it online!

---

Not using a builtin, 18 bytes:

```
[d10/d0!=F]dsFxz1-

```

Try it online!
> 3 votes

# Answer
# Java 8, ~~61~~ ~~59~~ ~~39~~ ~~37~~ 33 bytes

```
n->(int)Math.log10(n<0?-n:n+.5)+1

```

-4 bytes thanks to *@MarkJeronimus*.

Try it online.

**Explanation:**

```
n->            // Method with integer as both parameter and return-type
  (int)        //  Convert the following double to an integer (truncating its decimals):
    Math.log10(//   The log_10 of:
      n<0?     //    If the input is negative:
          -n   //     Use its absolute value
         :     //    Else:
          n+.5)//     Add 0.5 to the input instead
  +1           //  And add 1 to the result at the end

```
> 3 votes

# Answer
# , 40 bytes

```
function(x)max(ceiling(log10(abs(x))),0)

```

Try it online!
> 3 votes

# Answer
## Pip, 14 bytes

```
LNABq/LNt//1+1

```

https://tio.run/##K8gs@P/fx8/RqVDfx69EX99Q2/D/f0MDczNjC1NjCwA

Explanation

```
LN              natural log of...      (change of base becasue this is the only log function they had)
  ABq           the absolute value of the input...
     /          divided by...
      LNt       the natural log of 10...   (change of base)
         //1    integer divided by 1 (no floor function)
            +1  added to 1

```

This was inspired by the Chaincode solution.

This could probably be optimized.
> 3 votes

# Answer
# S.I.L.O.S, 41 bytes

```
readIO
i|
lblb
i/10
a+1
if i b
printInt a

```

Try it online!

Returns `1` for `0`.
> 2 votes

# Answer
# Lua, 40 bytes

Port from my python answer

```
print(math.log10(math.abs(10*...)+1)//1)

```

Try it online!
> 2 votes

# Answer
# C, 27 bytes

**Try Online**

```
f(n){return n?1+f(n/10):0;}

```

**C (gcc), 22 bytes**

```
f(n){n=n?1+f(n/10):0;}

```

**Using math, 29 bytes**

```
f(n){return 1+log10(abs(n));}

```
> 2 votes

# Answer
# K (ngn/k), ~~10~~ ~~9~~ 7 bytes

-3 bytes from @ngn (see Am I an insignificant array?)

```
#10\#!:

```

Try it online!

* `#!:` get the absolute value of the input (literally, take the count of the range of each value; e.g. `#!-2` -\> `#-2 -1` -\> `2`)
* `10\` "digit-ize" the input
* `#` take the count

A solution using `$` instead of `10\` save two bytes, but may be invalid given the question's rules.
> 2 votes

# Answer
## ARM Thumb-2 (no div instruction, no libgcc), 30 bytes

Raw machine code:

```
2800 d00b bfb8 4240 2201 2100 3101 380a
dafc 3201 0008 280a daf7 0010 4770

```

Uncommented assembly:

```
        .syntax unified
        .globl count_digits
        .thumb
        .thumb_func
count_digits:
        cmp     r0, #0
        beq     .Lret
        it      lt
        neglt   r0, r0
        movs    r2, #1
.Lcountloop:
        movs    r1, #0
.Ldivloop:
        adds    r1, #1
        subs    r0, #10
        bge     .Ldivloop
.Ldivloop_end:
        adds    r2, #1
        movs    r0, r1
        cmp     r0, #10
        bge     .Lcountloop
.Lcountloop_end:
        movs    r0, r2
.Lret:
        bx      lr

```

Returns 0 if 0.

### Explanation

C function signature:

```
int32_t count_digits(int32_t val);

```

First, we compare val to zero.

If it is zero, we return zero. If it is less than zero, we negate it.

```
count_digits:
        cmp     r0, #0
        beq     .Lret
        it      lt
        neglt   r0, r0

```

Set up our digit counter for the outer loop.

```
        movs    r2, #1

```

Now, a naïve subtraction based division loop

```
        movs    r1, #0
.Ldivloop:
        adds    r1, #1
        subs    r0, #10
        bge     .Ldivloop

```

Increment the digits counter, then loop to the outer loop if we are still more than 10.

```
.Ldivloop_end:
        adds    r2, #1
        movs    r0, r1
        cmp     r0, #10
        bge     .Lcountloop

```

Move the result into the return register and return.

```
.Lcountloop_end:
        movs    r0, r2
.Lret:
        bx      lr

```
> 2 votes

# Answer
# Julia, 7 bytes

```
ndigits

```

Try it online!
> 2 votes

# Answer
# PowerShell Core, 46 bytes

```
param($a)for($s=0;$a){$s+=!!($a=[int]$a/10)}$s

```

## Implementation Details

```
param($a)              # Defines the input parameter
for($s=0;$a){          # Initialise the result to 0 and iterates while the parameter is not 0
$s+=!!($a=[int]$a/10)  # Divides the parameter by 10 and increment the result variable
                       # by one if the result is not 0
}$s                    # Returns the result

```

Try it online!
> 2 votes

# Answer
# Excel, 26 bytes

```
=INT(LOG(A1^2+(A1=0))/2)+1

```

Log of the number squared / 2 is 1 byte shorter than `ABS`
> 2 votes

# Answer
# TI-Basic, ~~9~~ 8 bytes

```
int(log(1+10abs(Ans

```

Takes input in `Ans`.

-1 byte thanks to MarcMush.
> 2 votes

# Answer
# Python 2, 48 bytes

-3 thanks to ovs -1 thanks to pizzapants

```
lambda x:math.log10(abs(10*x)+1)//1
import math

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
Ä>T.nî

```

Try it online! or Try all tests

```
Ä      # Absolute value
 >     # Increment
  T.n  # Log base 10
     î # Round up

```
> 1 votes

# Answer
# C#, ~~49~~ 56 bytes

```
namespace System.Math{n=>n==0?1:Floor(Log10(Abs(n))+1);}

```
> 1 votes

# Answer
# Jelly, 5 bytes

```
A‘l⁵Ċ

```

Try it online!
> 1 votes

# Answer
# Ruby, 27 bytes

```
f=->x{x==0?0:1+f[x.abs/10]}

```

As a test:

```
tests = [[-45 , 2],
         [1254 , 4],
         [107638538 , 9],
         [-20000 , 5],
         [0 , 0 ],
         [-18 , 2]]

tests.each do |i, o|
  p f.call(i) == o
end

```

It outputs:

```
true
true
true
true
true
true

```
> 1 votes

# Answer
# Perl 5 `-Minteger -p`, ~~26~~ 24 bytes

```
1while++$\*abs($_/=10)}{

```

Try it online!
> 1 votes

# Answer
# @yBASIC, 53 bytes.

```
_#=@_>.@_
_%=_%/(_#*_#+!.)_=_+!.GOTO(@_)+"_"*!_%@__?_

```

Input should be stored in variable \_%
> 1 votes

# Answer
# Rust, 41 bytes

```
fn f(n:i32)->u8{n!=0&&return f(n/10)+1;0}

```

Try it online!
> 1 votes

# Answer
# Pyth, 10 bytes

```
.xhs.l.aQT

```

**Test suite**

Explanation:
```
.xhs.l.aQT  # Code
.xhs.l.aQTQ # With implicit variables
            # Print (implicit):
    .l   T  #   the log base 10 of:
      .aQ   #    the absolute value of the input
   s        #   floored
  h         #   plus 1
.x        Q #  unless it throws an error, in which case the input

```
Python 3 translation:
```
import math
Q=eval(input())
try:
    print(int(math.log(abs(Q),10))+1)
except:
    print(Q)

```
> 1 votes

# Answer
# Gol\>\<\>, 12 bytes

```
SA:z+aSLS(PB

```

Try it online!

### Example full program & How it works

```
1AGIE;GN
SA:z+aSLS(PB

1AGIE;GN
1AG       Register row 1 as function G
   IE;    Take input as int, halt if EOF
      GN  Call G and print the result as int

SA:z+aSLS(PB
SA            Absolute value
  :z+         Add 1 if zero
     aSL      Take log 10
        S(    Floor
          PB  Increment and return

```

Many math functions are prefixed with `S`, which made the code longer.

Adding 0.9 unconditionally (`9a,+`) and using ceiling (`S)`) is also possible with same byte count. Zero input yields 0 in this case.
> 1 votes

# Answer
# AWK, 33 bytes

```
$1=int(log(($1?$1^2:1)^.5)/2.3)+1

```

Try it online!

Basically, this will print the integer part of the log base 10 of the input, plus one. `2.3` is a working approximation of natural log of 10. To deal with negative numbers, it takes the square root of the power of two. If input is zero, returns `1` instead, so the pattern is different from `0`, which would return false and would not be printed. Too many necessary workarounds.
> 1 votes

# Answer
# , 38 bytes

```
f=function(x)`if`(x^2<100,1,1+f(x/10))

```

Try it online!

Unusually for , a recursive function seems to be shorter here than the previous answer using built-in functions (although this is mostly gained simply because we can skip `abs(x)` by using `x^2<100` as a condition instead)...
> 1 votes

# Answer
# Make, 80 bytes

```
$(N):
ifeq ($(N),0)
	@echo 0
else
	@expr 1 + $(shell make N=$$(($(N)/10)))
endif

```

Try it online!

I'm posting this entry for two reasons...

First, it's a ridiculous way to get the number of digits. :) It's recursively calling `make`, each time dividing the number by 10, and counting how many time that happens.

Second, it works on my Linux test system from the commandline (which is using `GNU Make 4.1`) but will not work at all on TIO (which appears to be using `GNU Make 4.2.1`). So I'm really curious about that and would like to know if it works for other people? It might just be that I don't know how to translate things like:

```
~/work/code-golf$ make N=888
3

```

to TIO's input format syntax?
> 1 votes

# Answer
# Factor, 26 bytes

```
[ abs log10 >integer 1 + ]

```

Try it online!
> 1 votes

# Answer
# Vyxal, 5 bytes

```
ȧ›∆τ⌈

```

Try it Online!

Thanks to the 05AB1E answer for providing me with an algorithm to port.

## Explained

```
ȧ›∆τ⌈
ȧ›      # abs(input) + 1
  ∆τ    # log_10(↑)
    ⌈   # ceil(↑)

```
> 1 votes

# Answer
# Thunno 2, 5 bytes

```
A⁺Ælṃ

```

Try it online!

```
A⁺Ælṃ  # Implicit input
A      # Absolute value
 ⁺     # Increment it
  Æl   # Log base 10
    ṃ  # Ceiling
       # Implicit output

```
> 1 votes

# Answer
# Japt v2.0a0, ~~3~~ 2 bytes

Split on each number and get the length. Is this ok? I'm not using any string method implicitly

*thanks @The Empty String Photographer*

```
ìl

```

Try it
> 1 votes

# Answer
# Raku, 25 bytes

```
{0 max.abs.log10.floor+1}

```

Try it online!
> 1 votes

# Answer
# Uiua, 7 bytes

```
⌈ₙ10+1⌵

```

Try it!

```
⌈ₙ10+1⌵
      ⌵  # absolute value
    +1   # increment
 ₙ10     # log base ten
⌈        # ceiling

```
> 1 votes

# Answer
# MATL, 5 bytes

```
|OYAn

```

Try it online!

### Explanation

```
|     % Implicitly input a number. Absolute value
OYA   % Convert to array of decimal digits
n     % Length. Implicitly display

```
> 0 votes

# Answer
# PowerShell, ~~52~~ 51 Bytes

```
$m=[math];$m::Floor($m::Log10($m::Abs($args[0])))+1

```

Thanks to Felipe for both fixing the Issue with Log10, and providing a 1byte save.

Any `System.Math` calls are extremely expensive in PowerShell.

Uses the method of getting the Log10 of the Abs Value of the input, and rounding that up.
> 0 votes

# Answer
# Octave, 27 bytes

```
@(x)fix(log10(abs(x+~x)))+1

```

Try it online!
> 0 votes

# Answer
# PHP, 23 Bytes

```
<?=-~log10(abs($argn));

```

Try it online!
> 0 votes

# Answer
## QBIC, 25 bytes

```
≈abs(:)>=1|b=b+1┘a=a/z}?b

```

This divides the input by 10, and keeps track of how many times we can do this until `N` \< 1.

Explanation:

```
≈abs(:)>=1| : gets cmd line input,
            ≈ starts a while loop,
            abs() is literal QBasic code and is for cases with negative n
            | is the terminator to the WHILE-condition
b=b+1       Keep track of the # of divisions
┘           Syntactic line break
a=a/z       Divide a by 10 (z==10 in QBIC)
}           End WHILE-loop body
?b          PRINT b

```
> 0 votes

# Answer
# Bash, 50 bytes

```
a=$1;until [ $a -eq 0 ];{ let i++ a=a/10;};echo $i

```

Try it online!

No string/array command, only count digits by integer division.
> 0 votes

# Answer
# Ruby, 33 bytes

```
->x{1+Math.log10(x.abs+0.1).to_i}

```

Try it online!
> 0 votes

# Answer
# bc, 6 bytes

```
length

```

Built-in function.
> 0 votes

# Answer
# Actually, 8 bytes

```
;0=+A╥Lu

```

Try it online!

Explanation:

```
;0=+A╥Lu
;0=       is input equal to 0?
   +      add 1 if input is 0, else add 0
    A     absolute value
     ╥L   log base 10, floor
       u  increment

```

This program effectively calculates `floor(log10(x))+1`. To deal with `log(0)` being undefined (actually it returns `(-inf+nanj)` which is a special way of saying it's undefined), the input is incremented if it is `0` prior to computing the length. Thus, `0` is considered to have a length of `1`.
> 0 votes

# Answer
# Pari/GP, 13 bytes

```
n->#digits(n)

```

Try it online!
> 0 votes

# Answer
# Vyxal `l`, 1 byte

```
ȧ

```

Try it Online!

This is why restricting built-ins is a bad idea. The `l` flag outputs the length of the top of the stack implicitly, which I don't think is a "function" - it's a feature of the language variant, not a function.

The `ȧ` simply gets the absolute value because `-` is counted in the size.
> 0 votes

# Answer
# jamforth, 6 bytes

```
UWIDTH

```

I'm not sure why gforth doesn't have UWIDTH. It's actually really useful.

This solution also works in arbitrary bases.
> 0 votes

---
Tags: code-golf, number, integer
---


title: N-chotomize a list

text:
# Question
Title: N-chotomize a list
Given a list of integers `L`, and an integer `N`, output `L` splitted in `N` sublists of equal lenghts.

### Non-divisible lengths

If `N` does not divide the length of `L`, then it is not possible that all sublists have equal length.

In any case, the last sublist of the output is the one that adapts its length to contain the remainder of the list.

This means that all sublists of `L` except for the last one should be of length **`length(L) // N`**, where `//` is floored division (e.g. `3//2 = 1`).

### Some rules

* `L` can be empty.
* `N >= 1`.
* You may use any built-in you want.
* You may take the input through `STDIN`, as a function argument, or anything similar.
* You may print the output to `STDOUT`, return it from a function, or anything similar.
* You may chose any format for the lists and the integer as long as it is the most natural representation of lists and integers in your language.

### Test cases

```
Input:  [1,2,3,4], 2
Output: [[1,2],[3,4]]

Input:  [-1,-2,3,4,-5], 2
Output: [[-1,-2],[3,4,-5]]

Input:  [1,2,3,4], 1
Output: [[1,2,3,4]]

Input:  [4,8,15,16,23,42], 5
Output: [[4],[8],[15],[16],[23,42]]

Input:  [4,8,15,16,23,42], 7
Output: [[],[],[],[],[],[],[4,8,15,16,23,42]]

Input:  [2,3,5,7,11,13,17,19,23], 3
Output: [[2,3,5],[7,11,13],[17,19,23]]

Input:  [], 3
Output: [[],[],[]]

Input:  [1,2,3,4,5,6,7,8], 3
Output: [[1,2],[3,4],[5,6,7,8]]

```

### Scoring

This is , so the shortest answer in bytes wins.

# Answer
# Pyth, ~~11~~ 10 bytes

1 byte thanks to @FryAmTheEggman.

```
cJEt*R/lJQ

```

Test suite.

Takes inputs in reversed order.

Sample input:

```
5
[1,2,3,4,5,6,7]

```

Sample output:

```
[[1], [2], [3], [4], [5, 6, 7]]

```

### Explanation

```
cJEt*R/lJQ     Main function, first input:Q, second input:E.
cJEt*R/lJQQ    Implicit arguments.

c              The function c is special.
               It can chop arrays.
               If the second argument is a list of integers,
               then it chops the first array at the indices
               specified by the second array.

 JE            The first argument is the second input, stored
               to the variable J.

   t*R/lJQQ    This is the second argument.
      /lJQ     Yield length of J, integer-divided by Q.
    *R    Q    Multiply it to the following respectively:
                   [0,1,2,3,...,Q-1]
   t           Then throw away the first element.
               For example, if Q=3 and E=[1,2,3,4,5,6,7,8],
               we would now have [3,6].

```
> 4 votes

# Answer
## JavaScript (ES6), 63 bytes

```
(a,n,l=a.length/n|0)=>[...Array(n)].map(_=>--n?a.splice(0,l):a)

```
> 4 votes

# Answer
# K (ngn/k), ~~18~~ 17 bytes

-1 thanks to @coltim

```
{*[!y;(-y)!#x]_x}

```

Try it online!
> 3 votes

# Answer
## Python, ~~76~~ 73 bytes

```
lambda L,N:list(map(lambda x,r=len(L)//N:L[x*r:][:r+(x>N-2)*N],range(N)))

```

Basically an unnamed function that performs the task. Thanks to LeakyNun for the bytes saved!
> 2 votes

# Answer
## Common Lisp, 114 bytes

```
(defun f(l n &optional(p(floor(length l)n))(i 1))(if(= i n)(list l)(cons(subseq l 0 p)(f(subseq l p)n p(+ i 1)))))

```

Ungolfed:

```
(defun f (l n &optional (p (floor (length l) n)) (i 1))
  (if (= i n) (list l)
              (cons (subseq l 0 p)
                    (f (subseq l p) n p (+ i 1))))
  )

```

Example call:

```
(format t "~A~C~C" (f (read) (read)) #\return #\newline)

```

Try it here!

Basically:

* If we are cutting the last group, return whatever's left of the initial list.
* Otherwise take `p = |L| / N` elements out of the list and join that to the result of a recursive call on the remainder. `i` is an iteration counter used for the stop condition.

I had misunderstood the challenge at first, thinking the program should build groups of `N` elements rather than `N` groups. Anyway, this version does the job for an extra 10 bytes. LisP won't win this time but I couldn't really miss the opportunity :')
> 2 votes

# Answer
## Haskell, ~~69~~ 67 bytes

```
a%b=a#b where l#1=[l];l#n|(h,t)<-splitAt(div(length a)b)l=h:t#(n-1)

```

Usage example: `[1,2,3,4] % 3` -\> `[[1],[2],[3,4]]`.

A simple recursive approach, similar to @xnor's answer.

Edit: @Will Ness saved 2 bytes. Thanks!
> 2 votes

# Answer
# Vyxal, 67 bitsv2, 8.375 bytes

```
L>ßwṘÞ÷RṘ

```

Try it Online!

Bitstring:

```
0110000000101110001001111010001000011101011000101111111101011010001

```
> 2 votes

# Answer
# , 34 bytes

```
](],#@;@]<@}.[)<:@[{.-@(<.@%~#)<\]

```

Try it online!

This was way harder than it should have been, and I threw away two approaches before getting this, which still feels long.

* `(<.@%~#)` Integer divide list size by `n`. This will be the "regular" bucket size (ie, the size of buckets which are not the final, variable bucket).
* `-@...<\]` Break up the list into buckets of those size. This will result in an extra bucket when the list is not evenly divisible.
* `<:@[{.` From that list of buckets, take one less than `n`. This many buckets are guaranteed to be the regular size. Note that if size of the original list is less than `n`, these regular buckets will have size 0.
* `(],#@;@]<@}.[)` To these regular elements append `],` all the remaining elements `#@;@]<@}.[`. That is, if there are `r` regular elements, kill the first `r` elements of the original list and put everything that remains into a single bucket. That is the final bucket which we'll append to the regular buckets. In the case of an evenly divisible list, it will be just one more regular element. Otherwise it will be a final jumbo element.

## , 34 bytes, K answer port (ish)

```
-@[{.]<;.1~i.@#@]<@e.i.@[*(<.@%~#)

```

Try it online!

bstrat's K answer inspired me to revisit an earlier approach of mine, which at a high-level was almost identical.

The difference in length between the J and K answers highlights interesting differences between K's cut primitive (which specifies cut points by indexes) and J's (which requires a boolean array where ones specify cut points). The J approach fares quite poorly in this problem, and requires additional post processing to make the empty cells match the problem specification.

Another approach I tried was using J's "remove the fret points" cut option to get the empty cells correct in a natural way, but doing this requires you to duplicate the fret points just-so, and thus incurs a heavy pre-processing cost.
> 2 votes

# Answer
# , 29 bytes

```
-@[{.(I.@(<.@%~+-@[{.|)#)</.]

```

Attempt This Online!

-2 thanks to Jonah for noticing that `</.` (grouping) followed by `-@[{.` (add enough empty groups) works. Why it works with an empty vector input is a mystery...

---

# , 31 bytes

```
]<@#~i.@[=/(I.@(<.@%~+-@[{.|)#)

```

Attempt This Online!

After all sorts of approaches tried and thrown away, I finally settled with the one that creates a boolean matrix and gives the chunks via `#`. Most others suffered badly when the "regular buckets" are empty.

For the input of `3` and `[1 2 3 4 5 6 7 8]`,

```
]<@#~i.@[=/(I.@(<.@%~+-@[{.|)#)
           (                 #)    call inner function with 3 and length of array (8):
               (<.@%~       )      size of regular bucket (2)
                           |       number of extra elements (2)
                      -@[{.        left-pad with zeros to the length of 3; [0 0 2]
                     +             elementwise add; [2 2 4]
            I.@    copy each index by the element; [0 0 1 1 2 2 2 2]
     i.@[          range of 3; [0 1 2]
         =/        outer product by equality;
                   [[1 1 0 0 0 0 0 0]
                    [0 0 1 1 0 0 0 0]
                    [0 0 0 0 1 1 1 1]]
]<@#~    for each row of the above, keep places corresponding to 1s;
         {[1 2] [3 4] [5 6 7 8]}

```

If I don't need to handle the cases where empty buckets are present, `i.@[=/` can be golfed to `=@`.
> 2 votes

# Answer
## F#, ~~100~~ 98 bytes

```
fun n l->
let a=List.length l/n
List.init n (fun i->if i<n-1 then l.[a*i..a*i+a-1] else l.[a*i..])

```

Using F# list slicing, with an if clause deciding whether to pick *a* elements or all remaining elements.
> 1 votes

# Answer
## PowerShell v2+, 125 bytes

```
param($l,$n)if($p=[math]::Floor(($c=$l.count)/$n)){1..$n|%{$l[(($_-1)*$p)..((($_*$p-1),$c)[!($_-$n)])]}}else{(,''*($n-1))+$l}

```

Feels too long, but I can't seem to come up with a way to get the slicing to work happily if there are empty arrays in the output, so I need the encapsulating `if`/`else` to handle those cases. Additionally, since PowerShell's default `.ToString()` for arrays via console output can look a little weird, you can tack on a `-join','` to show the arrays as comma-separated rather than newline-separated on the console. I've done that in the examples below to make the output more clear, but you won't want to do that if you're leaving the output on the pipeline for another command to pick up.

### Explanation

Takes input `param($l,$n)` for the list and number of partitions, respectively. We then enter an `if`/`else` statement. If the size of each partition, `$p` is non-zero (setting helper `$c` to be the `.count` along the way), we're in the `if`.

Inside the `if`, we loop from `1` to `$n` with `|%{...}`, and each iteration we're doing a pretty complex-looking array slice `$l[(($_-1)*$p)..((($_*$p-1),$c)[!($_-$n)])]`. The first parens is our start index, based on what partition we're on and how big our partition size is. We range that `..` with our end index, which is formed from a pseudo-ternary. Here, we're choosing between either `$c` (the literal end of the array), or the length of our partition, based on whether we're in the last chunk `$_-$n` or not.

Otherwise, we're in the `else`. We construct an empty array with the comma-operator `,''*` equal to one fewer partitions than requested, and then tack on the input array as the final element.

### Examples

Here I'm showing the partitions separated with newlines and each individual element separated with `,`, as described above.

```
PS C:\Tools\Scripts\golfing> .\n-chotomize-a-list.ps1 (1,2,3,4) 2
1,2
3,4

PS C:\Tools\Scripts\golfing> .\n-chotomize-a-list.ps1 (-1,-2,3,4,-5) 2
-1,-2
3,4,-5

PS C:\Tools\Scripts\golfing> .\n-chotomize-a-list.ps1 (1,2,3,4) 1
1,2,3,4

PS C:\Tools\Scripts\golfing> .\n-chotomize-a-list.ps1 (4,8,15,16,23,42) 5
4
8
15
16
23,42

PS C:\Tools\Scripts\golfing> .\n-chotomize-a-list.ps1 (4,8,15,16,23,42) 7

4,8,15,16,23,42

PS C:\Tools\Scripts\golfing> .\n-chotomize-a-list.ps1 (2,3,5,7,11,13,17,19,23) 3
2,3,5
7,11,13
17,19,23

PS C:\Tools\Scripts\golfing> .\n-chotomize-a-list.ps1 $null 3

PS C:\Tools\Scripts\golfing>

```
> 1 votes

# Answer
## Prolog, ~~100~~ 99 bytes.

```
n(A,B):-length(B,A).
p(L,K,G):-n(K,G),append(A,[_],G),n(N,L),M is N//K,maplist(n(M),A),append(G,L).

```

Call e.g.

> ?- p( \[1,2,3,4,5,6,7\], 3, X).
> X = \[\[1, 2\], \[3, 4\], \[5, 6, 7\]\] **.**
> 1 votes

# Answer
# JavaScript (Node.js), 56 bytes

```
f=(a,n,l=a.length/n|0)=>[a,...--n?f(a.splice(l),n,l):[]]

```

Try it online!
> 1 votes

# Answer
# PHP, 109 Bytes

```
<?for($n=(count($a=$_GET[0]))/($d=$_GET[1])^0;$i<$d;)$r[]=array_slice($a,$i*$n,++$i==$d?NULL:$n);print_r($r);

```

All Testcases
> 0 votes

---
Tags: code-golf, array
---


# Question
Title: Is there a shortest code to format string
# Code Golf Challenge

Given a string of 10 characters: `'abcdefghij'`

I want to format it in this pattern and print it in the console in a minimum number of characters: `(abc) def-ghij`

My solution:

```
print(f"({s[0:3]}) {s[3:6]}-{s[6::]}")

```

# Answer
> 4 votes
# Python 3, 35 bytes

```
print(f"({s:.3}) {s[3:6]}-{s[6:]}")

```

**Try it online!**

Uses the solution from the question but saves three bytes:

1. removes a redundant `:` in the final slice `s[6::]`, and
2. uses the `precision` specifier (`.`) of the `format_spec` (the bit after the `:` in `{...:...}`) which is overloaded for string types to give a prefix so `{s[0:3]}` -\> `{s[:3]}` -\> `{s:.3}`

# Answer
> 1 votes
# Python, 36 bytes

*slightly improved version of your f-string (see also Jonathan Allan's comment), wrapped in a function*

```
print(f"({s[:3]}) {s[3:6]}-{s[6:]}")

```

Attempt This Online!

---

# Python, 37 bytes

*without format strings*

```
print("("+s[:3]+")",s[3:6]+"-"+s[6:])

```

Attempt This Online!

uses that `print` inserts a space between arguments

---

# Python, 39 bytes

*C-style format string*

```
print("(%s%s%s) %s%s%s-%s%s%s%s"%(*s,))

```

Attempt This Online!

printing characters separately is slightly shorter than spiting string in 3 parts

# Answer
> 0 votes
# PowerShell, 46 bytes

```
"($($a[0..2])) $($a[3..5])-$($a[6..9])"-join''

```

Try it online!

The output is a little weird, if someone can suggest a fix to that it would be much appreciated!

---
Tags: code-golf, python
---