Zufälliger Long

[Naaram]

Hallo,

ich habe folgendes Problem. Ich muss Klassen schreiben (und das ist keien Hausaufgabe ), die Longs bzw. Integer in einem Intervall zufällig generiert. Im Unterschied zum Java: random long number in 0 <= x < n range - Stack Overflow soll auch die Generierung negativer zahlen möglich sein. Hat das jemand schon mal gemacht?

Ich habe etwas Angst da selbst was zu basteln.

 

[parabool]

Wenn du schon was funktionierendes hast:
Einen zweiten Zufallswert generieren der 0 oder 1 annehmen kann
und dann den 1. Zufallswert (je nach Ergebnis) mit -1 oder 1 (oder nicht) multiplizieren.


Edit: oder so: http://www.java-forum.org/java-basics-anfaenger-themen/86886-zufallszahl-negativbereich.html

 

[Naaram]

Naja das Problem ist folgendes, nehmen wir an, ich muss eine Zufallszahl zwischen -5.000.000.000 und 5.000.000.000 erzeugen. Wenn ich nun ein Random-Boolean erzeuge (für Vorzeichen), und danach eine Random-Zahl zwischen 0 und 5.000.000.000, dann ist die Chance für die 0 doppelt so groß. Wenn ich die 0 aber bei den negativen Zahlen rausnehme, dann ist die Chance auf eine bestimmte negative Zahl um 1/5.000.000.000 höher als auf eine entsprechende positive Zahl.

 

[SlaterB]

Standardvorgehen:
du erstellst eine Zufallszahl zwischen 0 und 10 Mio. und ziehst dann 5 Mio. ab

 

[Spacerat]

Lass dir Zahlen zwischen 0 und 10.000.000.000 erzeugen und zieh' 5.000.000.000 ab oder geht das nicht?
[EDIT]much too slow ... SlaterB meint sicher auch 10 Mrd.[/EDIT]

 

[Naaram]

Lass dir Zahlen zwischen 0 und 10.000.000.000 erzeugen und zieh' 5.000.000.000 ab oder geht das nicht?

Nein das mache ich jetzt genau so, aber das funktioniert nicht für hinreichend große n. Java hat ja keine unsigned typen.

 

[SlaterB]

na dann prüfe erst ob positiv oder negativ, und erstelle dann im positiven Fall 0-Max,
im negativen Fall nur von 0-Max-1 und bilde das auf -1 bis -Max ab,

wie auch immer das zu verschieben ist, das negative Maximum ist ja eh größer,
also wahrscheinlich doch 0-Max, auf -1 bis -Max-1 verschieben

(-9223372036854775808 ... 9223372036854775807)

edit: ich las irgendwie, dass es um den kompletten Long-Bereich geht, aber das steht ja doch nirgendwo,
was ist denn das Problem, welches 'hinreichend große n' ist gemeint? muss es bis zu 18 Stellen gehen?
mit einem unsigned wärst du doch nicht besser dran wenn du dann gar keine negativen Zahlen darstellen kannst?

 

[Spacerat]

Nein das mache ich jetzt genau so, aber das funktioniert nicht für hinreichend große n. Java hat ja keine unsigned typen.

Also 10 Mrd. passen noch in ein int. Ich weiss jetzt nicht was hinreichend grosse Zahlen sind. Im Zweifelsfall kann man auch mit "<Random>.nextBytes(byte[] target)" ein Bytearray erstellen und damit einen BigInteger instanzieren. Speziell für Primzahlen gibt es noch "BigInteger.probablePrime(int bitLength, Random rnd)".

 

[nillehammer]

Erzeug Dir mit Random zwei ints und shifte/odere sie in ein long. So geht's:

	public static long nextRandomSignedLong(final Random rnd) {

		long result = rnd.nextInt();
		
		result = result << Integer.SIZE;
		
		result |= rnd.nextInt();

		return result;
	}

[EDIT]
Ah, warte mal. Die Intervall-Anforderung hab ich garnicht beachtet! Hmm, noch mal bischen nachdenken...
[/EDIT]

 

[Spacerat]

[EDIT]
Ah, warte mal. Die Intervall-Anforderung hab ich garnicht beachtet! Hmm, noch mal bischen nachdenken...
[/EDIT]

Halb so wild. "(result & 0x7FFFFFFF) % intervall * 2 - intervall". Super Idee.

 

[Naaram]

Leider kommen bei rng.nextInt() % n keine gleichverteilten Zufallszahlen raus. Deswegen braucht man ja die Schleife.

 

[SlaterB]

mit 'die Schleife' meinst du den Link im ersten Posting?
zum Glück bin ich so schlau das nun alles zu verstehen (und mich auch selbst zu loben )

Random.nextLong(long n)
gibt es in der Tat nicht,
also nutze
nextLong(Random rng, long n)
aus dem Link

wie ich geschrieben habe zusammen mit

na dann prüfe erst ob positiv oder negativ, und erstelle dann im positiven Fall 0-Max,
im negativen Fall nur von 0-Max-1 und bilde das auf -1 bis -Max ab,

edit: ach nö, würde die wenigeren negativen Zahlen bevorzugen, falls diese weniger sind als 0 bis Max

------

oder auch die 'Standard-Variante', die dann auch die Methode aus dem Link braucht,
und erkläre was du mit 'funktioniert nicht für hinreichend große n' meinst

 

[nillehammer]

Leider kommen bei rng.nextInt() % n keine gleichverteilten Zufallszahlen raus. Deswegen braucht man ja die Schleife.

Dazu zunächst die API-Doc von Random.nextInt():

Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence.

Die Zahlen sind in dieser Implementierung also zwar nur pseudo-zufällig aber zumindest gleichverteilt.

Durch das Modulo ergeben sich aber tatsächlich Verschiebungen. Long geht im Negativen bis -xxxx7 und im Positiven bis xxxx8. Dadurch ergibt sich eine gerinfügig höhere Wahrscheinlichkeit für bestimmte Werte, je nachdem wie die Grenze gewählt wurde. Das wäre im Code noch zu berücksichtigen. Ich glaube, das hat Spacerat schon getan, wenn man sich seinen Beitrag im Antwort- oder Zitatmodus anschaut, hat er nämlich nicht einfach Modulo (%) geschrieben, sondern das hier:

(result & 0x7FFFFFFF) % intervall * 2 - intervall

 

[bone2]

Gibts doch alles fertig :S

        BigInteger c = new BigInteger(16, new Random());
        System.out.println(c);

ergibt ne gwünschte länge, muss man nur noch nach rechts oder linke schieben je nach anfang

[EDIT]einen makel entdeckt, den mein kopf gerade nich lösen mag.
man kann damit nur rnd zahlen in ganzen bit schritten erzeugen

bei 10 bis 20 wären es min 4 bit für die 10 range aber 4 bit ist ja 0-15[/EDIT]

 

[SlaterB]

schon wieder so ein Thread mit so vielen halben Lösungen..,

eine Korrektur habe ich noch anzumerken @nillehammer/ Spacerat:
> long result = rnd.nextInt();
> result = result << Integer.SIZE;
> result |= rnd.nextInt();

hier muss die dritte Zeile
> result |= (rnd.nextInt() & 0xFFFF);
lauten, sonst werden die 32 führenden 1en bei einem negativen zweiten Wert per | übernommen

vor dem Modulo lag die Wahrscheinlichkeit auf einen negativen Wert bei 75%,
durch das Modulo mag es gar nicht mehr unbedingt ein Problem sein

aber wo nun welche Wahrscheinlichkeiten abweichen, da klinke ich mich doch besser aus..

 

[nillehammer]

@SlaterB: Danke für den Hinweis! Ich war bis jetzt immer davon ausgegangen, dass bei logischen Operationen die Bitmasken "as is" unter einander gelegt werden. Dass sie ggf. upgecastet werden, was bei negativen Zahlen natürlich das Auffüllen mit einsen bedeutet, ist mir nie aufgefallen! (So einen Anwendungsfall hatte ich aber ehrlich gesagt auch noch nicht).