martok
|
|
April 23, 2011, 11:26:07 PM |
|
Hmm actually I just overflowed PostGreSQL's numeric format which is the best Postgres can do. Is there any way to make these numbers a bit more reasonably sized?
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
April 24, 2011, 04:38:40 AM Last edit: April 24, 2011, 05:12:18 AM by Holy-Fire |
|
Hmm actually I just overflowed PostGreSQL's numeric format which is the best Postgres can do. Is there any way to make these numbers a bit more reasonably sized?
Yes, there are at least two ways: 1. Periodical rescaling - once in a while (say, 100000 shares) go over all participants and divide their score by s, and reset s to 1. If you are able to do this after every share, you'll also get a more visually pleasant representation of the score. I assume that underflow simply results in 0. 2. Working on a logarithmic scale: Instead of keeping s and the score of each participant, keep their logs. Of course you'll need to adapt all calculations to the new scale, in particular you should use a robust method for addition: logadd (a,b) { M = max(a,b); return M + log ( exp(a-M) + exp(b-M) ); }
By the way, since it is only capability to work with large numbers that you need and not precision, you can safely use double (or single) precision with these modifications.
|
|
|
|
martok
|
|
April 24, 2011, 07:46:51 AM |
|
Hi,
I don't understand log scale well enough to implement that. Do you just set s to ln(r) as a base then increment s by logadd(s, r)?
However, rescaling did work quite well for getting new scores in but it does have the problem that as pools get faster and faster, rescale will have to occur more and more often.
The payment calculation breaks though. I am using: s = user score i = total number of shares submitted by everyone in the round select (1-f)*b*s*(r-1)/r^i That gives overflow because i is currently 82000 and r is 1.0108... so that result goes well outside double precision (r^i).
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
April 24, 2011, 12:10:53 PM Last edit: April 24, 2011, 01:14:19 PM by Holy-Fire |
|
Hi,
I don't understand log scale well enough to implement that. Do you just set s to ln(r) as a base then increment s by logadd(s, r)?
However, rescaling did work quite well for getting new scores in but it does have the problem that as pools get faster and faster, rescale will have to occur more and more often.
The payment calculation breaks though. I am using: s = user score i = total number of shares submitted by everyone in the round select (1-f)*b*s*(r-1)/r^i That gives overflow because i is currently 82000 and r is 1.0108... so that result goes well outside double precision (r^i).
Sorry, I should have clarified that the formula (1-f)*B*S*(r-1)/r^I (which is basically using the summation formula for geometric progressions to evaluate the total score) is valid only for the vanilla method as in the original post. Any changes (adjusting for difficulty changes, rescaling to prevent overflow) require rewriting the formula, and to avoid this complication it's best to not use a formula and just go over the scores of operator and all participants and sum them manually. Then split the (1-f)*B reward between everyone in proportion to their score divided by the total score. Don't forget that rescaling should be done for the operator's score as well. I could explain more about logarithmic scale, but if it's not intuitive to you it's best to use periodic rescaling instead. Maybe we'll revisit it when there's a real need (say, the rescaling becomes too resource-demanding).
|
|
|
|
martok
|
|
May 19, 2011, 12:16:18 AM |
|
Hi,
So here is my implementation used on the Continuum pool. Feel free to suggest improvements or things I overlooked. I am particularly interested in how this can be done without periodic rescaling as in moving to a hosted database server, I will have much less CPU power.
So we have round table as: id int, (f,c,b) double, os double ; operator score
share table id time worker round_id int references round(id) score double
The score is that assigned for the particular share and not the cumulative score. For that, select sum(score) from share where worker=x and round_id=y
The scoring function is written as a PostgreSQL insert trigger which fires on an insert on share: CREATE OR REPLACE FUNCTION share_score() RETURNS trigger AS $$ DECLARE rd round%rowtype; d double precision; p double precision; r double precision; s double precision; BEGIN d := difficulty from difficulty order by time desc limit 1; p := 1.0/d; select * into rd from round order by id desc limit 1; if rd is null then -- First round insert into round default values; select * into rd from round order by id desc limit 1; r := 1.0-p+p/rd.c; update round set os=1/(r-1) where id=rd.id; s := 1; else r := 1.0-p+p/rd.c; -- Get the last score s := score*r from share where round_id = rd.id and score is not null order by id desc limit 1; if s is null then -- first insert in this round s := 1; end if; end if; NEW.round_id := rd.id; if NEW.our_result = 'f' then return NEW; end if; -- Check for any needed rescaling if s > 1e+200 then update share set score=score/s where round_id=rd.id; update round set os=os/s where id=rd.id; s := 1; end if; NEW.score := s; RETURN NEW; END; $$ LANGUAGE plpgsql;
Then we have worker_payments function which takes round_id and returns a composit of varchar,numeric CREATE OR REPLACE FUNCTION worker_payments(rnd_id integer) RETURNS table( worker text, cr double precision) AS $$ DECLARE rd round%rowtype; totscore double precision; BEGIN select * into rd from round where id=rnd_id; totscore := sum(score)+rd.os from share where round_id = rd.id; RETURN QUERY select share.worker, (1-rd.f)*rd.b*sum(score)/totscore from share where round_id = rd.id and score is not null group by share.worker; RETURN; END; $$ LANGUAGE plpgsql stable;
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
May 26, 2011, 03:37:53 PM Last edit: May 29, 2011, 09:08:40 AM by Meni Rosenfeld |
|
Ok, I think I know just enough SQL to be able to translate this to logarithmic scale, obviating the need for periodic rescaling. I am assuming log and exp return the natural logarithm and exponentiation. You will of course need to check I didn't mess anything up and test it thoroughly. Note that keeping lr in cache will remove the need to calculate it for each share, and that the summation function in round end is somewhat heavier. Note also that the first function now returns the log of the score. Here is the code, I have also renamed os and score to los and lscore, and bolded the lines I changed.
CREATE OR REPLACE FUNCTION share_score() RETURNS trigger AS $$ DECLARE rd round%rowtype; d double precision; p double precision; lr double precision; ls double precision; BEGIN d := difficulty from difficulty order by time desc limit 1; p := 1.0/d; select * into rd from round order by id desc limit 1; if rd is null then -- First round insert into round default values; select * into rd from round order by id desc limit 1; lr := log(1.0-p+p/rd.c); update round set los=log(1/(exp(lr)-1)) where id=rd.id; ls := 0; else lr := log(1.0-p+p/rd.c); -- Get the last score ls := lscore+lr from share where round_id = rd.id and lscore is not null order by id desc limit 1; if ls is null then -- first insert in this round ls := 0; end if; end if; NEW.round_id := rd.id; if NEW.our_result = 'f' then return NEW; end if; -- No need for rescaling! NEW.lscore := ls; RETURN NEW; END; $$ LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION worker_payments(rnd_id integer) RETURNS table( worker text, cr double precision) AS $$ DECLARE rd round%rowtype; totscore double precision; max double precision; BEGIN select * into rd from round where id=rnd_id; max := lscore from share where round_id = rd.id and lscore is not null order by id desc limit 1; totscore := sum(exp(lscore-max))+exp(rd.los-max) from share where round_id = rd.id; RETURN QUERY select share.worker, (1-rd.f)*rd.b*sum(exp(lscore-max))/totscore from share where round_id = rd.id and lscore is not null group by share.worker; RETURN; END; $$ LANGUAGE plpgsql stable;
|
|
|
|
martok
|
|
May 26, 2011, 03:58:17 PM Last edit: May 26, 2011, 05:11:50 PM by martok |
|
Wow thanks very much. I'll adapt this and see how it works. Does the procedure differ from previous when the difficulty changes or do you just proceed with the new p?
Also, isn't: totscore := sum(exp(lscore-max))+exp(rd.los-max) from share likely to overflow any umeric types in PGSQL in the round calculation? I suppose I could just write that function using an arbitrary precision library...
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
May 26, 2011, 06:31:35 PM |
|
Wow thanks very much. I'll adapt this and see how it works. Does the procedure differ from previous when the difficulty changes or do you just proceed with the new p?
Actually, just moments ago I thought about this again and realized your code doesn't contain the part of updating on difficulty change. Is that on purpose? There is a simple way to implement this, and with a simple tweak it will work for logarithmic scale. Also, isn't: totscore := sum(exp(lscore-max))+exp(rd.los-max) from share likely to overflow any umeric types in PGSQL in the round calculation? I suppose I could just write that function using an arbitrary precision library...
No, that's the magic of the -max part. max can't be much smaller than lscore and los, so the exps won't overflow. They can underflow, but I'm assuming in this case they just return 0 which is ok. Oh, and I missed two places where score should be replaced with lscore, fixed now.
|
|
|
|
martok
|
|
May 26, 2011, 08:39:34 PM Last edit: May 26, 2011, 09:18:21 PM by martok |
|
My difficulty adjustment code is not written as a PLPGSQL function but is done in a cron script written in perl. It looks like: p1 = 1/od p2 = 1/nd update share set score=score*(p2/p1) update round set os=os*(p2/p1)
Simple stuff. From looking at your log code, would we just do: update share set score=ln(exp((max-score)*(p2/p1)))?
I don't pretend to understand this stuff yet but that's my wild guess at this point.
|
|
|
|
martok
|
|
May 26, 2011, 10:49:08 PM |
|
Hi,
Another question regarding logging method. Is there a way I can cache totalscore. A balance check is a very common one for users to perform and scanning over share for sum(exp(s-m)) is taking too long. In the exponential method, I was able to keep a totalscore in cache and as a new share came in (totalscore += newscore). It doesn't look that simple with this method since max changes, all of the previous exp(s-max) will also be different.
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
May 27, 2011, 12:51:27 PM |
|
My difficulty adjustment code is not written as a PLPGSQL function but is done in a cron script written in perl. It looks like: p1 = 1/od p2 = 1/nd update share set score=score*(p2/p1) update round set os=os*(p2/p1)
Ouch, you've done this wrong. In my specification I meant that the scores for existing shares will remain the same, while the variable s that specifies what will be the score for new shares decreases (multiplied by p2/p1). Equivalently, since it's all relative, you could fix s and multiply all scores by p1/p2. But what you've done has two problems: 1. You've multiplied existing scores by p2/p1 instead of p1/p2. 2. Since you don't keep s as a separate variable but rather read it from the shares table, you have scaled both the existing shares and the new shares, so the difficulty fix will actually have no effect whatsoever. Basically what you want is that the score for the first share submitted after the difficulty change will be multiplied by p2/p1. Then proceed as normal, each share will reference the last one and it will be ok. I don't know what's the DB-friendly way to do that. Once you show me your solution, I'll adapt it to log scale. Hi,
Another question regarding logging method. Is there a way I can cache totalscore. A balance check is a very common one for users to perform and scanning over share for sum(exp(s-m)) is taking too long. In the exponential method, I was able to keep a totalscore in cache and as a new share came in (totalscore += newscore). It doesn't look that simple with this method since max changes, all of the previous exp(s-max) will also be different.
It's quite simple. Note that the value chosen for max is not important, it just needs to be comparable to the highest lscore value and be used consistently. Keep a value ltotalscore which will represent the logarithm of the total score. Initialize it to los. When a new share is submitted, let ltotalscore += log (1+exp(lscore-ltotalscore)). Now, if at any point you want to find the balance of a worker, you do select (1-rd.f)*rd.b*sum(exp(lscore-ltotalscore)) from share where round_id = rd.id and lscore is not null and worker = worker_id; I assume you want to find the balance mid-round? The above will give you what would be the reward if the round ended now. I think it will be more useful to know what is the expected reward. This requires a small tweak, let me know if you are interested in it.
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
May 27, 2011, 02:13:24 PM |
|
I have added a correctness proof outline to the OP.
|
|
|
|
martok
|
|
May 27, 2011, 06:58:07 PM Last edit: May 27, 2011, 07:59:24 PM by martok |
|
Ouch, you've done this wrong. In my specification I meant that the scores for existing shares will remain the same, while the variable s that specifies what will be the score for new shares decreases (multiplied by p2/p1). Equivalently, since it's all relative, you could fix s and multiply all scores by p1/p2. But what you've done has two problems: 1. You've multiplied existing scores by p2/p1 instead of p1/p2. 2. Since you don't keep s as a separate variable but rather read it from the shares table, you have scaled both the existing shares and the new shares, so the difficulty fix will actually have no effect whatsoever. Basically what you want is that the score for the first share submitted after the difficulty change will be multiplied by p2/p1. Then proceed as normal, each share will reference the last one and it will be ok. I don't know what's the DB-friendly way to do that.
Once you show me your solution, I'll adapt it to log scale.
Ok, I've refactored the PLPG functions. Now storing r and lastscore in round tbl so difficulty change can just update round set lastscore=lastscore*(p2/p1) and the next insert should do the right thing.
|
|
|
|
martok
|
|
May 27, 2011, 07:01:12 PM |
|
I assume you want to find the balance mid-round? The above will give you what would be the reward if the round ended now. I think it will be more useful to know what is the expected reward. This requires a small tweak, let me know if you are interested in it.
Sure, that would probably be a more useful measure.
|
|
|
|
marcus_of_augustus
Legendary
Offline
Activity: 3920
Merit: 2349
Eadem mutata resurgo
|
|
May 27, 2011, 10:55:58 PM |
|
Don't want to butt in here guys but how does this bit work? update share set score=ln(exp((max-score)*(p2/p1)))?
Isn't that like doing sin(asin(f(x))) or a cos(acos(X)) ... or is it to round the numerical approximation off or some such?
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
May 28, 2011, 07:13:33 PM |
|
Don't want to butt in here guys but how does this bit work? update share set score=ln(exp((max-score)*(p2/p1)))?
This bit doesn't work (note that martok only asked if it would work). I will soon supply the correct formula. Isn't that like doing sin(asin(f(x))) or a cos(acos(X))
It is. ... or is it to round the numerical approximation off or some such?
It can have a numerical effect, but only for the worse. It can introduce a small error, and if the exp over/under flows you have a problem.
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
May 29, 2011, 07:20:02 PM |
|
Ouch, you've done this wrong. In my specification I meant that the scores for existing shares will remain the same, while the variable s that specifies what will be the score for new shares decreases (multiplied by p2/p1). Equivalently, since it's all relative, you could fix s and multiply all scores by p1/p2. But what you've done has two problems: 1. You've multiplied existing scores by p2/p1 instead of p1/p2. 2. Since you don't keep s as a separate variable but rather read it from the shares table, you have scaled both the existing shares and the new shares, so the difficulty fix will actually have no effect whatsoever. Basically what you want is that the score for the first share submitted after the difficulty change will be multiplied by p2/p1. Then proceed as normal, each share will reference the last one and it will be ok. I don't know what's the DB-friendly way to do that.
Once you show me your solution, I'll adapt it to log scale.
Ok, I've refactored the PLPG functions. Now storing r and lastscore in round tbl so difficulty change can just update round set lastscore=lastscore*(p2/p1) and the next insert should do the right thing. Good. To convert to log scale: 1. Instead of storing r and lastscore, store lr = log(r) and lastlscore = the lscore of the last submitted share. 2. On difficulty change, update round set lastlscore=lastlscore+log(p2/p1). I assume you want to find the balance mid-round? The above will give you what would be the reward if the round ended now. I think it will be more useful to know what is the expected reward. This requires a small tweak, let me know if you are interested in it.
Sure, that would probably be a more useful measure. In fact it's arguably even simpler. For this you don't need to keep ltotalscore. To find the expected payout of a worker for the current round, do select (1-rd.f)*(1-rd.c)*p*rd.b*sum(exp(lscore-lastlscore)) p should be calculated based on the current difficulty.
|
|
|
|
Craig
Newbie
Offline
Activity: 15
Merit: 0
|
|
May 30, 2011, 01:26:47 PM |
|
To understand the algorithm better, I tried to translate the SQL code from this thread into a more general pseudocode format. I decided to post it here in case it helps anyone else to understand how the scoring algorithm works. Note that it does not include the difficulty adjustment calculation as recently discussed. let f := <initial fixed fee, as portion of total payout> let c := <initial variable fee, as portion of total payout> let b := 50 // total block payout
add_share: let d := most recent difficulty let p := 1.0 / d
if first round: let lr := log(1.0 - p + p / c) let ls := 0 create round: round.los := log(1 / (exp(lr) - 1)) round.f := f round.c := c round.b := b
else with latest round: let lr := log(1.0 - p + p / round.c) if first share: let ls := 0 else with latest share: let ls := share.lscore + lr
create share: share.lscore := ls
calculate_payout: let round := most recent round
with latest share: let max := share.lscore with all shares: let totscore := sum(exp(share.lscore - max)) + exp(round.los - max)
for share in all shares grouped by worker: let credit := (1 - round.f) * round.b * sum(exp(share.lscore - max)) / totscore
|
|
|
|
Meni Rosenfeld (OP)
Donator
Legendary
Offline
Activity: 2058
Merit: 1054
|
|
May 30, 2011, 02:36:40 PM |
|
To understand the algorithm better, I tried to translate the SQL code from this thread into a more general pseudocode format. I decided to post it here in case it helps anyone else to understand how the scoring algorithm works.
Note that it does not include the difficulty adjustment calculation as recently discussed.
Note that to help understand how the scoring algorithm works, you would need to post it in linear scale. Since you wrote it in log scale, it really serves the purpose of helping understand how to implement it in a numerically robust way.
|
|
|
|
martok
|
|
May 30, 2011, 06:12:09 PM |
|
Good. To convert to log scale: 1. Instead of storing r and lastscore, store lr = log(r) and lastlscore = the lscore of the last submitted share. 2. On difficulty change, update round set lastlscore=lastlscore+log(p2/p1).
Got it, thanks. In fact it's arguably even simpler. For this you don't need to keep ltotalscore. To find the expected payout of a worker for the current round, do
select (1-rd.f)*(1-rd.c)*p*rd.b*sum(exp(lscore-lastlscore))
p should be calculated based on the current difficulty.
Hmm, unless I am doing something wrong, this is throwing out very small expected values per worker. Much lower than the current balance calculation. < 0.001 BTC.
|
|
|
|
|