GP2X Floating, Fixed Point Math


BattleCattle

Member
Joined
Oct 4, 2005
Messages
59
So, I'm starting to work on a 3D Library I'm designing for the GP2X (yes, another 3D lib being worked on, this one designed for performance from the ground up hopefully), and am having a difficult time deciding what internal representation of numbers I should use (floating point, fixed point, etc), and had a couple of questions. Here's what I'm looking at:

Non-integer numbers are generally stored in the form n * 2^e. as I understand it, with floating point, the number of bits dedicated to n & e can change, that is, the precision of each of the values can change. With fixed point, a certain number of bits are set aside for n, and a certain number of bits are set aside for e. This gives rise to four possible implementations (that immediately come to mind at least)

#1: using the standard 'float' data type -
Pros:
* 32 bit representation (balanced between accuracy and memory usage)
* flexible and versatile - can represent a large range of numbers fairly accurately
* no need to write math functions/macros involving bit shifts, etc

Cons:
SLOW, due to no FPU on-chip

#2: using a standard fixed-point (a 32 bit integer split, part of the bits for n part for e)
Pros:
* significantly faster than floating-point
* tried & true method - many resources/guides

Cons:
* significantly more rounding errors and narrower range of numbers represented than floats
* need to write own math functions using bit-shifts (no big deal really)
* big loss of precision during multiplication, due to lack of 64-bit intermediate representation of numbers during calculations

#3: use an extended fixed-point, separating n from e into two separate integers
Pros:
* Large range of numbers able to be accurately represented
* less concern about loss of precision / bad results from multiplication than standard fixed point (still an issue though)

Cons:
* more complicated / slower custom math functions (cannot just bit-shift to swap bits between n and e)
* more memory usage


#4: use an integer-based representation of floating point (a long int for the actual value, and then a single byte integer to specify how many bits of that value represent e)
Pros:
* floating-point precision using integer math

Cons:
* complicated custom math functions (might be) slower than just using floats in the first place (imagine multiplying two such numbers with different numbers of bits for the mantissa)
* still has a large loss of precision when multiplying, due to lack of 64 bit intermediate representation


The complexity of the math functions of #4 make me think that I probably wouldn't save any clock cycles (if any), and the difficulty shifting bits between n and e as well as the increased memory usage seem to make #3 less than ideal.

On the other hand, the slow operations of #1 and the loss of precision of multiplications of #2 make me cautious.

Any opinions out there as to what internal representation would probably be best for a 3D library for our lovely GP2X here? Granted I could always encapsulate the functionality that I need in a class and test out each of the four implementations to test for performance & accuracy, but I'm hoping to at least start by getting a working version with what I think will be the best overall. Also, does anyone have any quantitative data on how MUCH slower floating-point operations take on the ARM architecture (assuming GCC 4 optimizations)?
 
BattleCattle posted on Feb 11 2006 at 06:59 PM said:
Non-integer numbers are generally stored in the form n * 2^e. as I understand it, with floating point, the number of bits dedicated to n & e can change, that is, the precision of each of the values can change.

That's wrong. The number of bits dedicated to n and e are fixed, but the position of the decimal point is depended on the value e, thus the value represented by n can be moved from very large to very small but will have the same precision.

Andrew
 
Last edited by a moderator:
BattleCattle posted on Feb 11 2006 at 08:59 PM said:
So, I'm starting to work on a 3D Library I'm designing for the GP2X (yes, another 3D lib being worked on, this one designed for performance from the ground up hopefully), and am having a difficult time deciding what internal representation of numbers I should use (floating point, fixed point, etc), and had a couple of questions. Here's what I'm looking at:

Non-integer numbers are generally stored in the form n * 2^e. as I understand it, with floating point, the number of bits dedicated to n & e can change, that is, the precision of each of the values can change. With fixed point, a certain number of bits are set aside for n, and a certain number of bits are set aside for e. This gives rise to four possible implementations (that immediately come to mind at least)

#1: using the standard 'float' data type -
Pros:
* 32 bit representation (balanced between accuracy and memory usage)
* flexible and versatile - can represent a large range of numbers fairly accurately
* no need to write math functions/macros involving bit shifts, etc

Cons:
SLOW, due to no FPU on-chip

#2: using a standard fixed-point (a 32 bit integer split, part of the bits for n part for e)
Pros:
* significantly faster than floating-point
* tried & true method - many resources/guides

Cons:
* significantly more rounding errors and narrower range of numbers represented than floats
* need to write own math functions using bit-shifts (no big deal really)
* big loss of precision during multiplication, due to lack of 64-bit intermediate representation of numbers during calculations

#3: use an extended fixed-point, separating n from e into two separate integers
Pros:
* Large range of numbers able to be accurately represented
* less concern about loss of precision / bad results from multiplication than standard fixed point (still an issue though)

Cons:
* more complicated / slower custom math functions (cannot just bit-shift to swap bits between n and e)
* more memory usage


#4: use an integer-based representation of floating point (a long int for the actual value, and then a single byte integer to specify how many bits of that value represent e)
Pros:
* floating-point precision using integer math

Cons:
* complicated custom math functions (might be) slower than just using floats in the first place (imagine multiplying two such numbers with different numbers of bits for the mantissa)
* still has a large loss of precision when multiplying, due to lack of 64 bit intermediate representation


The complexity of the math functions of #4 make me think that I probably wouldn't save any clock cycles (if any), and the difficulty shifting bits between n and e as well as the increased memory usage seem to make #3 less than ideal.

On the other hand, the slow operations of #1 and the loss of precision of multiplications of #2 make me cautious.

Any opinions out there as to what internal representation would probably be best for a 3D library for our lovely GP2X here? Granted I could always encapsulate the functionality that I need in a class and test out each of the four implementations to test for performance & accuracy, but I'm hoping to at least start by getting a working version with what I think will be the best overall. Also, does anyone have any quantitative data on how MUCH slower floating-point operations take on the ARM architecture (assuming GCC 4 optimizations)?

You should use most appriopriate method for a task. The rasterizer will have different needs than say a transformation engine. It will be also very important to make some assumptions about target capabilities of 3d engine.

It is ok to sacrifice accuracy as long it will improve perfomance. Few pixels rendered not exactly right will not ruin a game however slow fps will.

So... experiment and profile. The hybrid solution will be probably the best and for a perfomance sake stick with intenger whenever possible.
 
Last edited by a moderator:
what language are you using, c++? because if you are trying to, say, multiply fractional numbers so that they will become integers, you could make a separate class for those conversions, and see how it performs. then you could make a dummy class that just passes the floats along, and then test them side by side.

best case scenario: you are able to handle all of your type conversions with a class or two, and then write the rest of your code without having to worry about it. but that's a lot to shoot for, i think.
 
nice thing about fixed point is that you can multiply and divide by powers of 2 by bit-shifting. also, you can do some other funky things with the bits like boolean logic.

http://www.wwnet.net/~stevelim/fixed.html
- assembly language (x86 i guess?) program for doing fixed-point

also have a look on google as there are bits of optimized fixed-point code out there for almost every language.
 
And also, if I read it correctly, your idea of standard fixed point is incorrect - whereas floating point indeed uses n and e in the fashion you described, fixed point (at least where I come from) does not use an exponent but rather fixed 'integer' and 'fraction' portions of the number, where the integer part is alike to a normal integer, where bit n represents the n'th power of 2, such that 1011b = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 11. In the fractional part, however, bits represent the negative powers of 2, such that

1011.11b = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 + 1*2^(-1) + 1*2^(-2)
= 8 + 2 + 1 + (1/2) + (1/4)

This can be simplified by thinking of bit 0 as the first bit to the left of the decimal point, counting down from 0 for the fractional part.

The definite advantage of this is that one can use normal, single, integer math operations for fixed point calculations! (provided that you agree on a consistent int:fract size, such as 16.16). For instance, adding two fixed point numbers can be done with a single ADD instruction. Multiplication is also simple, just multiply the two numbers together, and shift it 16 bits to the right (because you end up with a 32.32 number when multiplying two 16.16 numbers together) - you'll need a SMULL/UMULL instruction for this, and for division you need to shift the dividend 16 bits to the left (use a 64/32 = 32, ie long division). A lot simpler than keeping track of separate N and E values, although it (greatly) reduces the range and precision.
 
Incidentally, I ran Allegro's maths test program, and the results weren't heavily in favour of fixed point - the FPU emulation seems pretty good. The biggest winners were Allegro's trig functions, using lookup tables. Here are the stats - all in operations per second:

Code:
fixmul():    330236
float *:     256657
fixdiv():    115393
float /:     220159
fixsqrt():    50350
libc sqrtf(): 59469
fixsin():    341576
libc sin():   33396
fixcos():    341609
fixtan():    341634
libc tan():   16841
fixasin():   334655
fixacos():   334574
fixatan():   269789
libc atan():  37225
fixatan2():  104851
 
Just an OT thought.

If you are writing it from scratch, what about porting Irrlicht instead?

http://irrlicht.sourceforge.net/

It is a 3d engine for PCs and Macs but already runs on Linux and already has an internal software renderer (as a fallback from OGL and DirectX).

It is open source.

It might be as simple as changing the floating point to fixed for performance.

(I'll be trying this myself first thing when I get me hands on a GP2X)
 
andrew_j_w posted on Feb 11 2006 at 07:31 PM said:
That's wrong. The number of bits dedicated to n and e are fixed, but the position of the decimal point is depended on the value e, thus the value represented by n can be moved from very large to very small but will have the same precision.

Andrew
AntiPasta posted on Feb 12 2006 at 11:25 AM said:
And also, if I read it correctly, your idea of standard fixed point is incorrect - whereas floating point indeed uses n and e in the fashion you described, fixed point (at least where I come from) does not use an exponent but rather fixed 'integer' and 'fraction' portions of the number, where the integer part is alike to a normal integer, where bit n represents the n'th power of 2, such that 1011b = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 11. In the fractional part, however, bits represent the negative powers of 2, such that

1011.11b = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 + 1*2^(-1) + 1*2^(-2)
= 8 + 2 + 1 + (1/2) + (1/4)

This can be simplified by thinking of bit 0 as the first bit to the left of the decimal point, counting down from 0 for the fractional part.

The definite advantage of this is that one can use normal, single, integer math operations for fixed point calculations! (provided that you agree on a consistent int:fract size, such as 16.16). For instance, adding two fixed point numbers can be done with a single ADD instruction. Multiplication is also simple, just multiply the two numbers together, and shift it 16 bits to the right (because you end up with a 32.32 number when multiplying two 16.16 numbers together) - you'll need a SMULL/UMULL instruction for this, and for division you need to shift the dividend 16 bits to the left (use a 64/32 = 32, ie long division). A lot simpler than keeping track of separate N and E values, although it (greatly) reduces the range and precision.

Note to self: I should really save posts like this until I'm less sleep deprived

You two are certainly correct. I realized this about half an hour after I made the original post. I have it straightened out now, though, thanks for the explanations.

Dingo_aus posted on Feb 12 2006 at 01:33 PM said:
Just an OT thought.

If you are writing it from scratch, what about porting Irrlicht instead?

http://irrlicht.sourceforge.net/

It is a 3d engine for PCs and Macs but already runs on Linux and already has an internal software renderer (as a fallback from OGL and DirectX).

It is open source.

It might be as simple as changing the floating point to fixed for performance.

(I'll be trying this myself first thing when I get me hands on a GP2X)

Irrlicht looks pretty darn nice. Unfortunately, an engine with lightmaps, curved surfaces, collision detection, particle systems, large scale terrain support, pixel/vertex shaders, fog, transparencies, bump mapping, parallax mapping, sphere mapping, and character animation is most certainly designed for a system with a bit more pure number crunching power than the GP2X. Thats not to say that we can't have a few of these things, or even that it would be impossible to port, but
it would most likely reach the speed of a slideshow with taking many of these things out and optimizing heavily.

There are quite a number of 3d libraries & engines out there that are open source, and I believe a couple of other people are working on a couple of libraries based around OpenGL that are more likely to run at a decent speed on simple scenes.

I'm taking a bit of a different approach by writing a library from the ground up trying to design for speed based on the GP2X's hardware (no FPU or GPU, for example). No guarantees or even guesses as to release dates or performance, but I'll let people know if it gets running at a decent speed.
 
Last edited by a moderator:
Back
Top