Datum:
Mahlzeit! Ich habe da mal eine Schnapsidee zu Festkommazahlen; vielleicht interessiert es ja auch noch andere. In letzter Zeit gab es bei mehreren Threads das Stichwort Festkommazahl ([[Skalierung auf Int bei einer FFT (128-Punkte)]], aber auch andere). Das scheint gemeinhin so gehandhabt zu werden, daß man sich hoffentlich erstmal klar wird, wie man uint*_t oder int*_t auf Vor- und Nachkommastellen aufteilt und damit skalierte Werte bekommt. Additionen und Subtraktionen gehen wie gehabt (wenn man nicht versehentlich unterschiedliche Typen mischt), bei Multiplikationen muß man händisch die Skalierung korrigieren. Zwischenergebnisse können gerne über oder unterlaufen, auch wenn das Endergebnis harmlos ist. Der Typ den C sieht, ist erstmal eine normale ganze Zahl. Irgendeine Unterstützung seitens des Compilers (Typkontrolle, Korrektur der Skalierung, Typkonvertierung): komplette Fehlanzeige... Im Endeffekt hat man in seinem Quelltext viel Handarbeit, was viele Fehler provoziert und den Quelltext schnell unlesbar macht, was wiederum mehr Fehler provoziert. Das finde ich ziemlich unbefriedigend. (Ebenso unbefriedigend finde ich, daß man in so einem Forum vielen Leuten immer mühsam beibringen muß, was sie beachten müssen.) Man kann also relativ sauber und elegant programmieren, wenn man mit ganzen Zahlen auskommt. Sobald das nicht mehr geht, hat man die Wahl zwischen Pest und Cholera: Festkommazahlen in Handarbeit mit allen Nachteilen, oder float/double mit dem Problem der Geschwindigkeit, die gegen 0 konvergiert. Was man in C dagegen unternehmen könnte, ist eigentlich nicht viel. Mit Präprozessormakros kommt man nicht sehr weit und handelt sich gleich wieder neue, noch gemeinere Fehler ein. Also bleiben eigentlich nur Funktionen, die man sich mühsam schreibt und genauso mühsam anwendet. Für einen Festkommatyp, der z.B. auf 16 Bit Zahlen (unsigned) mit 5 binären Nachkommastellen arbeitet, müsste man sich Funktionen schreiben, was dann beim Aufruf etwa so aussehen könnte:
// irgendeine Rechnerei mit Gleitkomazahlen: double a = 1.5, b = 5, c; c = (25+3*a)/(a-20+b++); // das Gleiche wie oben, aber jetzt mit Fixkommazahlen: #include <ganzfix_16_5.h> ganzfix_u16_5_t a = ganzfix_u16_5_set_double( 1.5 ), b = ganzfix_u16_5_set_int( 5 ), c; c = ganzfix_u16_5_div( ganzfix_u16_5_add( ganzfix_u16_5_set_int( 25 ), ganzfix_u16_5_mul( ganzfix_u16_5_set_int( 3 ), a ) ), ganzfix_u16_5_add( ganzfix_u16_5_sub( a, ganzfix_u16_5_set_int( 20 ) ), b ) ); b = ganzfix_u16_5_add( b, ganzfix_u16_5_set_int( 1 ) ); |
Als lesbar würde ich so einen Quelltext nicht bezeichnen; das Umbrechen habe ich mir gleich gespart, weil es nichts bringt. Die ganzen Funktionen, die man für allerlei Operationen inkl. Konvertierungen so braucht, müssten für jede Variante von Festkommatyp (signed/unsigned, diverse Gesamtlängen und Nachkommastellen) geschrieben werden. Wenigstens wird es halbwegs laufzeiteffizient, falls man die Funktionen inline bekommt. Falls nicht, gute Nacht! Irgendwie ist das auch kein Fortschritt, sondern ziemlich unwürdig. Dann gibt es aber jetzt schon seit einiger Zeit C++. Da hat man parametrierbare Typen (template<...> class...) und überladene Operatoren. Auch wenn ich jetzt das böse Wort "C++" benutzt habe und einige gleich aufschreien, daß das auf einem Atmel doch gar nicht vernünftig geht, habe ich es mal ausprobiert und finde es gar nicht so schlecht. Weiter unten (nicht gleich jetzt, um niemanden unnötig zu verschrecken) kommt eine Headerdatei fixpoint.h. Um jetzt mal zu sehen, wie es mit Codegröße und Rechenzeit aussieht, habe ich mir ein Testprogramm AVR_LCD44780_fixpoint.cpp gebastelt (das war vorher ein Programm, um die LCD-Ausgabe zu probieren). Hier nur der interessante Teil, was den Test angeht:
#include "lcd-routines.h" #include "fixpoint.h" // Eine der folgenden Zeilen aktivieren, den Rest auskommentieren: typedef double test_t; typedef double const_t; const char*t_text="double"; //typedef uint8_t test_t; typedef uint8_t const_t; const char*t_text="uint8_t"; //typedef uint16_t test_t; typedef uint16_t const_t; const char*t_text="uint16_t"; //typedef uint32_t test_t; typedef uint32_t const_t; const char*t_text="uint32_t"; //typedef uint64_t test_t; typedef uint64_t const_t; const char*t_text="uint64_t"; //typedef Anyware::fixpoint< uint8_t, uint8_t, 1 > test_t; typedef uint8_t const_t; const char*t_text="f(8,8)"; //typedef Anyware::fixpoint< uint8_t, uint16_t, 1 > test_t; typedef uint8_t const_t; const char*t_text="f(8,16)"; //typedef Anyware::fixpoint< uint16_t, uint16_t, 1 > test_t; typedef uint16_t const_t; const char*t_text="f(16,16)"; //typedef Anyware::fixpoint< uint16_t, uint32_t, 1 > test_t; typedef uint16_t const_t; const char*t_text="f(16,32)"; //typedef Anyware::fixpoint< uint32_t, uint32_t, 1 > test_t; typedef uint32_t const_t; const char*t_text="f(32,32)"; //typedef Anyware::fixpoint< uint32_t, uint64_t, 1 > test_t; typedef uint32_t const_t; const char*t_text="f(32,64)"; //typedef Anyware::fixpoint< uint64_t, uint64_t, 1 > test_t; typedef uint64_t const_t; const char*t_text="f(64,64)"; volatile uint8_t bMessungLaeuft = 0; const int laufzeit_sec = 10; #ifdef __cplusplus const char *lang_text = "C++"; #else const char *lang_text = "C"; #endif /* ifdef __cplusplus */ int main( int nargs, char **args ) { char tmp_puffer[30]; uint32_t nGeschafft = 0; // Werte, mit denen etwas gerechnet werden soll: test_t a = (const_t)3, b = (const_t)1, c = (const_t)1; // LCD initialisieren, Timer starten // ... bMessungLaeuft = 1; while( bMessungLaeuft ) { size_t i; const size_t nLoop = 10; a = (const_t)3; b = (const_t)1; c = (const_t)1; for( i=0; i<nLoop; ++i ) { if( (i%4)<2 ) { b *= (const_t)2; a += b; c += a*b; } else { c -= a*b; a -= b; b /= (const_t)2; } } ++nGeschafft; // Durchläufe zählen } lcd_clear(); lcd_set_cursor( 0, 1 ); sprintf( tmp_puffer, "%.0f %s %s", (double)c, t_text, lang_text ); lcd_string( tmp_puffer ); lcd_set_cursor( 0, 2 ); sprintf( tmp_puffer, "%.1f / sec ", nGeschafft/(double)laufzeit_sec ); lcd_string( tmp_puffer ); while( "warten aufs jüngste Gericht" ) { } ... |
Daneben gibt es noch eine Interruptroutine, die nach (laufzeit_sec) Sekunden den Wert von (bMessungLaeuft) zu 0 setzt und damit die Meßschleife beendet. Nach der Meßschleife wird die Anzahl der Schleifendurchläufe pro Sekunde ausgegeben. Durch Auskommentieren je einer der typedef kann man die verschiedenen Typen leicht ausprobieren. Die Typen double und uint... sind die gewohnten aus C, dagegen sind die Typen Anyware::fixpoint< uint8_t, uint8_t, 1 > und folgende in fixpoint.h als template definiert. Mit den Parametern (hier: < uint8_t, uint8_t, 1 >) kann man den Typ zurechtschneidern. Dabei ist der erste Parameter der Grunddatentyp, der für die Rechnung und für das Speichern von Werten verwendet wird. Er definiert also, wieviele Stellen vor und nach dem Komma insgesamt zur Verfügung stehen. Es kann ein uint...- oder ein int...-Typ sein. Der zweite Parameter gibt an, welcher Datentyp an einigen Stellen intern für Zwischenwerte verwendet werden soll, wenn der Grunddatentyp möglicherweise zu kurz ist. Bei uint16_t als Grunddatentyp würde also uint32_t als zweiter Parameter an diesen Stellen einen Überlauf verhindern. Nutzt man den Wertebereich nicht ganz aus, kann man aber auch den zweiten Parameter gleich dem ersten setzen und spart Rechenzeit. Der dritte Parameter steht für die Anzahl Nachkommastellen. Bei Anyware::fixpoint< uint8_t, uint8_t, 1 > hätte man 7 Vor- und 1 Nachkommastelle, man hätte damit die möglichen Werte 0, 0.5, 1.0, ..., 127.0, 127.5. Es ist auch möglich, hier einen negativen Wert anzugeben. Dann hat man einen größeren Zahlenbereich mit einer gröberen Abstufung als 1. Anyware::fixpoint< uint8_t, uint8_t, -2 > könnte die Werte 0, 4, 8, ..., 1016, 1020 annehmen. Je nachdem, welchen Datentyp im obigen Testprogramm und je nachdem, ob man das Programm mit C oder C++ kompiliert, kommen folgende Laufzeiten und Codegrößen raus (Mega8 mit 16 MHz):
| n/sec | .text |
| C | C++ | C | C++ |
--------------------------------+-------+-------+------+------+
double | 3468 | 3468 | 4876 | 4876 |
--------------------------------+-------+-------+------+------+
uint8_t | 73487 | 73487 | 4312 | 4312 |
uint16_t | 51721 | 51721 | 4348 | 4348 |
uint32_t | 19614 | 19614 | 4500 | 4500 |
uint64_t | 1038 | 1038 | 6524 | 6524 |
--------------------------------+-------+-------+------+------+
fixpoint<uint8_t,uint8_t,1> | | 13161 | | 4584 |
fixpoint<uint8_t,uint16_t,1> | | 31907 | | 4552 |
fixpoint<uint16_t,uint16_t,1> | | 30300 | | 4560 |
fixpoint<uint16_t,uint32_t,1> | | 12859 | | 4726 |
fixpoint<uint32_t,uint32_t,1> | | 12629 | | 4760 |
fixpoint<uint32_t,uint64_t,1> | | 626 | | 6528 |
fixpoint<uint64_t,uint64_t,1> | | 597 | | 7206 |
--------------------------------+-------+-------+------+------+
|
Daran sieht man jedenfalls schon mal, daß es -unter sonst gleichen Umständen- vollkommen egal ist, ob man das Testprogramm als C oder C++ kompiliert (soweit es den jeweiligen Typ in C überhaupt gibt natürlich). Also lasse ich C mal forsch weg. Das Argument, daß C++ zuviel Overhead für MCs hat, gilt nicht für alles in C++. Bei aufwendigen Klassen, womöglich mit virtuellen Methoden und Resourcenallokierung, Strings, Streams etc. gilt das sicher. Aber bei Ausdrücken, die in C auch gültig wären, hat man sowieso keine Nachteile. Interessant wäre jetzt also, wie sich (unabhängig von C/C++) template-Funktionen gegenüber handgeschriebenen Funktionen verhalten. Beispiel: Vergleich Anzahl pro Sekunde uint16_t gegenüber fixpoint<uint16_t,uint16_t,1>. Bei uint16_t kommt man auf 51721 pro Sekunde, bei fixpoint auf 30300. Dabei muß man aber auch beachten, daß die uint16_t-Rechnung deutlich einfacher ist, weil es eben keinerlei Skalierung gibt gegenüber der Fixpunktzahl. Würde man mit uint16_t manuell eine Fixpunktarithmetik bauen, müsste man auch etwas Rechenzeit opfern. Ich gehe davon aus, daß damit eine handgeschriebene Version zumindest keinen großen Laufzeitvorteil hätte. Auch die Codegröße (4348 bei uint16_t gegenüber 4560 bei fixpoint) lässt nicht erwarten, daß man mit handgeschriebener Fixpunktarithmetik wesentlich besser liegen würde. Insgesamt sieht mir das gut genug aus, daß ich in Zukunft keine Festkommazahlen mehr von Hand anfasse, sondern lieber C++ nehme. Und hier die versprochene fixpoint.h:
//////////////////////////////////////////////////////////////////////////////// // // Time-stamp: "09.07.09 18:20 fixpoint.h klaus?wachtler.de" // //////////////////////////////////////////////////////////////////////////////// // // // C++ templates defining numerical fixed point types // -------------------------------------------------- // // // The functions are intended to be light weight and useful on small // systems like micro controllers. // // Speed and code size might be a little worse than integral // calculations but much better than floating point arithmetic // especially on systems without FPU. // // Tested with g++ 4.3.2 and avr-gcc 4.3.2. // // ATTENTION! // The code is tested only partially (as from 09.07.2009). // Not usable for production code. // //////////////////////////////////////////////////////////////////////////////// // // (C) 2009 Klaus Wachtler // Breidingstr. 17 // D-29614 Soltau // Phone: +49-171-4553039 // Mail: fixpoint<you guess the character?>wachtler.de // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License as // published by the Free Software Foundation; either version 3 of the // License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this program; if not, see <http://www.gnu.org/licenses/>. // //////////////////////////////////////////////////////////////////////////////// // // Template arguments: ////////////////////// // // - TBASE is some usual signed or unsigned integral type like // signed/unsigned int, int32_t, uint32_t etc.. // TBASE is used to keep an internal value which has to be scaled to // get the correct number. // // - TTEMP is another integral type used for values subject to // overflow if TBASE would be used. // You might want to use the same type for TBASE and TTEMP (like // fixpoint< int16_t, int16_t >) as long as you ensure to keep // intermediate results like in a*b within valid range. // If in doubt choose TTEMP one step larger than TBASE, so // fixpoint< uint8_t, uint16_t > or fixpoint< int32_t, int64_t > // seem to be a good choice. // Default ist TBASE. // // - LFRACTIONAL scales this value and determines range and // accuracy. It counts in binary digits. // A positive value of LFRACTIONAL gives a type with reduced range // and accuracy better than 1 by using LFRACTIONAL binary digits as // fractional part (LFRACTIONAL digits are used for the fractional // part, the rest of TBASE is used for the integer part), // while negative values of LFRACTIONAL give an extended range with // less accuracy (compared to TBASE). // * Example 1: // fixpoint< uint16_t, 3 > is based on uint16_t scaled // by 2**3=8. // While uint16_t has a range from 0 to 65535 with steps of 1 // fixpoint< uint16_t, 3 > has values from 0 to 8191.875 (65535/8) // with steps of 1/8=0.125. The fractional part is 3 binary // digits. // Possible values are 0, 0.125, 0.25, 0.375, 0.5 ... 8191.875. // * Example 2: // fixpoint< uint8_t, -2 > is based on uint8_t scaled // by 2**(-2)=1/4. // The values range from 0 (0*4) to 1020 (255*4) in steps of 4. // Possible values are 0, 4, 8, 12, ... 1020. // * Example 3: // fixpoint< uint8_t, 0 > is based on uint8_t without scaling. // This resembles uint8_t with values from 0 to 255. // * Example 4: // fixpoint< int8_t, -2 > is based on int8_t scaled // by 2**(-2)=1/4. // The values range from -512 (-128*4) to +508 (127*4) in steps of 4. // Possible values are -512, -508, -502, ... -4, 0, +4, ... +508. // // - ROUNDTONEAREST determines if assignments and initializations // cut off trailing digits (false) or rounds up to the nearest // integral value (true). // Default is true. // //////////////////////////////////////////////////////////////////////////////// // // Usage: ///////// // // Compilation: // // - Plain C is not supported. Use C++. // - Use #include <fixpoint.h> and give -I... if necessary. // - No libs needed (everything is inlined). // - Compile with -DNO_STDSTRING or #define NO_STDSTRING before // #include <fixpoint.h> if no std::string is available. // - Compile with -DNO_STDIOSTREAM or #define NO_STDIOSTREAM before // #include <fixpoint.h> if no iostreams are available. // - Don't worry about warnings saying "shift count is negative". // This occurs in dead code which will be optimized away by the // compiler later. // // // Object creation: // // fixpoint objects can be created either: // - without arguments (resulting in a 0 value) // - an integral value (with their base type); values being not // integral can not be defined this way even if LFRACTIONAL is // positive // - two integral values a and b (resulting in a/b, which will be cut // off or rounded to a valid value depending on template argument // ROUNDTONEAREST); this is done by a template method with any // integral types for a and b and usual C style promotions // performing the division. // If LFRACTIONAL is positive the type TTEMP should be wide enough to // hold a<<LFRACTIONAL. If LFRACTIONAL is negative TTEMP should be // able to keep b<<LFRACTIONAL. // - a floating point number (which will be cut off or rounded // to a valid value depending on template argument ROUNDTONEAREST) // // // Valid operations: // // | type of a | type of b | result | lvalue | notes // -----------+-----------+-----------+----------+--------+------------------------------ // f() | | | fixpoint | | constructor // -----------+-----------+-----------+----------+--------+------------------------------ // f(a) | base type | | fixpoint | | constructor (1) // -----------+-----------+-----------+----------+--------+------------------------------ // f(a) | double | | fixpoint | | constructor // -----------+-----------+-----------+----------+--------+------------------------------ // f(a,b) | integral | integral | fixpoint | | constructor (1) // -----------+-----------+-----------+----------+--------+------------------------------ // !a | fixpoint | | bool | | true if a==0 // -----------+-----------+-----------+----------+--------+------------------------------ // ++a | fixpoint | | fixpoint | yes | nop if LFRACTIONAL<0 // -----------+-----------+-----------+----------+--------+------------------------------ // a++ | fixpoint | | fixpoint | | nop if LFRACTIONAL<0 // -----------+-----------+-----------+----------+--------+------------------------------ // --a | fixpoint | | fixpoint | yes | nop if LFRACTIONAL<0 // -----------+-----------+-----------+----------+--------+------------------------------ // a-- | fixpoint | | fixpoint | | nop if LFRACTIONAL<0 // -----------+-----------+-----------+----------+--------+------------------------------ // +a | fixpoint | | fixpoint | | nop // -----------+-----------+-----------+----------+--------+------------------------------ // -a | fixpoint | | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a*b | fixpoint | fixpoint | fixpoint | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // a/b | fixpoint | fixpoint | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a%b | fixpoint | fixpoint | fixpoint | | x-n*y with n=x/y rounded -> 0 // -----------+-----------+-----------+----------+--------+------------------------------ // a+b | fixpoint | fixpoint | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a-b | fixpoint | fixpoint | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a<b | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // a>b | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // a<=b | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // a>=b | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // == | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // != | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // a&&b | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // a||b | fixpoint | fixpoint | bool | | // -----------+-----------+-----------+----------+--------+------------------------------ // a=b | fixpoint | any (2) | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a+=b | fixpoint | any (2) | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a-=b | fixpoint | any (2) | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a*=b | fixpoint | any (2) | fixpoint | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // a/=b | fixpoint | any (2) | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // a%=b | fixpoint | any (2) | fixpoint | | // -----------+-----------+-----------+----------+--------+------------------------------ // (double) | fixpoint | | double | | // -----------+-----------+-----------+----------+--------+------------------------------ // (int8_t) | fixpoint | | int8_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // (int16_t) | fixpoint | | int16_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // (int32_t) | fixpoint | | int32_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // (int64_t) | fixpoint | | int64_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // (uint8_t) | fixpoint | | uint8_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // (uint16_t) | fixpoint | | uint16_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // (uint32_t) | fixpoint | | uint32_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // (uint64_t) | fixpoint | | uint64_t | | (1) // -----------+-----------+-----------+----------+--------+------------------------------ // // (1) In operations like a*b an intermediate result might overflow // if TTEMP is as narrow as TBASE. // Please take care of the values and ranges. If in doubt choose // TTEMP wider than TBASE. // // (2) "any" means any type which can be converted to fixpoint, // i.e. the same fixpoint type, any integral type, float and double. // // // There is no implicit conversion between different fixpoint types. // Please convert manually. Example: // Anyware::fixpoint< int16_t, int32_t, 2 > a( 4 ); // Anyware::fixpoint< int32_t, int32_t, 8 > b( a.getBaseValue(), // 1<<a.getScaleBinaryExponent() // ); // // //////////////////////////////////////////////////////////////////////////////// // // History: /////////// // // 08.07.2009 kw - created // - tested on Linux + g++ 4.3.2 and avr-g++ 4.3.2 // // 09.07.2009 kw - template argument TTEMP // - types for intermediate values changed // - more comments // - test programs // // kw // // kw // // kw // // kw // //////////////////////////////////////////////////////////////////////////////// // // TODO: //////// // // - testing all cases (with rounding and without) // - external documentation // - take care for ROUNDTONEAREST in operator ...int... // - // - // - // - // - // //////////////////////////////////////////////////////////////////////////////// // // There are 2 demo programs: // // - testfixpoint_linux.cpp shows basic usage and makes some tests, // written for a PC system running Linux. It might or might not work on // other systems; there is no GUI needed. // // - AVR_LCD44780_fixpoint.cpp, lcd-routines.c and lcd-routines.h are // used to build a test program running on an Atmel AVR (AtMega8 // tested). // // It calculates some things in a loop until 10 seconds are elapsed // and writes the loop count to an LCD (Hitachi HDC44780). // For more information on connecting the AVR and the LCD see // AVR_LCD44780_fixpoint.cpp. // Changes on pin usage may be done in lcd-routines.h. // // Inside AVR_LCD44780_fixpoint.cpp there is a typedef where you can // set the type used for all calculations. // As long as you use C types here (int16_t, uint32_t, float etc.; // no fixpoint) the source file may be renamed to // AVR_LCD44780_fixpoint.c and compiled as traditional C for // comparison. // // There are two makefiles supplied: Makefile_AVR_c and Makefile_AVR_cpp // can be used to compile and flash the program on my system (atmega8, // 16 MHz, siprog using /dev/ttyS0) the C resp. C++ version or // modified as needed. // The Makefiles are derived from the sample files at [2]. // Caution! The original Makefile from [2] will overwrite the // C++ source (*.cpp) with the listing, because the replacement in the line: // CPPFLAGS += -Wa,-adhlns=$(<:.c=.lst) // fails (since the extension is not .c). // This leads to a listing file name identical to the source file // name. // I changed the listing file name to the full source name and .lst // appended, e.g. AVR_LCD44780_fixpoint.cpp.lst to avoid the mess. // //////////////////////////////////////////////////////////////////////////////// // // [1] Wikipedia Fixed-point arithmetic // http://en.wikipedia.org/wiki/Fixed-point_arithmetic // // // [2] http://www.mikrocontroller.net/ // //////////////////////////////////////////////////////////////////////////////// #define inline #ifndef _FIXPOINT_H_ #define _FIXPOINT_H_ // only valid in C++, not C #ifdef __cplusplus #include <stdint.h> #include <inttypes.h> #include <math.h> // A prior definition of NO_STDSTRING suppresses the conversion to // std::string and eliminates the need #include <string> // // A prior definition of NO_STDIOSTREAM suppresses output to // std::ostream and input from std::istream. #ifndef NO_STDSTRING #include <string> #endif /* ifndef NO_STDSTRING */ #ifndef NO_STDIOSTREAM #include <iostream> #endif /* ifndef NO_STDIOSTREAM */ namespace Anyware { template< typename TBASE = int16_t, typename TTEMP = TBASE, const int LFRACTIONAL = sizeof(TBASE)/2, const bool ROUNDTONEAREST = true > class fixpoint { public: // this type typedef fixpoint< TBASE, TTEMP, LFRACTIONAL, ROUNDTONEAREST > type; // // constructing // // ctor with no arguments: 0 fixpoint() : basevalue( 0 ) {} // ctor with integral value fixpoint( TBASE init ) : basevalue( LFRACTIONAL>0 ? ( init << LFRACTIONAL ) : ( ROUNDTONEAREST ? ( (((TTEMP)init)+(1<<(-LFRACTIONAL-1))) >> -LFRACTIONAL ) : ( init >> -LFRACTIONAL ) ) ) { } // ctor with floating point value fixpoint( const double &init ) : basevalue( ldexp( init, LFRACTIONAL ) + ( ROUNDTONEAREST ? ( init<0.0 ? -0.5 : +0.5 ) : 0.0 ) ) { } // ctor with a and b: initial value is a/b template< typename TA, typename TB > fixpoint( TA a, TB b ) : basevalue( ( ( b<0 ? (void)( (a=-a), (b=-b) ) : (void)0 ), ( LFRACTIONAL>0 ? ( ROUNDTONEAREST ? ( a>=0 ? (((((TTEMP)a)<<LFRACTIONAL)+(b/2))/b) : (((((TTEMP)a)<<LFRACTIONAL)-(b/2))/b) ) : (((TTEMP)a)<<LFRACTIONAL)/b ) : ( ROUNDTONEAREST ? ( a>0 ? ((a+(((TTEMP)b)<<(-LFRACTIONAL-1))) /(((TTEMP)b)<<-LFRACTIONAL)) : ((a-b/2)/(((TTEMP)b)<<-LFRACTIONAL)) ) : (a/(((TTEMP)b)<<-LFRACTIONAL)) ) ) ) ) { } // // conversions // operator double() const { return ldexp( double( basevalue ), -LFRACTIONAL ); } // TODO: take care for ROUNDTONEAREST #define _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(integraltype) \ operator integraltype() const \ { \ if( LFRACTIONAL>0 ) \ { \ return basevalue >> LFRACTIONAL; \ } \ else if( LFRACTIONAL<0 ) \ { \ return ((integraltype)basevalue) << -LFRACTIONAL; \ } \ else \ { \ return basevalue; \ } \ } _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(int8_t); _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(int16_t); _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(int32_t); _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(int64_t); _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(uint8_t); _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(uint16_t); _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(uint32_t); _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL(uint64_t); #undef _FIXPOINT_DEFINE_CONVERSION_TO_INTEGRAL // // operations // // !a bool operator!() const { return basevalue==0; } // prefix++: ++a returns modified value type &operator++() { if( LFRACTIONAL>=0 ) { basevalue += 1<<LFRACTIONAL; } return *this; } // postfix++: a++ returns unmodified value type operator++( int ) { type oldvalue( *this ); ++*this; return oldvalue; } // prefix--: --a returns modified value type &operator--() { if( LFRACTIONAL>=0 ) { basevalue += 1<<LFRACTIONAL; } return *this; } // postfix--: a-- returns unmodified value type operator--( int ) { type oldvalue( *this ); --*this; return oldvalue; } // +a does nothing type operator+() { return *this; } // -a negates type operator-() { type ret; ret.basevalue = -basevalue; return ret; } type operator*( const type &rS ) const { TTEMP tempvalue = TTEMP(basevalue) * rS.basevalue; if( LFRACTIONAL>0 ) { if( ROUNDTONEAREST ) { // get a bit away from 0 to have the result rounded instead // of truncating if( tempvalue>0 ) { tempvalue += 1<<(LFRACTIONAL-1); } else if( tempvalue<0 ) { tempvalue -= 1<<(LFRACTIONAL-1); } } tempvalue >>= LFRACTIONAL; } else if( LFRACTIONAL<0 ) { tempvalue <<= -LFRACTIONAL; } type ret; ret.basevalue = tempvalue; return ret; } type operator/( const type &rS ) const { if( LFRACTIONAL>0 ) { return type( TTEMP(basevalue)<<LFRACTIONAL, TTEMP(rS.basevalue)<<LFRACTIONAL ); } else { return type( basevalue, rS.basevalue ); } } type operator%( const type &rS ) const { type ret; ret.basevalue = basevalue % rS.basevalue; return ret; } // a+b type operator+( const type &rS ) const { type ret; ret.basevalue = basevalue + rS.basevalue; return ret; } // a-b type operator-( const type &rS ) const { type ret; ret.basevalue = basevalue - rS.basevalue; return ret; } // a<b bool operator<( const type &rS ) const { return basevalue<rS.basevalue; } // a>b bool operator>( const type &rS ) const { return basevalue>rS.basevalue; } // a<=b bool operator<=( const type &rS ) const { return basevalue<=rS.basevalue; } // a>=b bool operator>=( const type &rS ) const { return basevalue>=rS.basevalue; } // a==b bool operator==( const type &rS ) const { return basevalue==rS.basevalue; } // a!=b bool operator!=( const type &rS ) const { return basevalue!=rS.basevalue; } // a&&b bool operator&&( const type &rS ) const { return basevalue&&rS.basevalue; } // a||b bool operator||( const type &rS ) const { return basevalue||rS.basevalue; } // a=b template< typename T > const type &operator=( const T &rS ) { basevalue = type( rS ).basevalue; return *this; } // a+=b template< typename T > const type &operator+=( const T &rS ) { basevalue = ( *this + type( rS ) ).basevalue; return *this; } // a-=b template< typename T > const type &operator-=( const T &rS ) { basevalue = ( *this - type( rS ) ).basevalue; return *this; } // a*=b template< typename T > const type &operator*=( const T &rS ) { basevalue = ( *this * type( rS ) ).basevalue; return *this; } // a/=b template< typename T > const type &operator/=( const T &rS ) { basevalue = ( *this / type( rS ) ).basevalue; return *this; } // a%=b template< typename T > const type &operator%=( const T &rS ) { basevalue = ( *this % type( rS ) ).basevalue; return *this; } // returns the raw internal value // // The represented value might be calculated with // rawvalue/(2^scalebinaryexponent) TBASE getBaseValue() const { return basevalue; } // returns the binary exponent of the scale factor (length of // fractional part) // // The represented value might be calculated with // rawvalue/(2^scalebinaryexponent) int getScaleBinaryExponent() const { return LFRACTIONAL; } // returns the scale factor // // The represented value might be calculated with // rawvalue/(scale) double getScale() const { if( LFRACTIONAL>0 ) { return double(1<<LFRACTIONAL); } else if( LFRACTIONAL<0 ) { return 1.0/double(1<<-LFRACTIONAL); } else { return 1.0; } } #ifndef NO_STDIOSTREAM // Value will be converted to double for writing into stream. // Thus all floating point formatting from include <iomanip> like // std::setprecision(4) will work. void printToOstream( std::ostream &os ) const { #ifdef TESTFIXPOINT // test version: write internal value, scaling and resulting // value: os << "fixpoint( internal=" << basevalue << ", scaling=" << LFRACTIONAL << ", rounding=" << ROUNDTONEAREST << ", resulting=" << double( *this ) << " )"; #else // final version: write resulting value: os << double( *this ); #endif /* ifdef TESTFIXPOINT */ } void readFromIstream( std::istream &is ) { double dValue; is >> dValue; *this = dValue; } #endif /* ifndef NO_STDIOSTREAM */ private: TBASE basevalue; }; // template class fixpoint #ifndef NO_STDIOSTREAM template< typename TBASE, typename TTEMP, const int LFRACTIONAL, const bool ROUNDTONEAREST > inline std::ostream &operator<< ( std::ostream &os, const Anyware::fixpoint< TBASE, TTEMP, LFRACTIONAL, ROUNDTONEAREST > &f ) { f.printToOstream( os ); return os; } template< typename TBASE, typename TTEMP, const int LFRACTIONAL, const bool ROUNDTONEAREST > inline std::istream &operator>> ( std::istream &is, const Anyware::fixpoint< TBASE, TTEMP, LFRACTIONAL, ROUNDTONEAREST > &f ) { f.readFromIstream( is ); return is; } #endif /* ifndef NO_STDIOSTREAM */ } // namespace Anyware #endif /* ifdef __cplusplus */ #endif /* ifndef _FIXPOINT_H_ */ |
Dieser Stand ist sicher nicht produktionsreif, weil er großteils nur hingeschrieben und weitgehend ungetestet ist. Ich werde das sicher für mich noch hinfeilen. Falls noch jemand Interesse daran hat, bin ich aber natürlich für konstruktive Vorschläge offen...
Datum:
Die Zeile
#define inline |
in fixpoint.h gehört natürlich noch weg, sorry (noch nicht fertig wie gesagt...). Verrätst du mir noch, was TL;DR ist?
Datum:
Too Long; Don't Read :-) (für eine Mini-Zusammenfassung, die man darüber oder darunter schreibt)
Datum:
Angehängte Dateien:ok, eingesehen. Aber die meisten hier haben doch eh zuviel Zeit, dann können sie es auch ganz lesen ;-) Und die Überschrift sagt doch schon alles, oder? Nebenbei noch in aller Kürze die Ausgabe von einem Lauf...
Datum:
Nicht schlecht! Wow. Gute Arbeit
Das wäre doch mal was für eine zukünftig avr-libcpp.
Kritik:
Das Template ist so gestaltet, dass man einen zweiten Datentyp hat, der
bei Overflows benutzt wird.
Frage: Braucht man das überhaupt?
Meiner Meinung nach kann, wenn immer nur uint8_t * uint8_t im Spiel sind
maximal ein uint16_t herauskommen.
Sprich: Man kann doch automatisch veranlassen, dass auf den nächst
höheren Datentyp gecastet wird, wenn ein Überlauf passieren könnte. Oder
man castet bei Multiplikationen einfach immer auf den nächsthöheren Typ.
Das müsste innerhalb des Templates mit ein paar
if (sizeof(T) == 1)
{
//berechnung mit uint16_t ausführen
}
gehen. Oder irre ich mich jetzt? Zugegebenermaßen habe ich mir jetzt
nicht über jeden Fall, der auftreten kann Gedanken gemacht, aber
eigentlich sollte das doch so gehen.
Datum:
Klaus Wachtler schrieb: > Ich habe da mal eine Schnapsidee zu Festkommazahlen; vielleicht > interessiert es ja auch noch andere. > > In letzter Zeit gab es bei mehreren Threads das Stichwort > Festkommazahl ([[Skalierung auf Int bei einer FFT (128-Punkte)]], aber > auch andere). > Das scheint gemeinhin so gehandhabt zu werden, daß man sich > hoffentlich erstmal klar wird, wie man uint*_t oder int*_t auf Vor- > und Nachkommastellen aufteilt und damit skalierte Werte bekommt. > Additionen und Subtraktionen gehen wie gehabt (wenn man nicht > versehentlich unterschiedliche Typen mischt), bei Multiplikationen muß > man händisch die Skalierung korrigieren. Zwischenergebnisse können > gerne über oder unterlaufen, auch wenn das Endergebnis harmlos ist. > > Der Typ den C sieht, ist erstmal eine normale ganze Zahl. > Irgendeine Unterstützung seitens des Compilers (Typkontrolle, > Korrektur der Skalierung, Typkonvertierung): komplette Fehlanzeige... Nein, nicht komplett. GCC bietet auf GNU-C Ebene Unterstützung für Fixpunkt-Arithmetik verschiedener Genauigkeiten, zB als short _Fract, long _Fract, etc. Das beinhaltet Arithmetik, Typ-Umwandlungen und Unterstützung im Debug-Format dwarf-2. Auch saturierte Typen werden unterstützt: http://gcc.gnu.org/onlinedocs/gcc-4.3.3/gcc/Fixed_... Das einzige, klitzekleine Detail das noch fehlt, ist daß sich jemand hinsetzte und die Unterstützung in die Derivate einbaut, wo sowas sinnvoll ist. Dazu gehören Architekturen ohne FPU wie AVR, MSP, manche ARM-Derivate, usw. und auch Architekturen, die Fixpunkt-Arithmetik per Hardware unterstützen. Dazu gehörten zB AVRs der ATmega-Familie. Einfache Befehle würde man direkt in der Maschinenbeschreibung untertützen und inline expandieren, komplexere Sachen wie gewohnt in die libgcc auslagern und bei Bedarf einen (transparenten) Funktionsaufruf machen. Sooo viel Arbeit ist das garnicht mal, aber es müsste eben jemand machen... Vorteil -- Die Quelle wird besser leserlich, da man +, -, *, / ... verwenden kann -- Transparente Funktionsaufrufe sind effizienter als explizite -- Der Compiler kann Optimierungen ausführen -- C-Code ist portabel zwischen Compilern, die GNU-C implementieren und _Fract unterstützen. -- Spart Arbeit das Fixed-Arithmetik-Rädchen zum 10000 Mal neu zu erfinden und zu implementieren schnitzen Nachteil -- Kein Standard-C -- Kein Schwanz wird sich dazu bereit erklären diese Arbeit zu machen, zB für avr-gcc ;o) Johann
Datum:
@Simon: Gestern hatte ich auch nur einen Typ, hat mir aber dann doch nicht gefallen. Sicher kann man es im Voraus nicht sagen, was man für Zwischenergebisse braucht. Für den zweiten Datentyp kommen ernsthaft nur zwei Typen in Fragen: entweder der erste oder der nächst große (doppelte Länge). Bei (u)int64_t gibt es gar keinen nächstgrößeren. Aber wozu multipliziert man uint64_t mit uint_64_t? Das werden sicher nicht beides Zahlen sein, die am oberen des Wertebereiches kratzen. Solche Zahlen braucht man z.B. für Dateipositionen im Terabyte-Bereich, die wird man aber nicht miteinander multiplizieren, sondern eine große Zahl mit der Größe einer struct beispielsweise. Auch bei 32*32 Bit ist nicht immer gesagt, daß man auf 64 Bit ausweichen muß; das hängt jeweils vom Einzelfall ab. Deshalb wollte ich es dem Anwender überlassen, ob er es für nötig hält - schließlich kostet die größere Länge auch gleich Rechenzeit. Der temporäre Wert kann größer sein als das letztliche Ergebnis, z.B. bei Mulitplikation:
type operator*( const type &rS ) const
{
TTEMP tempvalue = TTEMP(basevalue) * rS.basevalue;
if( LFRACTIONAL>0 )
{
if( ROUNDTONEAREST )
{
// get a bit away from 0 to have the result rounded instead
// of truncating
if( tempvalue>0 )
{
tempvalue += 1<<(LFRACTIONAL-1);
}
else if( tempvalue<0 )
{
tempvalue -= 1<<(LFRACTIONAL-1);
}
}
tempvalue >>= LFRACTIONAL;
}
else if( LFRACTIONAL<0 )
{
tempvalue <<= -LFRACTIONAL;
}
type ret;
ret.basevalue = tempvalue;
return ret;
}
|
Es werden erst die internen Werte multipliziert, dann wird die zu hohe Skalierung ggf. durch Rechtsschieben korrigiert. Bis dahin kann es eng werden. Würde ich erst einen Operanden nach rechts schieben und dann multiplizieren, würde das Problem nicht auftreten. Dafür geht Genauigkeit verloren. Möglich wäre es auch, die Werte anzuschauen und jeweils so weit schieben, wie möglich, ohne Einsen zu verlieren, dann multiplizieren und falls es vorher nicht reichte die restlichen Stellen danach zu schieben. Das wiederum ist aufwendiger, also auch nicht der Bringer. Insofern denke ich, macht es Sinn, dem Anwender den schwarzen Peter zu geben; nur der kennt seine Zahlen und muß halt im Zweifelsfall Rechenzeit opfern.
Datum:
Die _Fract Typen haben das Komma aber immer an der gleichen Stelle, oder? Damit ist die Template-Bibliothek dann wesentlich flexibler.
Datum:
Hab grad nochmal über die fixpoint Klasse gelesen: - in type &operator--() ist noch ein copy&paste-Fehler - warum wird beim operator/ der shift verwendet, beim operator% aber nicht?
Datum:
> -- Kein Schwanz wird sich dazu bereit erklären diese Arbeit > zu machen, zB für avr-gcc ;o) Möglicherweise doch: http://archives.free.net.ph/message/20090110.12213...
Datum:
Klaus Wachtler schrieb: > Bei (u)int64_t gibt es gar keinen nächstgrößeren. > Aber wozu multipliziert man uint64_t mit uint_64_t? (u)int64_t sollte man auf dem AVR unbedingt vermeiden! Es ist zwar implementiert, aber von hinten durch die Brust ins Auge. D.h. es erzeugt deutlich größeren Code und ist auch deutlich langsamer als float. Soweit möglich, also besser float nehmen, statt (u)int64_t. double ist auf dem AVR garnicht implementiert. Laut C-Standard ist es erlaubt, daß double stillschweigend als float compiliert wird. Man merkt es also nur, wenn man sizeof(double) ausgibt oder daß ein paar Stellen Genauigkeit fehlen. Die optimierte float-lib "-lm" ist außerdem auf dem AVR garnicht so schlecht. Wenn man nicht gerade mit jedem % CPU-Leistung geizen muß oder noch was unbedingt in nen ATtiny13 reinpassen soll, kann man ruhig float nehmen. Insbesondere, wenn es um Berechnungen für die Werteausgabe an den langsamen Menschen geht. Wenn im Mapfile 264 Byte zusätzlich belegter SRAM auftauchen, hat man die falsche Lib genommen. Peter
Datum:
ManuelStahl schrieb: > Hab grad nochmal über die fixpoint Klasse gelesen: Danke! > > - in type &operator--() ist noch ein copy&paste-Fehler war falsch, habe ich jetzt hier korrigiert. > - warum wird beim operator/ der shift verwendet, beim operator% aber > nicht? Ich sehe jetzt nicht den Fehler und habe mal ein Beispiel probiert:
Anyware::fixpoint< int32_t, int32_t, 2, true > a( 25, 4 ), b( 10, 4 ); Anyware::fixpoint< int32_t, int32_t, 2, true > c; c = a/b; std::cout << "a=" << a << "\nb=" << b << "\na/b=" << c << std::endl << std::endl; c = a%b; std::cout << "a=" << a << "\nb=" << b << "\na%b=" << c << std::endl << std::endl; std::cout << "fmod(" << double(a) << "," << double(b) << ") meint: " << fmod( double(a), double(b) ) << std::endl; |
Das ergibt (wenn mit -DTESTFIXPOINT kompiliert, um die volle Ausgabe zu bekommen):
a=fixpoint( internal=25, scaling=2, rounding=1, resulting=6.25 ) b=fixpoint( internal=10, scaling=2, rounding=1, resulting=2.5 ) a/b=fixpoint( internal=10, scaling=2, rounding=1, resulting=2.5 ) a=fixpoint( internal=25, scaling=2, rounding=1, resulting=6.25 ) b=fixpoint( internal=10, scaling=2, rounding=1, resulting=2.5 ) a%b=fixpoint( internal=5, scaling=2, rounding=1, resulting=1.25 ) fmod(6.25,2.5) meint: 1.25 |
Wenn ich nicht gerade voll von der Rolle bin, sollte das eigentlich stimmen; 6.25/2.5 ist doch 2.5 (was operator/ liefert) und auf ganze Zahl abgerundet ist das 2; 2*2.5 gibt 5 und damit den Rest 1.25 auf 6.25. Bin jetzt aber etwas in Eile; ich sehe es mir heute oder morgen nachmittag nochmal an und stelle eine korrigierte Version (zumindest wg. operator--) irgendwohin. Nochmal Danke! mfgkw
Datum:
Peter Dannegger schrieb: > Laut C-Standard ist es erlaubt, daß double stillschweigend als float > compiliert wird. Wenn man es umgekehrt formuliert wird ein Schuh draus. Und zur Erfüllung des Standards fehlen bei 32bit doubles ein paar Stellen.
Datum:
Johann L. schrieb: > *Nachteil* > -- Kein Standard-C Es scheint dem Entwurf für "Embedded C" zu entsprechen: http://www.open-std.org/JTC1/SC22/wg14/www/docs/n1169.pdf Schön, dass da schon jemand bei GCC was gemacht hat, hatte ich gar nicht erwartet. > -- Kein Schwanz wird sich dazu bereit erklären diese Arbeit > zu machen, zB für avr-gcc ;o) Hmm, vielleicht ja hoffentlich mal irgendwann... Aber klar, wenn ich die Reonanz auf den Aufruf sehe, mal 64-bit-FP zu implementieren, dann wirst du wohl Recht haben. :-(
Datum:
so, den operator--() habe ich korrigiert. Bei operator/() und operator%() sehe ich irgendwie keinen Handlungsbedarf. Wenn es nicht wie erwartet funktioniert: bitte Bescheid sagen. Der jeweils aktuelle Stand liegt jetzt und bis auf weiteres immer unter http://mfgkw.dyndns.org/fixpoint_release.zip Beim Entpacken entsteht ein Verzeichnis, in dessen Name Datum und Uhrzeit des Stands steht.
Datum:
Thread verlagert; siehe in Zukunft Beitrag "Festkommazahlen mit C++" (hier kann meinetwegen geschlossen werden)
