Multiword shifted addition

[szevvy]

Hi,

I have a problem that Ive been grappling with for too long, and Im hoping that someone here might know how to do this.

I have two multi-word arrays of unsigned shorts, representing large numbers least significant word first. I want to add one of these arrays to the other, like you would normally add two multi-word arrays, except theres a catch I want to shift the first array left by an arbitary number of bits before adding it. So, if I wanted a shift of 79, each word would be shifted left by 9 bits and the whole thing would be ADCd into the second array, starting at the fourth word.

Now, I have thought about this, tried different things and for the life of me I cant get it to work, and work fast. Im currently doing something along the lines of

Code:

carry = setBit(RESULT_ARRAY, currentWord, currentBit, getBit(SOURCE_ARRAY, currentWordA, currentBitA) + getBit(RESULT_ARRAY, currentWord, currentBit) + carry);

for every line, which is very, very slow.

Could someone point me in the right direction, as Im sure that letting the CPU take care of adding would stop this thing from chugging.

Id be eternally grateful!

Thanks.

[Intel_Software_Netw1]

We'll forward your question to our engineering contacts and let you know how they respond.

Regards,

Lexi S.

IntelSoftware NetworkSupport

http://www.intel.com/software

Contact us

[szevvy]

I've done a bit of research on this, and it seems that I need the 'addition' step from shift-and-add multiword multiplication. However, I can't find any code to actually do this - and I honestly can't see how to implement it. When you shift values to the left you're eventually going to drop bits off the left side, and if you simply use a larger word(putting a 16 bit value by putting it into a 32 word value and then shifting) then the carry won't be automatically put into the carry flag - would I simply test the 17th bit of that 32 bit value and put it into the carry flag, or is there an easier way?

Thanks.

[Intel_Software_Netw1]

Hello,

Just a follow-up post to let you know we are still investigating your question. Thank you for your patience.

Best regards,

Jim A

IntelSoftware NetworkSupport

http://www.intel.com/software

Contact us

[Intel_Software_Netw1]

Hi,

Can you provide some further clarification?

1. What is the size of the two numbers that get added together? Is it always the same or can vary?
2. Can you define the size of multi-word in the context of the add operation? (may be the same as question #1)
3. What is the shift count range? Is it constant for the whole array or can vary?
4. What is the target processor?

If theyou can describe whatyou are trying to do in some pseudo code that will be best. Something like this, perhaps:

unsigned short a[256], b[256], result[??];
for(i-0; i<256; i++)
{

result = .

}

Thanks,

Jim A

IntelSoftware NetworkSupport

http://www.intel.com/software

Contact us

[szevvy]

1. The two numbers (say p and q)vary, anywhere between 2 and 1024 bits - but they have the same bitlength at any one time, the result is 2 times the bitlength of p or q.

2. As above.

3. Shift count range is the same as above - although it will always be the curent bitlength of p or q.

4. Any Pentium-class CPU.

Pseudocode, roughly:

Code:

unsigned short * p, *q, *result;
unsigned currentBitLength;

mainloop(int maxSize){
  p = unsigned short[(maxSize / 16) + 1);
  q = unsigned short[(maxSize / 16) + 1);
  result = unsigned short[maxSize / 8) + 1);

  currentBitLength = 0;

  while (true){
     
     if (equals(result,  wantedValue))
        break;

    if (lessThan(result, wantedValue)){
        if (blah)
           result = result + ( p << currentBitLength))
       else
           result = result + ( q << currentBitLength))

        bitLength++;

        break;

    }

    if (moreThan(result, wantedValue)
       currentBitLength--;
      
  }
}

Although the adding is currently done like this:

Code:

Code:
inline void add(int value, unsigned offset){   
 int carry = 0;
 int currentPart = offset / bitsPerWord;
 int currentBit = offset % bitsPerWord; 
 int currentPartA = 0;
 int currentBitA = 0;
 for (unsigned i = 0; i < level + 1; i++){
  carry = setBit(VALUE_MUL, currentPart, currentBit, getBit(value, currentPartA, currentBitA) + getBit(VALUE_MUL, currentPart, currentBit) + carry);
  if ((++currentBit) == bitsPerWord){
   currentPart++;
   currentBit = 0;
  }
  if ((++currentBitA) == bitsPerWord){
   currentPartA++;
   currentBitA = 0;
  }
 } 
 while (carry){
  carry = setBit(VALUE_MUL, currentPart, currentBit, getBit(VALUE_MUL, currentPart, currentBit) + carry);
  if ((++currentBit) == bitsPerWord){
   currentPart++;
   currentBit = 0;
  }
 }
}

Thanks for the help.

Message Edited by szevvy@hotmail.com on 02-09-2006 12:38 AM

Message Edited by szevvy@hotmail.com on 02-09-2006 12:38 AM