This is an archive of the discontinued LLVM Phabricator instance.

Change requirements on linear_congruential_engine
ClosedPublic

Authored by zoecarver on Jul 20 2019, 4:12 PM.

Details

Summary

This patch changes how linear_congruential_engine picks its randomization algorithm. It adds two restrictions, _OverflowOK and _SchrageOK. _OverflowOK means that m is a power of two so using the classic (a * x + c) % m will create a meaningless overflow. The second checks that Schrage's algorithm will produce results that are in bounds of min and max. This patch fixes 27839.

Diff Detail

Event Timeline

zoecarver created this revision.Jul 20 2019, 4:12 PM
zoecarver marked an inline comment as done.Jul 20 2019, 4:15 PM

I think it may be good to remove Schrage's algorithm altogether and file an LWG issue for the remaining edge cases. It is very slow and feels out of place in LCG. Additionally, Schrage's algorithm introduces lot's of added complexity and space for bugs.

libcxx/include/random
1677

This static_assert is redundant. Maybe I should remove it.

ldionne added a reviewer: Restricted Project.Nov 2 2020, 2:25 PM
ldionne added inline comments.
libcxx/include/random
1677

Can this be simplified to static_assert(!_MightOverflow || _OverflowOK || _ShrageOk, "");?

zoecarver marked an inline comment as done.Nov 3 2020, 12:42 PM
zoecarver added inline comments.
libcxx/include/random
1677

Yep :) Thanks.

zoecarver updated this revision to Diff 302667.EditedNov 3 2020, 12:51 PM
zoecarver marked an inline comment as done.
  • Rebase off master.
  • Fix static_assert (as suggested).
Herald added a project: Restricted Project. · View Herald TranscriptNov 3 2020, 12:51 PM
ldionne accepted this revision.Nov 10 2020, 6:55 AM

LGTM after fixing the nitpicks. For full disclosure, I'm relying on the tests a lot here because I am *not* a PRNG expert and I didn't take hours to research the algorithms in use. I'm trusting that you did look at other state of the art.

libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/alg.pass.cpp
69

Inconsistent indentation here.

libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/params.fail.cpp
18

Not needed.

20

Not needed.

34

Same.

This revision is now accepted and ready to land.Nov 10 2020, 6:55 AM

For full disclosure, I'm relying on the tests a lot here because I am *not* a PRNG expert and I didn't take hours to research the algorithms in use. I'm trusting that you did look at other state of the art.

Neither am I. Not sure what you mean by "state of the art." I mainly went off the discussion of the bug and various online guides. An important note: this only changes how we pick what algorithm to use, it doesn't change any of the algorithms themselves.

Anyway, I'll fix the comments and land this.