Skip to content

Binomial: Faster sampling for n * p >= 10 #740

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
dhardy merged 7 commits into from
Apr 1, 2019
Merged

Binomial: Faster sampling for n * p >= 10 #740

dhardy merged 7 commits into from
Apr 1, 2019

Conversation

@vks
Copy link
Collaborator

@vks vks commented Feb 21, 2019

Before:

test misc_binomial_1      ... bench:          13 ns/iter (+/- 0)
test misc_binomial_10     ... bench:          69 ns/iter (+/- 2)
test misc_binomial_100    ... bench:          70 ns/iter (+/- 2)
test misc_binomial_1000   ... bench:         599 ns/iter (+/- 9)
test misc_binomial_1e12   ... bench:         660 ns/iter (+/- 15)

After:

test misc_binomial_1      ... bench:          13 ns/iter (+/- 1)
test misc_binomial_10     ... bench:          70 ns/iter (+/- 10)
test misc_binomial_100    ... bench:          74 ns/iter (+/- 5)
test misc_binomial_1000   ... bench:         136 ns/iter (+/- 3)
test misc_binomial_1e12   ... bench:          57 ns/iter (+/- 3)

This requires #735.

@vks vks changed the title Binomial: Faster sampling for N * p > 10 Binomial: Faster sampling for n * p > 10 Feb 21, 2019
@vks vks changed the title Binomial: Faster sampling for n * p > 10 Binomial: Faster sampling for n * p >= 10 Feb 21, 2019
@vks
Copy link
Collaborator Author

vks commented Feb 21, 2019

cc @geq1t

@dhardy
Copy link
Member

dhardy commented Feb 22, 2019

Great. I will hold off merging this until after #735.

@geq1t
Copy link

geq1t commented Feb 26, 2019

I don't really have a say in this, but from what I've seen BTPE is a very fast algorithm for binomial sampling, so implementing it would almost certainly be a win. I'll see if I can get a copy of the paper to compare against.

@dhardy
Copy link
Member

dhardy commented Feb 27, 2019

Rebase please

@vks vks force-pushed the faster-binomial2 branch from bf96f64 to e5d8c2c Compare February 28, 2019 11:28
@vks
Copy link
Collaborator Author

vks commented Feb 28, 2019

I rebased on master.

@vks vks force-pushed the faster-binomial2 branch from e5d8c2c to a40b52d Compare March 13, 2019 18:16
@vks
Copy link
Collaborator Author

vks commented Mar 13, 2019

Rebased again. This includes the fix for MIPS.

@dhardy
Copy link
Member

dhardy commented Mar 14, 2019

Ah, sorry, I'll try to get to reviewing this this week.

dhardy
dhardy reviewed Mar 22, 2019
View reviewed changes
Copy link
Member

@dhardy dhardy left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The implementation appears to correspond to the algorithm in the K&S paper except where mentioned (apparently an error in the paper).

Why do you think some parts of the algorithm should be carried out with integers? It seems to me better to stick with floats until the result is ready.

vks added 7 commits March 29, 2019 14:23
@vks
Implement the BTPE for binomial sampling
daa02bd 
This should be more efficient than our previous algorithm, see [1].
The implementation is close to the algorithm as specified in the paper,
where many goto statements are used. It can still be refactored to be
more readable.

[1] Voratas Kachitvichyanukul and Bruce W. Schmeiser. 1988. Binomial
    random variate generation. Commun. ACM 31, 2 (February 1988),
    216-222. http://dx.doi.org/10.1145/42372.42381
@vks
Binomial test: Better output on error
4333a77
@vks
Binomial: Simplify code
cd822a0
@vks
Binomial: Eliminate some common subexpressions
f9cae57
@vks
Binomial: Use correct sign for stirling correction
f6d7407 
This was noted by the GSL implementors. The new signs were confirmed by
one of the authors publishing the original algorithm.
@vks
Binomial: Comment on difference to original algorithm
6e82023
@vks
Binomial: Move distribution initialization out of loop
f8149ab
@vks vks force-pushed the faster-binomial2 branch from a40b52d to f8149ab Compare March 29, 2019 14:50
@dhardy dhardy merged commit e47c5a9 into rust-random:master Apr 1, 2019
@vks vks deleted the faster-binomial2 branch April 1, 2019 14:24
@vks vks mentioned this pull request May 15, 2019
Merged
vks added a commit to vks/rand that referenced this pull request May 15, 2019
@vks
rand_distr: Update binomial distribution implementation
664dad2 
When moving the distribution from `rand` to `rand_distr`, the changes
from rust-random#740 were missed. This commit adds those changes.
@vks vks mentioned this pull request May 15, 2019
Merged
benjamin-lieser pushed a commit to benjamin-lieser/rand that referenced this pull request Feb 5, 2025
@vks
rand_distr: Update binomial distribution implementation
dff4420 
When moving the distribution from `rand` to `rand_distr`, the changes
from rust-random#740 were missed. This commit adds those changes.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@dhardy dhardy dhardy approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@vks @dhardy @geq1t