>-----< kishor > > I don't understand your point. In signed division we can't shift down > bits simply.In fractional representation (all numbers are between -1 and 1) we can and we do. -- Fredrik Östman
Floating point vs fixed arithmetics (signed 64-bit)
Started by ●March 26, 2012
Reply by ●March 26, 20122012-03-26
Reply by ●March 26, 20122012-03-26
On Mon, 26 Mar 2012 15:34:37 +0200, Arlet Ottens wrote:> On 03/26/2012 02:24 PM, kishor wrote: >> 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? > > Try doing a >> 15 instead of a / 0x8000 in your C code.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
Reply by ●March 26, 20122012-03-26
On 03/26/2012 07:25 PM, Tim Wescott wrote:> On Mon, 26 Mar 2012 15:34:37 +0200, Arlet Ottens wrote: > >> On 03/26/2012 02:24 PM, kishor wrote: >>> 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? >> >> Try doing a>> 15 instead of a / 0x8000 in your C code. > > 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.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.
Reply by ●March 26, 20122012-03-26
On Mon, 26 Mar 2012 20:19:56 +0200, Arlet Ottens <usenet+5@c-scape.nl> wrote:>On 03/26/2012 07:25 PM, Tim Wescott wrote: >> On Mon, 26 Mar 2012 15:34:37 +0200, Arlet Ottens wrote: >> >>> On 03/26/2012 02:24 PM, kishor wrote: >>>> 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? >>> >>> Try doing a>> 15 instead of a / 0x8000 in your C code. >> >> 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. > >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
Reply by ●March 26, 20122012-03-26
On Mon, 26 Mar 2012 16:45:27 -0400, Rich Webb wrote:> On Mon, 26 Mar 2012 20:19:56 +0200, Arlet Ottens <usenet+5@c-scape.nl> > wrote: > >>On 03/26/2012 07:25 PM, Tim Wescott wrote: >>> On Mon, 26 Mar 2012 15:34:37 +0200, Arlet Ottens wrote: >>> >>>> On 03/26/2012 02:24 PM, kishor wrote: >>>>> 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? >>>> >>>> Try doing a>> 15 instead of a / 0x8000 in your C code. >>> >>> 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. >> >>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.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
Reply by ●March 26, 20122012-03-26
On Mon, 26 Mar 2012 17:15:44 -0500, Tim Wescott <tim@seemywebsite.com> wrote:>On Mon, 26 Mar 2012 16:45:27 -0400, Rich Webb wrote: > >> On Mon, 26 Mar 2012 20:19:56 +0200, Arlet Ottens <usenet+5@c-scape.nl> >> wrote: >> >>>On 03/26/2012 07:25 PM, Tim Wescott wrote: >>>> On Mon, 26 Mar 2012 15:34:37 +0200, Arlet Ottens wrote: >>>> >>>>> On 03/26/2012 02:24 PM, kishor wrote: >>>>>> 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? >>>>> >>>>> Try doing a>> 15 instead of a / 0x8000 in your C code. >>>> >>>> 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. >>> >>>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. > >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.Aha! Damn that automatic quote-folding feature... -- Rich Webb Norfolk, VA
Reply by ●March 27, 20122012-03-27
kishor wrote:> Hi friends, > I am working on stellaris LM3s6965 (cortex-m3) & Keil 4.20 for data > acquisition. ADC > is signed 24-bit.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...............<email://Paul_E.Bennett@topmail.co.uk> Forth based HIDECS Consultancy Mob: +44 (0)7811-639972 Tel: +44 (0)1235-510979 Going Forth Safely ..... EBA. www.electric-boat-association.org.uk.. ********************************************************************
Reply by ●March 27, 20122012-03-27
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
2. Signed 32-bit divide by constant other than 2^n
It uses SMLAL (signed multiply & accumulate long) & other instructions
3. Unsigned 64-bit divide by constant of 2^n
It uses 2 LSR & 1 ORR instruction.
4. Unsigned 64-bit divide by constant other than 2^n
5. Signed 64-bit divide by constant of 2^n
6. 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.
Reply by ●March 27, 20122012-03-27
On 27/03/2012 13:59, kishor wrote:> 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 > > 2. Signed 32-bit divide by constant other than 2^n > It uses SMLAL (signed multiply& accumulate long)& other instructions > > 3. Unsigned 64-bit divide by constant of 2^n > It uses 2 LSR& 1 ORR instruction. > > 4. Unsigned 64-bit divide by constant other than 2^n > 5. Signed 64-bit divide by constant of 2^n > 6. 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?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).> 2. Is it possible to generate shift based logic to case 5 mentioned above? > (Signed 64-bit divide by constant of 2^n)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.> > Thanks, > Kishore. > >
Reply by ●March 27, 20122012-03-27
On Mon, 26 Mar 2012 02:22:21 -0700 (PDT), kishor <kiishor@gmail.com> wrote:> Hi friends, > I am working on stellaris LM3s6965 (cortex-m3) & Keil 4.20 for data >acquisition. ADC > is signed 24-bit. > > To perform software Gain calibration I have two options, > > 1. 64-bit fixed width arithmetic > uint16_t Gain; // 0x8000 means gain is 1 > int32_t ADC_Reading; // It contains 24-bit signed integer ADC >reading > > ADC_Reading = ((int64_t)ADC_Reading * Gain) / 0x8000; // >Gain calibration > > // As multiplication of signed 24-bit & unsigned 16-bit will not fit >into 32-bit variable > // I typecast it to int64_t. > > 2. Single precision Float > float Gain; > int32_t ADC_Reading; // It contains 24-bit signed integer ADC >reading > > ADC_Reading = ADC_Reading * Gain; // Gain >calibration > > Which is better for performance wise. > > Thanks, > Kishore.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: http://www.dtashley.com/howtos/2007/01/best_rational_approximation/ 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
