Software vs hardware floating-point [was Re: What happened ...]
|
Prev: What happened to computer architecture (and comp.arch?)
Next: Parallel huffman encoding and decoding algorithm/idea by Skybuck for sale !
From: Terje Mathisen on 10 Sep 2009 15:51 nmm1(a)cam.ac.uk wrote: > In article<wOmdnaYJINxgZzXXnZ2dnUVZ8jidnZ2d(a)lyse.net>, > Terje Mathisen<Terje.Mathisen(a)tmsw.no> wrote: >> >> I do remember that for tri-lin sampling the log2() function needs to >> have at least 10 fractional bits correct, I was able to discover/invent >> a fast SIMD style code that managed this without any lookup tables. > > No floating-point hardware is needed for implementing fast, efficient > logarithm functions - indeed, most implementations do most of their > work in fixed point! I went back into that 2-year old code, and you're totally right. :-) > > number = mantissa * 2^exponent > logarithm = exponent + polynomial(mantissa) > > Working out a suitable polynomial is easy, and the scaling can be (and > usually is) done statically. There really isn't a problem. inline int rr_log2(float f) { int e = AS_INT32(f); int m = ((e >> 7) & 0xffff) - 0x8000; m *= m; e += (5<<17) - (127<<23); m >>= 13; e -= m*5; return e; } The code above returns the binary log in 9:23 fixed-point format, so the fp version wraps this in a scaling mul. It takes the top of the mantissa, squares it, shifts down and does a mul by 5 which an x86 handles with either LEA or shift&add. Afair the results are quite close to perfect for the entire legal/possible input range. Terje -- - <Terje.Mathisen at tmsw.no> "almost all programming can be viewed as an exercise in caching"
From: Chris Gray on 11 Sep 2009 21:46 nmm1(a)cam.ac.uk writes: > Eh? The reason they switched was NOT because the algorithms weren't > fixed-point ones, but because their new 'computer science' employees > didn't have a clue about scaling. Few people under 70 do :-( Hmmph! I'm not that old, yet. I used fixed point in my AmigaMUD system, since I wanted to do graphical co-ordinates that way, and the software floating point on the early Amiga's was way too slow. The format was a fixed 16.16 representation. You declared the variables as type "fixed", and wrote constants with a decimal point but no exponent. The fixed-point worked fine, but it was a bad idea for graphics co-ordinates. -- Experience should guide us, not rule us. Chris Gray cg(a)GraySage.COM http://www.Nalug.ORG/ (Lego) http://www.GraySage.COM/cg/ (Other)
From: nmm1 on 12 Sep 2009 05:51 In article <87iqfpexzx.fsf(a)ami-cg.GraySage.com>, Chris Gray <cg(a)graysage.com> wrote: > >> Eh? The reason they switched was NOT because the algorithms weren't >> fixed-point ones, but because their new 'computer science' employees >> didn't have a clue about scaling. Few people under 70 do :-( > >Hmmph! I'm not that old, yet. I used fixed point in my AmigaMUD system, >since I wanted to do graphical co-ordinates that way, and the software >floating point on the early Amiga's was way too slow. The format was >a fixed 16.16 representation. You declared the variables as type >"fixed", and wrote constants with a decimal point but no exponent. >The fixed-point worked fine, but it was a bad idea for graphics >co-ordinates. I will bet that you weren't taught how to scale fixed-point numbers for numerical work in a computer science course! Why was it a problem for graphics co-ordinates? That's one of its classic uses. Regards, Nick Maclaren.
From: ChrisQ on 12 Sep 2009 08:07 nmm1(a)cam.ac.uk wrote: > In article <87iqfpexzx.fsf(a)ami-cg.GraySage.com>, > Chris Gray <cg(a)graysage.com> wrote: >>> Eh? The reason they switched was NOT because the algorithms weren't >>> fixed-point ones, but because their new 'computer science' employees >>> didn't have a clue about scaling. Few people under 70 do :-( >> Hmmph! I'm not that old, yet. I used fixed point in my AmigaMUD system, >> since I wanted to do graphical co-ordinates that way, and the software >> floating point on the early Amiga's was way too slow. The format was >> a fixed 16.16 representation. You declared the variables as type >> "fixed", and wrote constants with a decimal point but no exponent. >> The fixed-point worked fine, but it was a bad idea for graphics >> co-ordinates. > > I will bet that you weren't taught how to scale fixed-point numbers > for numerical work in a computer science course! > > Why was it a problem for graphics co-ordinates? That's one of its > classic uses. > > > Regards, > Nick Maclaren. For embedded work, I would only consider floating point as a last resort, because of the overhead and speed penalty. With fixed point, the trick is to scale everything to the expected range of values, which is nearly always known and also to the machine word size. Anything outside this range is an error. ie, trivial example to scale up: u32Result = (U32) u16InValue << u8ScaleFactor; u32Result /= u16Fraction; Two lines of C and only one integer divide. Scale up is similar. For trig functions, I mainly use lookup tables. ie: 16 + 1 bit sin takes only 16k of memory. This sort of thing becomes part of the toolbox for embedded work, especially for compute intensive stuff like graphics. Knuth's Tex package uses fixed point for all it's internal work, iirc, probably because the early machines were so slow. The problem with any generalised solution like float libraries is that they will never be as efficient as a problem specific solution. The trade off is that you have to do the work yourself. Perhaps powerfull modern desktops are making us all lazy :-)... Regards, Chris
From: Bernd Paysan on 12 Sep 2009 15:30
ChrisQ wrote: > Knuth's Tex package uses fixed point for all it's internal work, iirc, > probably because the early machines were so slow. Knuth explains that quite in detail, and it's not just because FP is slow, but also because it may lead to inaccurate results (especially with the wildly differing FP implementations back at that time). AFAIK, you can use FP for glues in TeX, because it's quite easy to achieve what Knuth wants (filll >> fill >> fil, just have filll=2^128*fill=2^256*fil, and you're done). This doesn't compromise on accuracy, because you'll convert the glue into an integer number (the basic units to stretch the words) before using it to stretch the words, anyway. The point here is that the right side of the rightmost word should align to the right side of the document, no matter how much spacing you inserted in between, and how many rounding errors you made on your way. This is fairly straight-forward in fixed point. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://www.jwdt.com/~paysan/ |