12
\$\begingroup\$

First, a mathematical interlude, short, and worth your while:

If 0 < a < 4, the logistic function f(x) = ax(1-x) maps the interval [0,1] inside itself. This means that one can play the iteration game; for instance, if a=2, the initial value 0.3 becomes 0.42, then 0.4872, etc.

As the parameter a increases, the quadratic function f becomes more complicated in the following sense:

  • 0 < a < 1 all initial values iterate toward 0.
  • 1 < a < 3 0 becomes repelling, but there is a new fixed point (a-1)/a that attracts all iterations.
  • 3 < a < 1+sqrt(6) the new fixed point becomes repelling, but a cycle of 2 attracting points appears.
  • 3.44949... < a < 3.54409... the 2-cycle becomes repelling, but a cycle of 4 attracting points appears.
  • etc.

Feigenbaum noticed that the lengths of these parameter intervals decrease at a rate that gets closer and closer to 4.6692..., the Feigenbaum constant. The wonderful discovery is that this period 2 bifurcation sequence is a general phenomenon shared by any function that (like the quadratic parabola) is increasing, then decreasing. This was one of the first reports on the universality of chaos.

Now for the challenge! Write the shortest possible code that computes the Feigenbaum constant to an accuracy of your choice. The point here is not to cheat the system by encoding a number that you googled, but to actually have the computer find the value. For reference, here is the constant to 30 digits:

4.669201609102990671853203821578

\$\endgroup\$
  • 5
    \$\begingroup\$ I'm surprised we don't already have a challenge to compute this constant, a nice idea that we've missed. Closest seems to be to plot the logistic attractor. I'd suggest having the code take in a maximum error or number of digits and produce the constant to within that accuracy (ignoring machine limits past some point). Or maybe to compute that ratio between the i'th and (i+1)st doubling intervals, as would converge to the constant. The golfer choosing an accuracy is too vague and not hardcoding is unenforceable. \$\endgroup\$ – xnor Jun 15 '17 at 4:54
  • \$\begingroup\$ I thought hard on how to phrase the challenge. The issue is that this is a notoriously hard thing to compute accurately, so I figured people would have more fun focusing on implementing a slick method, rather than getting that extra digit by brute force. If people feel differently, I will change the rules. \$\endgroup\$ – Rodrigo A. Pérez Jun 15 '17 at 5:09
  • 1
    \$\begingroup\$ What are you looking for as a slick method or avoiding brute force? Note that by default for code golfs we don't require any bounds on run-time or space, so answers tend to be very inefficient when optimized for being short. Maybe you're looking to make a fastest code or restricted complexity challenge? \$\endgroup\$ – xnor Jun 15 '17 at 5:14
3
\$\begingroup\$

Javascript, 141 138 135 131 bytes, 8 digits

It's something I guess. It should be improveable quite a bit. If anyone needs a start: how to calculate Feigenbaum. And if you rather want to know how to do it code-wise, check out this.

Copy paste the following code in your console. Calculates 4.669201668823243 (so not really precise).

b=1;c=0;e=3.2;for(i=2;i<13;i++){z=b-c;a=b+z/e;j=4;while(j--){x=y=0;k=2**i;while(k--){y=1-2*y*x;x=a-x*x;}a-=x/y}e=z/(a-b);c=b;b=a;e}

b=1;c=0;e=3.2;for(i=2;i<13;i++){z=b-c;a=b+z/e;j=4;while(j--){x=y=0;k=2**i;while(k--){y=1-2*y*x;x=a-x*x;}a-=x/y}e=z/(a-b);c=b;b=a;e}
console.log(e)

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

Python, 127 bytes

c,b,e=0,1,2
for i in range(2,13):a=b+(b-c)/e;exec(("x=y=0;"+"y,x=1-2*y*x,a-x*x;"*2**i+"a=a-x/y;")*17);d,c,b=(b-c)/(a-b),b,a;e=d

Credit goes for @ThomasW with his javascript answer.

Add print(d) to output 4.669201673141983. Takes a few seconds, due to the long strings being calculated before execution.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 84 bytes

A¹βA⁰εA³·²δF…²¦¹³«A⁺β∕⁻βεδαFχ«A⁰ξA⁰ψFX²ι«A⁻¹××ψ²ξψA⁻α×ξξξ»A⁻α∕ξψα»A∕⁻βε⁻αβδAβεAαβ»Iδ

Try it online! Link to verbose code for explanation.

Uses algorithm from here.

Prints 4.669200975097843 (6 digits)

\$\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.