Praktikum 5: Modulo Funktion

Benutzeravatar
DerWildeKaiser
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 16. Jan 2008 12:29

Praktikum 5: Modulo Funktion

Beitrag von DerWildeKaiser »

Wenn man die Java-Interne Modulo Funktion verwendet, kann es sein, dass man ein negatives Ergebnis zurückgegeben bekommt (z.B. bei der "quadratic_probing"-Methode)

Um das zu umgehen habe ich eine eigene Modulo-Methode implementiert und mich dabei an den Wikipedia-Artikel gehalten:
\((a\;\bmod\;m)= a - \left \lfloor \frac{a}{m} \right \rfloor \cdot m\)

In Java hab ich das so realisiert:

Code: Alles auswählen

private int mod(long a, long m){
	return (int)(a - (Math.floor(a/m)*m));
}
Wenn man nun mod(-1, 10) aufruft (zu diesem Fall kommt es in einem Test), liefert die Methode -1 zurück, was sie eigentlich nicht sollte.
Man könnte natürlich einfach immer den Absolut-Betrag zurück geben, aber ob das im Sinne der Aufgabenstellung ist!?

Benutzeravatar
Wang Tang
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 5. Dez 2006 17:57

Re: Praktikum 5: Modulo Funktion

Beitrag von Wang Tang »

Absolutbetrag wäre in vielen Fällen falsch, Beispiel:
-1 mod 10 = 9 != 1 = |-1 % 10|.

Man kann das z.B. mit ner Schleife lösen, die solange m zu b = a%m addiert, bis b >= 0 ist. Einen besseren Weg hab ich noch nicht gefunden, is halt schon recht blöd, dass in Java nur remainer und kein echtes mod eingebaut ist :/

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Maeher »

Die Gaußklammer \(\lfloor \cdot \rfloor\) bezeichnet die größte ganze Zahl, die kleiner oder gleich der Zahl in der Gaußklammer ist, also ohne den Rest der Division a:m. Für diese Variante gilt stets
z.B. also \(\lfloor -1{,}5 \rfloor = -2\)

Wie die rundungsfunktion von Java arbeitet weiß ich gerade nicht, ist aber irrelevant, da du eine ganzzahlige Division machst. -3/2 ergibt also bereits -1 anstatt den geforderten -2. Das runden ändert daran nichts.

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Mspringer »

Jo, ist mir schon vor Tagen aufgefallen und hatte mich gewundert, da meines Wissens nach modulo keine Zahl kleiner 0 als Ergebnis hat. Ich habs einfach gelöst in dem ich:

Code: Alles auswählen

if(address < 0)
   address = address + m;
gemacht habe.

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Maeher »

Hängt halt von der Definition von modulo ab. Kann als betragsmäßig kleinstmöglicher Rest, oder als kleinstmöglicher positiver Rest definiert sein.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Praktikum 5: Modulo Funktion

Beitrag von oren78 »

DerWildeKaiser hat geschrieben:Wenn man die Java-Interne Modulo Funktion verwendet, kann es sein, dass man ein negatives Ergebnis zurückgegeben bekommt (z.B. bei der "quadratic_probing"-Methode)
hatte ebenfalls das problem, die abhilfe war ein ganz simples: Math.abs(Adressposition) danach liefen die "quadratic_probing" cases bei mir durch...versuchs einfach mal....
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Mspringer »

Da wäre ich Vorsichtig. -1 mod 97 = 96 != 1 = 1 mod 97
Zuletzt geändert von Mspringer am 19. Jun 2008 13:49, insgesamt 3-mal geändert.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Praktikum 5: Modulo Funktion

Beitrag von oren78 »

also, ich weiß nicht warum, aber jedenfalls wenn ich als adresslänge (in der hashtabelle) KONSTANT 3 wähle laufen bei mir alle testcases durch, was meiner meinung nach totaler schwachsinn ist, da die adresslänge ja irgendwo dynamisch sein soll, sprich:

Hashtabellengröße: 10 = Adresslänge: 2
Hashtabellengröße: 100 = Adresslänge: 3
Hashtabellengröße: 1000 = Adresslänge: 4
usw...

ob das jetzt so gewollt ist erkenne ich aus der recht schwammigen aufgabenstellung nicht, aber hauptsache der müll läuft durch :D
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Mspringer »

oren78 hat geschrieben:also, ich weiß nicht warum, aber jedenfalls wenn ich als adresslänge (in der hashtabelle) KONSTANT 3 wähle laufen bei mir alle testcases durch, was meiner meinung nach totaler schwachsinn ist, da die adresslänge ja irgendwo dynamisch sein soll, sprich:

Hashtabellengröße: 10 = Adresslänge: 2
Hashtabellengröße: 100 = Adresslänge: 3
Hashtabellengröße: 1000 = Adresslänge: 4
usw...

ob das jetzt so gewollt ist erkenne ich aus der recht schwammigen aufgabenstellung nicht, aber hauptsache der müll läuft durch :D
Nein!

Hashtabellengröße: 10 = Adresslänge: 1 [0 - 9]
Hashtabellengröße: 100 = Adresslänge: 2 [0-99]
Hashtabellengröße: 1000 = Adresslänge: 3 [0 - 999]

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Praktikum 5: Modulo Funktion

Beitrag von oren78 »

hups...sorry, hast recht markus !! danke ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Maeher »

Mspringer hat geschrieben:Da wäre ich Vorsichtig. -1 mod 97 = 96 != 1 = 1 mod 97
Ich weiß nicht auf welches modulo du dich jetzt beziehst, aber das sogenannte symmetrische modulo wie es in Java verwendet wird, kriegt für -1 mod 97 eben -1 raus und nicht 96.

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Mspringer »

Das ist doch gerade der Punkt. Les doch mal den Beitrag vorher durch und nicht nur meinen ;)

Can
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 223
Registriert: 17. Okt 2006 15:14
Kontaktdaten:

Re: Praktikum 5: Modulo Funktion

Beitrag von Can »

Also ich hab das ganz einfach mit:

Code: Alles auswählen

if(h_i < 0) h_i += hashTable.length;
gelöst.
Sollte somit die negativen modulos richtig abdecken.
Cogito ergo sum

Antworten

Zurück zu „Archiv“