Ich versuche, einen Zeitstempel (nur Bruchteil von Sekunden) von Nanosekunden (Einheiten von 10 ^ -9 Sekunden) auf die untere Hälfte eines NTP-Zeitstempels (Einheiten von 2 ^ -32 Sekunden) zu skalieren. Effektiv bedeutet dies Multiplizieren mit 4,2949673. Aber ich muss es ohne Fließkomma-Mathematik tun, und ohne Ganzzahlen zu verwenden, die größer als 32 Bits sind (tatsächlich schreibe ich dies tatsächlich für einen 8-Bit-Mikrocontroller, so dass sogar 32-Bit-Mathematik teuer ist, insbesondere Divisionen).
Ich habe ein paar Algorithmen entwickelt, die einigermaßen gut funktionieren, aber ich habe keine wirklichen Grundlagen in numerischen Methoden, daher würde ich mich über Vorschläge freuen, wie man sie verbessern kann, oder irgendwelche anderen Algorithmen, die das wären genauer und / oder schneller.
Die ersten zwei Konstanten wurden gewählt, um die korrekte Zahl etwas zu unterschreiten, statt sie zu überschwingen, und der Endfaktor von 67078 wurde empirisch ermittelt, um dies zu korrigieren. Produziert Ergebnisse innerhalb von +/- 4 NTP-Einheiten mit dem korrekten Wert, was +/- 1 ns ist - akzeptabel, aber der Rest ändert sich mit ns . Ich denke, ich könnte einen anderen Begriff hinzufügen.
Basierend auf der binären Erweiterung von 4.2949673 (tatsächlich basierend auf der binären Erweiterung von 2.14748365, da ich mit der Verdoppelung anfange und eine hinzufüge, um das Runden zu erreichen). Möglicherweise schneller als Algorithmus 1 (ich habe die Benchmarks noch nicht rausgeholt). Die +3 wurde empirisch ermittelt, um ein Unterschießen aus dem Abbruch aller dieser niederwertigen Bits auszuschließen, aber es funktioniert nicht optimal.
Grundlegende Festkommamultiplikation, Simulieren eines 32x32 - & gt; 64 Produkt mit vier 16x16 - & gt; 32 Produkte. Die Konstante round wurde ausgewählt, um den Fehler mithilfe einer einfachen binären Suche zu minimieren. Dieser Ausdruck ist über den gesamten gültigen Bereich bis +/- 0,6 NTP gut.
Das führende 4 im Skalenfaktor wird in der Schicht behandelt. Compiler können in der Regel ziemlich anständigen Code für diese Art von Sache generieren, aber es kann oft mit handgeschriebenen Assembly rationalisiert werden, wenn Sie müssen.
Wenn Sie nicht so viel Genauigkeit benötigen, können Sie lowTerm und round loswerden und erhalten eine Antwort, die bis +/- 1.15 NTP gut ist:
Ich könnte das Offensichtliche sagen ... aber haben Sie die Interwebz für Fixpunkt-Mathematikbibliotheken gegoogelt? Es gibt viele von ihnen. Hier ist eine gute mit C ++ und x86-Implementierungen auf Flipcode-Archiven:
Tags und Links c numerical-methods fixed-point