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 pre-existing systems, algorithms or code I can read.