Floating Point Arithmetic and FTSP -- A solution

[GoogleCodeExporter]

I have recently noticed that the floating point division operation for 
calculating the slope of the linear regression line in TimeSyncP.nc file of 
FTSP protocol in TinyOS has some problems. If we take a look at the following 
nesC code of FTSP, we can see that localSum and offsetSum variables are 
int64_t. However, division of these two 64 bit numbers by casting to the float 
is problematic.

        for(i = 0; i < MAX_ENTRIES; ++i)
            if( table[i].state == ENTRY_FULL ) {
                int32_t a = table[i].localTime - newLocalAverage;
                int32_t b = table[i].timeOffset - newOffsetAverage;

                localSum += (int64_t)a * a;
                offsetSum += (int64_t)a * b;
            }

        if( localSum != 0 )
            newSkew = (float)offsetSum / (float)localSum;

        atomic
        {
            skew = newSkew;
            offsetAverage = newOffsetAverage;
            localAverage = newLocalAverage;
            numEntries = tableEntries;
        }

The main issue is, in Micaz platform floating point numbers are 32 bit numbers! 
(And may be in most other platforms). And if we cast an int64_t to float, we 
will get garbage data (especially when the casted variables are negative).

Consider the following localtime-globaltime pairs. These are the values I have 
recorded when running Ftsp between 2 nodes (1 root and 1 slave). The following 
8 entries are the pairs which the slave node  used to fill its regression 
table. If you run the linear regression code with the current code of FTSP in 
the tinyos 2.1.1 you wont get 0x4d457df value when the local time of the slave 
node is 0x4c61357.

[local=0x7b28be]    [global=0x896e7b]
[local=0x1048612]  [global=0x112cba8]
[local=0x18de365]  [global=0x19c28d5]
[local=0x21740b9]  [global=0x2258602]
[local=0x2a09e0c]  [global=0x2aee32e]
[local=0x329fb5f]   [global=0x338405b]
[local=0x3b358b2]  [global=0x3c19d87]
[local=0x43cb605]  [global=0x44afab3]
[local=0x4c61357]  [global=0x4d457df]

My suggestion is adding a getSlope function as follows:

  float getSlope(int64_t a,int64_t b){
    bool negative = FALSE;
    float s = 0.0;

    if(a<0){                    // get the original positive number
      negative = TRUE;
      a--;                    
      a =~a;                   
    }

    if(b<0){
      if(negative==FALSE){
        negative = TRUE;
      }
      else{
        negative = FALSE;
      }

      b--;
      b =~b;
    }

    while(((a>>32)&0xFFFFFFFF) || ((b>>32)&0xFFFFFFFF)){
      a>>=4;
      b>>=4;
    }

    s = (float)a/(float)b;

    if(negative == TRUE){
      s*=-1.0;
    }

    return s;
  }

This function converts int64_t variables to int32_t and then calculates the 
slope. Then we can change TimeSyncP.nc as:

        for(i = 0; i < MAX_ENTRIES; ++i)
            if( table[i].state == ENTRY_FULL ) {
                int32_t a = table[i].localTime - newLocalAverage;
                int32_t b = table[i].timeOffset - newOffsetAverage;

                localSum += (int64_t)a * a;
                offsetSum += (int64_t)a * b;
            }

        if( localSum != 0 )
            newSkew = getSlope(offsetSum,localSum);

        atomic
        {
            skew = newSkew;
            offsetAverage = newOffsetAverage;
            localAverage = newLocalAverage;
            numEntries = tableEntries;
        }

Any other suggestions or ideas??

Sinan

Ege University
Computer Engineering Department
Izmir, TURKEY

Original issue reported on code.google.com by sinanyi...@gmail.com on 24 Nov 2010 at 4:14

[GoogleCodeExporter]

"And if we cast an int64_t to float, we will get garbage data (especially when 
the casted variables are negative)."

I don't think this is true. It's true if you cast a pointer to an int to a 
pointer to a float, but casting the basic types should perform the proper 
conversion. You're of course going to lose precision for large integers, but it 
should not lead to garbage. Or am I missing something? Is there a concrete bug 
you've encountered? Your solution will add a significant amount of code to 
FTSP, making it bigger.

Original comment by philip.l...@gmail.com on 16 Dec 2010 at 11:54

• Changed state: Started

[GoogleCodeExporter]

Dear Philip,

I have examined FTSP source code deeply and saw that I have missed something. 

Thus, you can close this issue if you like.

Thanks all,

Sinan

Original comment by sinanyi...@gmail.com on 29 Dec 2010 at 2:27

[GoogleCodeExporter]

Closed based on Sinan's response.

Original comment by philip.l...@gmail.com on 3 Jan 2011 at 6:45

• Changed state: Invalid