27
\$\begingroup\$

The random Fibonacci sequence is defined as follows:

$$ f_n = \begin{cases} f_{n-1}+f_{n-2} \text{ with probability } 1/2 \\ f_{n-1}-f_{n-2} \text{ with probability } 1/2 \\ \end{cases} $$ $$ f_1 = f_2 = 1 $$

i.e. whether the next term is the sum or difference of the previous two is chosen at random, independently of previous terms. Your task is to implement this sequence.

Each random realization of the sequence must use consistent values. For example, if \$f_3 = 2\$, \$f_4\$ must then be either \$2+1 = 3\$ or \$2-1 = 1\$. This can be thought of as the sequence "remembering" previous values. This means that this example program is invalid, as previous values in the sequence are not maintained by later values. Furthermore, you should explain how your program meets the \$1/2\$ probability requirement.

As is standard for challenges, you can perform one of three tasks:

  • Take a positive integer \$n\$ as input and output \$f_n\$
  • Take a positive integer \$n\$ as input and output \$f_1, f_2, ..., f_n\$
  • Output the sequence indefinitely with no end

Again, as is standard, you may use either \$0\$ or \$1\$ indexing, but the two initial values \$f_1 = f_2 = 1\$ must be used.

This is , so the shortest code, in bytes, wins.

Examples

n -> possible values of f_n | probabilities of values
1 -> 1                      | 1
2 -> 1                      | 1
3 -> 2, 0                   | 1/2, 1/2
4 -> 3, 1, -1               | 1/4, 1/2, 1/4
5 -> 5, 3, 1, -1            | 1/8, 1/8, 3/8, 3/8
6 -> 8, 4, 2, 0, -2         | 1/16, 1/8, 1/4, 5/16, 1/4
\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – caird coinheringaahing Sep 16 at 15:20
  • \$\begingroup\$ May we assume \$n>2\$? (with 1-indexing) \$\endgroup\$ – Robin Ryder Sep 16 at 18:06
  • \$\begingroup\$ @RobinRyder, No you must handle the cases of \$n = 1\$ and \$n = 2\$ \$\endgroup\$ – caird coinheringaahing Sep 16 at 18:07
  • \$\begingroup\$ Don't get why \$f_5\$ can't be \$-3=-1-2\$? \$\endgroup\$ – Noodle9 Sep 17 at 15:33
  • 1
    \$\begingroup\$ @Noodle9 If \$f_3 = 2\$, because \$f_2\$ is always \$1\$, \$f_4\$ cannot be \$-1\$, it has to be either \$2 - 1 = 1\$ or \$2 + 1 = 3\$. Therefore, \$f_5\$ is any of \$1 - 2 = -1\$, \$1 + 2 = 3\$, \$3 - 2 = 1\$ or \$3 + 2 = 5\$ \$\endgroup\$ – caird coinheringaahing Sep 17 at 15:37

25 Answers 25

11
\$\begingroup\$

05AB1E, 8 7 bytes

λ₂D(‚Ω+

-1 byte thanks to @ovs.

Prints the infinite sequence.

Try it online.

Explanation:

λ        # Create a recursive environment to output the infinite sequence,
         # implicitly starting at a(0)=1
         #  (push a(n-1) implicitly)
 ₂       #  Push a(n-2) (NOTE: all negative a(n) are 0, so a(-1)=0)
  D      #  Duplicate a(n-2)
   (     #  Negate the copy: -a(n-2)
    ‚    #  Pair them together: [a(n-2), -a(n-2)]
     Ω   #  Pop and push a random item
      +  #  And add it to the a(n-1)
         # (after which the infinite list is output implicitly)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ λ is really a good builtin for this challenge ;). 7 bytes: λ₂D(‚Ω+. \$\endgroup\$ – ovs Sep 16 at 17:07
8
\$\begingroup\$

APL (Dyalog Unicode), 20 bytes

{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1

Try it online!

Takes n from stdin and prints first n terms.

{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1  ⍝ Full program. Input: n
{              }/⎕⍴1  ⍝ Reduce a vector of n ones...
           ¯2↑⍵  ⍝ Last two items ([0 1] for the first iteration)
   (¯1*?2)       ⍝ 1 or -1
          ⊥      ⍝ Base convert (or polynomial evaluate),
                 ⍝ giving f(x-2)+f(x-1) or -f(x-2)+f(x-1) with 50% chance each
 ⍵,              ⍝ Append to the previous iteration
| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Japt, 14 13 11 bytes

Outputs the nth term, 1-indexed. Uses JavaScript's Math.random() as seen here.

@Zä+iÍö)Ì}g

Try it, check the first n terms or view the distributions across 10,000 runs

@Zä+iÍö)Ì}g     :Implicit input of integer U
@               :Function taking an array as argument via parameter Z
 Zä             :  Consecutive pairs of Z reduced by
   +            :    Literal "+"
    i           :    Insert
     Í          :      "n" at index 2 with wrapping, resulting in "n+"
                :      (Hooray for shortcut abuse!)
      ö         :    Random character from that string, where XnY=Y-X
       )        :  End reduction
        Ì       :  Get last element
         }      :End function
          g     :Starting with [0,1], repeatedly run it through that function,
                : pushing the result back to it each time
                :Implicit output of Uth element, 0-indexed

To explain how the shortcut abuse works here: Í is Japt's shortcut for n2<space> which is primarily intended to be used for converting binary strings to integers (e.g., "1000"Í="1000"n2 =8). However, when you pass a 2 character+space shortcut like that to another method - in this case i - the space is used to close that method and the 2 characters are split & passed to that method as separate arguments. Which is handy here as the i method for strings expects one argument containing the string to be inserted and another, optional integer argument for the index it's to be inserted at.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

perl -061 -M5.010, 46 43 bytes

say$,while($,,$/)=($/,$/+$,-2*$,*(.5<rand))

Try it online!

This prints the infinite series.

Saved three bytes using a suggestion from Nahuel Fouilleul.

How does it work?

First trick is the command line switch -061. This sets the input record to 1 (as the ASCII value of 1 is 49, aka 61 in octal). The input record separator is $/.

We then use two variables to keep state, $,, which initially is the empty string, but Perl will treat that as 0 when used as a number. $/ is set to 1, as discussed above. In an infinite loop, we set $, to $/, and $/ to $, + $/, and then, with probability .5, subtract 2 * $, from the latter. We then print $,.

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ using while instead of redo can save 3 bytes Try it online! \$\endgroup\$ – Nahuel Fouilleul Sep 17 at 7:18
  • 1
    \$\begingroup\$ however as I understand the question the ouput should begin with 1,1 say should be before (saves only 2 bytes) Try it online! \$\endgroup\$ – Nahuel Fouilleul Sep 17 at 7:23
  • \$\begingroup\$ If we use $, instead of $y, and use say$,while... we still save three bytes. Try it online! \$\endgroup\$ – Abigail Sep 17 at 10:24
  • \$\begingroup\$ And say$/while($y,$/)=($/,.5>rand?$/+$y:$/-$y) saves another byte. Now 42. \$\endgroup\$ – Kjetil S. Sep 17 at 11:23
5
\$\begingroup\$

Jelly, 10 bytes

I'm pretty sure 10 is as good as it'll get in Jelly; I had some much longer solutions along the way.

1ṫ-ḅØ-XṭƲ¡

A monadic Link accepting an integer, which yields all values up to and including that 0-indexed index
(i.e. \$n \to [f_0, f_1,\cdots, f_n]\ |\ f_0=f_1=1 : f_n = f_{n-1} \pm f{n-2} \$).

Try it online!

How?

1ṫ-ḅØ-XṭƲ¡ - Link: integer, n
1          - set the left argument to 1
         ¡ - repeat this n times:
        Ʋ  -   last four links as a monad f(left):  e.g. left = [1,1,2,3,5,8]
 ṫ-        -     tail from 1-based, modular index -1            [5,8]
                 (tailing 1 from index -1 yields [1])
    Ø-     -     signs (a nilad)                                [-1,1]
   ḅ       -     convert from base (vectorises)                 [3,13]
                                        (i.e. [5×-1¹+8×-1°, 5×1¹+8×1°])
      X    -     random choice                                  3?
       ṭ   -     tack                                           [1,1,2,3,5,8,3]
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 45 bytes

Outputs f(n) using RandomInteger 0 or 1

#&@@Nest[+##|(-1)^Random@0[[0]]#&@@#&,0|1,#]&

Try it online!

-6 bytes from @att

I also tried this 46 bytes

If[#>1,#0[#-1]+(-1)^RandomInteger[]#0[#-2],#]&     

but the sequence could not "remember" the previous values

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 45 bytes \$\endgroup\$ – att Sep 16 at 21:14
5
\$\begingroup\$

Python 2, 66 64 bytes

Outputs the sequence infinitely.

from random import*
a=b=1
while 1:print a;a,b=b,b+choice([-a,a])

Try it online!

Python 2, 73 bytes

Outputs the nth term of the sequence.

from random import*
a,b=0,1
exec"a,b=b,b+choice([-a,a]);"*input()
print a

Try it online!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Nice solution! For the first one, you can initialize as a=b=1. \$\endgroup\$ – xnor Sep 17 at 0:46
4
\$\begingroup\$

J, 28 22 bytes

-6 thanks to Bubbler!

0{1&({,]#.~_1^?@2)&1 1

Try it online!

0{1&({,]#.~_1^?@2)&1 1
  1&      …       &1 1 a verb that will apply 1&… on 1 1 y (the input) times 
              ?@2        0 or  1
           _1^           1 or _1
       ]#.~              to base, e.g. 3 5:
                           (3* 1^1)+(5* 1^0) = 8 or
                           (3*_1^1)+(5*_1^0) = 2
     {,                  prepend tail of list, i.e. 5 8 or 5 2
0{                     take first element
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 22 bytes \$\endgroup\$ – Bubbler Sep 17 at 0:59
  • \$\begingroup\$ @Bubbler really everything is solvable with base conversion. :-) \$\endgroup\$ – xash Sep 17 at 1:08
4
\$\begingroup\$

JavaScript (ES6),  68 67 66 53  52 bytes

Saved 2 bytes thanks to @Shaggy

Returns the n-th term, 0-indexed.

f=(n,p=1,q=0)=>n?f(n-1,Math.random()<.5?p+q:p-q,p):p

Try it online!

Commented

f = (                // f is a recursive function taking:
  n,                 //   n = 0-indexed input
  p = 1,             //   p = previous value
  q = 0              //   q = penultimate value
) =>                 //
  n ?                // if n is not equal to 0:
    f(               //   do a recursive call:
      n - 1,         //     decrement n
      Math.random()  //     set p to either:
      < 0.5 ? p + q  //       p + q
            : p - q, //       or p - q
      p              //     copy the previous value in q
    )                //   end of recursive call
  :                  // else:
    p                //   return the last value
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 67 bytes, maybe? \$\endgroup\$ – Shaggy Sep 16 at 16:14
  • \$\begingroup\$ 52 bytes, I think. \$\endgroup\$ – Shaggy Sep 17 at 16:11
  • \$\begingroup\$ @Shaggy Yes, we definitely don"t need such a convoluted formula now that we're dealing with variables... \$\endgroup\$ – Arnauld Sep 17 at 16:37
  • \$\begingroup\$ Down to 50 bytes now, but I'm on my phone so you should probably double check the results. \$\endgroup\$ – Shaggy Sep 17 at 18:02
4
\$\begingroup\$

><>, 22 bytes

1|.00<-x+40.08&:{&:}n:

Try it Online!

This is usually a terrible language for challenges involving randomness, since the only source of randomness in ><> is x.

But in this case things works out alright. x sends the instruction pointer in a random direction, so it either wraps around to itself in the y-direction, or hits a + or - with equal probability.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

C (gcc), 58 57 47 bytes

a,b;f(x){a=--x?f(b=x),b+=rand(x=b)%2?a:-a,x:1;}

Try it online!

  • Saved 1 thanks to @ceilingcat
  • Saved 10 thanks to @Dominic van Essen

Recursive solution which starts all the calls needed before executing them, the last call initialize values.

a,b;         - aux variables
f(x){        - function tacking an integer n and 
               returning nth term 1 indexed.

a=           - return trough eax register
--x?f(b=x)   - call recursively before doing the job
x=b          - local x used as temp
,b+=rand()%2?a:-a  - rnd fib step
,x           - assign temp(x) to a
:1;}         - stop recursion and initialize a to 1

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice. Q from a C newbie: why do you need to call srand() within the function? Isn't it Ok just to leave it however it was initialized already? It looks as if sequential calls still give random output without it, for only 47 bytes... \$\endgroup\$ – Dominic van Essen Sep 19 at 11:34
  • \$\begingroup\$ @Dominic van Essen unfortunately srand() has to be called to seed the rnd() function, if we don't do it every time we hit run we get always the same results, which is not truly random. In C rnd() pick values from a list and the standard way to use it is to seed rnd by calling srand ( time ( 0 ) ); which uses the current time to move the cursor on that list. Anyway in code-golf we can use a trick, we use an address (&x ) instead of time. It's the shortest way found so far. \$\endgroup\$ – AZTECCO Sep 19 at 12:36
  • 2
    \$\begingroup\$ This being a function, you could argue that if your caller wants a different non-default random sequence, they can seed the PRNG. It's normal for C functions to use rand() without re-seeding it. Repeated calls to this function from the same caller (e.g. in a loop) will always get the same random number within one run of the program because stack ASLR (which indirectly randomizes &x) only happens once at process startup. If you don't re-seed, repeated calls will get later parts of one long random sequence. (Agreed with @DominicvanEssen) \$\endgroup\$ – Peter Cordes Sep 19 at 14:24
  • 2
    \$\begingroup\$ This is exactly the gist of why I asked, but explained better! reseeding each cycle seems much less random to me than seeding once in the calling program, and not re-seeding any more. \$\endgroup\$ – Dominic van Essen Sep 19 at 14:58
  • 2
    \$\begingroup\$ @Dominic van Essen seems like the newbie here is me lol, thanks to both for pointing that out, I completely agree and update my answer! \$\endgroup\$ – AZTECCO Sep 19 at 17:53
4
\$\begingroup\$

R, 69 ... 55 bytes

-1 byte thanks to Giuseppe (which led to a further -4 bytes), and -1 byte thanks to Dominic van Essen (which led to a further -1 byte)

F=0:1;repeat cat(" ",{F=F[2]+F[1]*(0:-1)^sample(2)}[1])

Try it online!

Prints the sequence indefinitely, separated by spaces.

F is initialized as the vector [1 1].

At each step, draw a random permutation of the vector [1 2] with sample(2). This means that (0:-1)^sample(2) is either [0^1 (-1)^2]=[0 1] or [0^2 (-1)^1]=[0 -1] (with probability 1/2 each). In both cases, F[1] takes the previous value of F[2], and depending on the random draw, F[2] becomes either F[2]+F[1]or F[2]-F[1]. Finish the step by printing the first value of F.

Note that I can make this 2 bytes shorter by using a stupid delimiter between sequence values: Try online a 53 byte version which uses the string TRUE as delimiter.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 61, I think. I'm pretty sure it's valid, but haven't had a chance to really look at the distribution. \$\endgroup\$ – Giuseppe Sep 16 at 19:53
  • \$\begingroup\$ @Giuseppe Well spotted, thanks! Calling cat first, as you suggested, but using repeat instead of while led to the current 57 byte solution. \$\endgroup\$ – Robin Ryder Sep 16 at 21:45
  • \$\begingroup\$ 56 bytes, I think. \$\endgroup\$ – Dominic van Essen Sep 18 at 21:51
  • \$\begingroup\$ @DominicvanEssen Good thinking, thanks! Furthermore, this allows a more efficient initialization of F, gaining another byte. \$\endgroup\$ – Robin Ryder Sep 20 at 19:16
3
\$\begingroup\$

Raku, 26 bytes

{1,1,*+* *(-1,1).pick...*}

Try it online!

Outputs a lazy infinite list. This is pretty much identical to the normal fibonacci program, but with *(-1,1).pick tacked on to randomly flip the sign of the second parameter.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 3, 77 bytes

from random import*
f=lambda n,t=0,o=1:o if n<2else f(n-1,o,o+choice((-t,t)))

A recursive function which accepts \$n\$ and yields a possible \$f_n\$.

Try it online! Or see the first few as sampled 10K-distributions.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Red, 75 bytes

func[n][a: b: 1 loop n - 1[set[a b]reduce[b b +(a * pick[1 -1]random 2)]]a]

Try it online!

Returns the nth term.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 38 bytes

Prints the sequence indefinitely. Adapted from J42161217's answer.

#0[Echo@+##,RandomChoice@{#,-#}]&[0,1]

Try it online!

Ungolfed:

f[a_, b_] := ( Echo[a+b]; f[a+b, RandomChoice[{a,-a}]] );
f[0, 1]
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

R, 55 54 53 52 51 49 48 47 bytes

Edit: -1 byte, and again -1 byte thanks to Giuseppe, -1 byte thanks to AZTECCO

cat(1);repeat cat(" ",T<-sign(rt(1,1))*F+(F=T))

Try it online! or check the n=6 distribution.

Full program taking no input. Returns full random fibonacci sequence.

Program to return nth element using the same approach is 48 bytes.

Commented:

cat(1);             # First, print the first element (1) 
                    # (T is initialized to 1 by default,
                    # and F is initialized to 0).
repeat              # Now, repeat indefinitely:
 cat(" ",           # output " ", followed by...
  T<-               #   T, updated to equal...
     sign(rt(1,1))  #   the sign of 1 randomization of 
                    #     the t-distribution with 1 degree-of-freedom
                    #     (distribution is centred around zero,
                    #     so sign is [+1,-1] with probability [.5,.5])...
     *F             #   times F (second-last value)...
       +(F=T))      #   plus T (last value)...
                    #   while updating F to equal T.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ use rt(1,1) instead of rnorm(1), as it's a byte shorter :-) \$\endgroup\$ – Giuseppe Sep 18 at 21:47
  • \$\begingroup\$ Thanks Giuseppe! I started going-through all of the r... functions, but got swamped when I realised that I didn't understand the parameters for most of them...! \$\endgroup\$ – Dominic van Essen Sep 18 at 21:54
  • \$\begingroup\$ (had some browser refreshing problems, so hopefully only posted once now...) \$\endgroup\$ – Dominic van Essen Sep 18 at 22:38
  • \$\begingroup\$ + coerces it's arguments to numeric if possible, so +T should work for another byte down. \$\endgroup\$ – Giuseppe Sep 20 at 13:19
3
\$\begingroup\$

Dotty, 75 bytes

val| :Stream[Int]=1#::1#::(|zip|.tail map(_*((math.random*2).toInt*2-1)+_))

Try it online

Same as below.

Scala, 91 87 85 84 bytes

Saved 4 bytes thanks to corvus_192

val| :Stream[Int]=1#::1#::(|zip|.tail map{t=>t._2+t._1*((math.random*2).toInt*2-1)})

Try it online

| is a Stream so that previous elements are remembered. To get the nth element, you can use |(n-1) (it's 0-indexed). To get the first n elements, use |.take(n) (l.take(n).toList to force it).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a few byte by using Stream instead of LazyList and dropping the () from math.random. \$\endgroup\$ – corvus_192 Sep 17 at 10:57
2
\$\begingroup\$

Charcoal, 28 bytes

≔⁰θ≔¹ηFN«≔⁺η×θ⊖⊗‽²ι≔ηθ≔ιη»Iθ

Try it online! Link is to verbose version of code. Outputs the nth number. Explanation:

≔⁰θ≔¹η

Start with 0 as the ith number and 1 as the i+1th number.

FN«

Loop n times.

≔⁺η×θ⊖⊗‽²ι

Calculate the next number.

≔ηθ≔ιη

Shuffle the values around.

»Iθ

Output the nth number.

29 bytes to output the first n numbers:

F²⊞υ¹FN⊞υ⁺§υ±¹×§υ±²⊖⊗‽²I✂υ⁰±²

Try it online! Link is to verbose version of code. Explanation:

F²⊞υ¹

Start with 1 as the first and second numbers.

FN

Loop n times.

⊞υ⁺§υ±¹×§υ±²⊖⊗‽²

Calculate the next number.

I✂υ⁰±²

Output all but two of the numbers.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Icon, 70 bytes

procedure n()
f:=[1,1]
while write(f[2])&push(f,f[1]+?[1,-1]*f[2])
end

Try it online!

Prints the sequene indefinitely.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

x86 machine code, 21 bytes

The rdtsc version is the same size for x86-64 machine code.

rdrand reg (3 bytes) gives us a truly random number. Branching on its sign bit is cheap. By testing only 1 bit, the 50/50 probability is obviously satisfied exactly with zero bias.

rdtsc (2 bytes) gives us a "reference cycle" timestamp whose low bits are somewhat random (it takes at least 25 cycles to run back-to-back RDTSC instructions, but the counter isn't running that much faster than we're sampling it). Testing one bit with test al, 1 leads to significant correlation between consecutive decisions, but test al,al / jnp (branch on the parity flag, horizontal xor of the low 8 bits) gives surprisingly good results, and could be used on pre-IvyBridge machines that lack rdrand. Both of them golf to the same overall size in 32-bit mode.

Try it online! NASM listing for rdrand version: EAX rfib(ECX), callable from C with MS __fastcall

21                         rfib:          ;;; 0-indexed.  ecx=5 gives the n=6 test case results.
22 00000020 31C0               xor eax, eax
23 00000022 99                 cdq                         ; EDX = fib[-1] = 0
24 00000023 40                 inc eax                     ; fib[0] = 1
25 00000024 E30E               jecxz   .done               ; ecx=0 : return 1 without looping

27                         .loop:
28 00000026 0FC7F7             rdrand  edi
29 00000029 85FF               test    edi, edi        ; 1 byte shorter than sar reg, imm / xor / sub 2's complement bithack
30 0000002B 7902               jns    .no_negate       ; the top bit is fully random
31 0000002D F7DA               neg    edx
32                         .no_negate:
33 0000002F 0FC1D0             xadd    eax, edx        ; like xchg + add, and same size
34 00000032 E2F2               loop   .loop
35                         .done:
36 00000034 C3                 ret
 size = 0x35 - 0x20 = 0x15 = 21 bytes

Note that xadd doesn't actually save any bytes vs. xchg eax, edx / add eax, edx. It's just fun. And it's "only" 3 uops, instead of 4 total, on Intel Skylake with register operands. (Normally the instruction is only used with the lock prefix and a memory destination, but it fully works with registers).

Test case:

  bash loop to test the ECX=5 case
$ asm-link -m32 -dn random-fib.asm &&
 { declare -A counts; counts=(); 
  for i in {1..10000}; do ./random-fib; ((counts[$?]++));done; 
  for i in "${!counts[@]}"; do echo "result: $(( i > 128 ? i-256 : i )):   
${counts[$i]} times";done }

result: 8:   617 times
result: 4:   1290 times
result: 2:   2464 times
result: 0:   3095 times
result: -2:   2534 times

NASM listing for rdtsc version: EBX rfib2(ECX). This version would be the same size in 64-bit mode; doesn't need 1-byte inc. RDTSC writes EAX and EDX so we can't take advantage of cdq in the init.

 2                         rfib2:            ; 0-index count in ECX, returns in EBX
 3 00000000 31F6               xor  esi, esi
 4 00000002 8D5E01             lea  ebx, [esi+1]           ; fib[0] = 1, fib[-1] = 0
 5 00000005 E30D               jecxz .done
 6                         .loop:
 7 00000007 0F31               rdtsc                       ; EDX:EAX = TimeStamp Counter
 8                         
 9 00000009 84C0               test    al, al               ; low bits are essentially random; high bits not so much
10 0000000B 7B02               jnp    .no_negate
11 0000000D F7DE               neg     esi
12                         .no_negate:
13 0000000F 0FC1F3             xadd    ebx, esi
14 00000012 E2F3               loop   .loop
15                         .done:
16                             ; returns in EBX
17 00000014 C3                 ret
 size = 0x15 = 21 bytes

Test results for ECX=5:

result: 8:   668 times         (ideal: 625)
result: 4:   1217 times        (ideal: 1250)
result: 2:   2514 times        (ideal: 2500)
result: 0:   3135 times        (ideal: 3125)
result: -2:   2466 times       (ideal: 2500)

vs. with test al, 1 / jnz to use just the low bit of the TSC as the random value:

  # test al,1  / jnz   version: correlation between successive results.
result: 8:   115 times
result: 4:   79 times
result: 2:   831 times
result: 0:   3070 times
result: -2:   5905 times

test al,4 happens to work reasonably well for long runs on my Skylake CPU (i7-6700k) which ramps up to 3.9GHz at the energy_performance_preference=balance_performance I'm using, vs. a reference (TSC) frequency of 4008 MHz (more info on x86 constant-TSC stuff). I imagine there's some strange alchemy of branch prediction, and rdtsc itself having ~25 cycle throughput (core clocks) on Skylake (https://uops.info).

Results are generally better distributed with test al,al / jnp though, so prefer that to take entropy from all 8 low bits. When CPU frequency is low (idle), so the TSC is not close to the same frequency as the core, taking entropy from a single bit might work even better, although the parity of the low 8 bits is probably still best.

I haven't tested on a CPU with turbo disabled where non-boost core clock exactly equals the TSC reference clock. That could more easily lead to bad patterns if the rdtsc throughput happens to be a power of 2 or something, perhaps favouring some sequence that lets branch prediction lock on.

All my testing has been with one invocation of the function per process startup. A Linux static executable is pretty efficient to start up, but is still vastly more expensive than calling the function in a loop from inside the process.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 56 53 52 bytes

Edit: -3 bytes thanks to AZTECCO, -1 byte thanks to ceilingcat

x;y;r(n){for(x=y=1;--n;)x=~-(rand()&2)*y+(y=x);x=y;}

Try it online!

Non-recursive answer in C.
Function that returns nth (one-based) element of random fibonacci sequence.

x;y;                # x & y hold last and last-but-one elements;
r(n){               # n is index of element we're looking for;
for(x=y=1;          # initialise first two elements to 1;
 --n;)              # now loop by decreasing n until it is zero,
 x=                 # update x to become equal to:
   ~-(rand()&2)*y   # plus-or-minus y...
   +(y=x)           # plus x
                    # (while updating y to equal the current x).
    ;x=y;}          # after looping, return y.

Note: Following some discussion in the comments here and in AZTECCO's answer, a consensus was reached that it is not necessary to initialize the random seed within a function. Of course, that this means that the calling program should do so, or the function may give the same sequence of pseudo-random output every time the calling program is run. A 74 byte variant of the function can itself initialize the random seed itself (but only on first call, so that subsequent calls from the same program run give different output).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can use --n instead of n-=n>0 . I think you have to seed rnd. See my coment on my answer. \$\endgroup\$ – AZTECCO Sep 19 at 13:27
  • 1
    \$\begingroup\$ @AZTECCO - Thanks for your explanation about seeding rand(): I've added variants here that now include this, so that our answers can be compared (yours is better!), but I'm not completely convinced that re-seeding every cycle is necessary or even desirable. It'd be interesting to know the consensus of C-golfers about this... \$\endgroup\$ – Dominic van Essen Sep 19 at 15:28
  • \$\begingroup\$ @AZTECCO - I think that --n causes a bug when calling r(0) (to get the first element in the sequence): this is why I used the much-more-complicated n-=n>0. If I'm missing something, please tell me! \$\endgroup\$ – Dominic van Essen Sep 19 at 15:30
  • 2
    \$\begingroup\$ Other C randomness answers have just used rand() without srand(). e.g. Randomizing until 0 and another C answer on the same question. In a function, it makes total sense that you seed the PRNG once at process startup, so it's not your responsibility and in fact you should not do that. If you were writing a whole program (e.g. a main) then it would make sense and arguably be required depending on the challenge, @AZTECCO. \$\endgroup\$ – Peter Cordes Sep 19 at 16:49
  • 1
    \$\begingroup\$ @Dominic van Essen sorry, I didn't noticed it was 0 based, you can switch to 1 based like this and should be fine \$\endgroup\$ – AZTECCO Sep 19 at 17:45
1
\$\begingroup\$

Bash, 65 bytes

a=1;b=1;while :;do echo $a;t=$b;:$[b+=$RANDOM&1?$a:-$a];a=$t;done

Try it online!

Endlessly outputs the latest and greatest version of the sequence.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Swift, 77 bytes

sequence(first:(1,1)){a,b in(b,.random() ?a+b:a-b)}.lazy.forEach{print($0.0)}

Outputs until Int overflow.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Lua, 81 bytes

t={1,1}for i=1,...do t[i]=t[i]or t[i-1]+t[i-2]*(math.random(2)*2-3)print(t[i])end

Try it online!

Takes number of members to be printed as an argument. Replace ... with 1/0 to print sequence forever at const of one byte.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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