Optimal Talmudic Zigzag

Makefile

URL = http://api.bitcoincharts.com/v1/csv/bitstampUSD.csv.gz

all: result.txt
	time -p node simulate.js prices.json 0.25 9

result.txt: prices.json
	time -p node optimize.js $< 100000 >|$@

prices.json: csv.gz
	zcat $< | awk -F , -f zigzag.awk >|$@

csv.gz:
	curl "$(URL)" >|$@

clean:
	-rm -f csv.gz prices.json result.txt

optimize.js

"use strict";

const fs = require("fs");

const argv = process.argv;
const depth = parseInt(argv.pop());
const json = fs.readFileSync(argv.pop(), "utf8");
const list = JSON.parse(json);

const growth = (p, q) => {
        const r = Math.sqrt(p / q);

        return Math.log((r + 1 / r) / 2);
};
const total = (p) => {
	const n = p.length;
	let g = 0;

	for (let i = 1; i < n; i++)
		g += growth(p[i - 1], p[i]);

	return g;
};
const diff = (p, q) => Math.sign(p - q);
const cut = (seq, trend) => {
	const n = seq.length;
	const m = Math.max(0, n - depth);
	let t, d;

	if (n < 4)
		return false;

	d = seq[n - 1];
	t = growth(d, seq[n - 2]);

	for (let i = n - 4; i >= m; i -= 2) {
		const a = seq[i];
		const b = seq[i + 1];
		const c = seq[i + 2];

		if (diff(d, b) != trend)
			break;

		t += growth(a, b);
		t += growth(b, c);

		if (growth(a, d) >= t) {
			seq.splice(i + 1, n - i - 2);
			return true;
		}
	}

	return false;
};
const tick = (acc, p) => {
	const n = acc.length;
	const p1 = acc[n - 1];
	const p2 = acc[n - 2];
	const trend = diff(p, p1);
	const prev = diff(p1, p2);

	if (p == p1)
		return acc;

	if (trend == prev)
		acc.pop();

	acc.push(p);

	while (cut(acc, trend))
		continue;

	return acc;
};
const otz = list.reduce(tick, []);

console.warn(list.length, total(list));
console.warn(otz.length, total(otz));
console.info(otz.join("\n"));

simulate.js

"use strict";

const fs = require("fs");

const argv = process.argv;
const delta = parseFloat(argv.pop()) / 100;
const fee = parseFloat(argv.pop()) / 100;
const json = fs.readFileSync(argv.pop(), "utf8");
const list = JSON.parse(json);

const talmud = (saldo, type) => {
	const sign = ("ask" == type) ? 1 : -1;
	const coef = 1 + 2 * sign * delta - delta * fee;

	return {
		type: type,
		amount: delta * saldo.base / coef,
		price: coef * saldo.counter / saldo.base
	};
};
const init = p => {
	const saldo = {
		base: 1,
		counter: p
	};

	return {
		count: 0,
		saldo: saldo,
		ask: talmud(saldo, "ask"),
		bid: talmud(saldo, "bid")
	};
};
const trade = (saldo, order, count) => {
	const sign = ("ask" == order.type) ? 1 : -1;
	const amount = order.amount;
	const volume = order.price * amount;
	const cost = fee * volume;

	saldo.base -= sign * amount,
	saldo.counter += sign * volume - cost;

	return {
		count: count + 1,
		saldo: saldo,
		ask: talmud(saldo, "ask"),
		bid: talmud(saldo, "bid")
	};
};
const tick = (acc, p) => {
	if (p > acc.ask.price)
		return trade(acc.saldo, acc.ask, acc.count);
	else if (p < acc.bid.price)
		return trade(acc.saldo, acc.bid, acc.count);
	else
		return acc;
};
const result = list.reduce(tick, init(list[0]));
const final = result.saldo;
const ratio = Math.sqrt(final.base * final.counter / list[0]);

console.info(delta, result.count, ratio);

zigzag.awk

BEGIN {
	printf("[");
}

1 == NR {
	prev = $2;
}

1 != NR {
	tick = $2;
	if (tick == prev)
		next;

	dir = (tick > prev) ? 1 : -1;
	if (trend != dir) {
		printf("%.2f,\n", prev);
		trend = dir;
	}

	prev = tick;
}

END {
	if (NR)
		printf("%.2f", prev);

	printf("]\n");
}