Laden...

Byte zu Base23

Letzter Beitrag vor 17 Tagen 9 Posts 358 Views
Byte zu Base23

Grüße,

Ich versuche gerade ein Mathe problem zu lösen und mir raucht der Schädel.

Ich habe zwei listen einmal mit der Einheit Base256(Byte) und eine liste als aus Ausgabe mit der Einheit Base23.

Ich muss in beide Richtungen Konvertieren.

Der Daten typ Base23 ist als char array definiert und ist als Zeichen A-W definiert.

Ich habe eine Lösung mir ausgedacht, die mir aber Kopfschmerzen einbringt. Um genau zu sagen ist meine Haupt sorge ist der übertrag. Ich kann nicht abschätzen wann der platz. Das anderer ist die Skalierbarkeit. Ich kann die den Prozess nicht auf mehrere Threads aufteilen.

Die Rechnung wird benötigt um bytes in eine Farb-Kodierung umzurechnen.

Meine frage ist, gibt es eine bessere Lösung ?

Das ist meine erste variante :

        const string Base23Table = "ABCDEFGHIJKLMNOPQRTUVW";
        
        internal static string Base255ToBase23(byte[] base255)
        {
            List<int> result = new List<int>();
            int carry = 0;

            foreach (byte b in base255)
            {
                int value = b + carry * 255;
                while (value > 0)
                {
                    result.Add(value % 23);
                    value /= 23;
                }
            }

            // Letzte Übertragsstelle hinzufügen, wenn sie größer als 0 ist
            if (carry > 0)
            {
                result.Add(carry);
            }

            // Konvertiere die Liste von Indizes in die Base23-Zeichenkette
            StringBuilder base23 = new StringBuilder();
            foreach (int index in result)
            {
                base23.Append(Base23Table[index]);
            }

            return base23.ToString();
        }

Es gibt zwar keine offizielle Unterstützung von Base23 in .NET - aber auf GitHub finde ich sehr sehr viele Beispielimplementierungen. Passt da nicht eine?
Die sehen auch mit entsprechenden Bit-Operations deutlich effizienter aus; mach halt mal ein Benchmark.

Was genau meinst Du mit Skalierbarkeit? Auf mehrere Threads würde das eh kein Sinn macht, weil die Threadverwaltung vermutlich mehr Power kosten würde als Du Skalierungsbenefits hättest. Und wenn dann eh Tasks statt Threads 😉

Grüße,

es gibt ja sehr viele Methoden, wie man so was macht, das was ich gefunden habe bisher hat ein bestimmtes Problem aufgewiesen:

Sie wollten in dezimal umrechnen um dann auf eine andere basis umzurechnen.

Die daten welche ich umrechnen will, können auch 30Byte und weit mehr sein.

Leider ist meine "Lösung" leider gescheitert. Es gibt da ein rechen Fehler den ich grade suche.

Die Funktion gibt bei [2,11](Byte-Array) nicht wie erwartet WW als Ergebnis raus, stattdessen kommt CL(Hex 81) als Ergebnis.

Erläuterung : Hex 211 ist gleich 529 als dezimal zahl, was 23^2 entsprich und somit WW.

Falls dir bei deiner such eine Methode aufgefallen ist, die eventuelle das Problem mit dem Speicher nicht hat, wäre sehr hilfreich.

Mfg.

Möchtest du eigentlich Base255 oder Base256 als Eingangsdaten?

PS: WW (als Base23) entspricht dezimal 22*23+22 = 528. Und das entspricht weder [2,11] in Base255 (= 521) noch in Base256 (= 523).

Edit:
Und auch dein bisheriger Umrechnungscode erscheint mir fehlerhaft (bes. die while-Schleife sowie das nirgendwo gesetzte carry!?). Schau mal in Horner-Schema: Umwandlung zwischen verschiedenen Zahlensystemen.

Das mit deinem Hex Array ist auch komisch für mich.
Ich hätte es so interpretiert: 2 B (=Dezimal 43)
Aber du meintest eigentlich 2 1 1 (=Dezimal 529)

Ich danke für eure Unterstützung.

Ich bin wohl etwas durcheinander geraten.

Das Ziel sind Base23 zu Base256 und umgekehrt.

Ich habe mir das Horner-Schema angesehen, die Umsetzung  macht mir aber noch Kopfzerbrechen.

Mfg.

Grüße,

Ich habe nach dem genannten Schema eine Funktion gebaut.

Es funktioniert, es ist aber echt langsam.

Für 10 MB braucht es 20 stunden.

        private static List<int> ConvertDecimalToBase(BigInteger decimalValue, int baseTo)
        {
            List<int> baseValue = new List<int>();
            while (decimalValue > 0)
            {
                int remainder = (int)(decimalValue % baseTo);
                baseValue.Add(remainder);
                decimalValue /= baseTo;
            }

            return baseValue;
        }
        public static List<int> ConvertBase256ToBase23(byte[] base256Array)
        {
            BigInteger value = 0;
            for (int i = base256Array.Length - 1; i >= 0; i--)
            {
                value = value * 256 + base256Array[i];
            }

            return ConvertDecimalToBase(value, 23);
        }

Du hast leider keinerlei Infos, was Du eigentlich testest zur Verfügung gestellt, daher hab ich ChatGPT mit o3-mini bedient. Hab aber natürlich auch keine 20 Stunden Zeit 😃

// Größe: 200 KB
const int sizeInBytes = 200 * 1024;
byte[] base256Value = new byte[sizeInBytes];

// Erzeugen eines zufälligen Byte-Arrays
using (RandomNumberGenerator rng = RandomNumberGenerator.Create())
{
    rng.GetBytes(base256Value);
}

// Da Base256ToBase23 den Wert als Big-Endian interpretiert und 
// BigInteger aus einem Byte-Array in two's complement interpretiert wird,
// stellen wir sicher, dass der Wert positiv ist.
// Falls das erste Byte (MSB im Big-Endian) >= 0x80 ist, setzen wir es auf einen kleineren Wert.
if (base256Value[0] >= 0x80)
{
    base256Value[0] = (byte)(base256Value[0] & 0x7F);
}

// Messen der Zeit für die Umrechnung von Base256 zu Base23
Stopwatch sw = Stopwatch.StartNew();
List<int> length = Source.ConvertBase256ToBase23(base256Value);
sw.Stop();

Console.WriteLine("Conversion finished in {0} ms.", sw.ElapsedMilliseconds);
Console.WriteLine("Length of Base23 string: " + length);

Dein Code braucht bei bei folgender Eingabe ~ 60 Sekunden auf meinem AMD 9950.

Conversion finished in 62376 ms.
Length of Base23 string: 362193

Ich hab auch o3-mini befragt einen besseren und effizienteren Code zu schreiben, der bei mir dann ~30 Sekunden dauert.

Conversion finished in 32243 ms.
Length of Base23 string: 362193
public static class AcceleratedBaseConverter
{
    // Definiert das Alphabet für Base23 (10 Ziffern + 13 Buchstaben)
    private const string Base23Alphabet = "0123456789ABCDEFGHJKLMN";

    // Hilfsdictionary für die Umrechnung eines Zeichens in den numerischen Wert.
    private static readonly Dictionary<char, int> Base23CharToValue = Base23Alphabet
        .Select((c, i) => new { c, i })
        .ToDictionary(x => x.c, x => x.i);

    /// <summary>
    /// Konvertiert einen Base23‑String in ein Byte‑Array (Base256, Big‑Endian) unter Verwendung
    /// eines Divide‑and‑Conquer‑Ansatzes zur Beschleunigung.
    /// </summary>
    /// <param name="input">Der Input-String in Base23.</param>
    /// <returns>Das Byte‑Array (Big‑Endian) zur Darstellung des Wertes.</returns>
    public static byte[] Base23ToBase256(string input)
    {
        // Erzeugt einen BigInteger aus dem Base23‑String mittels eines beschleunigten, parallelen Ansatzes.
        BigInteger bigInt = Base23ToBigInteger(input);

        // Wandelt den BigInteger in ein Byte‑Array um. BigInteger.ToByteArray() liefert little‑endian.
        byte[] littleEndianBytes = bigInt.ToByteArray();

        // Entfernt ggf. ein überflüssiges Vorzeichenbyte (bei positiven Werten kann ein zusätzliches 0-Byte am Ende vorkommen).
        if (littleEndianBytes.Length > 1 && littleEndianBytes[littleEndianBytes.Length - 1] == 0)
        {
            Array.Resize(ref littleEndianBytes, littleEndianBytes.Length - 1);
        }

        // In Big‑Endian umkehren.
        Array.Reverse(littleEndianBytes);
        return littleEndianBytes;
    }

    /// <summary>
    /// Konvertiert ein Byte‑Array (Base256, Big‑Endian) in einen Base23‑String.
    /// Diese Methode arbeitet sequentiell, da die wiederholte Division inhärent sequentiell ist.
    /// </summary>
    /// <param name="bytes">Das Byte‑Array in Big‑Endian.</param>
    /// <returns>Der Base23‑String.</returns>
    public static string Base256ToBase23(byte[] bytes)
    {
        if (bytes == null || bytes.Length == 0)
            return Base23Alphabet[0].ToString();

        // Klont und kehrt das Byte‑Array um, da BigInteger little‑endian erwartet.
        byte[] temp = (byte[])bytes.Clone();
        Array.Reverse(temp);
        BigInteger value = new(temp);

        if (value < 0)
            throw new ArgumentException("Negativer Wert wird nicht unterstützt.");

        // Sonderfall: 0.
        if (value.IsZero)
            return Base23Alphabet[0].ToString();

        // Umrechnung über wiederholte Division.
        List<char> chars = new();
        while (value > 0)
        {
            value = BigInteger.DivRem(value, 23, out BigInteger remainder);
            chars.Add(Base23Alphabet[(int)remainder]);
        }
        chars.Reverse();
        return new string(chars.ToArray());
    }

    /// <summary>
    /// Konvertiert einen Base23‑String in einen BigInteger unter Verwendung eines 
    /// Divide‑and‑Conquer‑Ansatzes. Dabei wird der String in Blöcke (Chunks) aufgeteilt,
    /// die unabhängig (und parallel) verarbeitet und anschließend wieder kombiniert werden.
    /// </summary>
    /// <param name="input">Der Base23‑String.</param>
    /// <returns>Der entsprechende BigInteger.</returns>
    public static BigInteger Base23ToBigInteger(string input)
    {
        if (string.IsNullOrEmpty(input))
            return BigInteger.Zero;

        // Wählen Sie eine sinnvolle Blockgröße (hier 1000 Zeichen pro Block).
        const int blockSize = 1000;
        int blockCount = (input.Length + blockSize - 1) / blockSize;
        BigInteger[] blockValues = new BigInteger[blockCount];
        int[] blockLengths = new int[blockCount];

        // Parallelverarbeitung der einzelnen Blöcke.
        Parallel.For(0, blockCount, i =>
        {
            int start = i * blockSize;
            int len = Math.Min(blockSize, input.Length - start);
            blockLengths[i] = len;
            // Verwende ReadOnlySpan<char> um Kopien (wie bei Substring) zu vermeiden.
            blockValues[i] = ConvertBlock(input.AsSpan(start, len));
        });

        // Precomputiere für jeden Block: power[i] = 23^(Länge des Blocks)
        BigInteger[] blockPowers = new BigInteger[blockCount];
        for (int i = 0; i < blockCount; i++)
        {
            blockPowers[i] = BigInteger.Pow(23, blockLengths[i]);
        }

        // Berechne von rechts her kumulative Faktoren:
        // factors[i] entspricht dem Faktor, mit dem der Block i gewichtet werden muss.
        // Es gilt: factors[i] = 23^(Summe der Längen der Blöcke i bis n-1)
        BigInteger[] factors = new BigInteger[blockCount + 1];
        factors[blockCount] = BigInteger.One;
        for (int i = blockCount - 1; i >= 0; i--)
        {
            factors[i] = factors[i + 1] * blockPowers[i];
        }

        // Kombiniere die Blöcke zu einem Gesamtwert:
        // Ergebnis = blockValues[0] * factors[1] + blockValues[1] * factors[2] + ... + blockValues[n-1]
        BigInteger result = BigInteger.Zero;
        for (int i = 0; i < blockCount; i++)
        {
            result += blockValues[i] * factors[i + 1];
        }
        return result;
    }

    /// <summary>
    /// Konvertiert einen Block (als ReadOnlySpan&lt;char&gt;) eines Base23‑Strings in einen BigInteger.
    /// Diese Methode arbeitet sequentiell.
    /// </summary>
    /// <param name="block">Der Block (Chunk) des Base23‑Strings.</param>
    /// <returns>Der entsprechende BigInteger-Wert dieses Blocks.</returns>
    private static BigInteger ConvertBlock(ReadOnlySpan<char> block)
    {
        BigInteger value = BigInteger.Zero;
        foreach (char c in block)
        {
            if (!Base23CharToValue.TryGetValue(c, out int digit))
                throw new ArgumentException($"Ungültiges Zeichen '{c}' im Input-String.");
            value = value * 23 + digit;
        }
        return value;
    }
}

Ich gehe aber davon aus, dass das noch um Welten optimiert werden kann - aber eher nicht mit Parallelität.


Aber noch der Disclaimer: ich hab die Ergebnisse nicht auf Korrektheit validiert.

Eine Zahl mit 10 Millionen Stellen ist aber auch schon sehr groß.

Aber noch ein paar Verbesserungsvorschläge:
- Kannst du nicht direkt den BigInteger(byte[]) Konstruktor benutzen?
- Statt Division und Modulo getrennt zu berechnen, kannst du DivRem benutzen.

Edit:

Abt, du warst schneller! Aber genau so meinte ich den verbesserten Code (nur an das Reverse des Arrays wegen Little-Endian hatte ich nicht gedacht).