Zufallszahlen zur Compile-Zeit
-
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
-
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/1LSSJiDeine 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?
-
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 vonx
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.
-
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.
-
Selbes Verhalten beim GCC 4.9 übrigens, wenn ich time.hxx nicht einbinde und einfach direkt
172014
hinschreibe.
-
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