• AVR Freaks

Hot!obtain root square in p24FJ64GA702 using C language

Author
soleil_sword
Starting Member
  • Total Posts : 50
  • Reward points : 0
  • Joined: 2009/03/12 14:03:59
  • Location: 0
  • Status: offline
2020/07/21 11:04:34 (permalink)
0

obtain root square in p24FJ64GA702 using C language

Hi,
I'm trying to get the root square in p24FJ64GA702 using C language.
The purpose is to process the readings from triaxial accelerometer/gyroscope/magnetometer.
The sensor has x, y, z axis readings for each measurements. A common method is to calculate the root square using the following fomulae:
Output = (x^2+y^2+z^2)^0.5;
Here, x, y, z are all 16-bit integer. Output can be a 32-bit integer.
I don't need a super high precision, anything that is simple to implement would be the best. (if the speed is faster, that would be even better, but that is not a hard requirement)
thank you very much!
 
#1

18 Replies Related Threads

    crosland
    Super Member
    • Total Posts : 2041
    • Reward points : 0
    • Joined: 2005/05/10 10:55:05
    • Location: Warks, UK
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 11:23:12 (permalink)
    1.5 (2)
    #2
    jtemples
    عُضْوٌ جَدِيد
    • Total Posts : 11982
    • Reward points : 0
    • Joined: 2004/02/13 12:31:19
    • Location: Southern California
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 11:40:16 (permalink)
    5 (2)
    Does the C sqrt() function not work for you?
    #3
    dan1138
    Super Member
    • Total Posts : 3858
    • Reward points : 0
    • Joined: 2007/02/21 23:04:16
    • Location: 0
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 14:58:31 (permalink)
    5 (3)
    An integer square root can be computed almost as quickly as a 32-bit divide.

    This Wikipedia Methods of computing square roots article you will find this code to compute an integer square root:
    int32_t isqrt(int32_t num) {
        assert(("sqrt input should be non-negative", num > 0));
        int32_t res = 0;
        int32_t bit = 1 << 30; // The second-to-top bit is set.
                               // Same as ((unsigned) INT32_MAX + 1) / 2.

        // "bit" starts at the highest power of four <= the argument.
        while (bit > num)
            bit >>= 2;

        while (bit != 0) {
            if (num >= res + bit) {
                num -= res + bit;
                res = (res >> 1) + bit;
            } else
                res >>= 1;
            bit >>= 2;
        }
        return res;
    }
    This method tends to be fairly quick on controllers that use integer math libraries as it uses shifts not divides.
    #4
    1and0
    Access is Denied
    • Total Posts : 11155
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 16:16:54 (permalink)
    5 (1)
    dan1138
    An integer square root can be computed almost as quickly as a 32-bit divide.

    This Wikipedia Methods of computing square roots article you will find this code to compute an integer square root:
    int32_t isqrt(int32_t num) {
        assert(("sqrt input should be non-negative", num > 0));
        int32_t res = 0;
        int32_t bit = 1 << 30; // The second-to-top bit is set.
                               // Same as ((unsigned) INT32_MAX + 1) / 2.


    Have not tested that function, but shouldn't that be:
    uint16_t isqrt(uint32_t num) {
     
        int32_t bit = 1UL << 30;

    #5
    jtemples
    عُضْوٌ جَدِيد
    • Total Posts : 11982
    • Reward points : 0
    • Joined: 2004/02/13 12:31:19
    • Location: Southern California
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 16:30:57 (permalink)
    0
    1and0

    Have not tested that function, but shouldn't that be:

    uint16_t isqrt(uint32_t num) {
        int32_t bit = 1UL << 30;


    1L << 30 since the target is signed.  But yes, the Wikipedia article assumes a 32-bit platform.
    #6
    1and0
    Access is Denied
    • Total Posts : 11155
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 16:40:49 (permalink)
    5 (2)
    jtemples
     
    1L << 30 since the target is signed.  But yes, the Wikipedia article assumes a 32-bit platform.

    Smile: Smile  So it should really be this:
    uint16_t isqrt(uint32_t num) {
     
        uint32_t res = 0;
        uint32_t bit = 1UL << 30;

    #7
    dan1138
    Super Member
    • Total Posts : 3858
    • Reward points : 0
    • Joined: 2007/02/21 23:04:16
    • Location: 0
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 17:19:34 (permalink)
    3 (2)
    Don't you guys know how to quibble. :)
    #8
    soleil_sword
    Starting Member
    • Total Posts : 50
    • Reward points : 0
    • Joined: 2009/03/12 14:03:59
    • Location: 0
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 17:58:06 (permalink)
    0
    thank you guys so much !!!
    I will try this code tomorrow ! 
    #9
    jtemples
    عُضْوٌ جَدِيد
    • Total Posts : 11982
    • Reward points : 0
    • Joined: 2004/02/13 12:31:19
    • Location: Southern California
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 21:01:51 (permalink)
    4 (2)
    I hadn't noticed they were returning a signed value from a square root function, which doesn't make much sense.  But then, sqrt() also returns a signed value...
    #10
    LdB_ECM
    Super Member
    • Total Posts : 436
    • Reward points : 0
    • Joined: 2019/04/16 22:01:25
    • Location: 0
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/21 21:35:07 (permalink)
    0
    No such thing as any type of unsigned float type ... so irrelevant.
    The use of signed int on isqrt is because the MSB bit can't ever be set and the optimizer can do more with ints vs unsigned int where it has to be careful with overflows as they are defined. If you write it in assembler taking care of that yourself there is probably nothing in it.
     
    If you doubt it measure the speed of any of the C code above and then change the types to unsigned and ruin it again. On most CPU and C compilers it's 20-50% slower with unsigned. There may be rare compiler and CPU's that isn't the case but given the MSB bit can never be set so you generally just write it that way for portability.
     
    So short answer is you gain nothing by using unsigned but in many situations you may lose speed.
    post edited by LdB_ECM - 2020/07/21 21:39:58
    #11
    1and0
    Access is Denied
    • Total Posts : 11155
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 02:34:07 (permalink)
    4 (2)
    LdB_ECM
    The use of signed int on isqrt is because the MSB bit can't ever be set and the optimizer can do more with ints vs unsigned int where it has to be careful with overflows as they are defined. If you write it in assembler taking care of that yourself there is probably nothing in it.

    Why can't you take a square root on an integer value >= 2^31 (0x80000000uL)?  I don't see any overflow in that function.
     

    If you doubt it measure the speed of any of the C code above and then change the types to unsigned and ruin it again. On most CPU and C compilers it's 20-50% slower with unsigned. There may be rare compiler and CPU's that isn't the case but given the MSB bit can never be set so you generally just write it that way for portability.

    I just did a brief measure with the latest XC16 Compiler v1.50 and the speed is the SAME for both signed and unsigned ints. In fact, the function with unsigned ints works for all 2^32 integers, while the function with signed ints works for only the 2^31 non-negative integers and of course fails for the 2^31 negative integers.
     
     

    So short answer is you gain nothing by using unsigned but in many situations you may lose speed.

    No, using unsigned int it is possible to take the square roots of ALL 32-bit integers and without loss of speed.
     
    Edit: If signed ints are used for this isqrt() and a negative value is passed in, the code will stick in an infinite loop inside the function. ;)
     
    post edited by 1and0 - 2020/07/22 03:11:53
    #12
    LdB_ECM
    Super Member
    • Total Posts : 436
    • Reward points : 0
    • Joined: 2019/04/16 22:01:25
    • Location: 0
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 03:56:01 (permalink)
    0
    You have gone off on a tangent (you are talking about num being uint32_t) .... read again what he said and I commented which is the "return value".
     
    So leave the return int signed and change the num interface to uint32_t and it will give you exactly the same range. The range is limited simply by the input type not the return type. You already noted above correctly the largest possible.
     
    I will take your word for the timing it isn't worth the effort even though I am a bit surprised because of the adds.
    #13
    1and0
    Access is Denied
    • Total Posts : 11155
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 04:12:10 (permalink)
    5 (3)
    LdB_ECM
    You have gone off on a tangent (you are talking about num being uint32_t) .... read again what he said and I commented which is the "return value".

    If it is just the "return value", then why did you write these:

    ... the optimizer can do more with ints vs unsigned int where it has to be careful with overflows as they are defined.

    How can returning an unsigned value causes overflow?
     
    ... and this

    If you doubt it measure the speed of any of the C code above and then change the types to unsigned and ruin it again. On most CPU and C compilers it's 20-50% slower with unsigned.

    How can returning unsigned slower than returning a signed?
     
     
     
    So leave the return int signed and change the num interface to uint32_t and it will give you exactly the same range. The range is limited simply by the input type not the return type. You already noted above correctly the largest possible.

    The range of the return value is uint16_t, and it should be faster than returning an int32_t. ;)
     
    #14
    LdB_ECM
    Super Member
    • Total Posts : 436
    • Reward points : 0
    • Joined: 2019/04/16 22:01:25
    • Location: 0
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 05:44:07 (permalink)
    3 (2)
    The return is linked to the temps .. change them back and forward between unsigned and signed. Look where the adds I mentioned are. What it isn't connected to is the type of the input variable which just determines if you end up with a signed/signed compare or an unsigned/signed compare and ultimately the range.
     
    Anyhow this has gone stupid I am out .. leave you to it .. really don't care that much.
    post edited by LdB_ECM - 2020/07/22 05:49:36
    #15
    1and0
    Access is Denied
    • Total Posts : 11155
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 06:06:27 (permalink)
    4.25 (4)
    LdB_ECM
    The return is linked to the temps .. change them back and forward between unsigned and signed. Look where the adds I mentioned are. What it isn't connected to is the type of the input variable which just determines if you end up with a signed/signed compare or an unsigned/signed compare and ultimately the range.
     
    Anyhow this has gone stupid I am out .. leave you to it .. really don't care that much.

    What's stupid is using signed values for a square root function. The input, temps, and output variables in that function should be unsigned. I'm not surprised at the timing, as I'd expect unsigned to be more efficient than signed.
     
    Edit: ... not to mention right shift of signed numbers has implementation-defined behavior. ;)
    post edited by 1and0 - 2020/07/22 06:19:38
    #16
    NorthGuy
    Super Member
    • Total Posts : 6307
    • Reward points : 0
    • Joined: 2014/02/23 14:23:23
    • Location: Northern Canada
    • Status: online
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 10:22:50 (permalink)
    5 (1)
    For this particular program, if you declare the variables as signed, it will work for the range from 0 to 2147483647. If you declare them as unsigned, it'll work for the range from 0 to 4294967295.
     
    The only difference is in the comparison operator. It makes the difference in results. All other operators are the same either for signed or unsigned. Signed comparison is slightly longer on 8-bit PICs, but doesn't matter on most other CPUs.
     
    The right shift may be arithmetic in signed version, which doesn't affect the result in this particular program, but may produce different code. On 8-bit PICs arithmetic shift would probably produce slightly longer code, but I don't think XC8 uses arithmetic shifts.
     
    #17
    1and0
    Access is Denied
    • Total Posts : 11155
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 10:44:51 (permalink)
    0
    NorthGuy
    On 8-bit PICs arithmetic shift would probably produce slightly longer code, but I don't think XC8 uses arithmetic shifts.

    XC8 does perform arithmetic shifts.
     
    That said, OP uses a PIC24. ;)
     
    post edited by 1and0 - 2020/07/22 10:49:08
    #18
    1and0
    Access is Denied
    • Total Posts : 11155
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: obtain root square in p24FJ64GA702 using C language 2020/07/22 14:39:22 (permalink)
    5 (6)
    XC16 also uses arithmetic shifts on signed integers.
     
    Comparing the disassembly listings of using uint32_t vs. int32_t variables, both unsigned and signed versions use the same number of instructions and cycles. The differences are unsigned uses logical shifts LSR and comparison conditions GTU and NC, while signed uses arithmetic shifts ASR and comparison conditions GT and LT.
     
    So, the conclusion is it's better to use unsigned, because it not only handles twice the input range but also avoids the infinite loop resulted from negative input. Also, use uint16_t, instead of int32_t, for the return type reduces two instructions and cycles.
    post edited by 1and0 - 2020/07/22 16:17:38
    #19
    Jump to:
    © 2020 APG vNext Commercial Version 4.5