<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=http://email.email.llvm.org/c/eJylVNuO2zYQ_Rr5ZWBBliyv_aAHb4INFuimKLpo-mZQ5FhiTJMCL1F2v74zkr2XIgFaBJAsiWPOnDnnDFunnprHXgcQxkCIwkdUMPZo4R5GEcA4d9K2AxEhq29_-_KpqjcryMry3kb0VhiQLvEruG_oj8aNoC1km0LpIIVXh9Y4eTqg7bRFWs5pa1Z_zMptH-MQsmqflXd0ycGkwHfe6dinNteOVqke_eoQEnLdrNzBY48wLYDCIL0eonaWakqTaAEERAwRBu86L85wdB4i7aCqtNQaPIuoJaSAIEVAWqbQljr75FTrTPwRtG4O5c539PVMd9g8bP2jUp4A8VXdTkXeVZZEaGAiuvxCBSUO-hkPkV7uPz8eHvZ_c0NZeQs1ZyFy4As1Dy550OeBwKKNYurPHTmVIQ6FP0hnO58opoW5Mktgq_210KbIyg8EiWQNnOiJZRwmNJfCl6qbAqI-Y-C_j72WPURxIha1dV5pKyJOe22XZ8XHrNjPv3spp3AH0bEriMU7Qa2Hkx4GXiYHCJjBwluw0KFFL6LzP3HBOI65FU_ppGf9B9GRRndHyr68Zl9quxTLOfvybfblm-w77khHGF0yClqEwYWgSX-G7PGF3f_HKm9mguB3Qm46sKwfE0gdh4hCsU4cewnk5FcaHfkCw2OMT_TtzDtKPyMJT0NkdBuikqQOC0QqwMOff32A1k3Rkd0xyerI9mf9PJtj3ssdB0dNZ-VNoK2RkhHUkQi88Ujz7SzjnPbncJsi6CNFacqJBmrsqL_D63xvZzskQ3VmG9yDoLE7c0ZQ7kJx5JOCFs666yMcLKI6cLIzs8SOfvX-e-dNfgcWFtC61PW8a2BQ7J1kSTsep3yhmkrtqp1YiBR755s_UvrO5wR1s0jeNP-a1fnwkO5MH8Z8uz6WNJZfUcbraUKOv6urarNa9JR_W21xVR6r1boVoqyEwDWq9Vrd3KhiiwsjWjShmZ2OthdWTuZhExMH9CDZLprNxl78Oi7dlEVZFquyXO2Kol7nhazFUZatqnbrXVvX2bqg00ybnPPw4bTwzZSyTV2goNEhhtcgiac70mdqgxBGHQ02_9X7dEaSo19szLqhX0yQmwnvPwL-E3o>53361</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            linear_congruential_engine::discard() could be faster
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            enhancement,
            libc++
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          Quuxplusone
      </td>
    </tr>
</table>

<pre>
    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.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyVVNuOozgQ_RryUgoiEJLwwEN6Wt1qaXpGq23tzFtkbAPeGBv5Mkz3128VJH1Z7UizEgRwxVWnzjnlxorn-qlXHpjW4ANzQQqYemngASbmQVt7VqYDFiApbz5_uy_K3QaSPH8wQTrDNHAb6RXsD-labSdQBpJdJpTnzIlToy0_n6TplJG4nOLWpLxN8kMfwuiT4pjkd3jxUUdPd9qp0McmVRZXsR7-Ku-jpLpJXsFTL2FeACE9d2oMyhqsyXXEBWAQpA8wOts5NkBrHQTcgVVxqdFyYEFxiF4CZ17iMoYO2Nm9FY3V4b-gdUsota7Drxe8_e7x4J6EcAiIruJmLvKhMkdCPRHRpRcqMLFXL_IU8OXhy9Pp8fidGkryGygpC5ID37B5sNGBGkYEK01gc3-2pVQaOWTuxK3pXMSYYvrKLIItjtdCuyzJPyEklNVTomeScZzRXApfqu4yCGqQnv4-9Yr3ENgZWVTGOqEMC3Lea7o0yW6T7Lj8Hjmfwx0ES65AFu8Ytu7PahxpGR3AYAEL78FCJ410LFj3CxdM05Qa9hzPatF_ZB1qdNdi9vU1-1qZNVsv2dfvs6_fZa-oIxVgslELaCSM1nuF-hNkJ1_Z_X-s0mYiCL4ict2BIf2IQOzYB8kE6USx10CKfsXR4a8wnAzhGb-t_kDpF4nC4xBp1fggOKpDAqEK8PjnX5-gsXN0InfMslq0_aBeFnMse6ljb7HpJN973BowGUKdkMC9kzjf1hDOeX8KNzGAajGKU440YGOt-glv831Y7BA11lls8AAMx26gjCDsheJAJwUuDKrrA5yMlOJEyQZiiRz95v2Pzpv9DiQsSGNj19OukUCRd6JB7Wic0pWoC1EVFVsFFbSsf1csHGqU4JV3KiTdKjpd_2u4l9OG2wE_tP5xfaxxjv-WPFyPHxyRu7IodptVX5dbWYrNtmQ7sW_bXSX3nG9kVRb7KmubQ7bSrJHa18toSNMzw2e3keuRNHygzheRl0lYqTrP8jzb5PmmyrJym2a8ZC3PG1FU26opy2Sb4eGldEro6CxauXoG2sTOY1ArH_xbELVSHcoxg8D8LIbeuvqPGH_SKYteWM191XNT_wAEvf25">