1

Topic: Combinatorics (from three fingers)

Therefore I have a small problem which I should optimize how much to a smog. My Universe contains N securities (N enough small, from 4 that 9). During each moment of time I receive the market quotation or the paper X, or spread S between two these securities. If I receive the spread quotation (i.e. a difference between two securities), I can calculate the synthetic price for two securities on a basis  and the last quotations for each of papers i, j://S (i, j) = X (i) - X (j) bid [i] = q [BID] - bid [j] ask [i] = q [ASK] - ask [j] ask [j] =-q [BID] - ask [i] bid [j] = q [ASK] - bid [i] I need to support optimally current highest rates, and the lowest requirements to these securities. In terms of the pseudocode I did till now the following: B [n x n] = [-9999...,-9999] A [n x n] = [9999..., 9999] BX [n x n] = [0..., 0] AX [n x n] = [0..., 0] best_bid (q): if type (q) = security://simple case i = q [IDX1] B [0 to N, i] = q [BID] A [0 to N, i] = q [ASK] if type (q [i]) = spread://S (i, j) = X (i) - X (j) i = q [IDX1] j = q [IDX2] BX [i, j] = q [BID] BX [j, i] =-q [ASK] return max_col (B + BX)//max value of each column in an element-wise addition Too-most I do for other side. Such perversion works, but brakes since I am forced to do iteration on all matrix on each step (max_col). Cleverer ideas at me does not arise yet. Can at whom there are thoughts?

2

Re: Combinatorics (from three fingers)

Hello, negres, you wrote: N> Can at whom there are thoughts? Formulate distinctly task setting.

3

Re: Combinatorics (from three fingers)

Hello, kov_serg, you wrote: _> Hello, negres, you wrote: N>> Can at whom there are thoughts? _> formulate distinctly task setting. , here more accurate description. (1) at a stock exchange bargain N securities,  [0] to  [N]. We admit them at us 10 , i.e. N = 10. (2) Me everyone to steam of microseconds come quotations on these papers. For the sake of simplicity we will consider that they come randomly and never (3) These quotations come simultaneously happen in two forms: and. The quotation on itself papers in the form of O [i, bid, ask]. The quotation on the linear difference between two papers X (i) - X (j), too in the form of S [i, j, bid, ask] (i <j always) where i (and j if is present) - decent paper numbers, bid - the price on which it is possible to sell, ask - the price on which it is possible to buy (4) After each new quotation, from 0 that N are interesting to me to each paper and. The lowest price on which I can buy it. The highest price on which I can sell it (5) These max bid/min ask the prices I can be formed both of quotations on papers and from the linear combinations on them. I.e. for any paper i I have a choice and. To buy/sell a paper through the simple market (3.). To buy/sell the linear combination (3.) and gets rid of a foot which it is not necessary through the simple market (3.) (6) For example if I want to buy a paper i, the lowest price for it will be: min (O [i, ask], {S [i, j, ask] - About [j, bid] for j in range (i+1, N)}) (7) When comes the new quotation, other prices remain. That is the new quotation comes to each moment of time when to me, at me already is N quotations on papers and 0.5*N^2 - N quotations on their linear combinations (8) My task as fast as possible to count ceiling prices of sale and floor prices of purchase of all N papers.

4

Re: Combinatorics (from three fingers)

Hello, negres, you wrote: N> (1) At a stock exchange bargain N securities,  [0] to  [N]. We admit them at us 10 , i.e. N = 10. Pieces = N+1 N> (2) Me everyone to steam of microseconds come quotations on these papers. For the sake of simplicity we will consider that they come randomly and never come simultaneously As long  it is considered ? N> (3) These quotations happen in two forms: N> and. The quotation on itself papers in the form of O [i, bid, ask] N>. The quotation on the linear difference between two papers X (i) - X (j), too in the form of S [i, j, bid, ask] (i <j always) N> where i (and j if is present) - decent paper numbers, bid - the price on which it is possible to sell, ask - the price on which it is possible to buy O [i, bid, ask] is the price of i th paper. As it is connected with bid and ask. And for what bid and ask N> (5) These max bid/min ask the prices can be formed both of quotations on papers and from the linear combinations on them. I.e. For any paper i I have choice N> and. To buy/sell a paper through the simple market (3.) N>. To buy/sell the linear combination (3.) and gets rid of a foot which it is not necessary through the simple market (3.) What criterion of an unnecessary foot? N> (6) for example if I want to buy a paper i, the lowest price for it will be: N> min (O [i, ask], {S [i, j, ask] - About [j, bid] for j in range (i+1, N)}) do not hurry up  more in detail min (O [i, {bid}, ask], {S [i, j, {bid}, ask] - About [j, bid, {ask}] for j in range (i+1, N)})

5

Re: Combinatorics (from three fingers)

6

Re: Combinatorics (from three fingers)

7

Re: Combinatorics (from three fingers)

Hello, kov_serg, you wrote: _> Hello, negres, you wrote: _> If I correctly understood for k we search: _> _> opt=min (X [k], S [k, r] +X [r]) for k <r <N _> Yes, correctly, only there can be two linear combinations: opt=min (X [k], S [k, r] +X [r], X [r]-S [r, k]) for k <r <N _> It will be possible to use a heap with which to know a minimum element at any moment. Not, sense has - N no maximum 10. T.e. The code is already written by my former colleague, I simply want to lower an amount of passes for each update (as a part of the general attempt basically to lower w2w latency). My thoughts while  first of all to break on two different operations: - update on S [i, j] causes only update X [i] and X [j] (since Only they depend on it) - update on X [i] causes already update of the price X [i] plus of the prices which from it depend through S [i, k] [code]//bid side only - ask will be symmetrical if (q.type == SPD) {S [i, j] = q.bid B [i] = max (B [i], S [i, j] + X [j]); B [j] = max (B [j], X [i] - S [i, j]);} else {X [i] = q.bid B [i] = max (B [i], X [i]); for (k=0; k <N; k ++) if (k (i) B [k] = max (B [k], S [k, i] + X [i]); if (k> i) B [k] = max (B [k], X [i] - S [i, k]);} [code] B.Poprobovat standard tricks - instead of vectors simply arrays on N or NxN ( in compile time), in the program all prices to store as int and other LL-magic.