Re: [boost] Is there any Interest in a Fixed Point Library?
- Original Message - From: Kevin Atkinson [EMAIL PROTECTED] To: Boost mailing list [EMAIL PROTECTED] Sent: Saturday, March 01, 2003 12:03 AM Subject: Re: [boost] Is there any Interest in a Fixed Point Library? On Fri, 28 Feb 2003, Stephen Nutt wrote: Kevin, I started on this must be close to a year ago, and I got wrapped up with other stuff and never got back to it. Well I don't have a large interest in it beyond simple arithmetic. The main reason that I wrote is to avoid having to deal with portably sending floating point numbers over the network. With integers all I have to worry about is endian order. One nifty option was to specify what would happen on overflow. There were two choices. Either the number would not overflow but go to its limit, or it would overflow in the 'expected' way. Yes I know what you mean. The problem is doing it efficiently. Efficiency was one key aspect of my design. So I used trait classes to handle the arithmetic. This way you could either use the highly efficent overflow traits (should be as efficient as doing fixed point arithmetic without a template with a decent compiler), or use the saturation traits class, which will increase compiled code size and reduce speed. Althought I don't need the saturation aspect for my purposes, fot the template class to be useful for the embedded folks, it seemed to be necessary. fixed int, 6 a = val1; fixed char, 3 b = val2; fixed long, 9 = a + b; without loss of precision. Can you post the implementation? I'll take a look for it and see if I can clean it up a little. I'll try and post it by the end of the weekend. -- http://kevin.atkinson.dhs.org ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Is there any Interest in a Fixed Point Library?
Kevin,
The classes still need much work (read as not fully implemented and full of
bugs etc). They compiler under MSVC++ 6.0 but you may find that you need to
add the following typedefs to get it to compile.
typedef unsigned __int64uintmax_t;
typedef __int64 intmax_t;
fixed_integer.hpp defines the template fixed. This contents of this should
be fairly simple to follow.
fixed_math.cpp simply contains a templated routine to calculate fixed point
square roots.
fixed_math.hpp contains the template class fixed_math plus lots of helper
classes. The public interface contains the following
add
subtract
multiple
divide
A couple of helper methods exist to handle large multiplications and
divisions without loss of precision. The methods can be rather large, but
most of the information is known at compile time. So for example the
implementation of multiply is
static inline result multiply (const IntegerType1 multiplier, const
IntegerType2 multiplicand)
{
BOOST_STATIC_CONSTANT (int, mshift = FractionalBits1 + FractionalBits2 -
fractional_bits);
BOOST_STATIC_ASSERT (mshift = 0);
if (std::numeric_limitsunsigned int::digits = traits::digits + mshift
+ traits::is_signed)
if (traits::is_signed)
return (static_castsigned int (multiplier) * multiplicand) mshift;
else
return (static_castunsigned int (multiplier) * multiplicand)
mshift;
if (std::numeric_limitsunsigned long::digits = traits::digits + mshift
+ traits::is_signed)
if (traits::is_signed)
return (static_castsigned long (multiplier) * multiplicand)
mshift;
else
return (static_castunsigned long (multiplier) * multiplicand)
mshift;
#ifndef BOOST_NO_INT64_T
if (std::numeric_limitsuint64_t::digits = traits::digits + mshift +
traits::is_signed)
if (traits::is_signed)
return (static_castint64_t (multiplier) * multiplicand) mshift;
else
return (static_castuint64_t (multiplier) * multiplicand) mshift;
#endif
return full_multiple (multiplier, multiplicand);
}
a good compiler should detect the only possible case and compile that line
in with the required constants.
Then there is a template to perform either saturated or non saturated math.
This would need changing if it were thought necessary to add another set of
methods that would throw an exception on overflow/underflow. (I did not
consider this at time of first writing.)
The biggest ugly mess in my mind is the shift template. This turned out to
be over half the file. The idea of it was to maximise compile time
knowledge of how to shift an integer, so the produced code would be as
efficient as hand coded shifts. Not sure what happened here, so I'll have
to take another look.
I'll try and do some more cleanup tomorrow or early in the week.
Stephen
- Original Message -
From: Kevin Atkinson [EMAIL PROTECTED]
To: Boost mailing list [EMAIL PROTECTED]
Sent: Saturday, March 01, 2003 12:03 AM
Subject: Re: [boost] Is there any Interest in a Fixed Point Library?
On Fri, 28 Feb 2003, Stephen Nutt wrote:
Kevin,
I started on this must be close to a year ago, and I got wrapped up with
other stuff and never got back to it.
Well I don't have a large interest in it beyond simple arithmetic. The
main reason that I wrote is to avoid having to deal with portably sending
floating point numbers over the network. With integers all I have to
worry about is endian order.
One nifty option was to specify what would happen on overflow. There
were
two choices. Either the number would not overflow but go to its limit,
or
it would overflow in the 'expected' way.
Yes I know what you mean. The problem is doing it efficiently.
fixed int, 6 a = val1;
fixed char, 3 b = val2;
fixed long, 9 = a + b;
without loss of precision.
Can you post the implementation?
--
http://kevin.atkinson.dhs.org
___
Unsubscribe other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
fixed_math.cpp
Description: Binary data
fixed_math.hpp
Description: Binary data
fixed_math.hpp
Description: Binary data
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
RE: [boost] Is there any Interest in a Fixed Point Library?
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Kevin Atkinson Sent: Friday, February 28, 2003 1:23 AM To: Boost mailing list Subject: RE: [boost] Is there any Interest in a Fixed Point Library? Why on earth didn't the language include fixed point and/or fractional types? Well in order for fractions to be really useful, that is to support exact values for basic arithmetic, you would also need a arbitrary size integer class as the numerator and denominator can get very large very fast unless the fraction is automatically reduces after each operation and even than the numbers can get big. Long ago I used a language when programmers were men and 16 bits and 8 kbytes was all you got. The 16 bit fractional type was very neat for holding lots of measurements, but it was all too easy, as with your proposal, to fall into over/underflow pits and calculation was usually best done using floating point. As you observe, the increased accuracy compared to float (just a little too small for some measurements like weights) but with half the memory of double, and of course the integer/binary nature are sometimes useful. I am curious why you say a float is just a little too small for some measurements like weights. I have always used doubles, but I never put much thought into it. Only that float is usually good for about 6 decimal digits, but a lab balance can easily weigh more decimal digits. So if you weigh the beaker and then the beaker plus stuff, you end up with little or no accuracy for the weight of stuff. For embedded systems without FPU, using doubles may be less attractive than fixedpoint. Paul Paul A Bristow, Prizet Farmhouse, Kendal, Cumbria, LA8 8AB UK +44 1539 561830 Mobile +44 7714 33 02 04 Mobile mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Is there any Interest in a Fixed Point Library?
Kevin, I started on this must be close to a year ago, and I got wrapped up with other stuff and never got back to it. A couple of interesting design ideas. Someone (sorry I forget who) pointed me towards a great pdf file describing a fixed point arithmetic enhancement for embedded compilers. It was very cool, and had some great ideas. One nifty option was to specify what would happen on overflow. There were two choices. Either the number would not overflow but go to its limit, or it would overflow in the 'expected' way. (Did that make sense?) So if I had a class fixedunsigned char, 3 a = 3.0;// 8 bit fixed point number with three significant bits a * 3 would either give me 7.96875 or 1.0 A possible third choice would be to raise an exception on overflow/underflow. My personal interest in the template was for a highly efficient 64 bit fixed point number. As it turned out, there was no 64 bit support in Boost at the time, and getting it turned out to be more of a pain than I had time for! It may be there now as I think I've seen others look for this also since. I put together some great templates so I could do arithmetic like fixed int, 6 a = val1; fixed char, 3 b = val2; fixed long, 9 = a + b; without loss of precision. I also have templates to do 64 bit arbitary fractional multiplication and division without loss of precision. I also have a 64 bit squareroot function lurking somewhere in the depths of my harddrive. I'm not sure how all of this would work if the type was say complex, but I'm sure it could be worked on. I'll look for the pdf I mentioned above and if I find it I'll post a url. I think this is a great place to start as I believe there is a reasonable demand for fixed point arithemetic in embedded computers. Stephen - Original Message - From: Kevin Atkinson [EMAIL PROTECTED] To: Boost mailing list [EMAIL PROTECTED] Sent: Wednesday, February 26, 2003 9:28 PM Subject: [boost] Is there any Interest in a Fixed Point Library? Is there any interest in a fixed point math library. Using templates the compiler can keep track of the radix point for you making using fixed point math a lot less tedious and error prone. Attached is a rudimentary implementation which would work acceptably when the exponent is not too large or too small. If the exponent is smaller or larger than the size of the underlying integer in bits this code will likely behave badly. I plan to use the attached code to avoid having to deal with serializing floating point numbers. A exponent of -30 (-31 if using an unsigned 32 bit integer) is especially useful for representing numbers between 0 and 1. The precision will actually be a bit better than a 32 bit float since the exponent does not have to be stored. Comments on the code welcome. I am not a numerical analysis specialist so don't expect me to write a fixed point library for anything beyond simple arithmetic. -- http://kevin.atkinson.dhs.org ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Is there any Interest in a Fixed Point Library?
Found it. A long read, but interesting. http://anubis.dkuug.dk/JTC1/SC22/WG14/www/docs/n972.pdf. To give credit where it is due, Bill Seymour sent me the URL back in August of last year. (Guess is was only 6 months ago I was doing this.) - Original Message - From: Stephen Nutt [EMAIL PROTECTED] To: Boost mailing list [EMAIL PROTECTED] Sent: Friday, February 28, 2003 7:48 PM Subject: Re: [boost] Is there any Interest in a Fixed Point Library? Kevin, I started on this must be close to a year ago, and I got wrapped up with other stuff and never got back to it. A couple of interesting design ideas. Someone (sorry I forget who) pointed me towards a great pdf file describing a fixed point arithmetic enhancement for embedded compilers. It was very cool, and had some great ideas. One nifty option was to specify what would happen on overflow. There were two choices. Either the number would not overflow but go to its limit, or it would overflow in the 'expected' way. (Did that make sense?) So if I had a class fixedunsigned char, 3 a = 3.0;// 8 bit fixed point number with three significant bits a * 3 would either give me 7.96875 or 1.0 A possible third choice would be to raise an exception on overflow/underflow. My personal interest in the template was for a highly efficient 64 bit fixed point number. As it turned out, there was no 64 bit support in Boost at the time, and getting it turned out to be more of a pain than I had time for! It may be there now as I think I've seen others look for this also since. I put together some great templates so I could do arithmetic like fixed int, 6 a = val1; fixed char, 3 b = val2; fixed long, 9 = a + b; without loss of precision. I also have templates to do 64 bit arbitary fractional multiplication and division without loss of precision. I also have a 64 bit squareroot function lurking somewhere in the depths of my harddrive. I'm not sure how all of this would work if the type was say complex, but I'm sure it could be worked on. I'll look for the pdf I mentioned above and if I find it I'll post a url. I think this is a great place to start as I believe there is a reasonable demand for fixed point arithemetic in embedded computers. Stephen - Original Message - From: Kevin Atkinson [EMAIL PROTECTED] To: Boost mailing list [EMAIL PROTECTED] Sent: Wednesday, February 26, 2003 9:28 PM Subject: [boost] Is there any Interest in a Fixed Point Library? Is there any interest in a fixed point math library. Using templates the compiler can keep track of the radix point for you making using fixed point math a lot less tedious and error prone. Attached is a rudimentary implementation which would work acceptably when the exponent is not too large or too small. If the exponent is smaller or larger than the size of the underlying integer in bits this code will likely behave badly. I plan to use the attached code to avoid having to deal with serializing floating point numbers. A exponent of -30 (-31 if using an unsigned 32 bit integer) is especially useful for representing numbers between 0 and 1. The precision will actually be a bit better than a 32 bit float since the exponent does not have to be stored. Comments on the code welcome. I am not a numerical analysis specialist so don't expect me to write a fixed point library for anything beyond simple arithmetic. -- http://kevin.atkinson.dhs.org -- -- ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
RE: [boost] Is there any Interest in a Fixed Point Library?
Yes - this looks potentially rather useful for some tasks, especially embedded systems. Why on earth didn't the language include fixed point and/or fractional types? As you observe, the increased accuracy compared to float (just a little too small for some measurements like weights) but with half the memory of double, and of course the integer/binary nature are sometimes useful. Do you have any test programs? Have you made any comparison with float and double speeds? HTH to encourage you. Paul Paul A Bristow, Prizet Farmhouse, Kendal, Cumbria, LA8 8AB UK +44 1539 561830 Mobile +44 7714 33 02 04 Mobile mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Kevin Atkinson Sent: Thursday, February 27, 2003 2:29 AM To: Boost mailing list Subject: [boost] Is there any Interest in a Fixed Point Library? Is there any interest in a fixed point math library. Using templates the compiler can keep track of the radix point for you making using fixed point math a lot less tedious and error prone. Attached is a rudimentary implementation which would work acceptably when the exponent is not too large or too small. If the exponent is smaller or larger than the size of the underlying integer in bits this code will likely behave badly. I plan to use the attached code to avoid having to deal with serializing floating point numbers. A exponent of -30 (-31 if using an unsigned 32 bit integer) is especially useful for representing numbers between 0 and 1. The precision will actually be a bit better than a 32 bit float since the exponent does not have to be stored. Comments on the code welcome. I am not a numerical analysis specialist so don't expect me to write a fixed point library for anything beyond simple arithmetic. -- http://kevin.atkinson.dhs.org ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
RE: [boost] Is there any Interest in a Fixed Point Library?
On Thu, 27 Feb 2003, Paul A. Bristow wrote: Yes - this looks potentially rather useful for some tasks, especially embedded systems. Why on earth didn't the language include fixed point and/or fractional types? Well in order for fractions to be really useful, that is to support exact values for basic arithmetic, you would also need a arbitrary size integer class as the numerator and denominator can get very large very fast unless the fraction is automatically reduces after each operation and even than the numbers can get big. As you observe, the increased accuracy compared to float (just a little too small for some measurements like weights) but with half the memory of double, and of course the integer/binary nature are sometimes useful. I am curious why you say a float is just a little tool small for some measurements like weights. I have always used doubles, but I never put much thought into it. Do you have any test programs? Have you made any comparison with float and double speeds? No. However in general fixed point math is comparable to speed to floating point math on systems with a good FPU. However, you might gain some speed when most operations or integer based and a floating point number is only used occasionally (say for taking an average) as you would save cycles on the conversion from an int to a floating point number. Of course, fixed point is extremely useful on FPU less systems and the speed up will be substantial. However, my library lacks fixed point versions of the basic math functions (sqrt, exp, sin, etc...), making it of limited usefulness speed wise on a FPU less system. If someone knows of a C library that provided these routines I might consider porting it. Also, When using fixed point math you might lose some precision (if going from a double to a 32 bit fixed point number as a 64 bit would be too slow). HTH to encourage you. Paul --- http://kevin.atkinson.dhs.org ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
