/
probability.go
executable file
·128 lines (122 loc) · 3.56 KB
/
probability.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/*
This file is part of go-palletone.
go-palletone is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
go-palletone is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with go-palletone. If not, see <http://www.gnu.org/licenses/>.
*/
/*
* @author PalletOne core developers <dev@pallet.one>
* @date 2018
*/
package algorithm
import (
"github.com/palletone/go-palletone/common"
"github.com/palletone/go-palletone/common/util"
"math/big"
)
//subUsers return the selected amount of sub-users determined from the mathematics protocol.
//expectedNum 期望数量
//weight 设置固定数值,即返回概率值*weight,返回值落在0 -- expectedNum/Total*weight之间的数值
func Selected(expectedNum uint, weight, total uint64, vrf []byte) int {
if total < 22 {
return 1 //todo test, is danger
}
hh := util.RlpHash(vrf)
h32 := hh[:common.HashLength]
//Total := 100
//weight=TokenPerUser; TotalTokenAmount = UserAmount * TokenPerUser
binomial := NewBinomial(int64(weight), int64(expectedNum), int64(total))
//binomial := NewApproxBinomial(int64(expectedNum), weight)
//binomial := &distuv.Binomial{
// N: float64(weight),
// P: float64(expectedNum) / float64(TotalTokenAmount()),
//}
// hash / 2^hashlen ∉ [ ∑0,j B(k;w,p), ∑0,j+1 B(k;w,p))
// hashBig := new(big.Int).SetBytes(vrf)
hashBig := new(big.Int).SetBytes(h32)
maxHash := new(big.Int).Exp(big.NewInt(2), big.NewInt(common.HashLength*8), nil)
hash := new(big.Rat).SetFrac(hashBig, maxHash)
var lower, upper *big.Rat
j := 0
for uint64(j) <= weight {
if upper != nil {
lower = upper
} else {
lower = binomial.CDF(int64(j))
}
upper = binomial.CDF(int64(j + 1))
//log.Infof("hash %v, lower %v , upper %v", hash.Sign(), lower.Sign(), upper.Sign())
if hash.Cmp(lower) >= 0 && hash.Cmp(upper) < 0 {
break
}
j++
}
//log.Infof("j %d", j)
if uint64(j) > weight {
j = 0
}
//j := parallelTrevels(runtime.NumCPU(), weight, hash, binomial)
return j
}
//func parallelTrevels(core int, N uint64, hash *big.Rat, binomial Binomial) int {
// var wg sync.WaitGroup
// groups := N / uint64(core)
// background, cancel := context.WithCancel(context.Background())
// resChan := make(chan int)
// notFound := make(chan struct{})
// for i := 0; i < core; i++ {
// go func(ctx context.Context, begin uint64) {
// wg.Add(1)
// defer wg.Done()
// var (
// end uint64
// upper, lower *big.Rat
// )
// if begin == uint64(core-2) {
// end = N + 1
// } else {
// end = groups * (begin + 1)
// }
// for j := groups * begin; j < end; j++ {
// select {
// case <-ctx.Done():
// return
// default:
// }
// if upper != nil {
// lower = upper
// } else {
// lower = binomial.CDF(int64(j))
// }
// upper = binomial.CDF(int64(j + 1))
// //log.Infof("hash %v, lower %v , upper %v", hash.Sign(), lower.Sign(), upper.Sign())
// if hash.Cmp(lower) >= 0 && hash.Cmp(upper) < 0 {
// resChan <- int(j)
// return
// }
// j++
// }
// return
// }(background, uint64(i))
// }
//
// go func() {
// wg.Wait()
// close(notFound)
// }()
//
// select {
// case j := <-resChan:
// cancel()
// return j
// case <-notFound:
// return 0
// }
//}