Probleme beim Implementieren von BigFloat

  • C#

Es gibt 53 Antworten in diesem Thema. Der letzte Beitrag () ist von Artentus.

    Probleme beim Implementieren von BigFloat

    Hallo Leute.

    Ich habe schon wieder eine Frage.
    Und zwar war ich gerade dabei meine MathUtils um eine BigFloat Klasse zu erweitern, da eine solche ja im Framework leider fehlt. Dabei bin ich so vorgegangen, dass ich einen Exponenten und eine Mantisse als BigInteger speichere, eben so wie es bei normalen Gleitkommazahlen auch gemacht wird.
    Der bisherige Code sieht so aus:
    Spoiler anzeigen

    C#-Quellcode

    1. public struct BigFloat : IComparable, IComparable<BigFloat>, IEquatable<BigFloat>
    2. {
    3. sbyte sign;
    4. BigInteger exponent;
    5. BigInteger mantissa;
    7. public BigFloat(float value)
    8. : this()
    9. {
    10. var desc = GetSingleDescription(value);
    11. sign = desc.sign;
    12. exponent = desc.exponent;
    13. mantissa = desc.mantissa;
    14. }
    16. public BigFloat(double value)
    17. : this()
    18. {
    19. var desc = GetDoubleDescription(value);
    20. sign = desc.sign;
    21. exponent = desc.exponent;
    22. mantissa = desc.mantissa;
    23. }
    25. public BigFloat(decimal value)
    26. : this()
    27. {
    28. var desc = GetDecimalDescription(value);
    29. sign = desc.sign;
    30. exponent = desc.exponent;
    31. mantissa = desc.mantissa;
    32. }
    34. public BigFloat(long value)
    35. : this()
    36. {
    37. var desc = GetInt64Description(value);
    38. sign = desc.sign;
    39. exponent = desc.exponent;
    40. mantissa = desc.mantissa;
    41. }
    43. private struct FloatDescription
    44. {
    45. internal sbyte sign;
    46. internal BigInteger exponent;
    47. internal BigInteger mantissa;
    48. }
    50. private FloatDescription GetSingleDescription(float value)
    51. {
    52. var desc = new FloatDescription();
    53. desc.sign = value < 0 ? (sbyte)-1 : (sbyte)0;
    54. uint rawBits;
    55. unsafe
    56. {
    57. rawBits = *(uint*)&value;
    58. }
    59. var rawExponent = (rawBits & 0x7F800000U) >> 23;
    60. var rawMantissa = rawBits & 0x7FFFFFU;
    61. desc.exponent = new BigInteger((int)rawExponent - 127);
    62. desc.mantissa = new BigInteger((1U << 23) + rawMantissa);
    63. return desc;
    64. }
    66. private FloatDescription GetDoubleDescription(double value)
    67. {
    68. var desc = new FloatDescription();
    69. desc.sign = value < 0 ? (sbyte)-1 : (sbyte)0;
    70. ulong rawBits;
    71. unsafe
    72. {
    73. rawBits = *(ulong*)&value;
    74. }
    75. var rawExponent = (rawBits & 0x7FF0000000000000UL) >> 52;
    76. var rawMantissa = rawBits & 0xFFFFFFFFFFFFFUL;
    77. desc.exponent = new BigInteger((long)rawExponent - 1023);
    78. desc.mantissa = new BigInteger((1UL << 52) + rawMantissa);
    79. return desc;
    80. }
    82. private FloatDescription GetDecimalDescription(decimal value)
    83. {
    84. var desc = new FloatDescription();
    85. desc.sign = value < 0 ? (sbyte)-1 : (sbyte)0;
    86. var bits = decimal.GetBits(value);
    88. return desc;
    89. }
    91. private FloatDescription GetInt64Description(long value)
    92. {
    93. var desc = new FloatDescription();
    94. desc.sign = value < 0 ? (sbyte)-1 : (sbyte)0;
    95. desc.exponent = new BigInteger(Convert.ToString(System.Math.Abs(value), 2).Length - 1);
    96. desc.mantissa = new BigInteger(System.Math.Abs(value));
    97. return desc;
    98. }
    100. public int CompareTo(object obj)
    101. {
    102. throw new NotImplementedException();
    103. }
    105. public int CompareTo(BigFloat other)
    106. {
    107. throw new NotImplementedException();
    108. }
    110. public bool Equals(BigFloat other)
    111. {
    112. throw new NotImplementedException();
    113. }
    114. }

    Nun bin ich jedoch auf einige Schwierigkeiten gestoßen.
    Zum einen wäre das die Konvertierung aus Decimal. Dieser Datentyp wird nicht mit Exponent und Mantisse, sondern auf eine andere Art gespeichert, bei der ich nicht weiß, wie ich sie konvertieren kann.
    Zum anderen wäre dies die Darstellung. Ich hab leider keinen Plan, wie ich die Stringdarstellung generieren soll, da die Ausgabe ja dezimal sein soll, der Exponent aber binär vorliegt.

    Außerdem würde ich mich freuen, wenn jemand mal den bisherigen Code auf Richtigkeit prüfen könnte.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Artentus“ ()

    Hi
    bin gerade unterwegs und kann's mir nicht allzu genau anschauen, aber statt auf BitConverter zu arbeiten, wär's doch nicht schlecht, direkt auf Zeigerebene zu arbeiten. So z.B.:

    C#-Quellcode

    1. public unsafe void Test(int val)
    2. {
    3. float cv = *(float*)&val;
    4. }

    &val gibt einen Zeiger auf val (auf den Wert aufm Stapel, da es ein Wertetyp ist). (float*) konvertiert den int*-Zeiger zu einem float*-Zeiger, da dieser Wert dann ebenfalls 4 Byte lang ist, stimmen die Größen überein. * dereferenziert den Wert am Zeiger dann als float. Das ist effizienter, als eine Byte-Konvertierung über BitConverter vorzunehmen, insbesondere, da nur die den Typen zugrunde liegende Arithmetik anders ist.
    Ich schau's mir später nochmal genauer an. Btw. eine Konvertierung von Byte, etc. halte ich eher nicht so für sinnvoll, da ja Long bzw. ULong die bereits umfassen könnten. D.h. die Konstruktoren an sich wären schon fast überflüssig.

    Gruß
    ~blaze~

    Hier wären genauere Infos zu Decimal: msdn.microsoft.com/en-us/libra…stem.decimal.getbits.aspx, falls du's nicht eh schon gefunden hast. Wie's aussieht, musst du wohl einen Basiswechsel vornehmen zur Basis 2 mit a^b = c^(b*log_c a). Ich würde das aber erst mal auf später verschieben. Decimal ist nicht mal ein primitiver Datentyp.
    Das Parsen eines Strings wäre noch relativ einfach, sobald Multiplikation und Addition funktionieren, allerdings ist die Frage, ob es nicht effizienter wäre, den Wert vor und nach dem Komma in ein BigInteger einzulesen, die negierte Anzahl der Bytes in den Exponenten zu packen und dann die Mantisse auf das andere drauf zu rechnen. Dürfte beim Vergleich der Werte auch zugute kommen. Überstehende Zweierpotenzen ohne Wert würde ich sofort eliminieren (also 0b100 um 2 nach rechts shiften und aufm Exponenten 2 draufrechnen).
    Umgekehrt ist mMn. schwieriger. die einfachste Version wäre, einfach solange durch 10 zu dividieren, bis das Ergebnis 0 ist und immer %10 an den Anfang des Strings zu packen (oder einfach ans Ende und dann den string reversen). Da würde ich btw. am Anfang auftrennen in n % 1 und n - n%1 und beide getrennt ausgeben.
    Bin gerade am Überlegen, ob n%1 nicht durch eine Multiplikation mit 10 und nachfolgendem m - m%1 zu lösen wäre.

    Ansonsten ist mir beim Überfliegen jetzt kein direkter Fehler ins Auge gesprungen. Nur das mit der String-Konversion nehm' ich dir übel :P. Nimm da einfach das höchstwertige, gesetzte Bit, das kriegst du über Bitshifts heraus.

    Gruß
    ~blaze~

    ~blaze~ schrieb:

    die negierte Anzahl der Bytes in den Exponenten zu packen und dann die Mantisse auf das andere drauf zu rechnen

    ~blaze~ schrieb:

    Da würde ich btw. am Anfang auftrennen in n % 1 und n - n%1 und beide getrennt ausgeben.
    Bin gerade am Überlegen, ob n%1 nicht durch eine Multiplikation mit 10 und nachfolgendem m - m%1 zu lösen wäre.

    Tut mir leid, bei den beiden Sachen komm ich (mal wieder) nicht mit.

    Und wie man eine Zahl zur Basis 10 in einen String umwandelt, weiß ich auch. Mein Problem damit ist, dass ich nicht weiß, wie ich die Stelle des Kommas herausfinden soll, denn es handelt sich ja um eine Zweierpotenz, nicht um eine Zehnerpotenz.

    Genau das meinte ich damit ;). Norme die Mantisse immer so, dass sie die Nachkommastellen darstellt, also quasi gilt 0,m * 256^e o.ä. Außerdem muss die erste Ziffer von m ungleich 0 sein. Dies wird erzwungen, indem du den Wert um genau so viel nach links shiftest, wie du Stellen hast (Achtung: bei einer Basis von 256, musst du nat. auch um 8 mal so viele Stellen shiften!).
    Jetzt auch klar, wo dann das Komma liegt?

    Gruß
    ~blaze~

    Also auf Wikipedia steht, dass das immer so gespeichert wird s * 1,m * 2^e, und genau so speichere ich das auch (die 1 hänge ich ja immer noch vorne dran).
    Und wenn die Basis ein Vielfaches von 2 wäre, dann würde das mit dem Komma auch gehen, aber 10 ist kein Vielfaches von 2. In Hexadezimal könnte ichs darstellen.

    ich wäre sogar so weit gegangen und hätte die 1 weggelassen, da es mMn. einfacher zum Rechnen ist.
    Wie du's letztendlich löst spielt sowieso keine Rolle. Wenn die Zahl selbst n = a,b ist, würde ich a und b getrennt ausgeben. a = n - b, b = n % 1. Die Position des Kommas ergibt sich aus dem Exponenten e und liegt dann wohl binär gesehen an der e-ten Stelle hinter dem Komma (?).
    a weißt du ja, wie du es ausgeben kannst, b funktioniert quasi analog, nur dass du wohl mit 10 multiplizieren musst und dann b % 10 ohne Rest ausgeben? Hätte ich zumindest so gelöst:

    C#-Quellcode

    1. StringBuilder sb;
    2. BigFloat b;
    3. while (b > 0)
    4. {
    5. b *= 10;
    6. sb.Append((int)b);
    7. b = b%1;
    8. }

    oder so.

    Ist klar, was ich mein?

    Gruß
    ~blaze~

    Ne, der Exponent bleibt für die Rechnung. An sich wär's ja eigentlich egal, aber du hast beim Speichern der Daten halt riesige Freiräume dann. Insofern wäre es auch ganz praktisch, erst mal zu überprüfen, ob die Mantisse überhaupt groß genug ist, sodass b != 0 ist, bzw. um wie viele Stellen die Mantisse zu weit rechts ist, um ein a != 0 zuzulassen. Extrem große Zahlen brauchen ja sonst auch extrem viel Speicher, Rechnungen sind viel langsamer, usw. Ggf. fällt dir auch so noch eine Optimierung ein, da die Stringdarstellung nach obigem Prinzip sehr ineffizient ist. Auf jeden Fall sind a und b nur bei der Darstellung der Zahl zu berechnen.
    Btw. wäre es auch nicht unbedingt so schlimm, die Darstellung und das Parsen von Zahlen nötig ineffizient zu gestalten, da das normalerweise nicht so oft benötigt wird, wie die Rechnungen an sich.

    Gruß
    ~blaze~

    Ich habs gerade mal versucht, bin aber gleich beim berechnen von a und b gescheitert.
    Mein Problem ist, dass ich nicht weiß, wie ich shiften muss, da die Mantisse ja eine variable Anzahl Bits besitzt. Ich müsste also zuerst die Anzahl der Mantissen-Bits herausfinden, weiß aber nicht, wie ich das tun soll.
    Ich bin deswegen gerade schon am Überlegen, ob ich die Genauigkeit nicht einfach nicht unendlich, sondern nur enorm hoch lege (auf 1024 Bit oder so), weil dann die Bitanzahlen wieder fest sind.

    Die Anzahl der Mantissen-Bits ergibt sich doch eigentlich aus den BigInteger-Daten, oder? Danach wäre einfach um die Anzahl der Mantissen-Bits-e nach rechts zu shiften. BigInteger basiert ja eigentlich auch nur auf einem Integer-Array, afaik, insofern wäre das halt dann quasi die Anzahl der Integer * 32.

    Gruß
    ~blaze~

    Aber der BigInteger hat leider keine "gib mir die Anzahl deiner Integer"-Funktion. Vergiss es, hab gerade gesehen, dass er eine "gib mir die Anzahl deiner Bytes"-Funktion besitzt.
    Da wäre dann aber die Sache, dass ja vorne dran noch ein paar Nullbits stehen könnten, die nicht zur zahl gehören. Die Anzahl der Bits ist ja nicht immer ein Vielfaches von 8.

    Und noch was, die Berechnung von b wäre dann noch ein Stück schwerer, da man da ja die unteren Bits ja nur mit Bitwise-AND bekommt, aber woher soll ich wissen, mit was ich Anden muss (theoretisch weiß ich, aber wie komme ich an eine Zahl, die genau die benötigte Anzahl gesetzter Bits besitzt)?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Artentus“ ()

    Das sollte gehen, indem du n % ((BigInteger)1 << n) rechnest. Effizienter könnt's aber sein, a zu berechnen (einfach um e rechtsshiften) und dann (a<<e) zu subtrahieren. Oder vielleicht geht auch -1 um (c-e) links zu shiften, wenn c die Anzahl der Bits der Mantisse ist und damit zu Anden.
    Sind die Nullbits signifikant? Beim a wohl nicht.

    Gruß
    ~blaze~

    Sie sind nicht signifikant, aber angenommen ich habe 10 Mantissenbits, dann sind nur die ersten beiden Bits im zweiten Byte relevant. Wenn der Exponent jetzt z.B. 3 ist dann shifte ich um 16 - 3 = 13 Bits nach rechts. Somit wäre a 0, weil ich alle 10 richtigen Bits weggeshiftet habe und ich mich in den Nullbits links der eigentlichen Zahl befinde.
    Ich werds jetzt glaube ich einfach so machen, dass ich 1KB für die Mantisse fix belege, dann kann ich nämlich alles nach den Normen von IEEE 754 handhaben.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Artentus“ ()

Facebook
Telefonspende