Zufallszahlen zur Compile-Zeit


  • Mod

    Wie hier "angekündigt" möchte ich VTMPL ein wenig auf Vordermann bringen, und atm versuche ich gerade einen Compile-Zeit PRNG einzubauen.

    Im Moment sieht das ganze so aus:

    template< std::uintmax_t c = 25214903917,
    	          std::uintmax_t a = 11,
    	          std::uintmax_t m = (1ull << 48) >
    	constexpr std::uintmax_t rand48( std::uintmax_t state = time() )
    	{
    		return (state * c + a) % m;
    	}
    

    Die Konstanten habe ich von POSIX' drand48 .

    Wobei time() so definiert ist:

    template< typename format = VTMPL_STRING("SsMmHh") >
    	constexpr std::uintmax_t time()
    	{
    		using str = VTMPL_STRING( __TIME__ );
    
    		constexpr auto Hh = parse_unsigned<str>().first;
    		constexpr auto Mm = parse_unsigned<str>(3).first;
    		constexpr auto Ss = parse_unsigned<str>(6).first;
    
    		std::uintmax_t rval = 0;
    
    		for( auto c : format::array )
    		{
    			rval *= 10;
    			switch(c)
    			{
    				case 'H': rval += Hh / 10; break;
    				case 'h': rval += Hh % 10; break;
    				case 'M': rval += Mm / 10; break;
    				case 'm': rval += Mm % 10; break;
    				case 'S': rval += Ss / 10; break;
    				case 's': rval += Ss % 10; break;
    
    				default:
    					VTMPL_ASSERT(0, "Invalid time format string!");
    			}
    		}
    
    		return rval;
    	}
    

    Das kann ich so natürlich nicht stehen lassen. Vor allem, weil zum Beispiel der LSB bei linearen Kongruenzgeneratoren bekanntlich dazu neigt, wenig Zufall zu zeigen und ich evt. einen Shift machen muss, um an die high-order Bits zu kommen. Allerdings soll die Qualität der Zufallszahlen nicht leiden.

    Hat jemand eine Idee was für ein PRNG sich hier gut eignen würde und implementierbar ist? Oder ob man die Zeit noch sinnvoller in einen String packen könnte, um den PRNG besser zu seeden?

    Das Repo ist hier. (Benötigter Compiler für den C++14-Code ist Clang >= 3.4, sonst sollte GCC 4.8 reichen).

    Vielen Dank für Ideen im Voraus.

    P.S.: Hat jemand auch zufällig noch eine bessere Assertion-Methode (mit Fehlermeldung) für constexpr-Funktionen? Momentan habe ich es so:

    #define VTMPL_ASSERT( B, MSG ) ( B? 0 : throw ::std::invalid_argument{MSG})
    

    Ist allerdings nicht sehr hübsch - die Fehlermeldung kriegt man nur zu sehen, wenn man auf die zweite logische Zeile des Compiler-Outputs schaut (subexpression not valid in a constant expression).



  • Multiply With Carry ist super.

    volkard hat mir mal eine Implementierung vorgeschlagen, die ich nun auch schon einige Zeit verwende. Vergiss nicht, ihn zu erwähnen 🙂


  • Mod

    War klar dass die Lösung dazu von Volkard kommt. 😃

    Gut, kleiner Test:

    #include "index_list.hxx"
    #include "algorithms.hxx"
    #include "time.hxx"
    
    #include <iterator>
    #include <iostream>
    
    template< std::uintmax_t a,
              std::uintmax_t mask,
              int shift >
    constexpr std::uintmax_t rand_impl( std::uintmax_t x )
    {
    	return a*(x&mask)+(x>>shift);
    }
    
    template< std::uintmax_t a = 4294967118,
              std::uintmax_t mask = 0xffffffff,
              int shift = 32 >
    constexpr std::uintmax_t rand( std::uintmax_t x )
    {
    	return rand_impl<a, mask, shift>(x? x : 1);
    }
    
    int main()
    {
    
    	using namespace vtmpl;
    	using namespace functions;
    
    	copy< sub_list<eval<generate_recursive<10, chain< from_function_ptr<std::uintmax_t, &rand>::function,
    	                                                  modulo           <std::uintmax_t, 10   >::function >::function,
    	                                       value_list<std::uintmax_t, time<VTMPL_STRING("HhMmSs")>()> >>, 1> >( std::ostream_iterator<std::uintmax_t>{std::cout, " "} );
    }
    

    Ausgabe:

    6 8 4 2 6 8 4 2 6 8
    
    2 6 8 4 2 6 8 4 2 6
    
    8 4 2 6 8 4 2 6 8 4
    

    Und zwar immer sowas. Nichts ungerades. Worauf genau ist das zurückzuführen?

    Nexus schrieb:

    Vergiss nicht, ihn zu erwähnen 🙂

    Auf keinen Fall. 🙂



  • Zur Laufzeit hat er noch ungerade Zahlen dabei.
    https://ideone.com/1LSSJi

    Deine Zahlen sind viel schlimmer als nur gerade Zahlen, sie sind immer
    6 8 4 2
    Rückwärts gelesen ist 2 4 8 6 2 4 8 6 2 4 8 6… die Folge der Endziffern der Zweierpotenzen. Ob das was zu bedeuten hat? Wie sehen die Zahlen aus, wenn Du %10 wegläßt?


  • Mod

    a * ( x & mask) + ( x >> shift )
    

    Damit immer gerade Zahlen herauskommen muss das LSB von a*(x&mask) und das LSB von (x >> shift) immer den gleichen Wert haben.

    Weil a gerade ist, wird das Produkt immer LSB = 0 haben. Also muss auch der LSB von (x >> shift) immer 0 sein.

    Der LSB von (x >> shift) ist genau dann 0, wenn das dreiunddreißigste Bit von x 0 ist.

    Hmm.

    Wie sehen die Zahlen aus, wenn Du %10 wegläßt?

    Hier mal hundert Zahlen ohne Modulo:

    165202
    709537157827836
    18320445695112183321
    4034941536540204777
    1077097940759904241
    15225684482536352076
    2576526502479054982
    17772549771398888455
    11902516376801053436
    2053371950223890525
    15337175421055998526
    2154156764651346093
    832137497223852512
    1607628732448582373
    9822116068662156950
    5711582885095073338
    7731244528034613771
    13055805085336791625
    8087596297962693323
    12309642165996468437
    12133744546030689850
    10772080149562307596
    13164782081298722170
    10177269947472123065
    9391575733387363446
    17130430542210366034
    3887585238828742349
    7669760471293026211
    3729226229867673389
    7950250686240588341
    8983838887856664070
    13693596548621828530
    6493770048280412094
    1500613125441597272
    16085783357756691583
    15923131680788672110
    4120070485795113834
    1973574268267953811
    3311973609001421089
    2738057760586933633
    13999761573072303444
    1090844496442265746
    4296874298402729926
    11010438367382001852
    18240378989381303459
    10849800677655621302
    5437162524039496111
    2265523477304705748
    8002336366320077361
    16695628390350023796
    6106155666080882920
    18157775071069866729
    2202272126584867383
    13534946032276304022
    9505251887306604904
    253751229389567467
    1231019674374341632
    2493168901221232095
    168794677923978970
    9341202849163721289
    16088328664470525885
    4863913500242917444
    17308661153883748422
    4528360746232977137
    4470410620244853897
    2005232638480019332
    16473867154908871341
    2689065228355216027
    17435582547020114637
    16654991114482835304
    4326093641935098845
    2926798527455530901
    18311511721806413350
    8551277775264962680
    8817019079483636324
    7095062909634395803
    274366190526542426
    13598110923525962756
    14780738618014398222
    2064186824126034874
    16290350107687649190
    16967310510173401520
    2928238697297965731
    12249635048885943358
    17655653791039426320
    5489622808781455988
    18180189215825025587
    16042764812072536654
    3366522284540931933
    7097584058358586244
    12821848231883312464
    12204769124595210600
    17088654540169831050
    14136906993251816655
    9476299793277184532
    6009184927601906316
    9752494614049490050
    4059014692097732554
    6670868479662639591
    15682740410497125611
    601315101185592810
    


  • Das sind jetzt total andere Zahlen, finde ich. Auch ungerade und so.
    edit: Drei kurze Folgen mit %100 wären auch spannend.


  • Mod

    Total irre.

    171903 // seed
    54
    72
    96
    28
    4
    72
    96
    28
    4
    ...
    
    171948
    64
    52
    36
    48
    64
    52
    36
    48
    ...
    
    172016
    88
    84
    12
    16
    88
    84
    12
    ...
    

    Aber wenn ich den Modulo auf 2^64-1 setze:

    172115
    739228265514570
    18315160677943951582
    4975704283593141053
    18083477040222744644
    14296870234884856646
    444408591854352655
    8979114121631575764
    7028762842301311312
    12237873217963521264
    

    Kannste das erklären? Oder ich muss die Antwort bei Gott suchen.


  • Mod

    Selbes Verhalten beim GCC 4.9 übrigens, wenn ich time.hxx nicht einbinde und einfach direkt 172014 hinschreibe.


  • Mod

    Ouch, ich habe den Fehler gefunden. Und es ist kein Fehler der Lib, sondern meiner. Es wird nicht Modulo 10 ausgegeben, sondern auch gespeichert. Also bekommt der Algo 6, 4, usw. als input. Hätte ich sehen sollen.

    Edit: Der Code funktioniert natürlich:

    #include "index_list.hxx"
    #include "time.hxx"
    #include "algorithms.hxx"
    
    #include <iterator>
    #include <iostream>
    
    template< std::uintmax_t a,
              std::uintmax_t mask,
              int shift >
    constexpr std::uintmax_t rand_impl( std::uintmax_t x )
    {
    	return a*(x&mask)+(x>>shift);
    }
    
    template< std::uintmax_t a = 4294967118,
              std::uintmax_t mask = 0xffffffff,
              int shift = 32 >
    constexpr std::uintmax_t rand( std::uintmax_t x )
    {
    	return rand_impl<a, mask, shift>(x? x : 1);
    }
    
    int main()
    {
    
        using namespace vtmpl;
        using namespace functions;
    
        using list = generate_recursive<20, from_function_ptr<std::uintmax_t, &rand>,
                                        value_list<std::uintmax_t, time()> >;
    
        copy< transform<eval<list>, modulo<std::uintmax_t, 10>> >( std::ostream_iterator<std::uintmax_t>{std::cout, "\n"} );
    }
    

    Ausgabe wie erwartet

    7 6 6 7 7 5 1 5 1 9 5 9 5 4 6 2 5 1 6 6 9
    

Anmelden zum Antworten