Wie gehen Sie mit Präzisionsproblemen in Matlab um?

Question

Ich versuche, einen Geburtstag Problem Rechner in Matlab zu schreiben, aber mit einer Genauigkeit Problem, (1 - sehr kleine Gleitkommazahl = 1).

Mein aktuelles Problem ist, dass ich sehen möchte, wie viele Versuche erforderlich sind, um eine UUID auf einer Website zu erraten, wo es 23.000.000 aktive Sitzungstoken gibt, die 128 Bits möglicher eindeutiger Werte haben, so dass die Wahrscheinlichkeit eines Rates gültiges Token ist über 50%.

Ich begann durch den Prozess Simulieren von:

1. ich meine success_rate bis (23.000.000/(2^128))
2. ich meine failure_rate auf (1 - success_rate)

Aber dann bemerkte ich, dass dieser Wert 1 ist.

Schlechter, Eingabe (1 - 23000000/(2^128))^n > 0.5 in Wolfram Alpha liefert keine sinnvollen Antworten.

Mein erster Gedanke war, Matlab vollständig zu entfernen und meine eigene Bibliothek in Java zu erstellen, die überhaupt keine Fließkommawerte verwendet und stattdessen die Verhältnisse als Paare von BigDecimal-Objekten speichert, wodurch alle Genauigkeitsprobleme eliminiert würden Berechnung am allerletzten Punkt und speichere diese Berechnung als ein Minimum-Maximum-Paar, um das Ergebnis als einen Bereich zu zeigen, in dem die Lösung liegt (wobei exakte Lösung nicht existiert, weil Gleitkommadivision Fehler und Werte verursacht, die nicht dargestellt werden können) Verwenden Sie Fließkomma der angegebenen Genauigkeit, kann aber genaue Antwort darstellen, indem Sie nur das tatsächliche Verhältnis angeben, das genau ist, da die Division niemals angewendet wird, stattdessen wird das Verhältnis angezeigt).

Gibt es eine Möglichkeit, sich mit dieser Art von Problem zu befassen, ohne ein solches System erfinden zu müssen, oder sind diese Probleme mit Floating-Point-Systemen unmöglich zu lösen?

Answer 1

... sind diese Probleme mit Floating-Point-Systemen nicht zu lösen?

Kurze Erläuterung:

Nun ja standardmäßig in MATLAB und nicht, wenn Sie die symbolischen Toolbox in MATLAB verwenden.

Sie können in MATLAB auf jeden Fall sehr sehr kleine Zahlen mit Gleitkommazahlen mit doppelter Genauigkeit darstellen. Das Problem, mit dem Sie es zu tun haben, liegt jedoch in der Verwendung von Gleitkommazahlen mit doppelter Genauigkeit, die zu viele Größenordnungen voneinander entfernt sind. Bei Berechnungen werden Sie durch die Genauigkeit der MATLAB-Berechnungen eingeschränkt.

Zum Glück gibt es eine Toolbox, um dieses Problem in Form der Symbolic Toolbox und variable-precision arithmetic zu lindern. Schauen Sie sich das an, wenn Sie etwas anderes als 1 erhalten möchten, wenn Sie 1 - (small_value) ausführen.

Längere Erläuterung:

http://www.mathworks.com/help/matlab/matlab_prog/floating-point-numbers.html#f2-98720

doppelte Genauigkeit Gleitkommazahlen in MATLAB hat eine ziemlich beeindruckende maximale Genauigkeit von -1.79769e+308 to -2.22507e-308 and 2.22507e-308 to 1.79769e+308.MATLAB berechnet jedoch nur eine maximale Genauigkeit von 53 Bits: eine Genauigkeit von 9,007199255 × 10¹⁵.

Hier ist meine Erklärung, wie das das Ergebnis produzieren könnte, die Sie je gesehen haben (1 - small_value = 1):

Die Zahl 1.234e12 mit einer Genauigkeit von etwa 1e16 dargestellt wird, was bedeutet, MATLAB auf diese arbeiten kann Nummer mit einem Fehler von etwa 1e-4. Simplyly, 2.345e-7 hat einen Berechnungsfehler von ungefähr . Daher wird das Hinzufügen der zwei Zahlen einen Fehler von 1e-4 haben, so dass die kleinere Zahl in dem Fehler der Berechnung, die MATLAB durchführt, verloren gegangen ist.

Wenn es Ihnen nichts ausmacht längere Berechnungszeiten abzuwarten, die mit der Ausführung von Operationen auf einer viel größeren Zahl als 53 Bit verbunden sind, dann würde ich Ihnen dringend die Symbolic Toolbox in MATLAB empfehlen (nämlich die vpa Funktion).

Wenn meine Antwort nicht gut zu Ihnen passt, können Sie vielleicht diese answer to a related question in den MATLAB-Foren ausprobieren. Ich habe Teile meiner Beispielnummern aus dieser Antwort genommen.

Happy Coding, ich hoffe, das hilft!

Answer 2

leicht erklärt:

mit:

eps(double(1)) 

in Matlab finden Sie die kleinste Lücke zwischen 1 (an seinem größten Präzision = double) und die nächste Gleitpunktzahl kann es finden unterscheiden, wenn Mathe Durchführung Operationen. In diesem Fall ist der Spalt gleich 2.2204e-016

Seit:

success_rate = (23,000,000/(2^128)) 

6.7591e-032 zurückkehren wird, und es ist viel kleiner als die oben eingeführte Lücke, wenn 1 durchführt - 6.7591e-032 Matlab versteht Das heißt, man subtrahiert 0 von 1 und erhält daher immer 1 als Antwort. Ich hoffe es hilft.

Answer 3

Die anderen Antworten haben erklärt, warum Sie die Berechnungen, die Sie wollen, nicht mit der Verschiedenheit der von Ihnen verwendeten Zahlen durchführen können. Wie ich in einem Kommentar erwähnt habe, können Sie jedoch mit kleineren Zahlen experimentieren, um einen Trend zu zeigen. Nennen wir den "projizierten" Wert size_of_key_space/(2 * number_of_keys). Dies ist eine Art naiv erwarteter Wert für eine 50% ige Erfolgswahrscheinlichkeit. Um dies zu beweisen, habe ich eine Simulation für eine Reihe verschiedener Schlüsselsätze und Schlüsselräume durchgeführt. Alle sind groß, mit unterschiedlichen sparsity:

function sparse_probability() 

num_keys = logspace(2, 5, 15); % number of keys varies from 1e2 to 1e5 
key_spaces = logspace(6, 12, 15); % size of key space varies from 1e6 to 1e12 
% so p_sucess varies from 1e-4 to 1e-7 

num_experiments = length(num_keys); 

results = zeros(1,num_experiments); 
proportions = zeros(1,num_experiments); 

for i = 1:num_experiments 
    num_objs = num_keys(i); 
    size_of_key_space = key_spaces(i); 
    p_success = num_objs/size_of_key_space; 
    p_fail = 1 - p_success; 

    total_fail = 1; 
    num_trials = 0; 
    while (total_fail > 0.5) 
     total_fail = total_fail * p_fail; 
     num_trials = num_trials + 1; 
    end 


    results(i) = num_trials; 
    proportions(i) = num_trials/(size_of_key_space/(2*num_objs)); 
    fprintf('p_success = %f, num_trials = %d, ratio = %f, num_keys = %e; size key_space = %e\n', 1 - total_fail, num_trials, proportions(i), num_objs, size_of_key_space); 
end 

Da den Größen des Schlüsselsatzes und Schlüsselraum erheblich variieren, berechne ich das Verhältnis der „projizierte“ Wert über, und die tatsächliche Anzahl der Versuche benötigten 50 zu erreichen % Wahrscheinlichkeit. Der Ausgang der Funktion oben ist:

p_success = 0.500044, num_trials = 6932, ratio = 1.386400, num_keys = 1.000000e+02; size key_space = 1.000000e+06 
p_success = 0.500010, num_trials = 11353, ratio = 1.386293, num_keys = 1.637894e+02; size key_space = 2.682696e+06 
p_success = 0.500006, num_trials = 18595, ratio = 1.386292, num_keys = 2.682696e+02; size key_space = 7.196857e+06 
p_success = 0.500008, num_trials = 30457, ratio = 1.386309, num_keys = 4.393971e+02; size key_space = 1.930698e+07 
p_success = 0.500004, num_trials = 49885, ratio = 1.386300, num_keys = 7.196857e+02; size key_space = 5.179475e+07 
p_success = 0.500001, num_trials = 81706, ratio = 1.386294, num_keys = 1.178769e+03; size key_space = 1.389495e+08 
p_success = 0.500001, num_trials = 133826, ratio = 1.386297, num_keys = 1.930698e+03; size key_space = 3.727594e+08 
p_success = 0.500002, num_trials = 219193, ratio = 1.386298, num_keys = 3.162278e+03; size key_space = 1.000000e+09 
p_success = 0.500001, num_trials = 359014, ratio = 1.386295, num_keys = 5.179475e+03; size key_space = 2.682696e+09 
p_success = 0.500001, num_trials = 588027, ratio = 1.386296, num_keys = 8.483429e+03; size key_space = 7.196857e+09 
p_success = 0.500000, num_trials = 963125, ratio = 1.386295, num_keys = 1.389495e+04; size key_space = 1.930698e+10 
p_success = 0.500000, num_trials = 1577496, ratio = 1.386294, num_keys = 2.275846e+04; size key_space = 5.179475e+10 
p_success = 0.500000, num_trials = 2583771, ratio = 1.386294, num_keys = 3.727594e+04; size key_space = 1.389495e+11 
p_success = 0.500000, num_trials = 4231943, ratio = 1.386295, num_keys = 6.105402e+04; size key_space = 3.727594e+11 
p_success = 0.500000, num_trials = 6931472, ratio = 1.386294, num_keys = 1.000000e+05; size key_space = 1.000000e+12 

Wenn Sie das Verhältnis Spalt im Vergleich zu der Größe des Schlüsselraumes zu zeichnen, würden Sie eine gerade Linie zu bekommen. Wie im Fall ist das Verhältnis im Wesentlichen konstant, solange der Schlüsselsatz und der Schlüsselraum mehrere Größenordnungen voneinander entfernt sind. Beachten Sie, dass die Sparsity variiert, aber das Verhältnis nicht beeinflusst. Dies ist typisch für diese Arten von spärlichen Wahrscheinlichkeitsproblemen.Aus diesem einfachen Experiment können Sie also mit SEHR hoher Wahrscheinlichkeit sagen, dass die Anzahl der benötigten Schlüssel mit 2.3e7 Schlüsseln in einem Schlüsselraum von 2^128 = 3.4e38 das Produkt der Verhältnisgrenze über 1.386294 mit dem projizierten Wert für eine Gesamtsumme von

ist

1.386294 * (2^128/(2 * 2.3e7)) = 1.02550305123542e+31 

Schätzungen erforderlich für eine 50% ige Chance, eine gültige UUID zu erraten.

Bei 1 Billion raten Sie eine Sekunde, würde es 325 Milliarden Jahre dauern, um so viele Vermutungen zu nehmen. Mit anderen Worten, du bist in Sicherheit. :)

Answer 4

Wie von anderen erklärt, ist (1 - 23000000/2^128) zu nah an einem, um in den 53 Bits der Mantisse in einem Gleitkommawert mit doppelter Genauigkeit dargestellt zu werden, also (1 - 230000000/2^128)^n kann nicht berechnet werden.

Andere Softwarepakete (Python + Sympy, Mathematica, ...) können Berechnungen mit beliebiger Genauigkeit ausführen, und für Matlab ist eine Multi-Präzisions-Computing-Toolbox verfügbar. Dadurch können Sie die Berechnung direkt durchführen.

Sie können stattdessen die Gleichung in eine Binomialentwicklung neu ordnen:

(a + b)^n = a^n + C(1,n)a^(n-1)b + C(2,n)a^(n-2)b^2 + ... 

Wo C (k, n) ist die Anzahl der Möglichkeiten von k Elemente aus einem Pool der Größe n wählen. Da b^k für größere k winzig ist, ignorieren Sie diese Begriffe und nähern sie als:

(1 - b)^n = 1 - n b + O(b^2) 

mit b = 23000000/2^38. Die Lösung 1 - n b = 0.5 für n ergibt die von anderen gegebene Näherung n = 2^128/(2 * 23000000).

Herbie kann Ihnen manchmal helfen, Gleichungen neu zu schreiben, um die numerische Stabilität zu verbessern.

Ein weiterer beliebter Trick besteht darin, eine Taylor-Erweiterung in der Nähe des Werts, den Sie annähern wollen, durchzuführen, wobei Sie ein Polynom angeben, das Sie für eine Reihe von Eingaben verwenden können. Der Grad des Polynoms und der gültige Bereich können mithilfe einer Bibliothek mit mehreren Genauigkeiten bestimmt werden, so dass Sie wissen, dass Ihre Werte im gesamten Bereich präzise sind. Wolfram Alpha bietet einen Online-Taylor-Taschenrechner.

1. Higham NJ:

   Weitere Details finden Sie in Büchern wie finden. Genauigkeit und Stabilität numerischer Algorithmen: Zweite Ausgabe. SIAM; 2002.

Answer 5

Das Problem, wie von allen anderen Antworten darauf hingewiesen, dass r = 3000000/(2^128) < eps(1)/2, so 1 + r == 1

Der einfachste Weg ist Ihren Ausdruck, und zu nutzen, einige andere Funktionen auf dem Weg neu zu ordnen. Rewrite:

(1 - 23000000/(2^128))^n = exp(n*log(1- 23000000/(2^128)) 

Nun, dies immer noch das gleiche Problem haben, aber es gibt eine log1p Funktion log(1+x) genau zu berechnen. So verwenden Sie stattdessen:

exp(n*log1p(-23000000/(2^128)))