Zufall wird nicht größer als 327**

Stromberg

Ich beschäftige mich grad mit dem sortieren, und da wollte ich in ein Feld zufällige Werte reinschreiben, die dann anschließend von meiner Funktion "Sort" sortiert werden. So aber irgendwie wird die Zufallszahl nicht größer als 327** und da stört mich irgendwie, da ich eigentlich einen Zufallsrange zwischen 0-50000 wollte (oder später vll. höher).

#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;

long rnd(long a,long b);
void Swap(int &a,int &b);
void Sort(int *array,int size);

int main()
{
    srand(time(0));
    rand();

    int data[30000];
    for (int i=0;i<30000;i++)
    {
        data[i]=rnd(0,50000); //<-- wird nicht größer als 327**
    }

    int anfang=time(0);

    Sort(data,30000);

    int ende=time(0);
    for (int i=0;i<30000;i++)
    {
        cout << data[i] << "\n";
    }
    cout << "Es sind " << ende-anfang << " Sekunden vergangen.\n";
    getch();

    return 0;
}

void Sort(int *array,int size)
{
    int minPos;
    for (int feld=0;feld<size-1;feld++)
    {
        minPos=feld;
        for (int i=feld+1;i<size;i++)
        {
            if (array[i]<array[minPos])
            {
                minPos=i;
            }
        }
        Swap(array[feld],array[minPos]);
    }
}

void Swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

long rnd(long a,long b)
{
     return (rand() % (b-a+1)) + a;
}

Nanuq

Der Wertebereich von int reicht nur bis 2^15-1 also 32767. rand() gibt ein int zurück.

MSDN schrieb:

The rand function returns a pseudorandom integer in the range 0 to RAND_MAX (32767).

Edit: Obwohl dein rnd natürlich größere Zahlen zurückgibt...
Auf was du abgesehen davon aufpassen solltest: du weist die long-Werte, die dein rnd zurückgibt, einem int-Feld zu:

int data[30000];

Stromberg

Wie meinst du das mit größeren Zahlen? Wie schaffe ich es den, das meine "rnd" Funktion größere Zahlen als 32767 zurückgibt?

multiplikation

Nanuq

Du verwendest die Funktion rand() und die gibt definitiv maximal 32767 zurück.

Diese Berechnung:

return (rand() % (b-a+1)) + a;

ergibt entsprechend für a = 0 und b = 50000 nicht Werte zwischen 0 und 50000 sondern zwischen 0 und 32767.

eine möglichkeit schrieb:

mulitplikation

Durch Multiplikation zweier rand()-Ergebnisse kannst du dir natürlich größere Zahlen generieren

otze

die lösung des problems könnte in etwa so sein:

long rnd(long a,long b)
{
    int SQRandMax=std::sqrt(b-a+1);

    return (rand() % SQRandMax)*(rand() % SQRandMax) + a;
}

camper

otze schrieb:

die lösung des problems könnte in etwa so sein:

long rnd(long a,long b)
{
    int SQRandMax=std::sqrt(b-a+1);

    return (rand() % SQRandMax)*(rand() % SQRandMax) + a;
}

Das liefert allerdings keine Gleichverteilung. Wie man sofort sieht, liefert das Produkt schon mal keine Primzahlen zwischen SQRandMax und (b-a+1). Mein Vorschlag wäre

long rnd(long a,long b)
{
    return (rand()*(RAND_MAX+1)+rand()) % (b-a+1) + a;
}

[

Multiplikation ist echt ne ... Lösung:

long rnd()
{
    unsigned long l = rand();
    unsigned long l2 = rand();
    return l << (sizeof(int) / 8) + l2;
}

oder so ähnlich...

Durch Bit-shifting halt...

Stelfer

Shifter schrieb:

Multiplikation ist echt ne ... Lösung:
long rnd()
{
    unsigned long l = rand();
    unsigned long l2 = rand();
    return l << (sizeof(int) / 8) + l2;
}
oder so ähnlich...

Durch Bit-shifting halt...

dann verlierst du die 0 und 1

walljumper

Alle zahlen bis 50000 wird er eh nie durch multiplikation erreichen können. Bei Primzahlen wäre das unmöglich.

Addition wäre da besser zwei rand() funktionen die von 0-25000 gehen wären eine bessere Lösung.

hustbaer

Das einfachste wäre wohl einen Generator zu verwenden der einen definierten Wertebereich ausspuckt, also z.B. fix 0 - (2^32-1) oder sowas. z.B. den boost::mt19937 aus Boost.Random.

Alles andere wird schnell ein wenig kompliziert wenn das Programm für beliebige Werte von RAND_MAX funktionieren soll.

Der Vorschlag von camper ist gut solange 0 - (RAND_MAX+1)^2-1 als Wertebereich ausreichend ist, und RAND_MAX klein genug ist dass es dabei nicht zu einem Überlauf kommt.

CodeFinder

Guckt Ihr:

http://www.c-plusplus.net/forum/viewtopic.php?t=39343
http://www.c-plusplus.net/forum/viewtopic.php?t=39344
http://www.c-plusplus.net/forum/viewtopic.php?t=39331

hustbaer

@CodeFinder:

und wo genau steht dort irgendetwas hilfreiches zur Frage wie man den Bereich der Zufallszahlen erweitern kann?