Day 4: Fibon­acci Foil

Guide writ­ten by prop. Con­tri­bu­tions from the Amaz­ing Com­munity.

Top of the moon­ing. It is dawn of the fourth day.

I know you can­not sleep. Across the win­dow, the wind is howl­ing at all the dry­ing lines strewn across the al­ley­way, hung between two ped­es­trian houses. A cricket chirps un­der the speckled in­digo sky. There is no moon for you to see to­night. In­stead, you see vari­ous clouds peek­ing over the ho­ri­zon, flow­ing sharply like blades of grass. Wait, is­n’t that the Ex­po­nen­tial Idle graph?

You wake up from your sleep. You have to find out who did this to your the­ory. Only then could you re­sume power­ing up its pro­gres­sion us­ing a new tool, called mile­stones.

Find­ing the cul­prit #

Let’s take a look at the the­ory’s code to see which part might be caus­ing the prob­lem.

The the­ory primar­ily runs the tick func­tion 10 times per second. Usu­ally, this will be the heav­iest part of your the­ory. Looks like it only has 3 lines, cal­cu­lat­ing the vari­ous up­grades. Each of these value re­trieval func­tions (getc1 or getc2) get called once. Let’s look at the init func­tion. These up­grades’ de­scrip­tion and in­form­a­tion are up­dated 10 times per second as well, and each of them also tries to re­trieve their val­ues once or twice. Hum…

Let’s take a look at them now. Na­ively, we can try to count the num­ber of lines. Al­though this is not the best tac­tic to gauge over­all per­form­ance, in this case we might be able to gleam some in­sight into the prob­lem:

While getc1 and getc2 both con­sist of 1 line, $f$’s value re­trieval func­tion has at least 3 lines: the level 0 case, the level 1 case, and the gen­eral case. But wait! In the gen­eral case, the func­tion calls it­self at a lower level! This is called re­cur­sion, and while it’s a use­ful tac­tic in pro­gram­ming, we can’t ig­nore the ef­fect on per­form­ance if we are re­cours­ing more than once, like we do here. Each func­tion call spawns up to two smal­ler func­tion calls, which means the total num­ber of calls very much ex­ceeds the 3 lines we see… In fact, the higher the level, the num­ber of func­tion calls per­formed grows ex­po­nen­tially? Ac­tu­ally, it is pro­por­tional to the Fibon­acci num­bers them­selves! This is not good.

Stop­ping Fibon­ac­ci’s foil #

Let’s look at how we can op­tim­ise these cal­cu­la­tions. While we can store our Fibon­acci num­bers in a lookup table to avoid re­cur­sion, not only does this ap­proach con­sume more memory as we level the up­grade, we may also hit the JavaS­cript in­ter­pret­er’s com­pu­ta­tional lim­its (which will be ex­plained at a later date). Be­sides, this would­n’t be a guide about a maths game without me mak­ing an ex­cuse to in­tro­duce any math­em­at­ical for­mu­lae. And turns out, we can cal­cu­late a Fibon­acci term fairly quickly us­ing one, known as Bin­et’s for­mula, which was de­rived by Jacques Phil­ippe Marie Binet, in some year, some­where:

$F(n)=\frac{(\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n}{\sqrt{5}}$

An ex­plan­a­tion of how this for­mula came to be can be found here. In the the­ory, let’s im­ple­ment this for­mula by first as­sign­ing re­usable con­stants glob­ally, and then cal­cu­lat­ing the term us­ing them:

const fibSqrt5 = BigNumber.FIVE.sqrt();
const fibA = (BigNumber.ONE + fibSqrt5) / BigNumber.TWO;
const fibB = (BigNumber.ONE - fibSqrt5) / BigNumber.TWO;

let getf = (level) => (fibA.pow(level) - fibB.pow(level)) / fibSqrt5;

Now, let’s head in game and check it out!

Un­for­tu­nately, it seems like we have en­countered our first er­ror. Press­ing on the warn­ing sign in the game gives us a clue of what er­ror we have en­countered, as well as what line of code it is on. Ad­di­tion­ally, the er­ror will also be logged in­side the SDK. Mine says:

Er­ror: (Line 65, Col 4) Ex­cep­tion of type ‘Ex­po­nen­tial­Idle.BigNum­ber+BigNumber­Ex­cep­tion’ was thrown.

This is an arith­metic ex­cep­tion. We know that while neg­at­ive num­bers can be raised to an in­teger power, and fibB is a neg­at­ive num­ber (ap­prox­im­atly -0.618) raised to an in­teger level, the game simply does not al­low us to do this. This is be­cause in JavaS­cript, in­tegers don’t ex­ist, but are part of the Num­ber class, which are ac­tu­ally double pre­ci­sion float­ing point num­bers (doubles for short), ana­log­ous to real num­bers. In math­em­at­ics, rais­ing a neg­at­ive real num­ber to an­other real num­ber’s power does­n’t usu­ally yield a real num­ber, un­less the power is also an in­teger, so this ex­cep­tion is thrown to pre­vent such an op­er­a­tion. Let’s cir­cum­vent this by pre­tend­ing fibB is pos­it­ive, and then check­ing for the power’s par­ity (whether it’s even or odd) to give the power a sign:

const fibSqrt5 = BigNumber.FIVE.sqrt();
const fibA = (BigNumber.ONE + fibSqrt5) / BigNumber.TWO;
const fibB = (fibSqrt5 - BigNumber.ONE) / BigNumber.TWO;

let getf = (level) =>
{
    if(level % 2 == 0)
        return (fibA.pow(level) - fibB.pow(level)) / fibSqrt5;
    return (fibA.pow(level) + fibB.pow(level)) / fibSqrt5;
};

Mar­vel­lous! The Binet for­mula works, and we no longer have to deal with the lag caused by these Fibon­acci num­bers!

Con­tinu­ing with pro­gres­sion #

Yes­ter­day, we talked about the pro­gres­sion in idle games. However, since we were hal­ted by our per­form­ance prob­lem, we did­n’t have enough time to im­ple­ment the auto­ma­tions of pro­gres­sion. In an Ex­po­nen­tial Idle the­ory, we’re given two tools: the Buy All but­ton, and the Auto-buyer. Like Pub­lic­a­tions, these can be cre­ated us­ing func­tions provided by the API:

let init = () =>
{
    ...
    theory.createBuyAllUpgrade(1, currency, BigNumber.from('1e12'));
    theory.createAutoBuyerUpgrade(2, currency, BigNumber.from('1e17'));
}

These up­grades will now be avail­able for pur­chase in the Per­man­ent tab, along with Pub­lic­a­tions. The Buy All up­grade un­locks a but­ton at the bot­tom of the screen that al­lows you to pur­chase all up­grades at once when clicked, while the Auto­buyer will peri­od­ic­ally per­form that ac­tion for you. Be­cause of this, the Auto­buyer is the ‘evol­u­tion’ of the Buy All but­ton, and should be set up to un­lock at a later point than the Buy All up­grade (for ex­ample, 1e17 from 1e12, as shown above).

Un­less, you’re the one who cre­ated Riemann Zeta Func­tion (curse you).

Power up with a mile­stone #

Aside from re­set and auto­ma­tion tools, the The­ory API also gives us an­other tool to provide power-ups to pro­gres­sion. These are called mile­stones, and they are un­locked ac­cord­ing to pro­gres­sion in the the­ory’s tau value, which is es­sen­tially your high score for the the­ory. Com­mon ef­fects for a mile­stone in­clude:

• Un­lock­ing a new term
• Power­ing an ex­ist­ing term
• Un­lock­ing an en­tirely new mech­anic

Today, we will be cre­at­ing our first mile­stone - a simple power in­crease for our $c_1$. Start by spe­cify­ing where mile­stone points are re­war­ded:

import { ExponentialCost, FreeCost, LinearCost } from '../api/Costs';

let init = () =>
{
    ...
    theory.setMilestoneCost(new LinearCost(15, 15));
}

While our nor­mal up­grades use ex­po­nen­tially scal­ing costs, mile­stones of­ten use a dif­fer­ent model called Lin­ear­Cost, and the way their costs are cal­cu­lated is on a ${\log }_{1}0$ scale. In this case, where the first point is re­war­ded cor­res­ponds not to 15 tau, but 1e15, and the next points’ costs will be mul­tiply by 1e15 each, start­ing at 1e30, 1e45, etc.

Next, let’s cre­ate the mile­stone us­ing the­ory.cre­ateMile­stone­Up­grade so we can have something to spend on:

import { Localization } from '../api/Localization';

let c1ExpMs;

let init = () =>
{
    ...
    {
        c1ExpMs = theory.createMilestoneUpgrade(0, 5);
        c1ExpMs.description = Localization.getUpgradeIncCustomExpDesc('c_1', '0.03');
        c1ExpMs.info = Localization.getUpgradeIncCustomExpInfo('c_1', '0.03');
        c1ExpMs.boughtOrRefunded = (_) => theory.invalidatePrimaryEquation();
    }
}

This mile­stone will add 0.03 to the ex­po­nent of $c_1$ every level, up to 5 levels. For the de­scrip­tion and in­form­a­tion, we use the Loc­al­iz­a­tion class to get the strings suit­able for this mile­stone (‘In­creases {0} ex­po­nent by {1}’), and as these strings do not need to be re­freshed, in­stead of as­sign­ing them to get­De­scrip­tion and get­Info, we as­sign them to de­scrip­tion and info. When we put a point into the mile­stone or take away from it, we should also up­date the primary equa­tion manu­ally with the­ory.in­val­id­ateP­rimaryEqua­tion to re­flect the in­form­a­tion shown on screen. But what in­form­a­tion? We haven’t even im­ple­men­ted the power in­crease:

let getc1Exp = (level) => 1 + 0.03 * level;

var tick = (elapsedTime, multiplier) =>
{
    ...
    currency.value += dt * bonus * getc1(c1.level).pow(getc1Exp(c1ExpMs.level)) * getc2(c2.level) * (BigNumber.ONE + getf(f.level));
}

var getPrimaryEquation = () => `\\dot{\\rho} = c_1${c1ExpMs.level ? `^{${getc1Exp(c1ExpMs.level)}}` : ''}c_2(1+f)`;

Now in the primary equa­tion, we see our first use of a tern­ary op­er­ator, writ­ten as x ? y : z, which takes in a con­di­tion (boolean), and re­turns one of two val­ues de­pend­ing on whether the con­di­tion is true. Here, the con­di­tion is spe­cified as a num­ber, which is only equi­val­ent to false when it is 0. This means that the ex­po­nent will not dis­play when the mile­stone’s level is 0 ($c_1$’s ex­po­nent is at 1), since dis­play­ing a power of 1 is re­dund­ant.

With the first im­ple­ment­a­tion of a mile­stone done, you can take a break and play the the­ory un­til you can buy it and test it out. We can verify that our in­come in­creases as we buy the mile­stone, and that it dis­plays $c_1$’s ex­po­nent on screen.

While your house burns down as the the­ory skyrock­ets into in­fin­ity, let’s add a qual­ity of life fea­ture: to be able to view $c_1$’s value after the mile­stone when the (i) but­ton is pressed. To do this, let’s modify its get­Info:

let init = () =>
{
    ...
    {
        c1 = theory.createUpgrade(1, currency, new ExponentialCost(10, 1));
        let getDesc = (level) => `c_1 = ${getc1(level).toString(0)}`;
        let getInfo = (level) =>
        {
            if(c1ExpMs.level)
                return `c_1^{${getc1Exp(c1ExpMs.level)}}=
                ${getc1(level).pow(getc1Exp(c1ExpMs.level)).toString()}`;
            return getDesc(level);
        }

        c1.getDescription = (amount) => Utils.getMath(getDesc(c1.level));
        c1.getInfo = (amount) => Utils.getMathTo(getInfo(c1.level),
        getInfo(c1.level + amount));
    }
}

Save the file. You will see that when you hold down the (i) but­ton on screen, it shows $c_1$’s ex­po­nent and its value after the mile­stone is ap­plied.

Af­ter­math #

The the­ory is slowly get­ting more com­plete. Al­though, with it seem­ingly skyrock­et­ing without stop­ping (in other words, di­ver­ging), we can’t really add any more con­tent. The the­ory at this point is not very com­pel­ling to play either. Join me to­mor­row on a quest to find the per­fect bal­ance for it.

Mean­while, the source code after today’s work can be found here:

import { BigNumber } from '../api/BigNumber';
import { ExponentialCost, FreeCost, LinearCost } from '../api/Costs';
import { Localization } from '../api/Localization';
import { theory } from '../api/Theory';
import { Utils } from '../api/Utils';

var id = 'my_theory';
var name = 'My Theory';
var description = 'The one and only.';
var authors = 'Stuart Clickus';

let currency;
let clicker;
let c1, c2;
let f;
let c1ExpMs;

let init = () =>
{
    currency = theory.createCurrency();

    {
        clicker = theory.createUpgrade(0, currency, new FreeCost);
        clicker.description = Utils.getMath('\\rho \\leftarrow \\rho + 1');
        clicker.info = 'Increases currency by 1';
        clicker.bought = (amount) => currency.value += 1;
    }

    {
        c1 = theory.createUpgrade(1, currency, new ExponentialCost(10, 1));
        let getDesc = (level) => `c_1 = ${getc1(level).toString(0)}`;
        let getInfo = (level) =>
        {
            if(c1ExpMs.level)
                return `c_1^{${getc1Exp(c1ExpMs.level)}}=
                ${getc1(level).pow(getc1Exp(c1ExpMs.level)).toString()}`;
            return getDesc(level);
        }

        c1.getDescription = (amount) => Utils.getMath(getDesc(c1.level));
        c1.getInfo = (amount) => Utils.getMathTo(getInfo(c1.level),
        getInfo(c1.level + amount));
    }

    {
        c2 = theory.createUpgrade(3, currency, new ExponentialCost(500, 3));
        let getDesc = (level) => `c_2 = ${getc2(level).toString(0)}`;
        c2.getDescription = (amount) => Utils.getMath(`c_2 = 2^{${c2.level}}`);
        c2.getInfo = (amount) => Utils.getMathTo(getDesc(c2.level),
        getDesc(c2.level + amount));
    }

    {
        f = theory.createUpgrade(2, currency, new ExponentialCost(200, 1.618034));
        let getDesc = (level) => `f = ${getf(level).toString(0)}`;
        f.getDescription = (amount) => Utils.getMath(getDesc(f.level));
        f.getInfo = (amount) => Utils.getMathTo(getDesc(f.level),
        getDesc(f.level + amount));
    }

    theory.createPublicationUpgrade(0, currency, BigNumber.from('1e7'));
    theory.createBuyAllUpgrade(1, currency, BigNumber.from('1e12'));
    theory.createAutoBuyerUpgrade(2, currency, BigNumber.from('1e17'));
    
    theory.setMilestoneCost(new LinearCost(15, 15));

    {
        c1ExpMs = theory.createMilestoneUpgrade(0, 5);
        c1ExpMs.description = Localization.getUpgradeIncCustomExpDesc('c_1', '0.03');
        c1ExpMs.info = Localization.getUpgradeIncCustomExpInfo('c_1', '0.03');
        c1ExpMs.boughtOrRefunded = (_) => theory.invalidatePrimaryEquation();
    }
}

let getc1 = (level) => Utils.getStepwisePowerSum(level, 2, 5, 0);
let getc1Exp = (level) => 1 + 0.03 * level;

let getc2 = (level) => BigNumber.TWO.pow(level);

const fibSqrt5 = BigNumber.FIVE.sqrt();
const fibA = (BigNumber.ONE + fibSqrt5) / BigNumber.TWO;
const fibB = (fibSqrt5 - BigNumber.ONE) / BigNumber.TWO;

let getf = (level) =>
{
    if(level % 2 == 0)
        return (fibA.pow(level) - fibB.pow(level)) / fibSqrt5;
    return (fibA.pow(level) + fibB.pow(level)) / fibSqrt5;
};

var tick = (elapsedTime, multiplier) =>
{
    let dt = BigNumber.from(elapsedTime * multiplier);
    let bonus = theory.publicationMultiplier;
    currency.value += dt * bonus * getc1(c1.level).pow(getc1Exp(c1ExpMs.level)) * getc2(c2.level) * (BigNumber.ONE + getf(f.level));
}

var getPrimaryEquation = () => `\\dot{\\rho} = c_1${c1ExpMs.level ? `^{${getc1Exp(c1ExpMs.level)}}` : ''}c_2(1+f)`;

var getSecondaryEquation = () => `${theory.latexSymbol} = \\max\\rho`;

var get2DGraphValue = () => currency.value.sign *
(BigNumber.ONE + currency.value.abs()).log10().toNumber();

const pubPower = 0.1;

var getPublicationMultiplier = (tau) => tau.pow(pubPower);

var getPublicationMultiplierFormula = (symbol) => `{${symbol}}^{${pubPower}}`;

var getTau = () => currency.value;

var getCurrencyFromTau = (tau) =>
[
    tau.max(BigNumber.ONE),
    currency.symbol
];

init();