| Issue |
53361
|
| Summary |
linear_congruential_engine::discard() could be faster
|
| Labels |
enhancement,
libc++
|
| Assignees |
|
| Reporter |
Quuxplusone
|
This all started when I was looking at [LWG3561 "Internal counter overflow in `discard_block_engine`."](https://cplusplus.github.io/LWG/issue3561) The issue description includes a test program for the "problematic use case" ([Godbolt](https://godbolt.org/z/s6M8rTddr)); the test program calls `g.discard(size_t(INT_MAX) + 5)`. With our implementation of `linear_congruential_engine::discard`, this simply loops `INT_MAX + 5` times, which takes inordinately long.
According to ["Fast skipping in a linear congruential generator"](https://www.nayuki.io/page/fast-skipping-in-a-linear-congruential-generator), it would be possible to reimplement `linear_congruential_engine::discard` to take O(lg n) time instead of O(n) time. That could be pretty cool.
Neither libstdc++ nor MSVC bother with this optimization either, so it's not like we're alone in this. But if we want to fix LWG3561 (which ultimately I assume we do), then we might _need_ to make `.discard(INT_MAX + 5)` fast enough to put in a unit test.
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
