classification
Title: random.vonmisesvariate() hangs for large kappa
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.4, Python 3.2, Python 3.3, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: mark.dickinson, python-dev, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2013-02-06 12:38 by serhiy.storchaka, last changed 2013-02-10 17:34 by serhiy.storchaka. This issue is now closed.

Files
File name Uploaded Description Edit
random_vonmisesvariate.diff serhiy.storchaka, 2013-02-07 11:42 review
random_vonmisesvariate_2.patch serhiy.storchaka, 2013-02-10 15:01 review
Messages (8)
msg181511 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-06 12:38
random.vonmisesvariate(0, 1e16) hangs.
msg181593 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-07 11:42
Here is an implementation which is more precise for small and large kappa, doesn't hang for large kappa, and even a little faster. It is mathematically totally equivalent to existing, but use more accurate calculations.
msg181785 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-02-10 11:17
Looks good to me.  I can confirm that the new formulas are equivalent to the old, at least for positive kappa.  (They're not the same for negative kappa, but that shouldn't matter in this context.)

Serhiy: do you know how the original formulas arose?  I don't have access to the "circular data" book, or to the original Best & Fisher paper, but that use of b in the original code is just plain peculiar;  I wonder why on earth anyone would want to go about computing  `a / (2 kappa)` that way.

I'd suggest leaving off the `u3 > 0.5` to `u3 >= 0.5` change for this particular issue;  I understand the motivation for the change, but it's unrelated to this issue, and seems like unnecessary code churn to me.

A test would be good!
msg181810 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-10 15:01
> Serhiy: do you know how the original formulas arose? 

No. I have not found any articles or books in the open access.

> A test would be good!

I was waiting for issue13355 and issue17149. Here is an updated patch with 
tests.
msg181818 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-02-10 16:35
I don't think the second added test_avg_std test makes sense, given that the number of random samples used by vonmisesvariate is unpredictable.  The variance in the second case should be close to 1/100.0 rather than 1/sqrt(2)/100.0, right?  If this code stays, there should at least be a comment explaining where the extra sqrt(2) comes from.

Apart from that, this patch looks good to me.
msg181819 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-10 17:19
> The variance in the second case should be close to 1/100.0 rather than 1/sqrt(2)/100.0, right?

Yes, but experiments exposed precisely 1/sqrt(2)/100.0 and I were confused by this fact. But now I noticed a comment at the top of the test: "Only works for distributions which do not consume variates in pairs". This test is not applicable to vonmisesvariate() which consumes more than one variate. u1, u2 and u3 are not independent.
msg181820 - (view) Author: Roundup Robot (python-dev) Date: 2013-02-10 17:32
New changeset 0f9113e1b541 by Serhiy Storchaka in branch '2.7':
Issue #17141: random.vonmisesvariate() no more hangs for large kappas.
http://hg.python.org/cpython/rev/0f9113e1b541

New changeset d94b73c95646 by Serhiy Storchaka in branch '3.2':
Issue #17141: random.vonmisesvariate() no more hangs for large kappas.
http://hg.python.org/cpython/rev/d94b73c95646

New changeset bdd993847ad0 by Serhiy Storchaka in branch '3.3':
Issue #17141: random.vonmisesvariate() no more hangs for large kappas.
http://hg.python.org/cpython/rev/bdd993847ad0

New changeset 407625051c45 by Serhiy Storchaka in branch 'default':
Issue #17141: random.vonmisesvariate() no more hangs for large kappas.
http://hg.python.org/cpython/rev/407625051c45
msg181821 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-10 17:34
Thanks for review.
History
Date User Action Args
2013-02-10 17:34:36serhiy.storchakasetmessages: + msg181821
2013-02-10 17:34:17serhiy.storchakasetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2013-02-10 17:32:44python-devsetnosy: + python-dev
messages: + msg181820
2013-02-10 17:19:37serhiy.storchakasetmessages: + msg181819
2013-02-10 16:35:29mark.dickinsonsetmessages: + msg181818
2013-02-10 15:01:54serhiy.storchakasetfiles: + random_vonmisesvariate_2.patch

messages: + msg181810
2013-02-10 11:17:27mark.dickinsonsetmessages: + msg181785
2013-02-07 11:43:01serhiy.storchakasetstage: needs patch -> patch review
2013-02-07 11:42:48serhiy.storchakasetfiles: + random_vonmisesvariate.diff
keywords: + patch
messages: + msg181593
2013-02-06 15:12:53mark.dickinsonsetnosy: + mark.dickinson
2013-02-06 12:38:01serhiy.storchakacreate