Waarom werkt uniform_int_distribution <uintmax_t> voor 62-bits nummers, maar niet voor 63 of 64-bits nummers?

I'm having difficulty understanding why this code, an attempt to use the new header in C++11, is correctly generating random numbers in [0, 2**62 - 1] but not [0, 2**63 - 1] or [0, 2**64 - 1].

#include 
#include 
#include 
#include 
#include 

static std::mt19937 engine;//Mersenne twister MT19937

void print_n_random_bits (unsigned int n);

int main (void) {
  engine.seed(time(0));
  print_n_random_bits(64);
  print_n_random_bits(63);
  print_n_random_bits(62);
  return 0;
}

void print_n_random_bits (unsigned int n)
{
  uintmax_t max;

  if (n == 8 * sizeof(uintmax_t)) {
    max = 0;
  } else {
    max = 1;
    max <<= n;
  }
  --max;

  std::uniform_int_distribution distribution(0, max);

  std::cout << n << " bits, max: " << max << std::endl;
  std::cout << distribution(engine) << std::endl;
}

Nu, een beetje meer graven onthult std: mt19937_64 , wat het juiste gedrag heeft, maar kan iemand mij uitleggen waarom iets dat werkt voor een 62-bits getal niet werkt voor een 64 bit-nummer?

Edit: Sorry, I didn't even specify the problem. The problem is that for 63 and 64 bit max values, the output is consistently a number in the range [0, 2**32 - 1], e.g.:

% ./rand                       
64 bits, max: 18446744073709551615
1803260654
63 bits, max: 9223372036854775807
3178301365
62 bits, max: 4611686018427387903
2943926730538475327

% ./rand                                
64 bits, max: 18446744073709551615
1525658116
63 bits, max: 9223372036854775807
2093351390
62 bits, max: 4611686018427387903
1513326512211312260

% ./rand                                                       
64 bits, max: 18446744073709551615
884934896
63 bits, max: 9223372036854775807
683284805
62 bits, max: 4611686018427387903
2333288494897435595

Edit 2: I'm using clang++ (Apple clang version 2.1 (tags/Apple/clang-163.7.1)) and "libc++". I can't easily test the above with GCC as my version doesn't have c++0x support.

 20
toegevoegd bewerkt
Bekeken: 33
de bron
Overweeg het misschien gewoon pech :)
toegevoegd de auteur Dani, de bron
Met GCC4.6.1 retourneren alle drie tests (62/63/64 bits) 64-bits waarden.
toegevoegd de auteur Mike Seymour, de bron
Met GCC4.5.1 retourneren alle drie tests (62/63/64 bits) 32-bits waarden. ideone.com/3GZ9S
toegevoegd de auteur interjay, de bron
Wat doet het precies dat is onverwacht? Dat wil zeggen, hoe presenteert het u precies met resultaten die afwijken van uw verwachtingen?
toegevoegd de auteur andand, de bron
En welke standaard bibliotheekimplementatie gebruikt u?
toegevoegd de auteur Fanael, de bron

2 antwoord

U hebt een fout gevonden in libc ++. Bedankt!!!

Ik heb de volgende oplossing vastgelegd voor Tip-over-romp-revisie 143104:

Index: include/algorithm
===================================================================
--- include/algorithm   (revision 143102)
+++ include/algorithm   (working copy)
@@ -2548,7 +2548,7 @@
         {
             __u = __e_() - _Engine::min();
         } while (__u >= __y0_);
-        if (__w0_ < _EDt)
+        if (__w0_ < _WDt)
             _S <<= __w0_;
         else
             _S = 0;
@@ -2561,7 +2561,7 @@
         {
             __u = __e_() - _Engine::min();
         } while (__u >= __y1_);
-        if (__w0_ < _EDt - 1)
+        if (__w0_ < _WDt - 1)
             _S <<= __w0_ + 1;
         else
             _S = 0;

Deze fix vereist geen hercompilatie van de binaire libc ++. Dylib.

23
toegevoegd
de bron
Ik weet het niet. Het algoritme is gespecificeerd in de standaardspecificatie voor independent_bits_engine.
toegevoegd de auteur Howard Hinnant, de bron
Heeft dat algoritme dat gebruikt wordt in libc ++ een bekende naam om erover te lezen?
toegevoegd de auteur Mateusz Drost, de bron
Wauw, snel werken! Bedankt Howard.
toegevoegd de auteur Qchmqs, de bron

Aangezien std :: mt19937 de 32-bits versie is, is het zeer waarschijnlijk dat het aannames maakt over welke bits wel en niet van belang zijn in de "werkruimte" bij het genereren van het volgende nummer. Dit resulteert dan in overloop bij het genereren van getallen die die laatste twee bits kunnen bevatten. Ik vermoed dat je zou merken dat de daadwerkelijke distributie niet echt uniform is met max. Aantallen hoger dan 2 ** 32 - 1 op de 32-bits motor.

0
toegevoegd
de bron
Zelfs als mt19937 32-bits getallen retourneert, mag uniform_int_distribution dan niet meerdere keren worden aangeroepen om 62/63/64-bits getallen te maken?
toegevoegd de auteur interjay, de bron
Ik weet het niet zeker. Korte onderzoeken suggereren dat de verdeling uniform is of zo dichtbij als verdoemd met max van 2 ** 62 - 1 , op basis van 1.000.000 gegenereerde gehele getallen.
toegevoegd de auteur Qchmqs, de bron