
March 14, 2011, 09:16:47 PM 

Hey,
I've tried google but it's not turning up much. I'm looking for algorithms to match up and fulfill an orderbook.
A offers 20 GBP for 10 BTC B offers 5 BTC for 9 GBP C offers 2 BTC for 6 GBP
Looking above we can see that to fulfill A's order, we can use B but not C's order:
BTC per GBP for A = A_want / A_amount = 10 / 20 = 0.5 BTC per GBP for B = B_amount / B_want = 5 / 9 = 0.56
if B_amount / B_want >= A_want / A_amount (rephrased to avoid float rounding errors) if B_amount * A_amount >= B_want * A_want then order is OK
So using B's rate to fulfill A's order gives A more BTC for his GBP's worth:
=> take B's order from A leaves: A offers 11 GBP for 5.5 BTC at the original rate of 0.5 (A got a better deal than he was asking for but the rate he has chosen remains fixed).
Do the comparison for C we see that (2 * 11 = 22) < 6 * 5.5... Ergo C's order is invalid for A.
HOWEVER
This isn't optimal at all. It has two problems:  The rate is fixed at what A has chosen.  Doesn't find the best all round solution to fulfill an order for everybody. I tried rephrasing it as a linear programming problem,
A offers 20 GBP for 10 BTC B offers 5 BTC for 9 GBP
x = X / GBP y = Y / BTC
Constraints: x <= 20 y <= 5
y >= x * 10 / 20 (from A's order) or y >= 0.5 x
x >= y * 9 / 5 (from B's order) or y >= 0.56 x
I have to maximise x + y in the space between those 2 lines and the box from the first 2 constraints... However the problem becomes error prone fast I can easily do bounds detection but am worried about bugs.
Implementation MUST be perfect. Therefore I'm asking if anybody knows any preexisting systems, algorithms or code I can read.
