Wie berechne ich die erste Dezimalstelle einer Division zwischen großen Zahlen?

Question

Ich habe zwei unsigned long longs X und Y, wobei X < Y, aber beide sehr groß sein können. Ich möchte die erste Ziffer nach dem Dezimalpunkt von X / Y berechnen. Zum Beispiel, wenn X 11 und Y 14 ist, dann ist 11 / 14 .785…, also sollte das Ergebnis 7 sein.

(X * 10) / Y würde funktionieren, außer wenn X * 10 überläuft, produziert es das falsche Ergebnis. Die Konvertierung in double würde funktionieren, wenn ich Grund zu der Annahme hätte, dass sie genau genug ist, um das richtige Ergebnis zu berechnen.

Dies ist in C. Vielen Dank für jede Hilfe!

Answer 1

Ich bin nicht bereit, ein genaues Ergebnis über den Gleitkomma-Cast zu garantieren, es sei denn, die Mantisse hat genug Bits, um alle ganzzahligen Werte genau darzustellen. Zum Beispiel, betrachte y=9223372036854775807 und x = (y div 10) - 1 = 922337203685477579. wobei "div" ganzzahlige Division ist. x/y ist 0,09999999999999999981568563067746..., aber mit Doubles bekommst du >= 0,1. Dies ist ein Ergebnis davon, dass Doubles nur 52 Stellen der Genauigkeit in der Signifikanten haben (während y 61 Bits und x ungefähr 58 benötigt)

Sie können möglicherweise eine 80-Bit- oder 128-Bit-FP-Genauigkeit verwenden, in welchem Fall Sie die richtige Antwort erhalten würden, weil die Mantisse >=64 Bit (ULL sind 64 Bit, richtig?) wäre und so könnten Sie die Zahlen verlustfrei darstellen.

Ich würde mit einer Approximation beginnen (entweder mit ganzzahliger oder FP-Arithmetik) und dann eine Testmultiplikation durchführen, um zu sehen, ob die Antwort 1 weniger oder mehr sein sollte. Der Schlüsselgedanke ist, dass Sie immer noch zwei möglicherweise überlaufene Ganzzahlen vergleichen können, solange Sie wissen, dass der Unterschied zwischen den beiden Mengen weniger als die Hälfte der maximalen vorzeichenlosen Ganzzahl beträgt. Diese Art von Vergleichstechnik ist notwendig, wenn z.B. TCP-Sequenznummern überlaufen.

Falls Sie nur ganzzahlige Arithmetik verwenden möchten, funktioniert die unten stehende Funktion "fdd(x,y)". Ich habe ein main() hinzugefügt, um einige Ergebnisse zu zeigen:

#include 
using namespace std;

typedef unsigned char ull; // ändern Sie char in einen beliebigen integralen Typ z.B. long long

const ull maxull=(ull)-1;
const ull halfull = maxull/2;
typedef unsigned long long asint;

// x = X mod (maxull+1), y= Y mod (maxull+1). wir kennen nur x und y
// wenn wir annehmen, dass |X-Y|x;
}

// vorausgesetzt x10 ist, um eine spätere Division durch 0 zu vermeiden
 ull r=y/10;
 if (r*10==y) return x/r;
 ull ub=x/(r+1); // ub >= 10x div y (ohne Überlauf)
 ull x10=x*10; // Überlauf zulassen
 cout<<"ub="<<(asint)ub<<" x10="<<(asint)x10<<" r="<<(asint)r<<" ";
 return less_mod_near(x10,ub) ? ub-1 : ub; 
  // den Fall, dass 10 gerade in y passt, haben wir bereits abgedeckt
}

int pdd(ull x, ull y,ull mustbe)
{
    ull d=fdd(x,y);
    cout << (asint)x << '/' << (asint)y << " = ." << (asint)d << "...";
    if (d!=mustbe) cout << " (sollte "<<(asint)mustbe<<" sein)";
    cout<

`Ausgabe:

0/1 = .0...
1/2 = .5...
11/101 = .1...
10/101 = .0...
ub=7 x10=234 r=6 49/69 = .7...
ub=7 x10=244 r=6 50/69 = .7...
ub=6 x10=224 r=6 48/69 = .6...
160/200 = .8...
161/200 = .8...
159/200 = .7...
ub=9 x10=236 r=25 254/255 = .9...`

Answer 2

Die Umwandlung in double würde funktionieren, wenn ich Grund zu der Annahme hätte, dass sie genau genug ist, um das richtige Ergebnis zu berechnen.

Wenn Sie nur die erste Ziffer benötigen, dann ist double sicherlich genau genug.

Bearbeiten: wrang-wrangs Gegenbeispiel in den Kommentaren beweist mich falsch.

Answer 3

Die Konvertierung in einen Double gibt 12 Bits Präzision sowohl im Divisor als auch im Dividenden von insgesamt 64 Bits auf. Die meiste Zeit liefert sie die korrekte Antwort, gelegentlich jedoch mit Rundungsfehlern, es sei denn, sie wird im 80-Bit-Fließkommaformat gespeichert.

Bearbeitung: Es sei denn, ich bin einfach zu müde, um den Fehler zu sehen, denke ich, dass die Antwort von wrang-wrang funktionieren wird. Ich habe morgen Arbeit, 6 Stunden Fahrt zum Kundenstandort. Ugg. Gute Nacht.

Bearbeiten: Noch eine Sache. x86 verwendet eine 80-Bit-interne Darstellung. Ich denke, es gibt Opcodes, die eine int64-zu-flot80-Konvertierung garantieren, wenn Sie ein paar ASM-Anweisungen herumwerfen möchten. Das wäre eine elegantere und sicherlich schnellere Lösung als eine reine C-Implementierung, obwohl sie nicht portabel wäre.

Answer 4

X % Y gibt den Rest R

Dann können Sie den Bruchteil Ihrer Antwort aus R und Y berechnen

R / Y

Um die erste Ziffer zu erhalten, verwenden Sie die Ganzzahldivision:

(long)((long)10*R/Y)

Dies sollte die Zahlen abrunden und alle zusätzlichen Dezimalstellen verwerfen.

Bearbeiten:

Um Ihre Frage anzupassen (für diejenigen, die pingelig sein wollen) ist es

Y % X = R

und

R / X

Answer 5

Wie wäre es mit

x / ((y + 9) / 10)

Das y + 9 steht für das Aufrunden des Quotienten y / 10 im Nenner, sodass das Gesamtergebnis abgerundet wird.

Für große x und y sollte es fast immer korrekt sein, aber es ist nicht perfekt, es ergibt 5 für dein Beispiel 11 / 14.

Das Problem ist, dass du aufgrund der Division Informationen verlierst. Da die Multiplikation mit zehn bereits überläuft, kommst du daran nicht vorbei, außer du verwendest einen größeren numerischen Datentyp.