boost::float_next mittels Lookup-Table?
-
TGGC schrieb:
Also es gibt maximal 2^32, ist also praktisch schon eine Moeglichkeit. Wenn auch nicht besonders elegant.
Naja, das wär schon übel die alle manuell zu schreiben.
Es müssten ja auch wesentlich weniger sein, weil die minimale Differenz ja immer für bestimmte feste Bereiche gilt und diese Bereiche ja exponentiell wachsen. Also etwa so:
Bereich Minimale Differenz -------------------------------- [1, 2] 1.1920929e-7 [2, 4] 2.3841858e-7 [4, 8] 4.7683716e-7 [8, 16] 9.5367432e-7 etc.
Also wären es ja nur 2^8 == 256 Bereiche die abgedeckt werden müssten, ist das korrekt?
Der Teil ist leider Performance-kritisch, deswegen suche ich nach einer möglichst schnellen Variante.
-
Deine Bereiche kannst du ja sehr simpel mit boost::math::float_next ueberpruefen, indem du die 2^32 Moeglichkeiten durchgehst und entsprechend zusammenfasst.
-
Die Boost-Funktion sieht mir eigentlich nicht so kompliziert aus, als dass ich einen Lookup-Table gerechtfertigt halte:
https://github.com/boostorg/math/blob/master/include/boost/math/special_functions/next.hpp#L108
Ich glaube man hat sich schneller in die nötigen Details zu Floating-Point-Zahlen eingearbeitet und das selbst implementiert, als dass man sich eine LUT-Lösung zusammenbastelt,
welche durch ihre Speicherzugriffe wahrscheinlich auch noch nicht besonders effizient sein wird.Mein Tip:
float_next
selbst implementieren da wahrscheinlich- schneller fertig
- effizienter
- man weiss nachher einiges mehr über Floating-Point-Zahlen (kann nie schaden!)Finnegan
-
Die nächste repräsentierbare Fließkommazahl ist, zumindest mit IEEE 754, trivial zu holen: Dort sind Floats nämlich schon lexikographisch sortiert, man braucht nur mit einem integralen Typ zu aliasen:
static_assert( sizeof(float) == sizeof(std::uint32_t) ); ++reinterpret_cast<std::uint32_t&>(f);
Alternativ kann man einfach
std::nexttowards
verwenden.
-
Arcoth schrieb:
Die nächste repräsentierbare Fließkommazahl ist, zumindest mit IEEE 754, trivial zu holen: Dort sind Floats nämlich schon lexikographisch sortiert, man braucht nur mit einem integralen Typ zu aliasen:
static_assert( sizeof(float) == sizeof(std::uint32_t) ); ++reinterpret_cast<std::uint32_t&>(f);
Alternativ kann man einfach
std::nexttowards
verwenden.Das Problem ist, ich muss mit der Funktionalität der Schaltbild-Sprache auskommen. Diese erlaubt zwar das definieren von eigenen Blöcken (== Funktionen) und hat Konstrukte wie
if
,for
,while
odergoto
sowie Variablen und ein paar simple Funktionen, ist aber ansonsten sehr eingeschränkt. Etwas vergleichbares zureinterpret_cast
gibt es z.B. nicht, weswegen das leider schonmal wegfällt.Finnegan schrieb:
Mein Tip: float_next selbst implementieren
Hm, wenn das nur mit den oben genannten Mitteln auskommt wäre das natürlich schön... muss mich mal durch den Source-Code arbeiten ob ich das so nachbauen kann...
Auf jeden Fall verwendet das ja schonmal
ldexp
, was ja mit doubles arbeitet... ich habe aber nur float zur Verfügung, macht das was? Oder kann ich einfach mit einer float Variante vonldexp
arbeiten ohne dass das Ergebnis beeinträchtigt wird?
-
Arcoth schrieb:
Die nächste repräsentierbare Fließkommazahl ist, zumindest mit IEEE 754, trivial zu holen: Dort sind Floats nämlich schon lexikographisch sortiert, man braucht nur mit einem integralen Typ zu aliasen:
static_assert( sizeof(float) == sizeof(std::uint32_t) ); ++reinterpret_cast<std::uint32_t&>(f);
Das ruft undefiniertes Verhalten hervor, weil es die "strikte Aliasingregel" verletzt. Genau denselben Bug findet man auch in dem viel zitiertem Quake3-Invers-Wurzel-Trick, der dann beim GCC ab -O2 nicht mehr das tut, was er soll.
Außerdem erhöhst Du da den Betrag, womit Du Dich bei einer negativen Zahl Richtung Richting Minus Unendlich bewegst und aus Unendlich (positiv wie negativ) ein NAN machst. Da könnte man eine domain_error Ausnahme schmeißen. Den Fall +/- 0 müsste man auch noch abfangen. IMHO, sollte float_next(-0.0f) == float_next(0.0f) sein.
std::numeric_limits<float>::is_iec559
könnte man noch mit in diestatic_assert
ion einbauen, um sicherzustellen, dass man es tatsächlich mit IEEE754 floats zu tun hat.
-
Das ruft undefiniertes Verhalten hervor, weil es die "strikte Aliasingregel" verletzt.
Das ist klar, anders ist diese effiziente Methode aber (ohne Lib-Funktionen wie
nexttoward
oder builtins etc.) nicht zu haben. Natürlich-fno-strict-aliasing
mitgeben.Außerdem erhöhst Du da den Betrag, womit Du Dich bei einer negativen Zahl Richtung Richting Minus Unendlich bewegst und aus Unendlich (positiv wie negativ) ein NAN machst. Da könnte man eine domain_error Ausnahme schmeißen. Den Fall +/- 0 müsste man auch noch abfangen. IMHO, sollte float_next(-0.0f) == float_next(0.0f) sein.
std::numeric_limits<float>::is_iec559
könnte man noch mit in diestatic_assert
ion einbauen, um sicherzustellen, dass man es tatsächlich mit IEEE754 floats zu tun hat.Ja, obiges war nur ein grobes PoC. Kann man alles noch verfeinern.
-
Hier ist eine etwas ausgereiftere Skizze (die annimmt, das wenigstens
isinf
undisnan
gegeben sind):#include <climits> #include <cmath> #include <cstdint> #include <limits> #include <stdexcept> #include <type_traits> template <typename T> struct identity {using type=T;}; template <typename Float> Float next( Float f ) { static_assert( std::numeric_limits<Float>::is_iec559, "" ); using IntAlias = typename std::conditional_t<sizeof(Float)*CHAR_BIT == 32, identity<std::uint32_t>, std::conditional_t<sizeof(Float)*CHAR_BIT == 64, identity<std::uint64_t>, #ifdef __SIZEOF_INT128__ std::conditional_t<sizeof(Float)*CHAR_BIT == 128, identity<unsigned __int128>, std::enable_if<false>> #else std::enable_if<false> #endif // defined >>::type; if (std::isinf(f) || std::isnan(f)) throw std::domain_error(""); auto& alias = reinterpret_cast<IntAlias&>(f); static const auto signbit_mask = IntAlias(1) << (sizeof(alias)*CHAR_BIT - 1); if (alias & signbit_mask) { if (f != 0) { --alias; if (f == 0) // If negative zero has emerged… f = 0; // correct to positive one } else { // f is negative zero alias &= ~signbit_mask; ++alias; } } else ++alias; return f; }
Ich hab versucht irgendwo Attribute oder Pragmas reinzuhauen, die strict aliasing unterbinden; Jedoch scheinen diese nicht zu funktionieren. Daher ist das oben genannte Flag hier Pflicht.
Edit:
sizeof(alias) * CHAR_BIT-1
ist nicht die schlauste Verteilung von Leerraum…
-
Arcoth schrieb:
Das ruft undefiniertes Verhalten hervor, weil es die "strikte Aliasingregel" verletzt.
Das ist klar, anders ist diese effiziente Methode aber (ohne Lib-Funktionen wie
nexttoward
oder builtins etc.) nicht zu haben.
Doch, ist sie:#include <limits> #include <cstring> #include <cstdint> std::uint32_t reinterpret_float_as_uint(float x) { static_assert(sizeof(float) == sizeof(std::uint32_t), "float/uint32_t incompatible"); std::uint32_t result; std::memcpy(&result, &x, sizeof result); return result; } float reinterpret_uint_as_float(std::uint32_t x) { static_assert(sizeof(float) == sizeof(std::uint32_t), "float/uint32_t incompatible"); float result; std::memcpy(&result, &x, sizeof result); return result; }
Im Kompilat wird bei eingeschalteter Optimierung auch nichts mehr von memcpy auftauchen. Der Compiler versteht, was da passiert und macht genau das, was man will ohne Overhead. Habe ich gerade per GCC mit "-O2" auf für die x86_64-Architektur ausprobiert und mir den Assemblercode angesehen.
-
Arcoth schrieb:
Das ruft undefiniertes Verhalten hervor, weil es die "strikte Aliasingregel" verletzt.
Das ist klar, anders ist diese effiziente Methode aber (ohne Lib-Funktionen wie
nexttoward
oder builtins etc.) nicht zu haben. Natürlich-fno-strict-aliasing
mitgeben.Unsinn. Man kann das sehr wohl so machen, dass es funktioniert:
std::uint32_t i; std::memcpy(&i, &f, sizeof(i)); ++i; std::memcpy(&f, &i, sizeof(i));
Man muss einfach nur hinschreiben, was man vom Compiler will. In C++. Nicht in "ich bin so super schlau"-Pseudo-Assembly-Style mit wilden Casts.
-
TyRoXx schrieb:
Arcoth schrieb:
Das ruft undefiniertes Verhalten hervor, weil es die "strikte Aliasingregel" verletzt.
Das ist klar, anders ist diese effiziente Methode aber (ohne Lib-Funktionen wie
nexttoward
oder builtins etc.) nicht zu haben. Natürlich-fno-strict-aliasing
mitgeben.Unsinn. Man kann das sehr wohl so machen, dass es funktioniert:
std::uint32_t i; std::memcpy(&i, &f, sizeof(i)); ++i; std::memcpy(&f, &i, sizeof(i));
Man muss einfach nur hinschreiben, was man vom Compiler will. In C++. Nicht in "ich bin so super schlau"-Pseudo-Assembly-Style mit wilden Casts.
Dein Code erzeugt genauso UB wie meiner.
-
Leider habe ich diese ganzen Casts/Funktionen nicht zur Verfügung. Ich brauche eine Lösung ohne
reinterpret_cast
und ohne Sachen wiememcpy
. Ich hab nur eine Artstatic_cast
.
-
happystudent schrieb:
Leider habe ich diese ganzen Casts/Funktionen nicht zur Verfügung. Ich brauche eine Lösung ohne
reinterpret_cast
und ohne Sachen wiememcpy
. Ich hab nur eine Artstatic_cast
.Was genau hast du denn zur Verfügung?
Arcoth schrieb:
Dein Code erzeugt genauso UB wie meiner.
In welcher Zeile und warum?
-
TyRoXx schrieb:
Was genau hast du denn zur Verfügung?
Ich habe drei Datentypen: int, float (beide 32 bit) und eine Art string (der aber eigentlich nur zur Text-Ausgabe dient). Für diese 3 Typen habe ich Konvertierungsfunktionen in alle Richtungen (für float -> int zum Beispiel entspricht das ja dann etwa einem static_cast). Die Typen kann ich auch als Array deklarieren.
An Operatoren für diese Datentypen habe ich +-*/, zum Vergleichen ==, !=, <, >, >=, <=. Sonst nix (also auch keine bit-shift operatoren o.ä.).
Darüber hinaus kann ich selbst erstellen: Funktionen (inklusive Rekursion), Schleifen, Verzweigungen, Variablen (von den oben genannten Typen). Und das wars dann im Großen und Ganzen auch schon. Sonst gibts nur noch ein paar Mathematische Grundfunktionen (Sinus, Cosinus, Pow, etc.).
Das sind quasi die Vorgaben. Und mit diesen Mitteln will ich jetzt eine (möglichst effiziente) Version von float_next erstellen.
-
Arcoth schrieb:
Dein Code erzeugt genauso UB wie meiner.
In welcher Zeile und warum?
Ab
++i
. Laut [expr.pre.incr] und [expr.ass]/7 ist dieser Ausdruck zu i = i + 1; (bis auf die doppelte Auswertung voni
) äquivalent. Es wird also eine l-t-r Konvertierung aufi
durchgeführt.Jedoch ist dort kein Objekt vom Typ
uint32_t
mehr existent; [basic.life]/(1.4):The lifetime of an object of type
T
ends when:
(1.3) — ifT
is a class type with a non-trivial destructor (12.4), the destructor call starts, or
(1.4) — the storage which the object occupies is reused or released.Du hast per
memcpy
den Speicher reused, daher wurde die lifetime des ursprünglichen Objektes beendet, und demnach ist die l-t-r Konvertierung von i - welches auf das ursprüngliche Objekt verweist - undefiniert:[basic.life]/6 schrieb:
Similarly, […] after the lifetime of an object has ended and before the storage which the object occupied is reused or released, any glvalue that refers to the original object may be used but only in limited ways. […] The program has undefined behavior if:
(6.1) — an lvalue-to-rvalue conversion (4.1) is applied to such a glvalue,Die Regel in [basic.types]/2 greift hier ebenfalls nicht.
Die aktuellen Regeln bezüglich lifetime sind zwar ziemlich schrott, aber obiges ist eben der Status Quo.
-
Ich muss gerade feststellen, dass der Standard ganz schön schwammig bei so einem wichtigen Thema ist. Ich weiß nur, dass man seit C die Bytes von PODs manipulieren darf. Das Ergebnis ist eben implementierungsabhängig, aber nicht undefiniert.
Was mich gerade stört, ist, dass nach deiner Argumentation selbst das undefiniert wäre:float f = 2; float i; std::memcpy(&i, &f, sizeof(i));
Das ist offensichtlich nicht der Fall.
-
TyRoXx schrieb:
I
Was mich gerade stört, ist, dass nach deiner Argumentation selbst das undefiniert wäre:float f = 2; float i; std::memcpy(&i, &f, sizeof(i));
Das ist offensichtlich nicht der Fall.
Nein. Hier greift [basic.types]/3:
For any trivially copyable type
T
, if two pointers toT
point to distinctT
objectsobj1
andobj2
, where neitherobj1
norobj2
is a base-class subobject, **if the underlying bytes (1.7) making upobj1
are copied intoobj2
,obj2
shall subsequently hold the same value asobj1
**.
-
Arcoth schrieb:
Nein. Hier greift [basic.types]/3:
For any trivially copyable type
T
, if two pointers toT
point to distinctT
objectsobj1
andobj2
, where neitherobj1
norobj2
is a base-class subobject, **if the underlying bytes (1.7) making upobj1
are copied intoobj2
,obj2
shall subsequently hold the same value asobj1
**.Die Regel besagt nur, dass der "value" gleich ist. Das bedeutet, dass kein versteckter Zustand existieren darf, den
memcpy
nicht mitnehmen kann. Ich kann daraus jetzt nicht erkennen, warum das bei ungleichen Typen sofort undefiniertes Verhalten ist.Man kann das Problem auf das hier reduzieren, richtig?
std::uint32_t t = 2; *reinterpret_cast<unsigned char *>(&t) += 1;
Ich dachte immer, dass so etwas erlaubt ist und keineswegs die Lebenszeit von
t
betrifft.
-
@TyRoXx: Das dachte und denke ich immer noch.
-
Wo steht denn, dass
memcpy
die Lebenszeit eines Objektes beendet? Ist das nicht als äquivalent zu einer Kopierschleife über diechar
s definiert?