Algorithms

Luc Pattyn wrote:

Hi, I guess there are lots of equation editors (MS Word has one) that can emit HTML code;
such code could be pasted into an article.

ccpptrain wrote:

Can one BYTE or short datatype variable store a value between 0 and 999999 ?

CPallini wrote:

but NOT ANY VALUE between 0 and 999999.

El Corazon wrote:

I believe the proper term would be ALL values between 0 and 999999

Abyte[750][750] = 290;<br />
u[290] = 999999; <br />
int value = u[ Abyte[750][750] ] = 999999;

using System;
using System.Diagnostics;

namespace stuff {

   
   public class MappedArray {
      private byte[,] _aByte = new byte[1000, 1000]; // we will store the 8 least significant bits here
      private byte[,] _msBit = new byte[1000, 125];  // we will store the 9th significant bits here, packed inside a byte  (1000 / 8 = 125)
      private int []  _U = new int[300];  // we will store the unique values ranging from 0 to 999999 here
      private int _uniqueCounter = 0;  // variable used to control the unique values that can be contained inside the array

      public MappedArray() {
			
      }

      protected int GetMappedIdx(int aValue) {
         for( int i = 0; i < _uniqueCounter; i++ )
            if( _U[i] == aValue )
               return i;

         if( _uniqueCounter >= 300 )
            throw new Exception("more than 300 unique elements");
         
         int idx = _uniqueCounter++;
         _U[idx] = aValue;
         return idx;
      }

      public void Set(int x, int y, int aValue) {
         Debug.Assert(x < 1000 && y < 1000);
         int mappedID = GetMappedIdx(aValue);

         // store the least 8 significant bits of the mappedID
         _aByte[x,y] = (byte)(mappedID & 0xff);

         // Now we will store the most significant bit (bit 9) in a packed array
         
         // first obtain the secondary idx of the byte that will store the bit
         int packedIdx = y / 8;
         byte msBits = _msBit[x, packedIdx];
         // now obtain the bit position of the msb inside this byte
         int bitpos = y % 8;
         if( mappedID >= 256 ) {
            // the most significant bit shoud be 1
            msBits|=  (byte)( 1 << bitpos);
         } else {
            // the most significant bit should be 0
            msBits&=  (byte)~( 1 << bitpos);
         }

         // store the updated packed bits
         _msBit[x, packedIdx] = msBits;

      }

      public int Get(int x, int y) {
         Debug.Assert(x < 1000 && y < 1000);
         
         // obtain the least 8 significant bits of the mappedID
         
         byte lsBits = _aByte[x,y];

         // Now we will retrieve the most significant bit (bit 9) from the packed array
         
         // first obtain the secondary idx of the byte that stores the bit
         int packedIdx = y / 8;
         byte msBits = _msBit[x, packedIdx];
         // now obtain the bit position of the msb inside this byte
         int bitpos = y % 8;

         // now extract the bit
         byte bitValue = (byte)(msBits & (1 << bitpos));

         // now reassemble the full 9-bit index value
         int idx = lsBits;
         if( bitValue != 0 )
            idx |= 0x100;
         return _U[idx];  // return the mapped value
      }
   }
}

private void button1_Click(object sender, System.EventArgs e) {
         MappedArray ma = new MappedArray();
         int[] rndArr = new int[300];
         Random rnd = new Random();

         for( int i = 0; i < 300; i++ )
            rndArr[i] = rnd.Next(999999);

         for( int i = 0; i < 1000; i++ ) 
            for( int j = 0; j < 1000; j++ ) {
               int val = rndArr[rnd.Next(300)];
               ma.Set(i, j, val);
               if( ma.Get(i,j) != val )
                  throw new Exception("oops, something's wrong with the mapping logic");
            }

      }

MikeMarq wrote:

I'm working on a project which needs to use a fair number of trigonometry functions and I was wondering how slow these functions are

cmk wrote:

FSIN, FCOS, FSINCOS, FPTAN : ~17-140

For each computer I got (from 8088 up until a Pentium-Pro) I used to update a table where I showed the speed of all the trig functions along with mul and div. It was quite amusing to see how they sped up through the years. If I find it in the next couple of days, I'll post it up here....

'droid