Wie viele Byte sind erforderlich, um zu halten N Dezimalstellen

Ich habe einen string beliebiger Länge darstellt, ein dezimaler integer-Wert, und konvertieren Sie diesen string in eine große Zahl im plain-binary-format (nicht BCD, mehr als 64 bits).

Ich bin auf der Suche nach einer guten einfachen Schätzung, wie viele bytes werden halt N Dezimalstellen sicher und ohne Verwendung von floating-point-Arithmetik.

  • 1) Macht Ihr großen int-Bibliothek haben einige Length Funktion? 2) Warum wollen Sie vermeiden floating point?
  • Es wird davon abhängen, wie es gespeichert ist. Für die standard-Kodierung, jede Ziffer verwendet 4 bits, so nBytes=(nDigits+1)/2. Sie sollten auch erwägen, Kompression, sogar in-memory-Komprimierung, mit einigen schnellen Algorithmus. Verhältnis variieren, aber Sie sparen Platz für Sie sicher. Siehe auch wenn Ihre Daten möglicherweise einige Muster, wie die Speicherung eines delta zwischen den Werten (nach Art z.B.), die noch mehr erhöhen die Kompression.
InformationsquelleAutor kludg | 2012-02-25
  1. 17

    Ohne Verwendung von Gleitkomma-Arithmetik: Für N Dezimalstellen, müssen Sie

    (98981 * N) / 238370 + 1

    bytes. 98981/238370 ist eine gute rationale approximation (von oben) zu log(10)/log(256) (9th konvergent), integer-division schneidet, daher fügen Sie 1. Die Formel wird eng für N < 238370, die Anzahl der bytes benötigt, um zu repräsentieren 10^N - 1 ist genau das gegeben, dass es überschätzt für N ein Vielfaches von 238370 und wirklich große N. Wenn Sie nicht zu viel Angst vor der Aufteilung der ungerade byte zu viel, können Sie auch (267 * N) /643 + 1, (49 * N) /118 + 1, (5 * N) /12 + 1 oder, womit etwa 10% des Platzes, (N + 1) /2.

    Als @Henrick Hellström Punkte heraus, in Delphi müsste man die Verwendung der div - operator für integer-division (verpasste den delphi-tag).

    • Für Klarheit, der / - operator führt eine floating point division. Verwenden Sie den div-operator.
    InformationsquelleAutor Daniel Fischer
  2. 6

    Müssen Sie so viele bits: ceil(N/log10(2)). Aufrunden auf das nächste Vielfache von 8, das heißt, ceil((N/log10(2))/8)+1 bytes.

    • Ich würde hinzufügen, der Sicherheit etwas zu berücksichtigen, für Rundungsfehler.
    • Ohne floating-point Arithmetik: da log10(2) =~ 3.3, können Sie einfach berechnen N*3.5/8 = (N*3 + N/2)/8. @CodeInChaos: ceil soll in der Runde. In jedem Fall wird die integer-Formel überschätzen.
    • Ich denke, eine einfache Abschätzung kann auf der Tatsache beruhen, dass 10 bits enthält 3 Dezimalstellen sicher.
    • das ist nicht gut genug. Angenommen, dass der exakte quotient ist 10.0001 (und einige weitere stellen), aber aufgrund von floating-point-Rundungsfehler der Wert, den Sie passieren, um ceil ist 9.9999. Dann ceil Runde wird es um 10 statt 11. Wenn Sie versuchen, um genügend Raum für etwas, zu unterschätzen ist das eine katastrophale Situation in der Erwägung, dass eine überschätzung der durch ein byte ist in der Regel in Ordnung, so müssen Sie vorsichtig sein, Ungenauigkeiten, wenn Sie Fließkomma-Arithmetik es zu tun.
    • Das sagte, ich denke, in diesem Fall sind Sie OK, weil die +1 fügen Sie bei der Umwandlung von bits in bytes ist genug, um Garantie, dass Ihre byte-Ergebnis ist nie zu unterschätzen, auch wenn Sie Ihre bit-Ergebnis ist. Der schlechte Fall ist eine "genaue Ergebnis" der (8*N) + 0.0001 erfordern N+1 bytes, aber das kommt als floating-point -(8*N) - 0.0001. Sie ceil zu 8*N, teilen N reservieren Sie N+1 bytes, jeder ist glücklich.
    InformationsquelleAutor zvrba
  3. 1

    ((size_t)ceil(N/log10(2)) + CHAR_BIT - 1) /CHAR_BIT

    Nun 1/log10(2) ~= 3.32 angenähert werden können als 10.0/3=3.3(3).

    Also ohne floating-point-wäre es bei den meisten (((size_t)N*10+2)/3 + CHAR_BIT - 1) /CHAR_BIT C bytes.

    Uhr overflows, wenn N ist groß.

    InformationsquelleAutor Alexey Frunze
  4. 0

    Vielleicht suchen Sie nach fixed-point Arithmetik

    Den maximalen Wert eines fixed-point-Typ ist einfach der größte Wert
    dargestellt werden kann in der zugrunde liegenden Ganzzahl, multipliziert mit
    der Skalierungsfaktor; und ähnlich für den minimalen Wert.
    Betrachten Sie zum Beispiel ein fixed-point-Typ, dargestellt als binäre
    ganze Zahl mit b bits im Zweierkomplement-format, mit einem scaling-Faktor
    1/2f (das ist die Letzte f-bits Bruchteil bits): die minimale
    Darstellbare Wert ist −2b-1/2f und der maximale Wert ist (2b-1-1)/2f.

    InformationsquelleAutor amit
Schreibe einen Kommentar