30
\$\begingroup\$

This question already has an answer here:

The Fibtraction sequence (as I call it) is similar to the Fibonacci sequence except, instead of adding numbers, you subtract them.

The first few numbers of this challenge are:

1, 2, -1, 3, -4, 7, -11, 18, -29, 47, -76, 123, -199, 322, -521, 843, -1364...

The sequence starts with 1 and 2. Every next number can be calculated by subtracting the previous number from the number before it.

1
2
-1 = 1 - 2
3  = 2 - (-1) = 2 + 1
-4 = -1 - 3
7  = 3 - (-4) = 3 + 4
...

In other words:

f(1) = 1
f(2) = 2
f(n) = f(n - 2) - f(n - 1)

This is OEIS sequence A061084.

Challenge

Write a program/function that takes a positive integer n as input and prints the nth number of the Fibtraction sequence.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • Your solution can either be 0-indexed or 1-indexed but please specify which.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
  • Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

These are 0-indexed.

Input      Output

1          2
2          -1
11         123
14         -521
21         15127
24         -64079
31         1860498

That pattern was totally not intentional. :P

This challenge was sandboxed.

Before you go pressing any buttons that do scary things, hear me out. This might be considered a dupe of the regular Fibonacci challenge and I agree, to some extent, that it should be easy enough to port solutions from there. However, the challenge is old and outdated; is severely under-specified; allows for two types of solutions; has answers that don't have easy ways to try online; and in general, is lacking of answers. Essentially, in my opinion, it doesn't serve as a good "catalogue" of solutions.

plz send teh codez

\$\endgroup\$

marked as duplicate by Poke, Mr. Xcoder, AdmBorkBork code-golf Jul 20 '17 at 12:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    \$\begingroup\$ Note that after the first two terms it devolves into the Lucas sequence with alternating signs. \$\endgroup\$ – ETHproductions Jul 8 '17 at 17:05
  • 2
    \$\begingroup\$ i could close this as a dupe of other Lucas number challenges but not having enough online executable answers is not reason to not be dupe. We could have a discussion about making that challenge clearer but it is still dupe regardless \$\endgroup\$ – Downgoat Jul 8 '17 at 17:33
  • 8
    \$\begingroup\$ Even if the old Fibonacci challenge has some shortcomings and doesn't serve it's purpose as a catalogue very well, the best solution would be to make a good, canonical Fibonacci challenge, not an almost-Fibonacci challenge, because no one will look for that as a repository of Fibonacci solutions. Before you do though, this should probably be brought up on meta. We've discussed retiring the old Fibonacci challenge a couple of times, and I think Chris said he'd be fine with it, but I'm not sure what to do with all the answers that do work there. \$\endgroup\$ – Martin Ender Jul 8 '17 at 17:37
  • 2
    \$\begingroup\$ Is this exactly similar to the regular Fibonacci sequence? If we say the first term of the Fibonacci sequence is 1, then second is also 1(0th term = 0 + 1). By that logic, this sequence should be 1, -1, 2, -3, 5, -8, 13, ..... \$\endgroup\$ – cst1992 Jul 9 '17 at 6:55
  • 3
    \$\begingroup\$ I voted to close this challenge. If we want to make a proper catalog for the Fibonacci sequence that has a well-defined specification, then I think it should be for the vanilla Fibonacci sequence and not a manipulation of it. The challenge this is a dupe of is a better candidate in my opinion. \$\endgroup\$ – Poke Jul 10 '17 at 17:34

36 Answers 36

26
\$\begingroup\$

Oasis, 4 bytes

c-21

Try it online!

0-indexed.

I saw this language used for a similar challenge once, and immediately I knew I should try it here. Can't say I'm disappointed.

Explanation

   1    a(0) = 1
  2     a(1) = 2
c       a(n) = a(n - 2)
 -                      - a(n - 1)
\$\endgroup\$
  • 1
    \$\begingroup\$ I saw this challenge with only 1 answer and figured I could get an Oasis answer in. 2 seconds later you did it. Nice :P \$\endgroup\$ – Emigna Jul 8 '17 at 17:17
  • 1
    \$\begingroup\$ Oh, wow, I'm a dumbass; I thought the chat was "05AB1E Oasis" as in a cool place to lounge. Little did I know it was a language. \$\endgroup\$ – Magic Octopus Urn Jul 11 '17 at 22:56
12
\$\begingroup\$

Python 2, 35 34 bytes

-1 byte thanks to ovs!

f=lambda n:n*(n<3)or f(n-2)-f(n-1)

Try it online!

Answers are 1-indexed. Takes advantage of f(2) and f(1) being equal to their respective inputs.

\$\endgroup\$
10
\$\begingroup\$

Javascript, 24 bytes

f=n=>n<3?n:f(n-2)-f(n-1)

f=n=>n<3?n:f(n-2)-f(n-1)

for (let i = 1; i <= 20; i++) {
  console.log(f(i))
}

\$\endgroup\$
9
\$\begingroup\$

Octave, 27 bytes

0-indexed.

@(n)([1,2]*[0,1;1,-1]^n)(1)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Very nice approach! \$\endgroup\$ – Luis Mendo Jul 8 '17 at 17:16
  • 1
    \$\begingroup\$ How does this work? \$\endgroup\$ – Kritixi Lithos Jul 20 '17 at 13:03
8
\$\begingroup\$

x86 Machine Code, 12 bytes

Iterative solution; 0-indexed

31 C0
40
8D 50 01
29 D0
92
E2 FB
C3

The above function takes a single input, n (passed in the ECX register, following Microsoft's fastcall calling convention), and returns the nth number of the Fibtraction sequence in the EAX register.

The implementation is based on the well-known trick for calculating a Fibonacci number using two variables, which Snowman's answer in Java reminded me of.

Not only is this solution much smaller in size than my first attempt (it even competes with Mathematica using a built-in), it will also be much faster because it is iterative, rather than recursive. Theoretical comp-sci's love for recursion is foiled once more!

Ungolfed assembly mnemonics:

Fibtraction:
   xor  eax, eax
   inc  eax                ; EAX = 1  (XOR+INC are 3 bytes; same as PUSH+POP)
   lea  edx, [eax + 1]     ; EDX = 2  (LEA is 3 bytes; same as PUSH+POP)
Iterate:
   sub  eax, edx           ; EAX = EAX - EDX
   xchg eax, edx           ; swap EAX and EDX
   loop Iterate            ; decrement ECX and keep looping as long as ECX != 0
   ret                     ; return, with result in EAX

Try it online!

A couple of things worth pointing out here…

  • We start by loading the constants 1 and 2 into registers. These are our starting values. The standard way, of course, to load constants into registers is mov reg, imm. That's fast, but it takes a whopping 5 bytes to encode. So, for code-golfing purposes, we make use of various other tricks to load values into registers. A 2-byte PUSH that pushes the immediate value onto the stack, followed by a 1-byte POP that pops the value off the top of the stack and into a register, is the workhorse trick—very common and very useful. But, if you are just setting the register to 1, you can do XOR+INC, which is the same 3 bytes. And, if you already have the value you want in a register, then you can build off of it using the magic LEA instruction, which is also only 3 bytes. Both of those tricks are showcased here, since they are more interesting and somewhat faster than the good old PUSH+POP.
  • Inside of the body of the loop, we do a pretty neat optimization. The fundamental operation we're doing here is:

    edx = (eax - edx)
    eax -= edx
    

    which would naively be translated to (indeed, this is what most C compilers do):

    sub  eax, edx                              ; 2 bytes
    mov  ebx, edx                              ; 2 bytes
    mov  edx, eax                              ; 2 bytes
    mov  eax, ebx                              ; 2 bytes
    

    or, somewhat better—rewrite the subtraction as addition of a negative so that the operand order can be reversed, allowing the result to end up in the desired register without having to clobber a temporary register (ICC is able to apply this optimization):

    neg  edx                                   ; 2 bytes
    add  edx, eax     ; edx = (eax - edx)      ; 2 bytes
    sub  eax, edx     ; eax -= edx             ; 2 bytes
    

    but I have written it as:

    sub  eax, edx                              ; 2 bytes
    xchg eax, edx                              ; 1 byte
    

    which is conceptually similar to the naive version (only one subtraction is done, then some moves), but much more compact because of the XCHG instruction. This avoids clobbering a register, and decreases the size of the code. (I guess you could have equally well used an XOR to avoid clobbering a register—the famous move-without-a-temporary trick—but XCHG is 1 fewer byte for golfing purposes.)

    Now, to be fair, the MOVs are probably much faster in real-world code, especially on modern processors that can elide moves in the front end via register renaming. Exchanges can't be elided, and aren't known for being particularly fast. If it weren't for register renaming, ICC's code (the add-a-negative approach) would probably be the fastest in the real-world, since it's compact and arithmetic operations are extremely efficient.

  • The LOOP instruction. This is an old CISC-style instruction that is equivalent to:

    dec  ecx
    jnz  Label
    

    but is avoided in modern code (and by all compilers) because it's actually slower than the above sequence. It's also less versatile, because it has the ECX register hard-coded as the counter. However, for code-golf purposes, it's great! And since we used a calling convention that passes the parameter in ECX, we don't even have to do anything!

    (If you wanted to use a different calling convention, you'd just have to do a MOV or XCHG at the very top of the function to copy the parameter into ECX; or, you could swap out the LOOP instruction for the expanded form shown above. Either of these would only cost a couple of bytes, maximum, so this optimization isn't really saving us much, but I think it does earn a couple of style points! :-)

Similarly, if you wanted to write this for x86-64, like my original answer, which uses a different calling convention, it would be easy to adapt. Either of these will do it, and both are only 14 bytes:

Fibtraction_64_A          |      Fibtraction_64_B:
   push 1                 |         mov  ecx, edi
   pop  rax               |         push 1
   lea  edx, [rax+1]      |         pop  rax
Iterate:                  |         lea  edx, [rax+1]
   sub  eax, edx          |      Iterate:
   xchg eax, edx          |         sub  eax, edx
   dec  edi               |         xchg eax, edx
   jg   Iterate           |         loop Iterate
   ret                    |         ret
\$\endgroup\$
  • \$\begingroup\$ +1 for the very detailed explanation. Is there a way to run this code on TIO? \$\endgroup\$ – Kritixi Lithos Jul 20 '17 at 13:13
  • \$\begingroup\$ @cows As it turns out, yes. I just didn't know how to do it at the time I wrote this answer. I've added in a link. The trick uses a C wrapper to call the assembly code. There is an assembler on TIO, but screen output is platform-specific (and often requires a lot of code in asm), so doing it that way is a much bigger pain, which is why I used to avoid it. \$\endgroup\$ – Cody Gray Jul 20 '17 at 13:24
8
\$\begingroup\$

Haskell, 29 26 bytes

Inspired by alephalpha's answer I thought, I'd derive an explicit formula. It's been a while since I did an Eigenvalue decomposition, turns out the explicit formula (even after golfing it down) is longer and fails because of floating point issues.

0-indexed:

(g!!)
g=1:scanl(flip(-))2g

Try it online!

Saved 3 bytes thanks to @Laikoni

Decomposition solution, 48 bytes

There are a couple eigenvector decompositions; the simplest is actually -1-indexed rather than 0-indexed or 1-indexed:

Prelude> map (\n -> ((-1 + sqrt 5)/2)**n + ((-1 - sqrt 5)/2)**n) [0..10]
[2.0,-1.0,3.0,-4.0,7.0,-11.0,18.0,-29.000000000000004,47.0,-76.0,123.0]

Since the (-1 + sqrt 5)/2 term is less than 1, we can absorb that into the needed round at the cost of adding some leading terms,

Prelude> [round$((-1 - sqrt 5)/2)^n|n<-[0..10]]
[1,-2,3,-4,7,-11,18,-29,47,-76,123]

So e.g. one can get to a function by, but this is not much-more golfable and it's 48 bytes:

((1:2: -1:[round$(-(1+sqrt 5)/2)^n|n<-[2..]])!!)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can drop the space in 2 g. Also anonymous functions are allowed, so you do not need the f=. \$\endgroup\$ – Laikoni Jul 9 '17 at 0:28
  • \$\begingroup\$ Whoops, thanks! I thought about the anonymous function too, but then I have a naked expression in the code. Is this ok? \$\endgroup\$ – ბიმო Jul 9 '17 at 14:24
  • \$\begingroup\$ That's fine, see the Guide to golfing rules in Haskell. For TIO you can either keep the f= or use this tip. \$\endgroup\$ – Laikoni Jul 9 '17 at 15:52
  • 1
    \$\begingroup\$ I think the most I can golf the explicit formula is the 48-byte ((1:2: -1:[round$(-(1+sqrt 5)/2)^n|n<-[2..]])!!), or subtract 6 bytes if the list is ok as output. \$\endgroup\$ – CR Drost Jul 10 '17 at 21:40
  • \$\begingroup\$ @CRDrost Yeah it's pretty much ungolfable (at least wrt. to the other solution). Feel free to create your own answer or edit it in, if you like. \$\endgroup\$ – ბიმო Jul 10 '17 at 21:45
6
\$\begingroup\$

cQuents, 8 bytes

=1,2:y-z

1-indexed. Since cQuents isn't stack based it isn't as terse as Oasis. Prints the whole sequence if no input is given.

Try it online!

Explanation

=1,2      Sequence start equals 1,2
    :     Mode: sequence. Prints the 1-indexed nth term for input n.
     y-z  Each item in the sequence equals the second to last item minus the last item
\$\endgroup\$
  • \$\begingroup\$ Note current version uses Y and Z instead of y and z \$\endgroup\$ – Stephen Feb 1 at 4:50
6
\$\begingroup\$

Jelly, 5 bytes

1_@¡3

0-indexed.

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Perl 6, 19 bytes

{(1,2,*-*...*)[$_]}

test it

Expanded:

{  # bare block lambda with implicit parameter 「$_」
  (

    1, 2,  # seed the sequence

    * - *  # WhateverCode lambda used to generate the rest of the values

    ...    # keep generating until:

    *      # never stop

  )[ $_ ]  # index into the sequence
}
\$\endgroup\$
  • \$\begingroup\$ If it was f(n) = f(n - 1) - f(n - 2) it would be {(1,2,*R-*...*)[$_]} instead \$\endgroup\$ – Brad Gilbert b2gills Jul 11 '17 at 16:04
6
\$\begingroup\$

05AB1E, 7 bytes

3XIFDŠ-

Try it online!

Explanation

3         # push 3
 X        # push 1
  IF      # input times do:
    D     # duplicate top of stack
     Š    # move the copy down 2 spaces on the stack
      -   # subtract top 2 numbers
\$\endgroup\$
  • \$\begingroup\$ Fails for 0 :( \$\endgroup\$ – Datboi Jul 9 '17 at 10:39
  • \$\begingroup\$ @Datboi: Thanks for notifying! Fortunately it was easily fixed without costing any bytes :) \$\endgroup\$ – Emigna Jul 9 '17 at 11:34
  • 1
    \$\begingroup\$ Oh wow. I was looking for a fix myself and the best I could come up with was 11 bytes but you just did it without using any more bytes :D gratz \$\endgroup\$ – Datboi Jul 9 '17 at 13:33
6
\$\begingroup\$

Mathematica (using a built-in), 18 12 bytes

Several bytes saved by user202729 !

LucasL[2-#]&

Or the same idea without a built-in, for 32 31 30 29 bytes:

Tr[{p=(1+5^.5)/2,1-p}^(2-#)]&

Uses 1-indexing. Try them at the Wolfram sandbox (they don't work in Mathics, unfortunately).

This uses the observation by ETHproductions and user202729 that the sequence is nearly the Lucas numbers (only with alternating sign, or reading backwards). The 29-byte function is the closed formula for the Lucas numbers.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think that is LucasL[1-#]& or something. I didn't test... \$\endgroup\$ – user202729 Jul 9 '17 at 9:50
5
\$\begingroup\$

Mathics, 31 bytes

f@1=1
f@2=2
f@x_:=f[x-2]-f[x-1]

-2 thanks to @MartinEnder!

Try it online!

\$\endgroup\$
  • \$\begingroup\$ The first two definitions can use = instead of := and it's shorter to define an operator ± instead of a function f, because you save the @s in the definitions. (I'm not sure the latter works in Mathics, but it would in Mathematica.) \$\endgroup\$ – Martin Ender Jul 8 '17 at 17:35
  • \$\begingroup\$ @MartinEnder thanks! I tried it with just = earlier but it didn't seem to work. \$\endgroup\$ – Pavel Jul 8 '17 at 17:37
  • 2
    \$\begingroup\$ The overall shortest approach is to use an unnamed function though: If[#<3,#,#0[#-2]-#0[#-1]]& \$\endgroup\$ – Martin Ender Jul 8 '17 at 17:39
  • \$\begingroup\$ @MartinEnder it uh... Doesn't work in mathics due to garbage Unicode support. Welp. \$\endgroup\$ – Pavel Jul 8 '17 at 17:43
  • \$\begingroup\$ You can post that answer, if you want. \$\endgroup\$ – Pavel Jul 8 '17 at 17:43
5
\$\begingroup\$

Brainfuck, 51 44 bytes

+++++>+>++<<[>[>>+<<-]>[<+>>-<-]>[<+>-]<<<-]

0-indexed, the input is on cell 0 and the output on cell 1.

Output is in two complement format.

Per this meta consensus, input for Turing machines may be written to the tape pre-execution, and the contents of the tape post-execution may be used as a Turing machine's output.

How?

# The tape: I O A B . . .
# I = input, O = output

>+     # O = 1
>++    # A = 2
<<[    
    >[>>+<<-]     # B = O              [ I   0   A   O  ]
    >[<+>>-<-]    # B = B - A, O = A   [ I   A   0  O-A ]
    >[<+>-]<<<    # A = B = O - A      [ I   A  O-A  0  ]
-]     # Repeat I times
\$\endgroup\$
  • \$\begingroup\$ Brainfuck is Brainfuck, not a Turing Machine. \$\endgroup\$ – Pavel Jul 9 '17 at 0:45
  • \$\begingroup\$ Can we have a TIO link? \$\endgroup\$ – totallyhuman Jul 9 '17 at 0:54
  • \$\begingroup\$ @Phoenix What's with that comment? It is anyway similar to a Turing machine, but lack random IP move. So it can be a subset of Turing machine (yet still Turing complete) \$\endgroup\$ – user202729 Jul 9 '17 at 10:12
4
\$\begingroup\$

PHP, 45 bytes

0-indexed

for($x=1,$y=2;$argn--;)$x=$x-$y=$x-$y;echo$x;

Try it online!

PHP, 46 bytes

1-indexed recursive function

function f($i){return$i<3?$i:f($i-2)-f($i-1);}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Java, 65 61 bytes

Golfed:

n->{int a=1,b=2;for(;n-->0;a-=b)b=a-b;System.out.println(a);}

This uses the standard trick of calculating Fibonacci using only two variables to hold the state, but modified to work with subtraction. I am aware that theoretically, System.out.print() should work here but in practice it is inconsistent with flushing output and sometimes (often enough to be an issue) will literally print nothing using the Oracle JVM.

This function is zero-indexed.

Try it online!

Ungolfed:

public class FibtractionFibonacciButWithSubtraction {

  public static void main(String[] args) {
    for (int i : new int[] { 1, 2, 11, 14, 21, 24, 31 }) {
      f(n -> {
        int a = 1, b = 2;
        for (; n-- > 0; a -= b)
          b = a - b;
        System.out.println(a);
      } , i);
    }
  }

  private static void f(java.util.function.Consumer<Integer> function, int n) {
    function.accept(n);
  }
}
\$\endgroup\$
  • \$\begingroup\$ You can use for(;n-->0;a-=b)b=a-b; instead of for(;n>0;--n){b=a-b;a-=b;} to save 4 bytes. \$\endgroup\$ – Nevay Jul 10 '17 at 11:27
3
\$\begingroup\$

C, 30 bytes

Try Online 1-indexed

s;f(n){s=n>2?f(n-2)-f(n-1):n;}
\$\endgroup\$
  • \$\begingroup\$ Is it acceptable to return the value through an external variable? I'm not very sure. \$\endgroup\$ – Keyu Gan Jul 10 '17 at 9:15
  • \$\begingroup\$ @KeyuGan the value is returned, one way or another, but consider this, this function does return the value of s with some compilers, try tcc on TIO \$\endgroup\$ – Khaled.K Jul 10 '17 at 11:47
  • \$\begingroup\$ @Khaled.K Astonishing! I used to think f(a){a=1;} in GCC return 1 is weird enough. But tcc proves to be more interesting. \$\endgroup\$ – Keyu Gan Jul 10 '17 at 12:11
2
\$\begingroup\$

Pari/GP, 26 bytes

n->([1,2]*[0,1;1,-1]^n)[1]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Common Lisp, 46 bytes

(defun f(n)(if(< n 3)n(-(f(- n 2))(f(1- n)))))

Try it online!

1-indexed, plain recursive solution.

\$\endgroup\$
2
\$\begingroup\$

R, 38 bytes

f=function(n)`if`(n<3,n,f(n-2)-f(n-1))

1-indexed solution

Explanation :

The 'if' function has the same syntax as ifelse : ifelse(test, TRUE, FALSE).

In this solution, we create a function f that begins to test if the input n is strictly inferior to 3 (i.e. equals to 1 or 2 ; test part of the 'if'). If its the case, the output is simply the input (TRUE part).

The function otherwise recursively calls itself and outputs the final result (FALSE part)

\$\endgroup\$
  • \$\begingroup\$ Can we have a TIO link? \$\endgroup\$ – totallyhuman Jul 9 '17 at 11:58
2
\$\begingroup\$

Mini-Flak, 72 bytes

(1-indexed)

({}(()()())(())[()()()()]){({}(([{}]({})))[({}([{}]{})[({})])][()])}{}{}

Try it online!

The TIO links have more comments, so it is easier to understand.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 34 33 bytes

A¹αA²βF…²θ¿﹪ι²A⁻βαβA⁻αβα⎇﹪Iθ²IαIβ

Try it online!

1-indexed. I insist on writing answers in a language with a totally different purpose... Link to the verbose version.

\$\endgroup\$
  • \$\begingroup\$ Save 1 byte by casting the result of the ternary instead of the two variables. \$\endgroup\$ – Neil Dec 2 '17 at 13:10
2
\$\begingroup\$

Ruby, 26 bytes

Nothing fancy here, it's just a translation of Python or Javascript solutions :

f=->n{n<3?n:f[n-2]-f[n-1]}

The results are 1-indexed.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

x86-64 Machine Code, 29 bytes

Simple recursive solution; 1-indexed

The following is a function written according to the System V AMD64 calling convention that computes and returns the nth number of the Fibtraction sequence. The sole parameter, n, is passed in the EDI register. The function returns its result in the EAX register.

53
51
89 F9
83 EF 02
7E 10
E8 00 00 00 00
8D 79 FF
91
E8 00 00 00 00
29 C1
91
59
5B
C3

Try it online! (Hey, I finally figured out how to make TIO work for assembly language! Ignore the ugly boilerplate to print numbers… :-p)

Ungolfed assembly mnemonics:

Fibtraction:
   push     rbx           ; preserve original value in EBX
   push     rcx           ; preserve original value in ECX
   mov      ecx, edi      ; preserve original 'n' in ECX
   sub      edi, 2        ; EDI = n - 2
   jle      .Finished     ; if n <= 2, we're done (base case for recursion)
   call     Fibtraction   ; compute f(EDI), which is f(n - 2)
   lea      edi, [rcx-1]  ; EDI = n - 1
   xchg     eax, ecx      ; save result of f(n-2) in ECX (which we can now safely clobber)
   call     Fibtraction   ; compute f(EDI), which is f(n - 1)
   sub      ecx, eax      ; calculate f(n - 2) - f(n - 1)
.Finished:                ; fall through...
   xchg     eax, ecx      ; move result from ECX into EAX
   pop      rcx           ; restore original value to ECX
   pop      rbx           ; restore original value to EBX
   ret                    ; return, with result in EAX

Okay, it's assembly language, so there are no fancy built-ins to help us. But just look at all of those 1-byte opcodes! PUSH, POP, and XCHG are all very handy here.
These XCHG instructions are really just substitutions for register-to-register MOVes. We don't actually need to exchange the values; we just care about a one-way movement. But, although normally MOV reg, reg and XCHG reg, reg are both 2 bytes, there is a special 1-byte encoding for XCHG when one of the operands is the accumulator (EAX). Thus, this substitution saves us a few bytes (at the possible expense of speed).

The only long, ugly instructions are the CALLs, used to invoke the function recursively. (Technically, all of those 0s in the opcodes get replaced by the linker with the function's actual 32-bit relative displacement when the code gets linked, but the resulting binary will be the same size in bytes because this won't change the length of the instruction.) But there isn't really anything we can do to reduce the size. CALL can be emulated as PUSH+JMP, but just the PUSH instruction alone consumes more bytes than CALL!

The recursive nature of this algorithm made it a fun and interesting challenge—to me, at least. It's not very often in the real world that you get to write recursive code! It just isn't an efficient way to do things. (Double recursion leads to exponential complexity! Bleh!) Compilers also do a bad job, in general, optimizing it, so this hand-written assembly is head-and-shoulders above what a C compiler would generate for the naive solution:

int Fibtraction(int n)  { return n <= 2 ? n : f(n-2) - f(n-1); }

(although it has been optimized for size, rather than speed, obviously).

\$\endgroup\$
2
\$\begingroup\$

SWI Prolog, 88bytes

Did I hear recursion? Prolog is here!

g(1,1).
g(2,2).
g(X,Y):-A is X-2,g(A,B),C is X-1,g(C,D),Y is B-D.
f(X):-g(X,Y),print(Y).

Try it: SWISH

\$\endgroup\$
2
\$\begingroup\$

><>, 17+3 = 20 bytes

43\n;
?!\:@-{1-:}

Try it online!

Input is expected on the stack at the start of the program, so +3 bytes for the -v flag.

\$\endgroup\$
2
\$\begingroup\$

Julia, 24 bytes

f(n)=n>2?f(n-2)-f(n-1):n

1-indexed

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Jul 10 '17 at 20:25
2
\$\begingroup\$

Fortress 0.1 Alpha, 39 bytes.

f(n)=if n<3then n else f(n-2)-f(n-1)end

The interpreter is archived here (direct download).

This language is old and dead, very dead. (1-indexed: f(1)=1, f(2)=2).

Can be placed into a program like this:

export Executable
f(n)=if n<3then n else f(n-2)-f(n-1)end
run(args) = do
    println(f(3))
end

Does this really need explaining? This is just the definition.

\$\endgroup\$
  • 1
    \$\begingroup\$ Is there absolutely no way of trying it online? \$\endgroup\$ – totallyhuman Jul 10 '17 at 17:07
  • 1
    \$\begingroup\$ Nope. If there was, I would've found it by now. Follow the link, it's archived. \$\endgroup\$ – Zacharý Jul 10 '17 at 17:07
1
\$\begingroup\$

Mathematica, 37 bytes

LinearRecurrence[{-1,1},{1,2},{#+1}]&
\$\endgroup\$
  • \$\begingroup\$ Does it work on Mathics? If so, can we have a TIO link? \$\endgroup\$ – totallyhuman Jul 8 '17 at 17:31
  • 1
    \$\begingroup\$ Once again, the obvious answer is shorter \$\endgroup\$ – Pavel Jul 8 '17 at 17:34
  • \$\begingroup\$ Although MartinEnder came up with an even shorter, more obvious solution. \$\endgroup\$ – Pavel Jul 8 '17 at 17:47
1
\$\begingroup\$

dc, 32 bytes

?3sb1sc[lblcdsb-sc1-d0<d]dsdxlbp

1-indexed.

Try it online!

Explanation

?     # Take input and push it onto the main stack.
3sb   # Push 3 into register "b".
1sc   # Push 1 into register "c".
[     # Begin macro definition.
 lblc # Load the values in registers "b" and "c" onto the main stack.
 dsb  # Duplicate the top-of-stack value and push it into register "b".
 -sc  # Push the difference of the top two values into register "c".
 1-d  # Subtract 1 from the top-of-stack value and duplicate the result.
 0<d  # If the result is greater than 0, execute the macro in register "d".
]     # End macro definition.
dsdx  # Duplicate the macro, push a copy into register "d", and execute the 
      # remaining copy.
lbp   # Output the value stored in register "b".      
\$\endgroup\$
1
\$\begingroup\$

VBA, 62 Bytes

Recursive function that takes input, n, as integer and outputs the 1-indexed element of A061084

Function f(n):If n<3Then f=n Else f=f(n-2)-f(n-1):End Function
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.