Bitcoin Forum
June 22, 2018, 05:46:08 PM
 News: Latest stable version of Bitcoin Core: 0.16.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
genjix
Legendary

Offline

Activity: 1232
Merit: 1000

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

Offline

Posts: 1529689568

Ignore
 1529689568

1529689568
 Report to moderator
1529689568
Hero Member

Offline

Posts: 1529689568

Ignore
 1529689568

1529689568
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1529689568
Hero Member

Offline

Posts: 1529689568

Ignore
 1529689568

1529689568
 Report to moderator
1529689568
Hero Member

Offline

Posts: 1529689568

Ignore
 1529689568

1529689568
 Report to moderator
1529689568
Hero Member

Offline

Posts: 1529689568

Ignore
 1529689568

1529689568
 Report to moderator
grondilu
Legendary

Offline

Activity: 1134
Merit: 1001

 March 14, 2011, 09:24:48 PM

You might have a look at davout's website code, if you like ruby.

I have also been thinking about that for a few weeks now.  I'm working on yet-another implementation in bash.

The problem with this kind of stuff is, as you pointed out, it's easy to make a simple implementation but much more complex if you want to make it optimal.

I can't believe there is not more public documentation about these kinds of algorithms.
 Pages: [1]
 « previous topic next topic »