suche einen Beweis für das Verhalten von Integern
Jochen Theodorou
mir geht es hier um das Überlauferhalten von Integern. int in Java wäre
ein Beispiel.
nun ist es so, dass Operationen wie +,*,- zu diesem Überlaufverhalten
führen kann. Für Java gilt bei diesen Operationen, dass alles was die 32
Bit übersteigen würde abgeschnitten wird. x+y kann also zum Beispiel ein
negatives Ergebnis haben, obwohl x und y positiv sind. Es gilt auch,
dass alle Zwischenergebnisse immer vom Typ int sind. Ein
Informationsverlust ist also möglich.
Würden jetzt die Zwischenergebnisse nicht das Überlaufverhalten zeigen
und sich immer entsprechend vergrößern, würde man natürlich andere
Ergebnisse erhalten... was aber wenn man das Ergebnis dann durch
abschneiden überflüssiger Bits in einen int packt? Ergeben sich dann
noch immer anderen Ergebnisse?
Als Beispiel:
2^31 * 2 = 2^32
nun passt 2^32 nicht in einen positiven int, statt dessen erhält man
einen int, der nur ein gesetztes Vorzeichenbit hat, also die kleinste
mögliche int Zahl repräsentiert. Mehr Bits für das Zwischenergebnis zur
Verfügung zu haben macht in diesem Fall also keinen Unterschied.
2^31 * 2^31 = 2^62
Das ist eine Zahl, wo das 62te Bit gesetzt ist, das existiert für int
aber nicht, also ergibt sich als Ergebnis 0. Auch hier hat das keine
Auswirkung. Offensichtlich braucht man komplexere Formeln um wirklich
einen Unterschied zu sehen.
2^31 * 2^31 - 1 = 2^62 - 1
gemäß obigen ergibt sich hier für int -1, denn 2^31*2^31 ist ja 0, also
ist 0-1=-1. Rechne ich mit dem genauen Ergebnis und mache dann daraus
einen int, dann erhalte ich allerdings auch -1. Wieder macht es keinen
Unterschied.
Ich suche also entweder einen Beweis das ich hier beliebig komplexe
Formeln bauen kann ohne dass sich das Endergebnis unterscheiden wird,
oder ein Gegenbeispiel.
Meine Vermutung ist ja, dass es einen Unterschied macht, allerdings
wüsste ich gerne unter welchen Umständen. Wie muss die Formeln geartet
sein damit es einen Unterschied macht?
Zumindest ein paar Hinweise wären super
Gruss theo
Sebastian Biallas
Die kanonische Abbildung f von der Menge der Ganzen Zahlen (Z) in die
Menge Z/(2^32)Z (also die Restklasse modulo 2^32) ist homomorph
bezüglich der Operationen + und *.
Oder vielleicht einfacher:
(x + y) mod m = ((x mod m) + (y mod m)) mod m
und (x * y) mod m = ((x mod m) * (y mod m)) mod m
Reicht Dir das?
--
Gruß,
Sebastian
Jochen Theodorou
[...]
> Die kanonische Abbildung f von der Menge der Ganzen Zahlen (Z) in die
> Menge Z/(2^32)Z (also die Restklasse modulo 2^32) ist homomorph
> bezüglich der Operationen + und *.
>
> Oder vielleicht einfacher:
> (x + y) mod m = ((x mod m) + (y mod m)) mod m
> und (x * y) mod m = ((x mod m) * (y mod m)) mod m
>
> Reicht Dir das?
das mit dem Modulo hätte ich doch auch hinbringen müssen ;) Das reicht
mir in der Tat. Es erlaubt mir eine interessante Optimierung, danke.
Danke, gruß theo
Florian Stock
Jochen Theodorou <blac...@gmx.org> writes:
> mir geht es hier um das Überlauferhalten von Integern. int in Java
> wäre ein Beispiel.
ohne genaure Hinweise kann man Pauschal nichts dazu sagen. Es kommt auf
die Programmiersprache, verwendter Standard und die Hardware
an. Bspw. ist es in der Finanzmathematik durchaus noch ueblich Zahlen
NICHT in dem ueblichen dualen Stellenwertsystem zu speichern, sondern
als BCDs. Auch haben diverse Programmiersprachen bestimmte Anforderungen
bzw. Freiheiten was das Ueberlaufverhalten angeht (z.B. hat C da
durchaus unterschiedliche Ansichten bei signed und unsigned
Ueberlaufen - bei signed ist das Verhalten explizit undefined, d.h. der
Compiler darf machen was er will, der gcc z.B. macht aus
int f(int x) { return 0x7ffffff0 < x && x + 32 < 0x7fffffff; }
einfach ein konstantes return 0, obwohl beim wrapping Verhalten bei signed
(welches fuer C aber explizit fuer signed nicht definiert ist) das ganze
aequivalent zu 0x7ffffff0 < x ist.)
Auch waere es denkbar, dass die Hardware kein 2er Komplement fuer die
Darstellung von negativen Zahlen benutzt (muesste zwar Heutzutage schon
etwas sehr exotisches sein, aber wer weiss...).
Florian
Jochen Theodorou
> Hallo,
>
> Jochen Theodorou <blac...@gmx.org> writes:
>
>> mir geht es hier um das Überlauferhalten von Integern. int in Java
>> wäre ein Beispiel.
>
> ohne genaure Hinweise kann man Pauschal nichts dazu sagen. Es kommt auf
> die Programmiersprache, verwendter Standard und die Hardware
> an.
sagte doch zum Beispiel Java ;)
> Bspw. ist es in der Finanzmathematik durchaus noch ueblich Zahlen
> NICHT in dem ueblichen dualen Stellenwertsystem zu speichern, sondern
> als BCDs.
Java hat für int 2er Komplementzahlen, egal welche Hardware
> Auch haben diverse Programmiersprachen bestimmte Anforderungen
> bzw. Freiheiten was das Ueberlaufverhalten angeht (z.B. hat C da
> durchaus unterschiedliche Ansichten bei signed und unsigned
> Ueberlaufen
Java hat alles signed
Gruss theo