Ich habe ein Array von nicht signierten Zeichen in c Ich versuche in Basis 10 zu drucken, und ich bin fest. Ich denke, das wird im Code besser erklärt, also gegeben:
%Vor%Ich möchte 197121 drucken.
Dies ist trivial mit kleinen Basis-256-Arrays. Man kann einfach 1 * 256 ^ 0 + 2 * 256 ^ 1 + 3 * 256 ^ 2.
Wenn mein Array jedoch 100 Byte groß war, wird dies schnell zu einem Problem. Es gibt keinen integralen Typ in C, der 100 Bytes groß ist, weshalb ich zu Beginn Zahlen in unsignierten char-Arrays speichere.
Wie soll ich diese Zahl in der Basis 10 effizient ausdrucken?
Ich bin ein bisschen verloren.
Es gibt keine einfache Möglichkeit, dies nur mit der Standard-C-Bibliothek zu tun. Sie müssen entweder die Funktion selbst schreiben (nicht empfohlen) oder eine externe Bibliothek wie GMP verwenden.
Wenn Sie beispielsweise GMP verwenden, können Sie Folgendes tun:
%Vor%Als ich diese Frage sah, wollte ich sie lösen, aber in diesem Moment war ich sehr beschäftigt. Dieses letzte Wochenende konnte ich einige Stunden Freizeit gewinnen, also habe ich über meine ausstehende Herausforderung nachgedacht.
Zunächst schlage ich vor, dass Sie die obige Antwort berücksichtigen. Ich benutze nie GMP-Bibliothek, aber ich bin sicher, dass es eine bessere Lösung als ein handgemachter Code ist. Sie könnten auch interessiert sein, Code von bc Rechner zu analysieren; es kann mit großen Zahlen arbeiten und ich habe meinen eigenen Code getestet.
Ok, wenn du dich immer noch für einen Code interessierst (nur mit Support C Sprache und Standard C Bibliothek) kann ich dir etwas geben.
Vor allem ein bisschen Theorie. In der grundlegenden numerischen Theorie (modulare arithmetische Ebene) gibt es einen Algorithmus, der mich dazu inspiriert, zu einer Lösung zu kommen. Multiply and Power Algorithmus zum Lösen von a ^ N Modul m:
%Vor%Dabei ist k die Anzahl der Stellen minus einer von N in der binären Darstellung, und n_i ist eine binäre Zahl. Zum Beispiel (N ist der Exponent):
%Vor%Wenn wir eine Moduloperation als Integer-Division durchführen, können wir einen Teil der Zahl verlieren, so dass wir nur den Algorithmus modifizieren müssen, um relevante Daten nicht zu verpassen.
Hier ist mein Code (achten Sie darauf, dass es ein Ad-hoc-Code ist, starke Abhängigkeit von may Computer Arch. Grundsätzlich spiele ich mit Datenlänge der C-Sprache, also vorsichtig, weil meine Datenlänge nicht die gleiche sein könnte):
%Vor%Zum Kompilieren:
%Vor%Um das Ergebnis zu prüfen, verwenden Sie die direkte Ausgabe als und Eingabe in bc. Einfaches Shell-Skript:
%Vor%Wir haben und Array von unsigned int (4 Bytes), wo wir bei jedem int des Arrays eine Anzahl von 9 Ziffern speichern (% 1000000000UL); daher num [0] haben wir die ersten 9 Ziffern, num [1] wir haben die Ziffern 10 bis 18, num [2] ... Ich benutze herkömmliches Gedächtnis, um zu arbeiten, aber eine Verbesserung kann es mit dynamischem Gedächtnis tun. Ok, aber wie lang könnte es das Array sein? (oder wie viel Speicher müssen wir zuweisen?). Mit bc Calculator (bc -l mit mathlib) können wir bestimmen, wie viele Ziffern eine Zahl hat:
%Vor%Wenn wir Zahlen kennen, wissen wir, wieviele Zahlen wir brauchen:
%Vor%Wenn Sie mit einem Wert wie (2 ^ k) ^ N arbeiten, können Sie den Logarithmus mit diesem Ausdruck auflösen:
%Vor%um die genaue Länge des Integer-Arrays zu bestimmen. Beispiel:
%Vor%Der Wert 1000000000UL (10 ^ 9) ist sehr wichtig. Eine Konstante wie 10000000000UL (10 ^ 10) funktioniert nicht, weil sie einen Überlauf erzeugen kann (versuchen Sie, was mit der Zahl 16 ^ 16 und 10 ^ 10 konstant passiert), und eine Konstante kleiner als 1000000000UL (10 ^ 8) ist korrekt Wir müssen mehr Speicher reservieren und mehr Schritte ausführen. 10 ^ 9 ist die Schlüsselkonstante für unsigned int von 32 Bits und unsigned long long int von 64 Bits.
Der Code besteht aus zwei Teilen: Multiply (einfach) und Power by 2 (schwerer). Multiplizieren ist nur Multiplikation und Skalierung und propagieren den Integer-Überlauf. Nach dem Prinzip der assoziativen Eigenschaft in Mathe wird genau das umgekehrte Prinzip ausgeführt. Wenn also k (A + B + C) ist, dann wollen wir kA + kB + kC, wobei die Zahl k * A * 10 ^ 18 + k * B * 10 ist ^ 9 + k C. Im Allgemeinen kann die Operation k C eine Zahl größer als 999 999 999 erzeugen, aber nie größer als 0xFF FF FF FF FF FF FF FF. Eine Zahl größer als 64 Bits kann niemals in einer Multiplikation auftreten, weil C eine vorzeichenlose ganze Zahl von 32 Bits ist und k eine vorzeichenlose Abkürzung von 16 Bits ist. Im Wortsfall haben wir diese Nummer:
%Vor%Nach Mul k B müssen wir 0x FF FE von der letzten Multiplikation von C addieren (B = k (C / Modul)), und so weiter (wir haben 18 Bit arithmetischen Offset, genug, um korrekte Werte zu garantieren).
Die Leistung ist komplexer, aber es ist im Wesentlichen das gleiche Problem (Multiplikation und Add), also gebe ich ein paar Tricks über die Code-Power:
Ich habe eine andere Methode entwickelt, die große Zahlen hinzufügt. Diese letzten beweise ich nicht so viel, aber ich denke, es funktioniert gut. Sei nicht böse mit mir, wenn es einen Fehler hat.
... und das ist alles!
PD1: Entwickelt in
%Vor%Zahlen wie 256 ^ 1024 geben es aus:
%Vor%Ein bucle, das compute i ^ i ist, wo ich zu i = 1 ... 1024 gehe:
%Vor%Für Zahlen wie 65355 ^ 65355 ist die aufgewendete Zeit verrückt.
PD2: Meine Antwort ist so spät, aber ich hoffe, dass mein Code nützlich sein wird.
PD3: Entschuldigung, erklären Sie mir auf Englisch ist eines meiner schlimmsten Handicaps!
Letztes Update: Ich hatte gerade eine Idee, dass mit demselben Algorithmus, aber mit anderer Implementierung, die Antwort verbessert und der zu verwendende Betragsspeicher reduziert wird (wir können die vollständigen Bits von unsigned int verwenden).Das Geheimnis: n ^ 2 = n * n = n * (n - 1 + 1) = n * (n - 1) + n. (Ich werde diesen neuen Code nicht machen, aber wenn jemand interessiert ist, vielleicht nach den Prüfungen ...)
Hier ist eine Funktion, die das tut, was Sie wollen:
%Vor% Das sieht für mich perfekt lesbar aus. Übergeben Sie einfach das Array unsigned char * , das Sie konvertieren möchten, und die Größe. Beachten Sie, dass es nicht perfekt sein wird - für willkürliche Genauigkeit empfehle ich, in die GNU MP BigNum-Bibliothek zu schauen, wie bereits vorgeschlagen wurde.
Als Bonus mag ich es nicht, wenn Sie Ihre Zahlen in Little-Endian-Reihenfolge speichern, also ist hier eine Version, wenn Sie Basis-256-Nummern in Big-Endian-Reihenfolge speichern möchten:
%Vor%Nur Dinge zu beachten.
Es ist vielleicht zu spät oder zu irrelevant, um diesen Vorschlag zu machen, aber könnten Sie jedes Byte als zwei Basis 10 Ziffern (oder eine Basis 100) statt einer Basis 256 speichern? Wenn Sie die Division noch nicht implementiert haben, bedeutet das, dass Sie nur addieren, subtrahieren und vielleicht multiplizieren können. Diese sollten nicht zu schwer zu konvertieren sein. Sobald Sie das getan haben, wäre das Drucken trivial.
Tags und Links c base-conversion