Hallo, Can anyone point me to a document describing the error introduced by doing fixed point arithmetic (+,-,*,/)? Best regards: Michael
Fixed point error
Started by ●November 22, 2010
Reply by ●November 22, 20102010-11-22
mscatdk <msc@n_o_s_p_a_m.lite.dk> wrote:>Can anyone point me to a document describing the error introduced by doing >fixed point arithmetic (+,-,*,/)?Fixed point arithmetic is exact. No error. Steve
Reply by ●November 22, 20102010-11-22
On 11/22/2010 11:21 AM, Steve Pope wrote:> mscatdk<msc@n_o_s_p_a_m.lite.dk> wrote: > >> Can anyone point me to a document describing the error introduced by doing >> fixed point arithmetic (+,-,*,/)? > > Fixed point arithmetic is exact. No error.Well... Fixed point divide isn't, at least as implemented on most machines: a fixed-point divide returns the next-smallest element within the field to the 'correct' answer. I.e. with integer math x = 5 / 3 sets x = 1. Fixed point multiplication isn't really, either -- when you multiply two fixed-point numbers together there's always a possibility of either an answer that's out of the range of the type, or a need to truncate precision. This is readily apparent with integers -- go to your friendly local C compiler and see what answer you get to int x; x = MAX_INT * MAX_INT; // or is it INT_MAX? I can never remember Any fractional type is going to potentially lose precision, and most fractional types will overflow -- even Q15 notation, if it's underlying type is 2's compliment, will have a tough time gracefully handling -1 * -1. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●November 22, 20102010-11-22
On 11/22/2010 11:19 AM, mscatdk wrote:> Hallo, > > Can anyone point me to a document describing the error introduced by doing > fixed point arithmetic (+,-,*,/)?I can't think of any off the top of my head. Normally you model this by understanding what your tools do about truncation and overflow, and modeling that as separate quantization and (you hope) saturation blocks. What search terms did you use when you Googled it? -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●November 22, 20102010-11-22
Tim Wescott <tim@seemywebsite.com> wrote:>On 11/22/2010 11:21 AM, Steve Pope wrote:>> Fixed point arithmetic is exact. No error.>Well...>Fixed point divide isn't, at least as implemented on most machines: a >fixed-point divide returns the next-smallest element within the field to >the 'correct' answer. I.e. with integer math x = 5 / 3 sets x = 1.Fixed point division produces a quotient and a remainder. It's most definitely an exact operation. It happens to be on a ring and not on a field. It's floating point operations that aren't exact... because they are trying to operate on the field of real numbers, but can't exactly. Not that this is other than an academic distinction... Steve
Reply by ●November 22, 20102010-11-22
>On 11/22/2010 11:19 AM, mscatdk wrote: >> Hallo, >> >> Can anyone point me to a document describing the error introduced bydoing>> fixed point arithmetic (+,-,*,/)?As Tim said, errors are introduced due to quantization, overflow and truncation (for example, adjusting number of bits in result after a multiplication). I found this paper here on "finite wordlength effects" that may put you on the right path: http://www.sps.ele.tue.nl/members/J.H.F.Ritzerfeld/pdfs/aeu89.pdf The following book on numerical analysis describes round off effects on computer arithmetic in general: http://tinyurl.com/29ty7vk Hope this helps! Shawn Stevenson http://www.linkedin.com/in/sestevenson
Reply by ●November 22, 20102010-11-22
On Nov 22, 2:52�pm, Tim Wescott <t...@seemywebsite.com> wrote:> On 11/22/2010 11:21 AM, Steve Pope wrote: > > > mscatdk<msc@n_o_s_p_a_m.lite.dk> �wrote: > > >> Can anyone point me to a document describing the error introduced by doing > >> fixed point arithmetic (+,-,*,/)? > > > Fixed point arithmetic is exact. �No error. > > Well... > > Fixed point divide isn't, at least as implemented on most machines: a > fixed-point divide returns the next-smallest element within the field to > the 'correct' answer. �I.e. with integer math x = 5 / 3 sets x = 1. > > Fixed point multiplication isn't really, either -- when you multiply two > fixed-point numbers together there's always a possibility of either an > answer that's out of the range of the type, or a need to truncate > precision. �This is readily apparent with integers -- go to your > friendly local C compiler and see what answer you get to > > � �int x; > � �x = MAX_INT * MAX_INT; �// or is it INT_MAX? �I can never remember > > Any fractional type is going to potentially lose precision, and most > fractional types will overflow -- even Q15 notation, if it's underlying > type is 2's compliment, will have a tough time gracefully handling -1 * -1. > > -- > > Tim Wescott > Wescott Design Serviceshttp://www.wescottdesign.com > > Do you need to implement control loops in software? > "Applied Control Theory for Embedded Systems" was written for you. > See details athttp://www.wescottdesign.com/actfes/actfes.htmlcomplement The -1 * -1 problem shows up with the assember abs instruction. 1 instruction to get the answer, several to check it. Dirk
Reply by ●November 22, 20102010-11-22
On 11/22/2010 02:52 PM, Dirk Bell wrote:> On Nov 22, 2:52 pm, Tim Wescott<t...@seemywebsite.com> wrote: >> On 11/22/2010 11:21 AM, Steve Pope wrote: >> >>> mscatdk<msc@n_o_s_p_a_m.lite.dk> wrote: >> >>>> Can anyone point me to a document describing the error introduced by doing >>>> fixed point arithmetic (+,-,*,/)? >> >>> Fixed point arithmetic is exact. No error. >> >> Well... >> >> Fixed point divide isn't, at least as implemented on most machines: a >> fixed-point divide returns the next-smallest element within the field to >> the 'correct' answer. I.e. with integer math x = 5 / 3 sets x = 1. >> >> Fixed point multiplication isn't really, either -- when you multiply two >> fixed-point numbers together there's always a possibility of either an >> answer that's out of the range of the type, or a need to truncate >> precision. This is readily apparent with integers -- go to your >> friendly local C compiler and see what answer you get to >> >> int x; >> x = MAX_INT * MAX_INT; // or is it INT_MAX? I can never remember >> >> Any fractional type is going to potentially lose precision, and most >> fractional types will overflow -- even Q15 notation, if it's underlying >> type is 2's compliment, will have a tough time gracefully handling -1 * -1. >> >> -- >> >> Tim Wescott >> Wescott Design Serviceshttp://www.wescottdesign.com >> >> Do you need to implement control loops in software? >> "Applied Control Theory for Embedded Systems" was written for you. >> See details athttp://www.wescottdesign.com/actfes/actfes.html > > complement > > The -1 * -1 problem shows up with the assember abs instruction. 1 > instruction to get the answer, several to check it.What processor? 2's compliment certainly has a bugabo with 0x8000 (or 0x80000000, depending on your word length). It's certainly been a rich source of obscure and hard-to-kill bugs for me down the years. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●November 22, 20102010-11-22
On Nov 22, 2:19�pm, "mscatdk" <msc@n_o_s_p_a_m.lite.dk> wrote:> Hallo, > > Can anyone point me to a document describing the error introduced by doing > fixed point arithmetic (+,-,*,/)? >dunno if it has all that you need, but Randy Yates wrote a nice doc: http://www.digitalsignallabs.com/fp.pdf fixed-point arithmetic is the same as integer arithmetic, but sometimes has scaling involved. addition/subtraction has no scaling but multiplication by a range like [-1, 1) does. that scaling is accomplished by bit shifting and will end up shifting bits off of the right side of the word and unless there is another lessor-significant word to receive those bits, errors are introduced. multiplying a fixed-point number by 0.0625 (which is 1/16) will result in the 4 LSBs dropping offa the right side of the word. r b-j
Reply by ●November 22, 20102010-11-22
Tim Wescott <tim@seemywebsite.com> writes:> On 11/22/2010 02:52 PM, Dirk Bell wrote: >> On Nov 22, 2:52 pm, Tim Wescott<t...@seemywebsite.com> wrote: >>> On 11/22/2010 11:21 AM, Steve Pope wrote: >>> >>>> mscatdk<msc@n_o_s_p_a_m.lite.dk> wrote: >>> >>>>> Can anyone point me to a document describing the error introduced by doing >>>>> fixed point arithmetic (+,-,*,/)? >>> >>>> Fixed point arithmetic is exact. No error. >>> >>> Well... >>> >>> Fixed point divide isn't, at least as implemented on most machines: a >>> fixed-point divide returns the next-smallest element within the field to >>> the 'correct' answer. I.e. with integer math x = 5 / 3 sets x = 1. >>> >>> Fixed point multiplication isn't really, either -- when you multiply two >>> fixed-point numbers together there's always a possibility of either an >>> answer that's out of the range of the type, or a need to truncate >>> precision. This is readily apparent with integers -- go to your >>> friendly local C compiler and see what answer you get to >>> >>> int x; >>> x = MAX_INT * MAX_INT; // or is it INT_MAX? I can never remember >>> >>> Any fractional type is going to potentially lose precision, and most >>> fractional types will overflow -- even Q15 notation, if it's underlying >>> type is 2's compliment, will have a tough time gracefully handling -1 * -1. >>> >>> -- >>> >>> Tim Wescott >>> Wescott Design Serviceshttp://www.wescottdesign.com >>> >>> Do you need to implement control loops in software? >>> "Applied Control Theory for Embedded Systems" was written for you. >>> See details athttp://www.wescottdesign.com/actfes/actfes.html >> >> complement >> >> The -1 * -1 problem shows up with the assember abs instruction. 1 >> instruction to get the answer, several to check it. > > What processor?Pretty much all of them. I think you are confused about this. If you have two N-bit, signed, two's complement integers that are both at full-scale minimum, -2^{N-1}, then their product is -2^{N-1} * -2^{N-1} = 2^{2 * N - 2} Since the maximum value of an M-bit, M = 2 * N, word is 2^{M - 1} - 1, what we require is that 2^{M - 1} - 1 >= 2^{2 * N - 2} 2^{2 * N - 1} - 1 >= 2^{2 * N - 2} 2 - 1 / (2^{2 * N - 2} >= 1 1 >= 1 / (2^{2 * N - 2}) which is true when N >= 1. QED.> 2's compliment certainly has a bugabo with 0x8000 (or 0x80000000, > depending on your word length). It's certainly been a rich source of > obscure and hard-to-kill bugs for me down the years.No, it doesn't have a problem with this, at least not in terms of straight multiplication. However, I know the problem you're thinking of. A processor such as the old Motorola 56k, which does "fractional" arithmetic usually left-shifts the result of every multiply by one. That is fine except for the one case you mention: full-scale negative squared. -- Randy Yates % "And all you had to say Digital Signal Labs % was that you were mailto://yates@ieee.org % gonna stay." http://www.digitalsignallabs.com % Getting To The Point', *Balance of Power*, ELO
