Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Zahlenraten in C
98 views
Skip to first unread message
F. W.
Jun 22, 2021, 1:42:42 AM6/22/21
to
Ein kleines "Abfallprodukt".
Vielleicht kann jemand irgendwas damit anfangen:
// zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
// Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
// Public Domain
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main ()
{
int iGedachteZahl; // Die vom Computer gedachte Zahl
int iZahlMin, iZahlMax; // Minimale und maximale gedachte Zahl
int iVermutung; // Welche Zahl vermutet der Spieler?
printf ("Ich denke mir also eine Zahl...");
// Zufallszahl generieren
iZahlMin = 0;
iZahlMax = 100;
srand (time (0));
iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
printf ("...fertig. \n");
do {
printf ("Ihre Vermutung?");
scanf ("%d", &iVermutung);
if (iVermutung > iGedachteZahl) {
printf ("Die Zahl ist kleiner! \n");
};
if (iVermutung < iGedachteZahl) {
printf ("Die Zahl ist größer! \n");
}
} while (iVermutung != iGedachteZahl);
printf ("Richtig geraten!!!! Es war die %d!", iGedachteZahl);
return 0;
}
FW
Vielleicht kann jemand irgendwas damit anfangen:
// zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
// Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
// Public Domain
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main ()
{
int iGedachteZahl; // Die vom Computer gedachte Zahl
int iZahlMin, iZahlMax; // Minimale und maximale gedachte Zahl
int iVermutung; // Welche Zahl vermutet der Spieler?
printf ("Ich denke mir also eine Zahl...");
// Zufallszahl generieren
iZahlMin = 0;
iZahlMax = 100;
srand (time (0));
iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
printf ("...fertig. \n");
do {
printf ("Ihre Vermutung?");
scanf ("%d", &iVermutung);
if (iVermutung > iGedachteZahl) {
printf ("Die Zahl ist kleiner! \n");
};
if (iVermutung < iGedachteZahl) {
printf ("Die Zahl ist größer! \n");
}
} while (iVermutung != iGedachteZahl);
printf ("Richtig geraten!!!! Es war die %d!", iGedachteZahl);
return 0;
}
FW
Bonita Montero
Jun 22, 2021, 2:18:34 AM6/22/21
to
Am 22.06.2021 um 07:42 schrieb F. W.:
> Ein kleines "Abfallprodukt".
>
> Vielleicht kann jemand irgendwas damit anfangen:
>
> // zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
> // Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
> // Public Domain
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <time.h>
>
> int main ()
> {
> int iGedachteZahl; // Die vom Computer gedachte Zahl
> int iZahlMin, iZahlMax; // Minimale und maximale gedachte Zahl
> int iVermutung; // Welche Zahl vermutet der Spieler?
>
> printf ("Ich denke mir also eine Zahl...");
>
> // Zufallszahl generieren
> iZahlMin = 0;
> iZahlMax = 100;
> srand (time (0));
> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
> Ein kleines "Abfallprodukt".
>
> Vielleicht kann jemand irgendwas damit anfangen:
>
> // zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
> // Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
> // Public Domain
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <time.h>
>
> int main ()
> {
> int iGedachteZahl; // Die vom Computer gedachte Zahl
> int iZahlMin, iZahlMax; // Minimale und maximale gedachte Zahl
> int iVermutung; // Welche Zahl vermutet der Spieler?
>
> printf ("Ich denke mir also eine Zahl...");
>
> // Zufallszahl generieren
> iZahlMin = 0;
> iZahlMax = 100;
> srand (time (0));
> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
F. W.
Jun 22, 2021, 2:27:45 AM6/22/21
to
Am 22.06.2021 um 08:18 schrieb Bonita Montero:
>> srand (time (0));
>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
>> srand (time (0));
>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
FW
Bonita Montero
Jun 22, 2021, 2:38:49 AM6/22/21
to
>>> srand (time (0));
>>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
Ja, das hab ich mich gerade auch gefragt, wie man aus einem Strom
>>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
Zufallszahlen die alle vom selben Typ sind und alle einen bestimmten
Wertebereich gleichmäßig ausschöpfen einen Strom Zufallszahlen in
einem anderen beliebigen Wertebereich macht.
In C++ ist die Zufallszahlen-Generierung zweistufig. Da hat man
einen Generator wie mt19937_64 (Mersenne-Twister, das beste was
es an nicht-kryptografischen Zufallszahlen-Generatoren gibt),
der 64-bittige Zufallszahlen gibt. Und man hat sogenannte Adapter
-Objekte die sich aus dem Generator-Objekten eben die Zufallszah-
len beziehen und das dann eben nach mir unbekannter Art so ver-
wustehn, dass darauf ein Zufallss-Strom unterschiedlicher Typen
(integer, floating point) mit unterschiedlichen Verteilungen
(z.B. Gleichverteilung oder Normalverteilung) gemacht wird.
Das was Du da oben machst sähe also so aus:
#include <random>
using namespace std;
...
{
...
mt19937_64 generator( (random_device())() );
uniform_int_distribution<int> adaptor( iZahMin, iZahlMax );
...
}
Und der adaptor muss ja das machen was Du da versuchst, nur eben
technisch sauber realisiert. Wie er das macht - keine Ahnung.
Bonita Montero
Jun 22, 2021, 2:39:25 AM6/22/21
to
int iRand = adaptor( generator );
Thomas Koenig
Jun 22, 2021, 2:46:59 AM6/22/21
to
F. W. <m...@home.com> schrieb:
kann man natürlich mit bsearch machen.
Interessant finde ich eine andere Fragestellung: Wenn Alice sich
die Zahl ausdenkt und Bob sie zu erraten versucht, wie sehen
die jeweils optimalen Strategien aus, wenn Alice die Zahl der
Ratevorgänge maximieren möchte und Bob sie minimieren?
Damit sehr lose zusammenhängend: Wenn qsort tatsächlich
als reiner Quicksort implementiert ist, kann man es durch
geeignet präparierte Daten in eine quadratische Laufzeit und
linearen Stackbedarf zwingen (und das durch eine entsprechende
Vergleichsfunktion, die keine Daten vergleicht, sondern gezielt den
Algorithmus verwirrt, rausfinden). Neuere qsort-Implementierungen
geben auf, wenn die Suche nach dem Pivotelement zu schwierig wird,
und gehen dann auf was anderes (z.B. Heapsort).
> Ein kleines "Abfallprodukt".
>
> Vielleicht kann jemand irgendwas damit anfangen:
>
> // zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
> // Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
> // Public Domain
Die andere Seite (wo der Computer versucht, die Zahl zu erraten)
>
> Vielleicht kann jemand irgendwas damit anfangen:
>
> // zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
> // Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
> // Public Domain
kann man natürlich mit bsearch machen.
Interessant finde ich eine andere Fragestellung: Wenn Alice sich
die Zahl ausdenkt und Bob sie zu erraten versucht, wie sehen
die jeweils optimalen Strategien aus, wenn Alice die Zahl der
Ratevorgänge maximieren möchte und Bob sie minimieren?
Damit sehr lose zusammenhängend: Wenn qsort tatsächlich
als reiner Quicksort implementiert ist, kann man es durch
geeignet präparierte Daten in eine quadratische Laufzeit und
linearen Stackbedarf zwingen (und das durch eine entsprechende
Vergleichsfunktion, die keine Daten vergleicht, sondern gezielt den
Algorithmus verwirrt, rausfinden). Neuere qsort-Implementierungen
geben auf, wenn die Suche nach dem Pivotelement zu schwierig wird,
und gehen dann auf was anderes (z.B. Heapsort).
F. W.
Jun 22, 2021, 2:51:37 AM6/22/21
to
Am 22.06.2021 um 08:46 schrieb Thomas Koenig:
> Interessant finde ich eine andere Fragestellung: Wenn Alice sich
> die Zahl ausdenkt und Bob sie zu erraten versucht, wie sehen die
> jeweils optimalen Strategien aus, wenn Alice die Zahl der
> Ratevorgänge maximieren möchte und Bob sie minimieren?
Also wenn der Computer (mein Progrämmchen) dabei dann Alice wäre und ich
> Interessant finde ich eine andere Fragestellung: Wenn Alice sich
> die Zahl ausdenkt und Bob sie zu erraten versucht, wie sehen die
> jeweils optimalen Strategien aus, wenn Alice die Zahl der
> Ratevorgänge maximieren möchte und Bob sie minimieren?
Bob, hätte ich für mich nur die Strategie, jeweils die Hälfte der
verbliebenen Zahlen zu nehmen.
Also z. B.
Vermutung: 50 => "Zahl ist größer"
Zwischen 50 und 100, also 75
Ist sie noch größer, zwischen 75 und 100 usw. den unbekannten Bereicht
immer verkleinern.
Für Alice hätte ich keine Strategie parat. Vielleicht nahe an den
vermuteten Grenzen denken: 76 statt 75, 24 statt 25 usw. damit das Raten
möglichst lange dauert.
Wenn ich das Problem richtig verstanden habe...
FW
F. W.
Jun 22, 2021, 2:51:51 AM6/22/21
to
Am 22.06.2021 um 08:39 schrieb Bonita Montero:
Danke Dir :-)
FW
Danke Dir :-)
FW
Helmut Schellong
Jun 22, 2021, 4:31:12 AM6/22/21
to
On 06/22/2021 07:42, F. W. wrote:
> Ein kleines "Abfallprodukt".
>
> Vielleicht kann jemand irgendwas damit anfangen:
>
> // zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
> // Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
> // Public Domain
>
> #include <stdio.h>
> [...].
> Ein kleines "Abfallprodukt".
>
> Vielleicht kann jemand irgendwas damit anfangen:
>
> // zahlenraten.c - Ein kleines Spiel, bei dem der Computer sich eine
> // Zahl ausdenkt und Sie diese erraten müssen. 27.04.2021
> // Public Domain
>
> #include <stdio.h>
Eine solche Intervallschachtelung habe ich seit 25 Jahren
auf meiner http://www.schellong.de/ in JavaScript.
Für die besten Random-Funktionen 'random' suchen in:
http://www.schellong.de/htm/bishmnk.htm
Stichwort: 'Spritz-Algorithmus'
--
Mit freundlichen Grüßen
Helmut Schellong v...@schellong.biz
www.schellong.de www.schellong.com www.schellong.biz
http://www.schellong.de/c.htm
http://www.schellong.de/htm/audio_proj.htm
http://www.schellong.de/htm/audio_unsinn.htm
Thomas Koenig
Jun 22, 2021, 6:08:07 AM6/22/21
to
F. W. <m...@home.com> schrieb:
:-)
> Für Alice hätte ich keine Strategie parat. Vielleicht nahe an den
> vermuteten Grenzen denken: 76 statt 75, 24 statt 25 usw. damit das Raten
> möglichst lange dauert.
Man könnte die Binärsuche modifizieren. Wenn z.B. die Zahl zwischen
1 und 1000 inklusive liegen muss, dann wäre 507 eine genau so
valide "Mitte" für die Suche wie 500, damit wäre das Schlupfloch,
dass man sich irgendwo in der Mitte auf eine Zahl setzt, die nach
dem einfachen bsearch - Algorithmus spät drankommt, zu.
Hilft aber gegen die Strategie "Alice nimmt immer 1" nicht.
Hmm...
> Am 22.06.2021 um 08:46 schrieb Thomas Koenig:
>
>> Interessant finde ich eine andere Fragestellung: Wenn Alice sich
>> die Zahl ausdenkt und Bob sie zu erraten versucht, wie sehen die
>> jeweils optimalen Strategien aus, wenn Alice die Zahl der
>> Ratevorgänge maximieren möchte und Bob sie minimieren?
>
> Also wenn der Computer (mein Progrämmchen) dabei dann Alice wäre und ich
> Bob, hätte ich für mich nur die Strategie, jeweils die Hälfte der
> verbliebenen Zahlen zu nehmen.
>
> Also z. B.
>
> Vermutung: 50 => "Zahl ist größer"
>
> Zwischen 50 und 100, also 75
Mit anderen Worten: bsearch(), könnte man direkt auch so programmieren
>
>> Interessant finde ich eine andere Fragestellung: Wenn Alice sich
>> die Zahl ausdenkt und Bob sie zu erraten versucht, wie sehen die
>> jeweils optimalen Strategien aus, wenn Alice die Zahl der
>> Ratevorgänge maximieren möchte und Bob sie minimieren?
>
> Also wenn der Computer (mein Progrämmchen) dabei dann Alice wäre und ich
> Bob, hätte ich für mich nur die Strategie, jeweils die Hälfte der
> verbliebenen Zahlen zu nehmen.
>
> Also z. B.
>
> Vermutung: 50 => "Zahl ist größer"
>
> Zwischen 50 und 100, also 75
:-)
> Für Alice hätte ich keine Strategie parat. Vielleicht nahe an den
> vermuteten Grenzen denken: 76 statt 75, 24 statt 25 usw. damit das Raten
> möglichst lange dauert.
1 und 1000 inklusive liegen muss, dann wäre 507 eine genau so
valide "Mitte" für die Suche wie 500, damit wäre das Schlupfloch,
dass man sich irgendwo in der Mitte auf eine Zahl setzt, die nach
dem einfachen bsearch - Algorithmus spät drankommt, zu.
Hilft aber gegen die Strategie "Alice nimmt immer 1" nicht.
Hmm...
jo...@schily.net
Jun 22, 2021, 7:14:53 AM6/22/21
to
In article <sarvbo$cmq$1...@dont-email.me>,
Bonita Montero <Bonita....@gmail.com> wrote:
>> Â iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
Das merkt niemand....
... und wenn es unbedingt besser sein soll, nimmt man halt drand48().
--
EMail:jo...@schily.net Jörg Schilling D-13353 Berlin
Blog: http://schily.blogspot.com/
URL: http://cdrecord.org/private/ http://sourceforge.net/projects/schilytools/files/
Bonita Montero <Bonita....@gmail.com> wrote:
>> Â iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
Wen interessiert das in diesem Zusammenhang?
Das merkt niemand....
... und wenn es unbedingt besser sein soll, nimmt man halt drand48().
--
EMail:jo...@schily.net Jörg Schilling D-13353 Berlin
Blog: http://schily.blogspot.com/
URL: http://cdrecord.org/private/ http://sourceforge.net/projects/schilytools/files/
jo...@schily.net
Jun 22, 2021, 7:21:47 AM6/22/21
to
In article <sarvsv$hv6$2...@gioia.aioe.org>, F. W. <m...@home.com> wrote:
>Am 22.06.2021 um 08:18 schrieb Bonita Montero:
>
>>> Â Â srand (time (0));
>Am 22.06.2021 um 08:18 schrieb Bonita Montero:
>
>>> Â Â iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>
>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>
>Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
zahl = drand48() * (iZahlMax - iZahlMin) + iZahlMin;
>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>
>Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
jo...@schily.net
Jun 22, 2021, 7:25:43 AM6/22/21
to
In article <sas112$3te$1...@newsreader4.netcologne.de>,
Thomas Koenig <tko...@netcologne.de> wrote:
>Damit sehr lose zusammenhängend: Wenn qsort tatsächlich
Optimierung, wenn man auch bei großen Listen weder viel Stack noch viel
Zeit verbrauchen möchte.
Thomas Koenig <tko...@netcologne.de> wrote:
>Damit sehr lose zusammenhängend: Wenn qsort tatsächlich
>als reiner Quicksort implementiert ist, kann man es durch
>geeignet präparierte Daten in eine quadratische Laufzeit und
>linearen Stackbedarf zwingen (und das durch eine entsprechende
>Vergleichsfunktion, die keine Daten vergleicht, sondern gezielt den
>Algorithmus verwirrt, rausfinden). Neuere qsort-Implementierungen
>geben auf, wenn die Suche nach dem Pivotelement zu schwierig wird,
>und gehen dann auf was anderes (z.B. Heapsort).
Wenn es ums Sortieren geht, ist Shellsort (vom Bourne Shell) eine gute
>Vergleichsfunktion, die keine Daten vergleicht, sondern gezielt den
>Algorithmus verwirrt, rausfinden). Neuere qsort-Implementierungen
>geben auf, wenn die Suche nach dem Pivotelement zu schwierig wird,
>und gehen dann auf was anderes (z.B. Heapsort).
Optimierung, wenn man auch bei großen Listen weder viel Stack noch viel
Zeit verbrauchen möchte.
Bonita Montero
Jun 22, 2021, 10:19:50 AM6/22/21
to
> zahl = drand48() * (iZahlMax - iZahlMin) + iZahlMin;
Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
Je kleiner die Zahl, desto höher die Präzision. Daher fände
ich es besser, man nimmt einfach eine Zufallszahl die bis
2^N-1, multipliziert das * (max - min) und shiftet Das Ergeb-
nis dann um N Bits. Und schneller ist eine Integer-Multipli-
kation sowieso.
jo...@schily.net
Jun 22, 2021, 11:17:45 AM6/22/21
to
In article <sasri4$rsi$1...@dont-email.me>,
Wie kommst Du auf diese seltsame Behauptung.
Das Ergebnis ist zudem im Bereich 0.0 .. 1.0
Bonita Montero <Bonita....@gmail.com> wrote:
>> zahl = drand48() * (iZahlMax - iZahlMin) + iZahlMin;
>
>Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
>Je kleiner die Zahl, desto höher die Präzision. Daher fände
>> zahl = drand48() * (iZahlMax - iZahlMin) + iZahlMin;
>
>Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
Wie kommst Du auf diese seltsame Behauptung.
Das Ergebnis ist zudem im Bereich 0.0 .. 1.0
Christian Weisgerber
Jun 22, 2021, 11:30:07 AM6/22/21
to
On 2021-06-22, F. W. <m...@home.com> wrote:
>>> srand (time (0));
>>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>
>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>
> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
https://github.com/openbsd/src/blob/master/lib/libc/crypt/arc4random_uniform.c
>>> srand (time (0));
>>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>
>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>
> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
/*
* Calculate a uniformly distributed random number less than upper_bound
* avoiding "modulo bias".
*
* Uniformity is achieved by generating new random numbers until the one
* returned is outside the range [0, 2**32 % upper_bound). This
* guarantees the selected random number will be inside
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
* after reduction modulo upper_bound.
*/
uint32_t
arc4random_uniform(uint32_t upper_bound)
{
uint32_t r, min;
if (upper_bound < 2)
return 0;
/* 2**32 % x == (2**32 - x) % x */
min = -upper_bound % upper_bound;
/*
* This could theoretically loop forever but each retry has
* p > 0.5 (worst case, usually far better) of selecting a
* number inside the range we need, so it should rarely need
* to re-roll.
*/
for (;;) {
r = arc4random();
if (r >= min)
break;
}
return r % upper_bound;
}
--
Christian "naddy" Weisgerber na...@mips.inka.de
jo...@schily.net
Jun 22, 2021, 11:53:55 AM6/22/21
to
In article <slrnsd3tnr...@lorvorc.mips.inka.de>,
aber der betreffende Antrag wurde 2 Jahre später wieder zurückgezogen.
>>>> Â Â srand (time (0));
>>>> Â Â iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>>
>>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>>
>> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
>
>https://github.com/openbsd/src/blob/master/lib/libc/crypt/arc4random_uniform.c
Vor 14 Jahren gab es einen Versuch diesen Generator in POSIX zu integrieren,
>>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>>
>> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
>
>https://github.com/openbsd/src/blob/master/lib/libc/crypt/arc4random_uniform.c
aber der betreffende Antrag wurde 2 Jahre später wieder zurückgezogen.
Bonita Montero
Jun 22, 2021, 12:21:16 PM6/22/21
to
>> Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
>> Je kleiner die Zahl, desto höher die Präzision. ...
> Wie kommst Du auf diese seltsame Behauptung.
> Das Ergebnis ist zudem im Bereich 0.0 .. 1.0
Genauigkeit.
Thomas Koenig
Jun 22, 2021, 12:37:06 PM6/22/21
to
jo...@schily.net <jo...@schily.net> schrieb:
"Shellsort" wurde von https://de.wikipedia.org/wiki/Donald_L._Shell
entwickelt, das hat mit der Bourne shell erst mal nix zu tun :-)
> eine gute
> Optimierung, wenn man auch bei großen Listen weder viel Stack noch viel
> Zeit verbrauchen möchte.
Shellsort ist mit der richtigen gap sequence nicht schlecht, aber
wenn Quicksort aus Gründen von pathologischen Eingabedaten
quadratisch explodiert, dann ist Heapsort als Backup mit
seiner O(n*log(n)) worst case - Zeit und ohne Zusatsspeicher
zuverlässiger, wenn auch nicht unbedingt schneller. Ist
halt nicht cache-freundlich...
> In article <sas112$3te$1...@newsreader4.netcologne.de>,
> Thomas Koenig <tko...@netcologne.de> wrote:
>
>>Damit sehr lose zusammenhängend: Wenn qsort tatsächlich
>>als reiner Quicksort implementiert ist, kann man es durch
>>geeignet präparierte Daten in eine quadratische Laufzeit und
>>linearen Stackbedarf zwingen (und das durch eine entsprechende
>>Vergleichsfunktion, die keine Daten vergleicht, sondern gezielt den
>>Algorithmus verwirrt, rausfinden). Neuere qsort-Implementierungen
>>geben auf, wenn die Suche nach dem Pivotelement zu schwierig wird,
>>und gehen dann auf was anderes (z.B. Heapsort).
>
>
> Wenn es ums Sortieren geht, ist Shellsort (vom Bourne Shell)
Äh...
> Thomas Koenig <tko...@netcologne.de> wrote:
>
>>Damit sehr lose zusammenhängend: Wenn qsort tatsächlich
>>als reiner Quicksort implementiert ist, kann man es durch
>>geeignet präparierte Daten in eine quadratische Laufzeit und
>>linearen Stackbedarf zwingen (und das durch eine entsprechende
>>Vergleichsfunktion, die keine Daten vergleicht, sondern gezielt den
>>Algorithmus verwirrt, rausfinden). Neuere qsort-Implementierungen
>>geben auf, wenn die Suche nach dem Pivotelement zu schwierig wird,
>>und gehen dann auf was anderes (z.B. Heapsort).
>
>
> Wenn es ums Sortieren geht, ist Shellsort (vom Bourne Shell)
"Shellsort" wurde von https://de.wikipedia.org/wiki/Donald_L._Shell
entwickelt, das hat mit der Bourne shell erst mal nix zu tun :-)
> eine gute
> Optimierung, wenn man auch bei großen Listen weder viel Stack noch viel
> Zeit verbrauchen möchte.
wenn Quicksort aus Gründen von pathologischen Eingabedaten
quadratisch explodiert, dann ist Heapsort als Backup mit
seiner O(n*log(n)) worst case - Zeit und ohne Zusatsspeicher
zuverlässiger, wenn auch nicht unbedingt schneller. Ist
halt nicht cache-freundlich...
Thomas Koenig
Jun 22, 2021, 12:42:20 PM6/22/21
to
Bonita Montero <Bonita....@gmail.com> schrieb:
der zwischen 0.5 und 1 einen anderen Minimalabstand zwischen
zwei Zahlen als zwschen 0.25 und 0.5, der ist schon ziemlich
merkwürdig und hat eine Fehlermeldung verdient.
> Daher fände
> ich es besser, man nimmt einfach eine Zufallszahl die bis
> 2^N-1, multipliziert das * (max - min) und shiftet Das Ergeb-
> nis dann um N Bits. Und schneller ist eine Integer-Multipli-
> kation sowieso.
Was genau ist N bei dir?
>> zahl = drand48() * (iZahlMax - iZahlMin) + iZahlMin;
>
> Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
> Je kleiner die Zahl, desto höher die Präzision.
Das ist natürlich richtig, aber ein Zusfallszahlengenerator,
>
> Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
> Je kleiner die Zahl, desto höher die Präzision.
der zwischen 0.5 und 1 einen anderen Minimalabstand zwischen
zwei Zahlen als zwschen 0.25 und 0.5, der ist schon ziemlich
merkwürdig und hat eine Fehlermeldung verdient.
> Daher fände
> ich es besser, man nimmt einfach eine Zufallszahl die bis
> 2^N-1, multipliziert das * (max - min) und shiftet Das Ergeb-
> nis dann um N Bits. Und schneller ist eine Integer-Multipli-
> kation sowieso.
Bonita Montero
Jun 22, 2021, 12:49:46 PM6/22/21
to
> Das ist natürlich richtig, aber ein Zusfallszahlengenerator,
> der zwischen 0.5 und 1 einen anderen Minimalabstand zwischen
> zwei Zahlen als zwschen 0.25 und 0.5, der ist schon ziemlich
> merkwürdig und hat eine Fehlermeldung verdient.
Ja, die Qualität der Zufalls-zahlen ist mit kleinerem Multi-
> der zwischen 0.5 und 1 einen anderen Minimalabstand zwischen
> zwei Zahlen als zwschen 0.25 und 0.5, der ist schon ziemlich
> merkwürdig und hat eine Fehlermeldung verdient.
plikator höher.
Ich weiß auch gar nicht wieso man FP-Werte als Zufalls-Zahlen
für Integer-Werte als Ziel-Werte nehmen sollte da die Zufalls-
zahlen-Generatoren eh mit Integer-Zahlen arbeiten.
>> Daher fände
>> ich es besser, man nimmt einfach eine Zufallszahl die bis
>> 2^N-1, multipliziert das * (max - min) und shiftet Das Ergeb-
>> nis dann um N Bits. Und schneller ist eine Integer-Multipli-
>> kation sowieso.
> Was genau ist N bei dir?
Thomas Koenig
Jun 22, 2021, 1:00:52 PM6/22/21
to
Bonita Montero
Jun 22, 2021, 1:11:46 PM6/22/21
to
>>>> Daher fände
>>>> ich es besser, man nimmt einfach eine Zufallszahl die bis
>>>> 2^N-1, multipliziert das * (max - min) und shiftet Das Ergeb-
>>>> nis dann um N Bits. Und schneller ist eine Integer-Multipli-
>>>> kation sowieso.
>>> Was genau ist N bei dir?
>> Das ist beliebig. Je größer N, desto genauer die Gleichverteilung.
> N=1024 wäre also valide?
Wirst wohl keine CPU finden die so einen Datentypen hat. N=64 wäre
>>>> ich es besser, man nimmt einfach eine Zufallszahl die bis
>>>> 2^N-1, multipliziert das * (max - min) und shiftet Das Ergeb-
>>>> nis dann um N Bits. Und schneller ist eine Integer-Multipli-
>>>> kation sowieso.
>>> Was genau ist N bei dir?
>> Das ist beliebig. Je größer N, desto genauer die Gleichverteilung.
> N=1024 wäre also valide?
machbar, denn Du kannst auf heutigen CPUs 64 * 64 = 128 Bit multi-
plizieren und dafür bieten die Compiler auch entsprechende Intrin-
sics, dass man auch an beide 64-Bit-Datenwörter kommt; oder eben
nur an das obere, denn wenn N = 64 dann muss ja das untere verwor-
fen werden.
jo...@schily.net
Jun 22, 2021, 1:41:50 PM6/22/21
to
In article <sat2lr$v00$1...@dont-email.me>,
>Genauigkeit.
Ein Effekt, den man in diesem Nuntzungsszenario aber nur bemerkt, wenn
der Zielzahlenbereich größer als 10**16 wird. Die Mantisse eines Double
hat 53 Bits...
Bonita Montero <Bonita....@gmail.com> wrote:
>>> Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
>>> Je kleiner die Zahl, desto höher die Präzision. ...
>>> Floating Point Zahlen haben keine gleichverteilte Genauigkeit.
>
>> Wie kommst Du auf diese seltsame Behauptung.
>> Das Ergebnis ist zudem im Bereich 0.0 .. 1.0
>
>Ja, aber die Zahlen die näher an Null sind haben eine höhere
>> Wie kommst Du auf diese seltsame Behauptung.
>> Das Ergebnis ist zudem im Bereich 0.0 .. 1.0
>
>Genauigkeit.
Ein Effekt, den man in diesem Nuntzungsszenario aber nur bemerkt, wenn
der Zielzahlenbereich größer als 10**16 wird. Die Mantisse eines Double
hat 53 Bits...
Christian Garbs
Jun 22, 2021, 3:43:30 PM6/22/21
to
Mahlzeit!
Problematisch ist nicht die Genauigkeit der rand()-Funktion, sondern
das Modulo. Problematisch ist nur die höchste, potenziell "halbe"
Wiederholung, bis einschließlich RAND_MAX. Da müsste man etwas
rumrechnen und die Ergebnisse, die in dem betroffenen Bereich liegen,
wegwerfen und einfach nochmal würfeln.
Ich bin zu faul, das jetzt allgemeingültig nachzubauen, aber hier mal
an einem Beispiel:
- rand() liefere perfekt gleichverteilte Zahlen von 0 bis 7
(inklusive)
- ich möchte eine Zahl von 1-3 haben (inkusive)
Wenn ich nun mit zahl = (rand() % 3) + 1 arbeite, dann passiert folgendes:
rand() | Ergebnis
-------------------
0 | 1
1 | 2
2 | 3
3 | 1
4 | 2
5 | 3
6 | 1
7 | 2
1 und 2 kommen 3x vor, die 3 nur 2x. Damit ist es nach der Umrechnung
nicht mehr gleichverteilt.
Wenn man eine Schleife um rand() baut, die Rückgaben 6 und 7 verwirft
und rand() solange aufruft, bis maximal 5 zurückkommt, passt es.
Gruß
Christian
--
....Christian.Garbs....................................https://www.cgarbs.de
"Don't give up, lose interest." (Miranda Cornielle, Columbia Internet)
das Modulo. Problematisch ist nur die höchste, potenziell "halbe"
Wiederholung, bis einschließlich RAND_MAX. Da müsste man etwas
rumrechnen und die Ergebnisse, die in dem betroffenen Bereich liegen,
wegwerfen und einfach nochmal würfeln.
Ich bin zu faul, das jetzt allgemeingültig nachzubauen, aber hier mal
an einem Beispiel:
- rand() liefere perfekt gleichverteilte Zahlen von 0 bis 7
(inklusive)
- ich möchte eine Zahl von 1-3 haben (inkusive)
Wenn ich nun mit zahl = (rand() % 3) + 1 arbeite, dann passiert folgendes:
rand() | Ergebnis
-------------------
0 | 1
1 | 2
2 | 3
3 | 1
4 | 2
5 | 3
6 | 1
7 | 2
1 und 2 kommen 3x vor, die 3 nur 2x. Damit ist es nach der Umrechnung
nicht mehr gleichverteilt.
Wenn man eine Schleife um rand() baut, die Rückgaben 6 und 7 verwirft
und rand() solange aufruft, bis maximal 5 zurückkommt, passt es.
Gruß
Christian
--
....Christian.Garbs....................................https://www.cgarbs.de
"Don't give up, lose interest." (Miranda Cornielle, Columbia Internet)
Rainer Weikusat
Jun 22, 2021, 4:21:25 PM6/22/21
to
Christian Garbs <mi...@cgarbs.de> writes:
> Mahlzeit!
> F. W. <m...@home.com> wrote:
>> Am 22.06.2021 um 08:18 schrieb Bonita Montero:
>>
>>>> srand (time (0));
>>>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>>
>>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>>
>> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
>
> Problematisch ist nicht die Genauigkeit der rand()-Funktion, sondern
> das Modulo. Problematisch ist nur die höchste, potenziell "halbe"
> Wiederholung, bis einschließlich RAND_MAX. Da müsste man etwas
> rumrechnen und die Ergebnisse, die in dem betroffenen Bereich liegen,
> wegwerfen und einfach nochmal würfeln.
Alternative: Man benutzt ein Bereichsgröße, durch die man RAND_MAX glatt
> Mahlzeit!
> F. W. <m...@home.com> wrote:
>> Am 22.06.2021 um 08:18 schrieb Bonita Montero:
>>
>>>> srand (time (0));
>>>> iGedachteZahl = (rand() % (iZahlMax - iZahlMin + 1)) + iZahlMin;
>>
>>> Wirklich gleichverteilt randomisiert ist das nicht unbedingt.
>>
>> Wie ginge es denn besser? Ich habe mir einen abgebrochen. :-)
>
> Problematisch ist nicht die Genauigkeit der rand()-Funktion, sondern
> das Modulo. Problematisch ist nur die höchste, potenziell "halbe"
> Wiederholung, bis einschließlich RAND_MAX. Da müsste man etwas
> rumrechnen und die Ergebnisse, die in dem betroffenen Bereich liegen,
> wegwerfen und einfach nochmal würfeln.
teilen kann. Für praktische Zwecke also eine 2er-Potenz < RAND_MAX. Sei
diese x, dann entpricht rand() % x rand & (x - 1), dh man reduziert das
Ergebnis auf eine bestimmte Zahl von Bits. Falls die Zahlen, die rand()
zurückliefert, gleichmäßig verteilt sind, muß das auch für jede
Untermenge der Bit-Werte einer solchen Zahl gelten.
jo...@schily.net
Jun 23, 2021, 7:46:36 AM6/23/21
to
In article <87wnqlk...@doppelsaurus.mobileactivedefense.com>,
auch nicht greift, wenn man einen Wertebewreich von z.B. 0..5 braucht.
Auch findest Du weder in der Solaris Doku, noch im POSIX Standard zu rand()
die Aussage, daß rand() gleichverteilte Zahlen liefert. Dieses Attribut
findest Du allerdings garantiert für drand48()
Rainer Weikusat <rwei...@talktalk.net> wrote:
>Alternative: Man benutzt ein Bereichsgröße, durch die man RAND_MAX glatt
>teilen kann. Für praktische Zwecke also eine 2er-Potenz < RAND_MAX. Sei
>diese x, dann entpricht rand() % x rand & (x - 1), dh man reduziert das
>Ergebnis auf eine bestimmte Zahl von Bits. Falls die Zahlen, die rand()
>zurückliefert, gleichmäßig verteilt sind, muß das auch für jede
>Untermenge der Bit-Werte einer solchen Zahl gelten.
Dumm nur, daß RAND_MAX typischerweise 32767 ist und daß Deine Methode halt
>Alternative: Man benutzt ein Bereichsgröße, durch die man RAND_MAX glatt
>teilen kann. Für praktische Zwecke also eine 2er-Potenz < RAND_MAX. Sei
>diese x, dann entpricht rand() % x rand & (x - 1), dh man reduziert das
>Ergebnis auf eine bestimmte Zahl von Bits. Falls die Zahlen, die rand()
>zurückliefert, gleichmäßig verteilt sind, muß das auch für jede
>Untermenge der Bit-Werte einer solchen Zahl gelten.
auch nicht greift, wenn man einen Wertebewreich von z.B. 0..5 braucht.
Auch findest Du weder in der Solaris Doku, noch im POSIX Standard zu rand()
die Aussage, daß rand() gleichverteilte Zahlen liefert. Dieses Attribut
findest Du allerdings garantiert für drand48()
Bonita Montero
Jun 23, 2021, 8:25:32 AM6/23/21
to
> Dumm nur, daß RAND_MAX typischerweise 32767 ...
Ist doch passend für einen 15-Bit-Shift.
Ist doch passend für einen 15-Bit-Shift.
Bonita Montero
Jun 23, 2021, 8:27:08 AM6/23/21
to
>> Dumm nur, daß RAND_MAX typischerweise 32767 ...
> Ist doch passend für einen 15-Bit-Shift.
Wenn man eine Zufallszahl von [0..N) haben will.
> Ist doch passend für einen 15-Bit-Shift.
Ansonsten addiert man auf das x in rand() * x eins drauf.
Helmut Schellong
Jun 23, 2021, 10:00:29 AM6/23/21
to
Ich wundere mich, daß rand() überhaupt noch verwendet wird.
Vor mehreren Jahrzehnten las ich, daß die völlig veraltet ist und
schlechte (miese) Eigenschaften hat.
Man solle doch random() oder [dl]rand48() nehmen.
Seit langer Zeit soll man noch besser arc4random() nehmen.
Seit einigen Jahren soll man noch viel besser spritz_random()
nehmen, weil die Verwendung von arc4random() in einigen
Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
https://de.wikipedia.org/wiki/RC4#Sicherheit
Bonita Montero
Jun 23, 2021, 10:35:13 AM6/23/21
to
> Seit einigen Jahren soll man noch viel besser spritz_random()
> nehmen, weil die Verwendung von arc4random() in einigen
> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
> https://de.wikipedia.org/wiki/RC4#Sicherheit
Du kennst wohl auch nicht die unterschiedlichen Notwendigkeiten
> nehmen, weil die Verwendung von arc4random() in einigen
> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
> https://de.wikipedia.org/wiki/RC4#Sicherheit
bei kryptografischen und nicht-kryptografischen PRNGs.
Helmut Schellong
Jun 23, 2021, 10:50:44 AM6/23/21
to
Aber rand() ist wirklich indiskutabel.
Ich begann 1987 mit lrand48().
Bonita Montero
Jun 23, 2021, 10:59:02 AM6/23/21
to
>>> Seit einigen Jahren soll man noch viel besser spritz_random()
>>> nehmen, weil die Verwendung von arc4random() in einigen
>>> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
>>> https://de.wikipedia.org/wiki/RC4#Sicherheit
>> Du kennst wohl auch nicht die unterschiedlichen Notwendigkeiten
>> bei kryptografischen und nicht-kryptografischen PRNGs.
> Kenne ich.
> Aber rand() ist wirklich indiskutabel.
> Ich begann 1987 mit lrand48().
Ich find das Nonplusultra aller nicht-kryptografischen PRNGs ist
>>> nehmen, weil die Verwendung von arc4random() in einigen
>>> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
>>> https://de.wikipedia.org/wiki/RC4#Sicherheit
>> Du kennst wohl auch nicht die unterschiedlichen Notwendigkeiten
>> bei kryptografischen und nicht-kryptografischen PRNGs.
> Kenne ich.
> Aber rand() ist wirklich indiskutabel.
> Ich begann 1987 mit lrand48().
der Mersenne Twister:
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;
int main()
{
using mt_type = mt19937_64;
using result_type = mt_type::result_type;
using hrc_tp = time_point<high_resolution_clock>;
mt_type mt;
result_type sum = 0;
hrc_tp start = high_resolution_clock::now();
for( size_t i = 1'000'000'000; i; --i )
sum += mt();
result_type volatile vsum = sum;
double ns = (int64_t)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 1'000'000'000.0;
cout << ns << endl;
}
Auf meinem Rechner braucht der für jedes 64-Bit-Ergebnis
ca. 3,5ns (ca. 15 Takte); es dürfte keinen PRNG der gleichen
Güte geben der so schnell ist.
Bonita Montero
Jun 23, 2021, 11:07:18 AM6/23/21
to
Rainer Weikusat
Jun 23, 2021, 1:53:08 PM6/23/21
to
jo...@schily.net writes:
> In article <87wnqlk...@doppelsaurus.mobileactivedefense.com>,
> Rainer Weikusat <rwei...@talktalk.net> wrote:
>
>>Alternative: Man benutzt ein Bereichsgröße, durch die man RAND_MAX glatt
> In article <87wnqlk...@doppelsaurus.mobileactivedefense.com>,
> Rainer Weikusat <rwei...@talktalk.net> wrote:
>
>>teilen kann. Für praktische Zwecke also eine 2er-Potenz < RAND_MAX. Sei
>>diese x, dann entpricht rand() % x rand & (x - 1), dh man reduziert das
>>Ergebnis auf eine bestimmte Zahl von Bits. Falls die Zahlen, die rand()
>>zurückliefert, gleichmäßig verteilt sind, muß das auch für jede
>>Ergebnis auf eine bestimmte Zahl von Bits. Falls die Zahlen, die rand()
>>Untermenge der Bit-Werte einer solchen Zahl gelten.
>
> Dumm nur, daß RAND_MAX typischerweise 32767 ist
Mein Fehler: Ich hatte angenommen, RAND_MAX sei die Anzahl möglicher
>
> Dumm nur, daß RAND_MAX typischerweise 32767 ist
Zahlen und nicht die größte davon. Dh man muß im ersten Satz anstelle
von RAND_MAX RAND_MAX + 1 nehmen. Der mit den 2er-Potenzen stimmt auch
so (wenn die zugrundeliegende Annahme über den Wertebereich der
erzeugten Zahlen stimmt).
Thomas Koenig
Jun 23, 2021, 3:07:48 PM6/23/21
to
Helmut Schellong <r...@schellong.biz> schrieb:
Und für ein Zahlenraten-Spiel reicht die Qualität allemal.
> Vor mehreren Jahrzehnten las ich, daß die völlig veraltet ist und
> schlechte (miese) Eigenschaften hat.
Typischerweise steht ein linearer Kongruenzgenerator dahinter.
Schnell zu implentieren, aber für ernsthafte Anwendungen nicht
wirklich zu gebrauchen.
> Man solle doch random() oder [dl]rand48() nehmen.
>
> Seit langer Zeit soll man noch besser arc4random() nehmen.
Ist das eine BSD-Spezialität?
> On 06/23/2021 14:27, Bonita Montero wrote:
>>>> Dumm nur, daß RAND_MAX typischerweise 32767 ...
>>
>>> Ist doch passend für einen 15-Bit-Shift.
>>
>> Wenn man eine Zufallszahl von [0..N) haben will.
>> Ansonsten addiert man auf das x in rand() * x eins drauf.
>>
> .
> Ich wundere mich, daß rand() überhaupt noch verwendet wird.
Komptatibilität.
>>>> Dumm nur, daß RAND_MAX typischerweise 32767 ...
>>
>>> Ist doch passend für einen 15-Bit-Shift.
>>
>> Wenn man eine Zufallszahl von [0..N) haben will.
>> Ansonsten addiert man auf das x in rand() * x eins drauf.
>>
> .
> Ich wundere mich, daß rand() überhaupt noch verwendet wird.
Und für ein Zahlenraten-Spiel reicht die Qualität allemal.
> Vor mehreren Jahrzehnten las ich, daß die völlig veraltet ist und
> schlechte (miese) Eigenschaften hat.
Schnell zu implentieren, aber für ernsthafte Anwendungen nicht
wirklich zu gebrauchen.
> Man solle doch random() oder [dl]rand48() nehmen.
>
> Seit langer Zeit soll man noch besser arc4random() nehmen.
jo...@schily.net
Jun 23, 2021, 3:51:59 PM6/23/21
to
In article <sb00q3$rl8$1...@newsreader4.netcologne.de>,
Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
vor vielen Jahren zurückgezogen.
Thomas Koenig <tko...@netcologne.de> wrote:
>>
>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>
>Ist das eine BSD-Spezialität?
>>
>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>
Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
vor vielen Jahren zurückgezogen.
Christian Weisgerber
Jun 23, 2021, 5:30:04 PM6/23/21
to
On 2021-06-23, Helmut Schellong <r...@schellong.biz> wrote:
> Seit langer Zeit soll man noch besser arc4random() nehmen.
>
> Seit einigen Jahren soll man noch viel besser spritz_random()
> nehmen, weil die Verwendung von arc4random() in einigen
> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
>
> https://de.wikipedia.org/wiki/RC4#Sicherheit
arc4random() ist eine API und hat mit der RC4-Stromchiffre nichts
> Seit langer Zeit soll man noch besser arc4random() nehmen.
>
> Seit einigen Jahren soll man noch viel besser spritz_random()
> nehmen, weil die Verwendung von arc4random() in einigen
> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
>
> https://de.wikipedia.org/wiki/RC4#Sicherheit
zu tun.
Christian Weisgerber
Jun 23, 2021, 6:30:05 PM6/23/21
to
On 2021-06-23, jo...@schily.net <jo...@schily.net> wrote:
>>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>
>>Ist das eine BSD-Spezialität?
>
> Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
> vor vielen Jahren zurückgezogen.
Solaris hat es.
>>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>
>>Ist das eine BSD-Spezialität?
>
> Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
> vor vielen Jahren zurückgezogen.
Christian Weisgerber
Jun 23, 2021, 6:30:05 PM6/23/21
to
On 2021-06-23, Thomas Koenig <tko...@netcologne.de> wrote:
>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>
> Ist das eine BSD-Spezialität?
Das ist inzwischen weithin verfügbar.
>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>
> Ist das eine BSD-Spezialität?
Helmut Schellong
Jun 23, 2021, 8:04:48 PM6/23/21
to
On 06/23/2021 21:07, Thomas Koenig wrote:
> Helmut Schellong <r...@schellong.biz> schrieb:
>> On 06/23/2021 14:27, Bonita Montero wrote:
>>>>> Dumm nur, daß RAND_MAX typischerweise 32767 ...
>>>
>>>> Ist doch passend für einen 15-Bit-Shift.
>>>
>>> Wenn man eine Zufallszahl von [0..N) haben will.
>>> Ansonsten addiert man auf das x in rand() * x eins drauf.
>>>
>> .
>> Ich wundere mich, daß rand() überhaupt noch verwendet wird.
>
> Komptatibilität.
>
> Und für ein Zahlenraten-Spiel reicht die Qualität allemal.
Ja, auf jeden Fall.
> Helmut Schellong <r...@schellong.biz> schrieb:
>> On 06/23/2021 14:27, Bonita Montero wrote:
>>>>> Dumm nur, daß RAND_MAX typischerweise 32767 ...
>>>
>>>> Ist doch passend für einen 15-Bit-Shift.
>>>
>>> Wenn man eine Zufallszahl von [0..N) haben will.
>>> Ansonsten addiert man auf das x in rand() * x eins drauf.
>>>
>> .
>> Ich wundere mich, daß rand() überhaupt noch verwendet wird.
>
> Komptatibilität.
>
> Und für ein Zahlenraten-Spiel reicht die Qualität allemal.
>> Vor mehreren Jahrzehnten las ich, daß die völlig veraltet ist und
>> schlechte (miese) Eigenschaften hat.
>
> Typischerweise steht ein linearer Kongruenzgenerator dahinter.
> Schnell zu implentieren, aber für ernsthafte Anwendungen nicht
> wirklich zu gebrauchen.
>
>> Man solle doch random() oder [dl]rand48() nehmen.
>>
>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>
> Ist das eine BSD-Spezialität?
>
NAME
arc4random, arc4random_buf, arc4random_uniform, arc4random_stir,
arc4random_addrandom - arc4 random number generator
LIBRARY
Standard C Library (libc, -lc)
SYNOPSIS
#include <stdlib.h>
uint32_t
arc4random(void);
void
arc4random_buf(void *buf, size_t nbytes);
uint32_t
arc4random_uniform(uint32_t upper_bound);
void
arc4random_stir(void);
void
arc4random_addrandom(unsigned char *dat, int datlen);
DESCRIPTION
The arc4random() function uses the key stream generator employed by the
arc4 cipher, which uses 8*8 8 bit S-Boxes. The S-Boxes can be in about
(2**1700) states. The arc4random() function returns pseudo-random
numbers in the range of 0 to (2**32)-1, and therefore has twice
the range of rand(3) and random(3).
--------------------------------------------------------------------
Ich selbst habe 'Spritz' implementiert, den Nachfolger.
Der liest u.a. aus einem uninitialisierten Puffer im Stack, um
niemals gleiche Sequenzen zu generieren.
Helmut Schellong
Jun 23, 2021, 8:08:49 PM6/23/21
to
On 06/23/2021 21:51, jo...@schily.net wrote:
> In article <sb00q3$rl8$1...@newsreader4.netcologne.de>,
> Thomas Koenig <tko...@netcologne.de> wrote:
>>>
>>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>
>> Ist das eine BSD-Spezialität?
>
> Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
> vor vielen Jahren zurückgezogen.
>
.
> In article <sb00q3$rl8$1...@newsreader4.netcologne.de>,
> Thomas Koenig <tko...@netcologne.de> wrote:
>>>
>>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>
>> Ist das eine BSD-Spezialität?
>
> Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
> vor vielen Jahren zurückgezogen.
>
Man sollte auch besser den Nachfolger 'Spritz' standardisieren.
Im Krypto-Bereich ist Arc4 seit 2015 teils verboten.
Helmut Schellong
Jun 23, 2021, 8:11:00 PM6/23/21
to
On 06/23/2021 23:11, Christian Weisgerber wrote:
> On 2021-06-23, Helmut Schellong <r...@schellong.biz> wrote:
>
>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>
>> Seit einigen Jahren soll man noch viel besser spritz_random()
>> nehmen, weil die Verwendung von arc4random() in einigen
>> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
>>
>> https://de.wikipedia.org/wiki/RC4#Sicherheit
>
> arc4random() ist eine API und hat mit der RC4-Stromchiffre nichts
> zu tun.
>
Es wird die typische S-Box verwendet.
> On 2021-06-23, Helmut Schellong <r...@schellong.biz> wrote:
>
>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>
>> Seit einigen Jahren soll man noch viel besser spritz_random()
>> nehmen, weil die Verwendung von arc4random() in einigen
>> Bereichen inzwischen verboten ist, wegen ungenügender Eigenschaften.
>>
>> https://de.wikipedia.org/wiki/RC4#Sicherheit
>
> arc4random() ist eine API und hat mit der RC4-Stromchiffre nichts
> zu tun.
>
Das ist der Kern des Algorithmus.
Enrik Berkhan
Jun 24, 2021, 1:13:06 AM6/24/21
to
Christian Weisgerber <na...@mips.inka.de> wrote:
> arc4random() ist eine API und hat mit der RC4-Stromchiffre nichts
> zu tun.
Hier (libbsd auf Ubuntu) steht in der man page:
> arc4random() ist eine API und hat mit der RC4-Stromchiffre nichts
> zu tun.
"The original version of this random number generator used the RC4 (also
known as ARC4) algorithm. In OpenBSD 5.5 it was replaced with the
ChaCha20 cipher, and it may be replaced again in the future as
cryptographic techniques advance. A good mnemonic is “A Replacement
Call for Random”."
"nichts zu tun" finde ich da nicht ganz passend, falls die Aussage
stimmt.
Gruß,
Enrik
Helmut Schellong
Jun 24, 2021, 6:27:40 AM6/24/21
to
ARC4RANDOM(3) FreeBSD Library Functions Manual ARC4RANDOM(3)
...
HISTORY
RC4 has been designed by RSA Data Security, Inc. It was posted
anonymously to the USENET and was confirmed to be equivalent
by several sources who had access to the original cipher.
Since RC4 used to be a trade secret, the cipher is now referred
to as ARC4.
jo...@schily.net
Jun 24, 2021, 6:43:21 AM6/24/21
to
In article <slrnsd7a50...@lorvorc.mips.inka.de>,
>
>Solaris hat es.
Du meinst vemutlich Illumos?
Christian Weisgerber <na...@mips.inka.de> wrote:
>On 2021-06-23, jo...@schily.net <jo...@schily.net> wrote:
>
>>>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>>
>>>Ist das eine BSD-SpezialitĆ Ā¤t?
>On 2021-06-23, jo...@schily.net <jo...@schily.net> wrote:
>
>>>> Seit langer Zeit soll man noch besser arc4random() nehmen.
>>>
>>
>> Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
>> vor vielen Jahren zurĆ¼ckgezogen.
>> Ja es scheint so und wie ich schrieb, wurde der Antrag das zu standardisieren
>
>Solaris hat es.
Du meinst vemutlich Illumos?
Christian Weisgerber
Jun 24, 2021, 4:55:06 PM6/24/21
to
On 2021-06-24, Enrik Berkhan <Enrik....@inka.de> wrote:
>> arc4random() ist eine API und hat mit der RC4-Stromchiffre nichts
>> zu tun.
>
> Hier (libbsd auf Ubuntu) steht in der man page:
>
> "The original version of this random number generator used the RC4 (also
> known as ARC4) algorithm. In OpenBSD 5.5 it was replaced with the
> ChaCha20 cipher, and it may be replaced again in the future as
> cryptographic techniques advance. A good mnemonic is “A Replacement
> Call for Random”."
Korrekt.
>> arc4random() ist eine API und hat mit der RC4-Stromchiffre nichts
>> zu tun.
>
> Hier (libbsd auf Ubuntu) steht in der man page:
>
> "The original version of this random number generator used the RC4 (also
> known as ARC4) algorithm. In OpenBSD 5.5 it was replaced with the
> ChaCha20 cipher, and it may be replaced again in the future as
> cryptographic techniques advance. A good mnemonic is “A Replacement
> Call for Random”."
arc4random(), arc4random_buf(), arc4random_uniform() sind erstmal
eine Programmierschnittstelle, die Zufallszahlen liefert. Wie diese
erzeugt werden, ist ein Implementierungsdetail, das den Anwender
der Schnittstelle nicht zu interessieren braucht.
Dass eine historische Implementierung einmal RC4 verwendet hat, tut
der Programmierschnittstelle keinen Abbruch. Aktuelle Implementierungen
verwenden andere Algorithmen. RC4 als Argument gegen arc4random()
ins Feld zu führen, ist eine reine Nebelkerze.
Thomas Koenig
Jun 24, 2021, 5:07:10 PM6/24/21
to
Christian Weisgerber <na...@mips.inka.de> schrieb:
> Dass eine historische Implementierung einmal RC4 verwendet hat, tut
> der Programmierschnittstelle keinen Abbruch. Aktuelle Implementierungen
> verwenden andere Algorithmen. RC4 als Argument gegen arc4random()
> ins Feld zu führen, ist eine reine Nebelkerze.
Frage ist halt, wofür man das verwendet. Die Kritik scheint
sich vor allem auf kryptographische Anwendungen zu konzentrieren.
Mich würde arg wundern, wenn eine früher mal als Verschlüsselung
gedachte Stromchiffre bei einer Monte-Carlo-Simulation miese
Ergebnisse liefen würde (wofür lineare Kongruenzgeneratoren
berüchtigt sind).
> Dass eine historische Implementierung einmal RC4 verwendet hat, tut
> der Programmierschnittstelle keinen Abbruch. Aktuelle Implementierungen
> verwenden andere Algorithmen. RC4 als Argument gegen arc4random()
> ins Feld zu führen, ist eine reine Nebelkerze.
sich vor allem auf kryptographische Anwendungen zu konzentrieren.
Mich würde arg wundern, wenn eine früher mal als Verschlüsselung
gedachte Stromchiffre bei einer Monte-Carlo-Simulation miese
Ergebnisse liefen würde (wofür lineare Kongruenzgeneratoren
berüchtigt sind).
Thomas Koenig
Dec 17, 2021, 2:54:50 AM12/17/21
to
Stefan Ram <r...@zedat.fu-berlin.de> schrieb:
Siehe hierzu auch
https://dilbert.com/strip/2001-10-25 und https://xkcd.com/221/ .
(Wenn rand() die standard-library-Funktion ist, dann ist das
allerdings eine eher schlechte Idee. Die dort typischerweise
verwendeten linearen Kongruenzgeneratoren haben schlechtere
Eigenschaften, wenn man sich die niederwerigen Bits anschaut.)
> Christian Garbs <mi...@cgarbs.de> writes:
>>Wenn man eine Schleife um rand() baut, die Rückgaben 6 und 7 verwirft
>>und rand() solange aufruft, bis maximal 5 zurückkommt, passt es.
>
> Man hat aber keine Garantie, daß dies terminiert.
>>Wenn man eine Schleife um rand() baut, die Rückgaben 6 und 7 verwirft
>>und rand() solange aufruft, bis maximal 5 zurückkommt, passt es.
>
Siehe hierzu auch
https://dilbert.com/strip/2001-10-25 und https://xkcd.com/221/ .
(Wenn rand() die standard-library-Funktion ist, dann ist das
allerdings eine eher schlechte Idee. Die dort typischerweise
verwendeten linearen Kongruenzgeneratoren haben schlechtere
Eigenschaften, wenn man sich die niederwerigen Bits anschaut.)
0 new messages