floating point calculations.

That can help significantly with the syntax, but it can still be hard to get an optimal implementation. Depending on your class (or template) structure and your compiler, you might end up with significant overhead to using the class. Even if you can arrange for an optimal balance between inlining and function calls, you will still not get as efficient an implementation as the compiler's native types, because you don't (for most compilers) have access to the cpu's flags, and the compiler will be unable to do extra optimisation such as pre-calculating values, strength reduction (such as changing a division by a constant into a multiplication), and efficient register allocation.

Hard for it to do so when it isn't invoked.

As I said, this is assembly we're talking about.

(and yes, any halfway decent compiler will turn x / 4 into (x >> 2), assuming that it is used).

--
http://www.wescottdesign.com

... snip ...

However, ensure that the multiplication doesn't overflow, and don't allow rearrangement. I.e., in C, write: (200 * 21) / 4. That is after assuring the 200 * 21 won't overflow. You may need to use longs for the calculation.

The parentheses above ensure that the computation is not rearranged in to 200 / 4 * 21. Check the assembly code. That should work, but the compiler may be faulty. Then you will have to use:

thing = 200; /* done by earlier code */ ... /* code to ensure no overflow */ temp = thing * 21; ans = temp / 4;

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.

... snip ...

In general, when using software floating point, you will find that addition (or subtraction) is the slowest basic operation, due to the need to find a common 'size' to inflict on both operands. Division is the next slowest, and multiplication the fastest.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.

Floating point addition/subtractions can be quite slow due to the need to denormalize the smaller operand by shifting it right by up to 24 bits for a 32 bit single precision float and normalizing the sum/difference by shifting it left by up to 24 bits.

On an 8 bitter, an initial bulk shift with 8 or 16 bits can be done with byte moves and then doing the remaining 1-7 bit shift the traditional way. Floating multiply can be faster, if the processor has a decent

8x8=>16, 16x16=>32 or 32x32=>64 bit single cycle unsigned integer multiply instruction. With only an 8x8=>16 (and 16x16=>16) bit HW multiplication instruction, nine such multiplications are needed for the single precision case. Even with 8x8 multiply instructions, it might still be more effective in doing the 24x24=>24 bit mantissa multiplication the traditional way by shifts and adds.

Paul

I've not found that to be true on any of the platforms I've benchmarked. For example, I timed the four operations on a

6800, and add/sub was about 1ms, and mult/div was about 4ms.

--
Grant Edwards                   grante             Yow! Please come home with
                                  at               me ... I have Tylenol!!
                               visi.com

I compared the fixed point math to the emulated floating point on AVR, HC12, TMS28xx and BlackFin. For the same control algorithms implemented in C/C++, the floating point variant can be expected somewhat 15 times slower then the integer. The float add/sub/mul speed is in the same ballpark, however the division is much slower, being somewhat x4..x10 of the other operations.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

You seem to have spawned a bunch of conversations, most of which don't seem to help.

We have used conversion to scaled integers to accomplish this on low end micros. This has limitations in that ideally you need to know the number of decimal places that you have, or at least the number that are significant.. Using you example numbers, and a limit of 2 decimals, you mulitply the float by 100 and convert to an integer. 5.25 now becomes 525.

Do the multiplication as shown and you have the answer scaled up by 100, (200 * 525 = 105,000).

Simply divide it down by the applicable factors and subtracting intermediate values to get the real answer.

105,000 / 100 = 1050 (units) 105,000 - 105,000 = 0, so you are done.

123 * 1.23 = ?

123 * (1.23 * 100) = ? 123 * 123 = 15129 15129 / 100 = 151 (units) 15129 / (151*100) = ? 15129 - 15100 = 29 (non zero, so keep going) 29 / 10 = 2 (tenths) 29 - (2*10) = ? 29 - 20 = 9 (non zero, so keep going) Next division is by 1, so you are done, the 9 is now hundreths. Now reassemble the pieces.

151 units + 2 tenths + 9 hundreths = 151.29

Scott

We implemented a fixed point library a couple years ago and were surprised to find that for transcendental functions that for the same data sizes 4 byte float and 8:24 fixed for example the execution time was remarkably similar. From an application point of view fixed point gave increased precision and floating point gave larger dynamic range. As several people have pointed out the biggest time issue is normalization on processors that don't have a barrel shifter.

Regards,

-- Walter Banks Byte Craft Limited

This is safe to do for unsigned numbers and numbers (x) that can be determined to be positive at compile time.

Regards,

-- Walter Banks Byte Craft Limited

I am surprised at this result. I worked on array processors many years ago and division does not have a direct method of calculation. Instead they used an iterative approximation method using multiplies to get the estimate. I believe that for 32 bit floating point (not IEEE, it was before that) they used 7 iterations which got very close. On a 100 MFLOPS machine running at 25 MHz (ECL!) they did a adds and multiplies in the same time. Of course, this is not software, but the same complexity applies to software operations. In general the adds require a denormalization, the add and a renormalization while the multiply only requires the multiply and normalization steps. However, the multiply can take more than one operation compared to the add.

I have read that to implement the full IEEE spec requires a lot of extra steps for error checking which will slow down all of it.

Any idea how they are performing the divide that it runs as fast as the multiply?

Rick

1. There are the fast hardware dividers which essentually perform several steps of the trivial division algorithm at once.
2. The division can be computed as the multiplication by 1/x, where 1/x is computed as the Taylor series. The whole series can be computed in parallel if the hardware allows for that.
3. LUT and approximation.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

Or how they are performing a multiply that is as slow as their divide?

Jon

That was years ago, so I may be mis-remembering something, and I no longer have access to the floating point library in question (IIRC, it was from US Software). IIRC, it was probably a

68HC11 rather than a 6800 as I originally stated.

--
Grant Edwards                   grante             Yow! Did YOU find a
                                  at               DIGITAL WATCH in YOUR box
                               visi.com            of VELVEETA?

The 6800 did not have a multiply instruction and even the 6809 multiply was _slow_, thus you had to perform the 24x24 bit mantissa multiplication by repeated shifts and adds (24 times).

In float add/sub the denormalisation+normalisation phases typically required only a few bit shifts, seldom the full 24 bit shifts, requiring a considerably smaller number of (8 bit) instructions than the 24x24 bit multiply.

However, if the instruction set contains single cycle reasonably wide unsigned integer multiply instruction, the float add/mul execution times would be much closer to each other.

Paul

Just to add a little. For software implementations I've done for division, for example, the two inputs are already presumed to be normalized and the iterative division algorithm takes up the hog's share of the cycle count. Re-normalizing is usually hardly more than a few instructions to cover a few conditions. Where normalization has bit me is when first packing perviously non-normalized (fixed format) values prior to an integer (or FP) division in order to maximize useful bits in the result and with addition and subtraction where de-normalizing of one or the other is required. Often, I'll choose to instead perform the addition entirely in fixed point, jacking up the numerators so that a common divisor is assumed, and then performing the normalization and final division in a last step.

Combinatorial barrel shifters are a big plus, often neglected in ALU designs for integer processors. It takes space though and end-use designers often don't look for it so I suppose it doesn't score well on the must-do list for manufacturers.

Something else that probably doesn't rank high on the must-do list, as many aren't even aware of the possibility and don't look for it, is a simple, single-bit producing instruction for integer division that can be used as part of a sequence to achieve fuller divisions. The gates required are close to nil (trivial addition to ALU die space and no change to the longest combinatorial path, I think.) The larger cost may be pressure on the instruction space and having to write more documentation.

Jon

Good point. The platforms I'm remembering didn't have hw multiply (or if they did, it was pretty narrow). Oddly, the platforms where I've used floating point were all slow (and often 8-bit). I've used ARM7 quite a bit which has a barrel-shifter and hw multiply, but never did floating point on that platform.

--
Grant

Try adding two values with magnitudes differing by the register size (roughly). That means what the integral part of the FP value is held in.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.

For a complete example of an 8080 system, designed for speed and accuracy, including trig, log, exponential functions, see:

"Falconer Floating Point Arithmetic" by Charles Falconer,

in DDJ, March 1979, p.4 and April 1979, p.16. There were later improvements, basically minor, which improved the multiply and divide times.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.