none
Verständnisfrage: Wie übergroßen Integer als Zahl darstellen RRS feed

  • 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

    Freitag, 19. November 2010 16:06

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-c

    Gruß Elmar

    Freitag, 19. November 2010 18:48
  • 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.Click

            Dim Len As Integer
            Dim Result As String
            Dim Num1 As String = "30555"
            Dim Num2 As String = "987654"

            Result = AddNumbers(Num1, Num2)
            Len = Result.Length

            MsgBox _
                    (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 Sub

        Private Function AddNumbers _
                (ByVal Num1 As String, _
                 ByVal Num2 As String) As String

            Dim 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 If

            Dim 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    ' Überlaufpuffer

            Dim X As Byte
            For i = 1 To Len
                j = Len - i
                X = _
                    CByte(Buffer1.Substring(j, 1)) + _
                    CByte(Buffer2.Substring(j, 1)) + _
                    OV

                OV = X \ Z
                X = X Mod Z
                RBuffer = X.ToString & RBuffer
            Next
            If OV > 0 Then
                RBuffer = "1" & RBuffer
            End If
            Return RBuffer
        End Function

    End 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)

    Dienstag, 23. November 2010 10:38

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-c

    Gruß Elmar

    Freitag, 19. November 2010 18:48
  • 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            1000

    Wenn man sich aber nur jedes Byte einzeln ansieht, dann ist dies so

    Bytes 2 1
    binär 00000011 11101000
    hex             3           E8
    dec             3           232

    Wie komme ich nun dazu 1000 auszugeben, wenn ich doch nur weiß das Byte 1 = 232 und Byte 2 = 3 ist?

    Danke
    Reinhard

    Freitag, 19. November 2010 21:53
  • 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
    Samstag, 20. November 2010 13:41
  • 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

    Sonntag, 21. November 2010 15:28
  • 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
    Dienstag, 23. November 2010 08:39
  • 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/Zahlbasiswechsel

    Um 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.
    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.

    Wenn die Recheneinheit (ALU) dsa selbst nicht mehr ausführen kann, muß man
    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 Konvertierungen

    Konkret 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

     

     

    Dienstag, 23. November 2010 09:47
  • 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.:

    c = CByte((CInt(b) + CInt(a)) Mod 256)
    
    was zunächst die Operanden explizit auf Integer anhebt (sonst wird die Addition konvertiert und schlägt fehl)
    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

    Dienstag, 23. November 2010 10:36
  • 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.Click

            Dim Len As Integer
            Dim Result As String
            Dim Num1 As String = "30555"
            Dim Num2 As String = "987654"

            Result = AddNumbers(Num1, Num2)
            Len = Result.Length

            MsgBox _
                    (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 Sub

        Private Function AddNumbers _
                (ByVal Num1 As String, _
                 ByVal Num2 As String) As String

            Dim 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 If

            Dim 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    ' Überlaufpuffer

            Dim X As Byte
            For i = 1 To Len
                j = Len - i
                X = _
                    CByte(Buffer1.Substring(j, 1)) + _
                    CByte(Buffer2.Substring(j, 1)) + _
                    OV

                OV = X \ Z
                X = X Mod Z
                RBuffer = X.ToString & RBuffer
            Next
            If OV > 0 Then
                RBuffer = "1" & RBuffer
            End If
            Return RBuffer
        End Function

    End 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)

    Dienstag, 23. November 2010 10:38
  • 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 Basic

    Mit 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)

    Dienstag, 23. November 2010 10:47
  • 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

    Dienstag, 23. November 2010 11:51
  • 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

    Dienstag, 23. November 2010 22:31
  • 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. :)

    Donnerstag, 25. Oktober 2018 19:35