n-bitige Zufallszahl generieren fuer bitset mit n>1000



  • Hi Forum,

    ich arbeite gerade mit dem dynamic_biset aus der boost library, die bisets in meinem Program koennen sehr gross sein (ab 1000 bit aufwaerts) ich muss nun die bitsets mit zufaelligen Werten fuellen. Wie kann ich nun 1000 bitige oder groessere Zufallszahlen generieren. Was ist der schnellste Weg das zu tun. Da ich Boost verwende kann ich auch den Random Generator daraus benutzten aber die Zahlen gehen nur bis 2^32.

    Beim dynamic_biset kann man auch einen String zu initialisierung nutzen, ich habe ueberlegt einen "n" Zeichen langen string zu generieren und dann random_shufle zu nuten aber das ist mir zu langsam.

    Das Zahlen generieren sollte moeglichst schnell gehen.
    Wie kann man das machen?



  • Erstell das bitset doch leer und geh mit einer Schleife drüber und setz die einzelnen Bits mit rand() % 2 ?



  • Evtl. erst ein dynamic_bitset zufällig erzeugen und dann kopieren/zuweisen?

    #include <algorithm>
    #include <cstdint>
    #include <functional>
    #include <iostream>
    #include <iterator>
    #include <random>
    
    #include <boost/dynamic_bitset.hpp>
    
    boost::dynamic_bitset<> generate(size_t n){
      using namespace std;
      typedef uint64_t Block_type;
      static default_random_engine rng;
      static uniform_int_distribution<Block_type> d;
      Block_type arr[32];
      auto gen = bind(d, rng);
      generate(begin(arr), end(arr), gen);
      boost::dynamic_bitset<> ret(begin(arr), end(arr));
      if (n != 2048)   // 64 * 32 = 2048
        ret.resize(n);
      return ret;
    }
    
    int main(){
      boost::dynamic_bitset<> b = generate(5);
      std::cout << "5: " << b << '\n';
      b = generate(1024);
      std::cout << "1024: " << b << '\n';
      b = generate(2048);
      std::cout << "2048: " << b << '\n'; 
    }
    


  • Das scheint eine sehr gute Loesung zu sein. Aber aus irgendeinem Grund gibt generate immer nur ein 1024 bit grosses bitset zurueck.



  • MeckiDerIgel schrieb:

    Das scheint eine sehr gute Loesung zu sein. Aber aus irgendeinem Grund gibt generate immer nur ein 1024 bit grosses bitset zurueck.

    "sehr gut" ist in diesem Fall vielleicht etwas viel... 🙂

    Wahrscheinlich bist du/ist Dein dynamic_bitset 32bittig unterwegs.
    Sauber wäre wohl, dynamic_bitset::block_type statt uint64_t zu verwenden. Und dann anhand bits_per_block die notwendige Arraygröße zu bestimmen, um auf die Bitanzahl zu kommen.

    boost::dynamic_bitset<> generate(int n){
      using namespace std;
      typedef boost::dynamic_bitset<>   bitset_type;
      typedef bitset_type::block_type   block_type;
      const int bpb  = bitset_type::bits_per_block;
      const int size = 2048;
      block_type arr[size%bpb ? size/bpb+1 : size/bpb];
      static default_random_engine rng;
      static uniform_int_distribution<block_type> d;
    
      auto gen = bind(d, rng);
      generate(begin(arr), end(arr), gen);
      bitset_type ret(begin(arr), end(arr));
      if (n != size)
        ret.resize(n);
      return ret;
    }
    

    So ungefähr...



  • Ethon schrieb:

    Erstell das bitset doch leer und geh mit einer Schleife drüber und setz die einzelnen Bits mit rand() % 2 ?

    😮

    Eigentlich würde ich da eher mit C++11s std::random (bzw. dem von Boost) zufällige 64-Bit (in seinem Fall wohl eher 32-Bit) Primzahlen erzeugen und diese dann per Shift auf die Bits übertragen.
    So mache ich es zumindest um große Pseudo-Zufalls-Primzahlen zu erzeugen.



  • Sone schrieb:

    Ethon schrieb:

    Erstell das bitset doch leer und geh mit einer Schleife drüber und setz die einzelnen Bits mit rand() % 2 ?

    😮

    Eigentlich würde ich da eher mit C++11s std::random (bzw. dem von Boost) zufällige 64-Bit (in seinem Fall wohl eher 32-Bit) Primzahlen erzeugen und diese dann per Shift auf die Bits übertragen.
    So mache ich es zumindest um große Pseudo-Zufalls-Primzahlen zu erzeugen.

    Höh? Ob rand() oder den C++11 Krempel ist ja fast egal, außer man braucht Zufallszahlen einer bestimmten Qualität ...

    Ich meinte soetwas:

    boost::dynamic_bitset<> bs;
    bs.resize(2048);
    for(size_t i = 0; i < 2048; ++i)
        bs[i] = rand() % 2;
    

    Denke nicht dass das sonderlich ineffizient ist. Aber das wäre zu testen.
    Natürlich ist es schlauer die Bits wortweise zu setzen wie Furble Wurble es macht ... aber was solls. 😉



  • Ethon schrieb:

    Sone schrieb:

    Ethon schrieb:

    Erstell das bitset doch leer und geh mit einer Schleife drüber und setz die einzelnen Bits mit rand() % 2 ?

    😮

    Eigentlich würde ich da eher mit C++11s std::random (bzw. dem von Boost) zufällige 64-Bit (in seinem Fall wohl eher 32-Bit) Primzahlen erzeugen und diese dann per Shift auf die Bits übertragen.
    So mache ich es zumindest um große Pseudo-Zufalls-Primzahlen zu erzeugen.

    Höh? Ob rand() oder den C++11 Krempel ist ja fast egal, außer man braucht Zufallszahlen einer bestimmten Qualität ...

    Es ging nicht um das C++11, sondern das - wie du es nennst - wortweise Erzeugen, wie es Furble macht.


Log in to reply