Floating point vs fixed arithmetics (signed 64-bit)

Op Mon, 26 Mar 2012 11:22:21 +0200 schreef kishor :

An (u)int64_t multiplication is always faster than a float multiplication, assuming you don't have a hardware FPU.

Also, if you can deal with some loss of precision, you can pre-divide both operands enough to be able to use 32-bit multiplication.

--
Gemaakt met Opera's revolutionaire e-mailprogramma:  
http://www.opera.com/mail/
(Remove the obvious prefix to reply privately.)

Cortex-M3 has a 32x32->64 bit multiply instruction, so if your compiler is smart enough, it might use that. Check the generated assembly output.

If not, write your own assembly version.

Unless you require the absolutely fastest performance (and someone asking the original question clearly is not - or he would already have found the answer), do not write your own assembly code. It's just pointless optimisation for optimisation's sake.

By all means, look at the generated assembly and see if it uses the ideal instruction. If it doesn't, then file a report or support request with the compiler supplier if you want.

Don't do inline assembly unless you really have a reason for it, especially if you are not used to it.

Thanks for reply,

Compiler has generated "UMULL" instruction, (32-bit * 32-bit) As it is signed multiplication it generated another three instructions.

Assembly listing is as below,

r1 - ADC_Reading (signed) r2 - Gain (unsigned)

UMULL r0,r5,r1,r2 ; unsigned multiply 32 * 32 ASRS r3,r1,#31 ; Arithmetic Shift Right MLA r2,r3,r2,r5 ; Multiply & Accumulate MLA r1,r1,r12,r2 ; Multiply & Accumulate

MOV r2,#0x8000 MOV r3,r12

BL __aeabi_ldivmod ; 64-bits divider function

So multiplication is not a big deal. signed 64-bit divide takes time.

So still is it better than float?

Thanks, Kishore.

You don't need the division. You need to shift down 31 bits to get back to 32 bits.

Perhaps the ALU can do to all for you in one step. Check the compiler for a built-in function for 32-bit signed fractional multiplication.

Read up on fractional arithmetic.

--
Fredrik Östman

=20

I don't understand your point. In signed division we can't shift down bits = simply.

=20

Is there other method which avoids 64-bit division?

Kishore.

Try doing a >> 15 instead of a / 0x8000 in your C code.

Correct.

But the compiler should do the strength reduction for you - take note of the sign, do everything unsigned, then restore the sign. If it doesn't, then check your optimisation settings and/or complain to the supplier.

Yes - do everything unsigned. First think if the incoming data really is signed - in most cases it is not. But if you have signed data (say from a differential input), first note the sign then convert to a positive value if needed. Then do your scaling and division (and if the compiler can't convert an unsigned divide by 0x8000 to a shift, it's a poor compiler - and you can do the shift by hand). Then restore the sign.

simply.

The difference is at most 1 LSB due to rounding differences, which is probably less than your ADC noise.

You can make the difference even smaller by using a 32 bit gain variable.

You could also find out if ADC value is negative, reverse the sign, perform unsigned arithmetic, and reverse the sign of the result.

In fractional representation (all numbers are between -1 and 1) we can and we do.

--
Fredrik Östman

But note that ANSI C leaves the contents of the most significant bits of a right-shift of a negative number up to the implementor -- it is equally valid within ANSI-C specs to shift in zeros (affecting both sign and magnitude) as it is to shift in ones.

The only reliable way to do this across compilers (and even major revisions) is to convert to unsigned, shift (unsigned right shifts always shift in zeros), then restore the sign as necessary.

It should be habit. Never right-shift a signed number when it might be positive.

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

I agree that a right shift on a negative value is implementation defined, but it's very unlikely that a compiler for Cortex M3 would not use the arithmetic shift right instruction.

If you're really paranoid, you could build in a run-time check at program initialization for expected right shift behavior.

Why not do an explicit divide by 2 (or 4 or 8 or ...)? Surely most modern compilers are smart enough to recognize that this can be accomplished via an arithmetic right shift if the processor supports such an instruction or a "logical right shift" (zero filled) followed by stuffing ones up topside if the old MSB was set and the type was signed.

Just curious.

--
Rich Webb     Norfolk, VA

Actually, your answer was in the context you included: the OP's machine code shows a divide function being called, with 0x8000 as the denominator.

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

Aha! Damn that automatic quote-folding feature...

--
Rich Webb     Norfolk, VA

Except when the numbers really do get to be too ridiculously large or wide ranging to handle doing the calculations by long fractions will tend to be faster for most instrumentation needs.

It is always best to look closely at the various ways you can implement your calculations. Gains are easy by fractions (width limited multiplies that discard the least significant bits). Calibration curves can often be done by Polynomial Approximations (see Hastings reference).

"Approximations for Digital Computers" by Cecil Hastings Jr., T. Hayward, James P. Wong Jr. ISBN 0-691-07914-5

--
********************************************************************
Paul E. Bennett...............
Forth based HIDECS Consultancy
Mob: +44 (0)7811-639972
Tel: +44 (0)1235-510979
Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
********************************************************************

Sorry for late reply,

I have experimented few things,

1. Signed 32-bit divide by constant of 2^n Compiler uses 2 ASR (Arithmetic shift right) & 1 ADD instruction instead of SDIV instruction

1. Signed 32-bit divide by constant other than 2^n It uses SMLAL (signed multiply & accumulate long) & other instructions

2. Unsigned 64-bit divide by constant of 2^n It uses 2 LSR & 1 ORR instruction.

1. Unsigned 64-bit divide by constant other than 2^n

1. Signed 64-bit divide by constant of 2^n
2. Signed 64-bit divide by constant other than 2^n

It calls __aeabi_ldivmod, __aeabi_uldivmod functions

I have two queries,

1. Is hardware DIV / SDIV instructions are slower than shift logic?
2. Is it possible to generate shift based logic to case 5 mentioned above? (Signed 64-bit divide by constant of 2^n)

Thanks, Kishore.

of SDIV instruction

Yes. DIV instructions take several cycles (I don't know how many for the M3), and will cause pipeline stalls which reduce the throughput of other instructions. Shifts are therefore faster, even if they need a few other instructions around them. It is also faster to multiply by a scaled pre-calculated reciprocal (case 2 above).

Yes.

The easiest way to make sure you get signed division right is to separate out the sign, then use unsigned arithmetic. That way you can't go wrong, and the C code is portable.

Without FPU support, assuming that the processor has basic integer multiplication instructions, integer operations are ALWAYS faster than floating-point operations. Usually _far_ faster. And always more precise.

The general nature of computers is that all data into the computer has to be quantized in some way (the machine can only accept digital data), and all data out has to be quantized in some way (again, the machine can only output digital data).

There is already quantization error coming in because it is entering a discrete system. How much error depends on the quality of the hardware, which usually depends on how much one was willing to spend on it.

One measure of "goodness" of calculations is whether, for a given set of inputs (all integers), one can prove analytically that one is able to select the best outputs (again, all integers). This confines any error to the hardware rather than the software.

It ends up that for many types of calculations, using integer operations, one can meet this measure of goodness. However, one usually requires larger integers than development tools support in a native way. Which means inline assembly or large integer libraries which were written in assembly-language. Preferably the latter.

In the specific case of linearly scaling by a factor, generally what one wants to do is select a rational number h/k close to the real number to be multiplied by.

There are two subcases.

k = 2^q may be a power of two, in which case it is an integer multiplication followed by a shift or a "byte pluck". It should be obvious why this is extremely efficient.

2^q may be something other than a power of two, which is the general case. In that case, you may find this web page helpful:

Finding the best rational approximation when k is not a power of 2 is a topic from number theory, and all the information you are likely to need is at the page above. Software is included.

You're welcome.

Dave Ashley