Benutzer mit den meisten Antworten
Verständnisfrage: Wie übergroßen Integer als Zahl darstellen

Frage
-
Hallo,
gehen wir mal kurz davon aus, das es eigentlich nur 8bit integer datentypen gibt.
Dann hätten wir ein Problem, das die Zahl 1000 nicht dargestellt werden könnte,
da es zum Überlauf kommt. Nun war es in der Vergangenheit so und trotzdem gab
es Programme welche 250+250+250+250=1000 rechnen konnte.Frage: Wie wird sowas gemacht?
Aktuell könnte man sagen, wie kann ich eine 512bittige Zahl darstellen?
Intern könnte ich 8x64bit Felder in einer Struktur anlegen und dann füllen lassen, wie aber
kann ich mir dann die Zahl berechnen und darstellen?
Danke
Reinhard
Antworten
-
Hallo Reinhard,
man kann das auch mit Hand codieren, wie die Wikipedia bei Dualsystem zeigt.
Zur Implementationen verwendet man üblicherweise ein Byte-Array
Selbst muß das aber nicht mehr machen.Mit .NET 4.0 findest Du mit BigInteger eine Implementation,
weitere http://stackoverflow.com/questions/176775/big-integers-in-cGruß Elmar
- Als Antwort vorgeschlagen Holger M. Rößler Dienstag, 23. November 2010 11:51
- Als Antwort markiert Robert Breitenhofer Donnerstag, 25. November 2010 10:26
-
Hallo Reinhard,
gehen wir mal kurz davon aus, das es eigentlich nur 8bit
integer datentypen gibt.
Dann hätten wir ein Problem, das die Zahl 1000 nicht
dargestellt werden könnte, da es zum Überlauf kommt.
Nun war es in der Vergangenheit so und trotzdem gab
es Programme welche 250+250+250+250=1000 rechnen
konnte.
Frage: Wie wird sowas gemacht?Du schreibst Dir einfach eine Funktion, die genauso
rechnet, wie Du es beim Rechnen auf einem Stück
Papier machst.
Hier ein Beispiel für die Addition zweier beliebig grosser
Zahlen (30555 + 987654):Public Class Form1
Private Sub Form1_Click _
(ByVal sender As Object, _
ByVal e As System.EventArgs _
) Handles Me.ClickDim Len As Integer
Dim Result As String
Dim Num1 As String = "30555"
Dim Num2 As String = "987654"Result = AddNumbers(Num1, Num2)
Len = Result.LengthMsgBox _
(Num1.PadLeft(Len, "0"c) & ControlChars.CrLf & _
Num2.PadLeft(Len, "0"c) & ControlChars.CrLf & _
New String("_"c, Len) & ControlChars.CrLf & _
Result.PadLeft(Len, "0"c))
End SubPrivate Function AddNumbers _
(ByVal Num1 As String, _
ByVal Num2 As String) As StringDim i As Integer
Dim j As Integer
Dim Z As Byte = 10
Dim Len As Integer = Num1.Length
If Num2.Length > Len Then
Len = Num2.Length
End IfDim Buffer1 As String = Num1.PadLeft(Len, "0"c)
Dim Buffer2 As String = Num2.PadLeft(Len, "0"c)
Dim RBuffer As String = "" ' Ergebnispuffer
Dim OV As Byte ' ÜberlaufpufferDim X As Byte
For i = 1 To Len
j = Len - i
X = _
CByte(Buffer1.Substring(j, 1)) + _
CByte(Buffer2.Substring(j, 1)) + _
OVOV = X \ Z
X = X Mod Z
RBuffer = X.ToString & RBuffer
Next
If OV > 0 Then
RBuffer = "1" & RBuffer
End If
Return RBuffer
End FunctionEnd Class
Obwohl Zahlen beliebiger Grösse addiert werden, wird in
der Function AddNumbers immer nur mit Werten vom
Typ Byte gerechnet. Die zu addierenden Werte werden
als Strings übergeben und das Resultat wird ebenfalls
wieder als String zurückgegeben, womit auch hier eine
Grössenbegrenzung durch einen numerischen Datentyp
ausgeschlossen ist.Als Fleissaufgabe darfst Du nun mal eine Funktion zum
Multiplizieren zweier Zahlen schreiben. ;-)Gruß aus St.Georgen
Peter Götz
www.gssg.de (mit VB-Tipps u. Beispielprogrammen)- Als Antwort markiert Robert Breitenhofer Donnerstag, 25. November 2010 10:27
Alle Antworten
-
Hallo Reinhard,
man kann das auch mit Hand codieren, wie die Wikipedia bei Dualsystem zeigt.
Zur Implementationen verwendet man üblicherweise ein Byte-Array
Selbst muß das aber nicht mehr machen.Mit .NET 4.0 findest Du mit BigInteger eine Implementation,
weitere http://stackoverflow.com/questions/176775/big-integers-in-cGruß Elmar
- Als Antwort vorgeschlagen Holger M. Rößler Dienstag, 23. November 2010 11:51
- Als Antwort markiert Robert Breitenhofer Donnerstag, 25. November 2010 10:26
-
Hallo Elmar,
danke, ich habe den wiki Artikel gelesen, allerdings denke ich, das meine Fragen damit noch nicht beantwortet sind, oder?
Beispiel mit der Zahl 1000. Diese kann wie folgt dargestellt werden
Bytes 2 1
binär 00000011 11101000
hex 3 E8
dec 1000Wenn man sich aber nur jedes Byte einzeln ansieht, dann ist dies so
Bytes 2 1
binär 00000011 11101000
hex 3 E8
dec 3 232Wie komme ich nun dazu 1000 auszugeben, wenn ich doch nur weiß das Byte 1 = 232 und Byte 2 = 3 ist?
DankeReinhard -
Hallo Reinhard,
Ein Wert des zweiten Byte hat bezogen auf das Dezimalsystem die Wertigkeit 256. Also lautet die Formel:
3 * 256 + 232 ergibt 1000
Habe ich Deine Frage so richtig verstanden?
schöne Grüße Ellen
------------------------------------------
P.S Nachtrag. mathematischer Ansatz im Dualsystem. Darstellung einer 16bit Zahl durch ein high Byte und low Byte.
m= 3 high byte) n=232 (low byte) in dezimal
e = m * 2^8 + n * 2^0
2^0 ist definitionsgemäss 1
Mit bytes rechne und arbeite ich auch sehr gerne im Zahlensystem Basis 256. Das bietet sich hier an. Die Formel lautet dann:
e = m * 256^1 + n * 256^0
Erkennst Du die Unterschiede?
jetzt eine 32bit Zahl dargestellt durch 4 bytes p,l,m,n:
e = p * 256^3 + l * 256^2 + m * 256^1 + n * 256^0
Ich benutze/ I'm using VB2008 & VB2010- Bearbeitet Ellen Ramcke Samstag, 20. November 2010 16:03 Nachtrag
-
Hallo Ellen,
vielen Dank. Ich habe mich noch nicht richtig ausgedrückt denke ich.
Ich frage mich, wie es sein kann, das es Programme gibt, die eine Zahl darstellen ohne das es einen Datentyp gibt, welcher groß genug wäre diese zu speichern.
Bei meinem konstruierte Fall, es gibt nur einen Datentyp der 1 Byte groß sein kann, würde ich gerne die Zahl 1000 ermitteln und ausgeben.
Wie würde das gehen? ich kann ja nicht 3*256 rechnen, da diese Berechnung wieder 2 Bytes bräuchte um das Ergebnis zu speichern.
Verstehst du mein Problem? Wie kann ich eine 512 bit Zahl darstellen wenn ich nur einen 64 bit Integer habe?
Ja, ich kann 8 64bit Integer nehmen und dann die Zahl im Speicher halten, wie aber kann ich das Resultat anzeigen?
Jede mathematische Rechnung würde doch immer mit overflow enden, oder?
Wie kann die CPU (oder wer auch immer) die Berechnung durchführen. Warum weiss ich bei meinem konstruierten Fall, das wenn das
lowByte = 232 ist und das highByte=3, das ich dann 1000 ausgebe. Es wird doch niemand eine Liste halten, die sagt
wenn lowByte=... und highByte=... dann 1000 ansonsten 1001 oder 1002 usw...
Wie funktioniert das?
Danke
Reinhard
-
Verstehst du mein Problem? Wie kann ich eine 512 bit Zahl darstellen wenn ich nur einen 64 bit Integer habe?
Ja, ich kann 8 64bit Integer nehmen und dann die Zahl im Speicher halten, wie aber kann ich das Resultat anzeigen?
Jede mathematische Rechnung würde doch immer mit overflow enden, oder?
Hallo Reinhard,
eine CPU kann beliegig große Datenbreiten verarbeiten unabhängig von der physikalischen Datenbreite. Das liegt an der Architektur eines Prozessors. Dazu notwendig sind:
a) die Fähigkeit einen Additionsüberlauf zu erkennen (idR Carry Flag im Prozessorstatusregister
b.) den Additionsrest zu behalten.
Du willst also in Visual Basic mit 512 bit Datenbreite rechnen. Schauen wir mal auf dieses Sample:
Module Module1 Sub Main() Dim a As Byte = 232 Dim b As Byte = 100 Dim c As Byte Try c = b + a Catch ex As OverflowException Console.WriteLine("Ergebniss: {0}", c) End Try End Sub End Module
Die Operation wird nicht durchgeführt und lauf auf diese Ausnahme. Das Ergebnis ist C=0. Ich hatte erwartet das C den Wert 77 enthält. So hätte man eine Möglichkeit. Gefunden habe ich nichts über overflow Behandlung. Ich glaube Dein Vorhaben ist nicht machbar in Visual Basic
Oder Hat jemand anders noch eine Idee?
Gruß Ellen
Ich benutze/ I'm using VB2008 & VB2010 -
Hallo Reinhard,
ich hatte den Thread etwas aus den Augen verloren.
Grundsätzlich funktioniert das Rechnen schon so wie bereits verlinkt unter
http://de.wikipedia.org/wiki/Dualsystem#Umrechnen_von_Dualzahlen_in_andere_Stellenwertsysteme
oder allgemeiner auch http://de.wikipedia.org/wiki/ZahlbasiswechselUm eine binäre Zahl (Basis 2) im Dezimalsyteem (Basis 10) darzustellen,
wäre eine Modulo Berechnung erforderlich - eine Division mit Restwert.
Der jeweilige Rest (Remainder) wird als Stelle dargestellt und die Modulo
Berechnung solange durchgeführt der letzte Rest (Wert hier < 10) verarbeitet wurde.Letztendlich ist nicht relevant wie breit dabei die ALU des Prozessors ist.
Wenn die Recheneinheit (ALU) dsa selbst nicht mehr ausführen kann, muß man
Früher war das mal nur 8 bit, heute sind es oft 64 - aber es gab in den Anfangszeiten
auch andere Wortbreiten und Taschenrechner arbeiteten (früher) auch mal mit nur 4 Bits.
die Rechenschritte eben selbst ausführen und die Daten jeweils aus dem Speicher
in die Register holen und das Ergebnis zurück verfrachten und dabei die
Byte-Reihenfolge (Endianness) beachten. Was spätestens dann wichtig wird,
wenn man anstatt Byte ein UInteger (oder ULong) Array zur internen Speicherung verwendet.
.NET MS IL kennt nur Arithmetik Opcodes für Integer und aufwärts, ein Byte wird
für eine Rechenoperation zunächst auf ein Integer erweitert,
siehe Erweiternde und eingrenzende KonvertierungenKonkret wird das etwas komplexer, deswegen hatte ich auf die C# Beispiele
(für VB.NET kenne ich gerade keine) verlinkt. Schau Dir z. B. den Quellcode von
http://www.codeproject.com/KB/cs/biginteger.aspx an.
(Andere Klassen wie das .NET 4.0 BigInteger verwenden intern wiederum UInteger)Gruß Elmar
-
Hallo Ellen,
in Deinem Beispiel wird für Null ausgegeben, weil die Zuweisung für C nicht mehr ausgeführt wird,
sondern vorher die OverflowException eintritt. Und damit behält C seinen Standardwert (= 0).Und insofern sollte das Console.WriteLine im Try Block stehen, denn im Catch Block kann es
keinen sinnvollen Wert liefern.Was die Addition von Byte-"Zahlen" angeht: Die gibt es gar nicht.
.NET kennt (siehe auch Antwort an Reinhard) nur Arithmetik für Integer und aufwärts.
Und so wird die Addition als Integer Operation ausgeführt, d. h. die beiden Operanden
(a und b) werden zunächst auf einen Integer erweitert und addiert.Für das Zwischenergebnis (dann noch 323) erfolgt eine Konvertierung auf eine Byte,
die dann jedoch fehlschlägt und zu einer OverflowException führt.Visual Basic verwendet bei Konvertierung im Standard immer eine Überprüfung,
die man über Überprüfungen auf Ganzzahlüberlauf entfernen (projektweit) deaktivieren kann.Tut man das, so wäre das Ergebnis 76. Um es ohne Deaktivierung hinzukriegen,
wäre einiges mehr notwendig, z. B.:was zunächst die Operanden explizit auf Integer anhebt (sonst wird die Addition konvertiert und schlägt fehl)c = CByte((CInt(b) + CInt(a)) Mod 256)
und das Ergebnis auf den Wertebereich eines Bytes begrenzt, damit die (jetzt explizite) CByte-Konvertierung
keine Ausnahme verursacht.Auch in Gedenken an eine andere Diskussion ;-)
Der C# Compiler arbeitet anders rum, dort aktiviert man eine Überprüfung mit checked
bzw. kann es für Anweisungen via unchecked abschalten.Visual Basic hat insofern mehr kaufmännische Wurzeln und solche Operationen sind
zwar durchaus machbar, erfordern aber einigen Aufwand.
(Was nicht heisst das C# besser wäre: Dort fällt ein unbedarfter Entwickler auf die Nase,
wenn die Absichten umgekehrt sind, ein kaufmännisch korrektes Ergebnis erwartet wird.)Gruß Elmar
-
Hallo Reinhard,
gehen wir mal kurz davon aus, das es eigentlich nur 8bit
integer datentypen gibt.
Dann hätten wir ein Problem, das die Zahl 1000 nicht
dargestellt werden könnte, da es zum Überlauf kommt.
Nun war es in der Vergangenheit so und trotzdem gab
es Programme welche 250+250+250+250=1000 rechnen
konnte.
Frage: Wie wird sowas gemacht?Du schreibst Dir einfach eine Funktion, die genauso
rechnet, wie Du es beim Rechnen auf einem Stück
Papier machst.
Hier ein Beispiel für die Addition zweier beliebig grosser
Zahlen (30555 + 987654):Public Class Form1
Private Sub Form1_Click _
(ByVal sender As Object, _
ByVal e As System.EventArgs _
) Handles Me.ClickDim Len As Integer
Dim Result As String
Dim Num1 As String = "30555"
Dim Num2 As String = "987654"Result = AddNumbers(Num1, Num2)
Len = Result.LengthMsgBox _
(Num1.PadLeft(Len, "0"c) & ControlChars.CrLf & _
Num2.PadLeft(Len, "0"c) & ControlChars.CrLf & _
New String("_"c, Len) & ControlChars.CrLf & _
Result.PadLeft(Len, "0"c))
End SubPrivate Function AddNumbers _
(ByVal Num1 As String, _
ByVal Num2 As String) As StringDim i As Integer
Dim j As Integer
Dim Z As Byte = 10
Dim Len As Integer = Num1.Length
If Num2.Length > Len Then
Len = Num2.Length
End IfDim Buffer1 As String = Num1.PadLeft(Len, "0"c)
Dim Buffer2 As String = Num2.PadLeft(Len, "0"c)
Dim RBuffer As String = "" ' Ergebnispuffer
Dim OV As Byte ' ÜberlaufpufferDim X As Byte
For i = 1 To Len
j = Len - i
X = _
CByte(Buffer1.Substring(j, 1)) + _
CByte(Buffer2.Substring(j, 1)) + _
OVOV = X \ Z
X = X Mod Z
RBuffer = X.ToString & RBuffer
Next
If OV > 0 Then
RBuffer = "1" & RBuffer
End If
Return RBuffer
End FunctionEnd Class
Obwohl Zahlen beliebiger Grösse addiert werden, wird in
der Function AddNumbers immer nur mit Werten vom
Typ Byte gerechnet. Die zu addierenden Werte werden
als Strings übergeben und das Resultat wird ebenfalls
wieder als String zurückgegeben, womit auch hier eine
Grössenbegrenzung durch einen numerischen Datentyp
ausgeschlossen ist.Als Fleissaufgabe darfst Du nun mal eine Funktion zum
Multiplizieren zweier Zahlen schreiben. ;-)Gruß aus St.Georgen
Peter Götz
www.gssg.de (mit VB-Tipps u. Beispielprogrammen)- Als Antwort markiert Robert Breitenhofer Donnerstag, 25. November 2010 10:27
-
Hallo Ellen,
eine CPU kann beliegig große Datenbreiten verarbeiten unabhängig
von der physikalischen Datenbreite. Das liegt an der Architektur eines
Prozessors.Das wäre mir aber schon ein wenig zu pauschal.
Hat die CPU z.B. 16 Bit breite Register, dann ist eben
genau bei dieser Datenbreite (+ Überlauf) Schluss.
Den Rest muss Soft- bzw. Firmware erledigen.Dazu notwendig sind:
a) die Fähigkeit einen Additionsüberlauf zu erkennen
(idR Carry Flag im Prozessorstatusregister
b.) den Additionsrest zu behalten.
Du willst also in Visual Basic mit 512 bit Datenbreite rechnen.
Schauen wir mal auf dieses Sample:
Module Module1
Sub Main()
Dim a As Byte = 232
Dim b As Byte = 100
Dim c As Byte
Try
c = b + a
Catch ex As OverflowException
Console.WriteLine("Ergebniss: {0}", c)
End Try
End Sub
End Module
Die Operation wird nicht durchgeführt und lauf auf diese Ausnahme.
Das Ergebnis ist C=0. Ich hatte erwartet das C den Wert 77 enthält.
So hätte man eine Möglichkeit. Gefunden habe ich nichts über
overflow Behandlung.Man rechnet eben genauso wie beim Addieren zweier Zahlen auf
einem Stück Papier, wo man sich den Überlauf für die jeweilige
Addition der einzelnen Ziffern merkt und zur nächst höheren Stelle
(Übertrag) addiert (s. mein anderes Posting)Ich glaube Dein Vorhaben ist nicht machbar
in Visual BasicMit einer entspr. Funktion ist das schon machbar.
Oder Hat jemand anders noch eine Idee?
s. mein anderes Posting in diesem Thread.
Gruß aus St.Georgen
Peter Götz
www.gssg.de (mit VB-Tipps u. Beispielprogrammen) -
Hallo Reinhard,
Schau dir doch mal an, wie Microsoft das im .net Framework gelöst hat. Die BigInteger Struktur im Namespace System.Numerics kann quasi beliebig große Ganzzahlen darstellen kann. (http://msdn.microsoft.com/de-de/library/system.numerics.biginteger.aspx)
Viele Grüße
Holger M. Rößler
-
Hallo zusammen,
erst mal vielen Dank für all eure Hilfe.
Da sind ziemlich viel Information (mehr als in ein Byte passen) und die muss ich erstmal verdauen.
Ich werde das durcharbeiten, meine Hausaufgaben machen ;-) und dann hoffentlich mit
erweitertem Verstand die nächste schusselige Frage stellen ;-)
Schönen Abend noch
Reinhard
-
Vielen, vielen Dank für den gesamten Thread. Dieser darf auf gar keinen Fall verschwinden. Auch wenn BigInteger eine gute Lösung für sehr große Zahlen liefert, so ist ein Grundverständnis durchaus angebracht. Ich war sehr erstaunt, als ich sah wie eine sehr große Zahl in einem 10 stelligen Byte Array untergebracht wurde. Mir war das so nicht bewusst.
Natürlich geht es um Verschlüsselung, nicht darum diese selbst zu schreiben, sondern nur um ein Grundverständnis. Dabei fragt man sich eben, wie verschlüsseln denn Systeme die keine BigInteger haben. Und wie addiert, multipliziert man int Arrays usw. :)