adding bytes

that's really easy to do:

at first you should write yourself a couple of routines to do add, subtract, binary shift and so on for your array numbers..

here is a couple of them:

void add (unsigned char * sum, unsigned char *a, unsigned char *b)
{
  // add two values
  int carry = 0;
  for ( int i=200; i; i--)
  {
    int c = (int)a[i-1] + (int)b[-1] + carry;
    carry=0;
    if ( c>256 ) carry = 1;
    sum[i-1] = c&255;
  }
}

void sub (unsigned char * sum, unsigned char *a, unsigned char *b)
{
  // subtract two values
  int carry = 0;
  for ( int i=200; i; i--)
  {
    int c = (int)a[i-1] - (int)b[-1] - carry;
    carry=0;
    if ( c<0 ) carry = 1;
    sum[i-1] = c&255;
  }
}

void shift (unsigned char * val)
{
  // shift by one to the right.
  int carry = 0;
  for ( int i=0; i<200; i++)
  {
    int oldcarry = carry;
    if ( val[i]&1 ) carry = 1;
    val[i]>>=1;
    if ( oldcarry ) val[i]|=128;
  }
}


the trick is, that you do it like you would calculate an addition on paper (you learned that in school I think).

you need a variable to hold the carry value since c doesn't have something like that.

when you want to do division follow the steps on this webpage:

http://hsc.csu.edu.au/compstud/courses/23unit/comptech/97/division.htm

they explain how to do division by using more simple arithmetic (say shifts and subracts).. the web page is really cool..


I hope this helps.. if not let me know..

(btw. i haven't checked the code I wrote, but I'm pretty sure it works.. don't flame me if I made a typo)

  Nils

this one also looks good...


http://www.math.grin.edu/~rebelsky/Courses/152/97F/Readings/student-binary.html



nils

Division can be done with substracting. The number of times substraction did not result in less than zero, is the answer to the division.

I can't understand what you are trying to do?  Whats the carryold and carry value do, where does it affect anything?  Can you help me understand what you wrote?  I only have one array of chars of max length 200, but the array isn't always 200.  I need to add up the binary values of all the bytes in the array and then divide that number by a constant 16-bit binary number and append the remainder of that division to the end of the array somehow.

ok. the carry thing is used as a reminder of a overflow of two additions.

if you add two bytes your result may not fit into a byte anymore. In this case you can use a carry to remind that the last addition was overflowed and add the carry to the next addition.

one example in decimal:

    24
   +38
   ----


first you add the least significant numbers (4 and 8). the result is 12. since 12 is more than 9 (the most significant number in decimal) you set the least significant number of the sum to 2 and set your carry to one. (the carry is just used to signal, that the _last_ addition overflowed).

now you add the next significant numbers (2 and 3) and also add the carry to it (1 in this case since the last addition overflowed. otherwise it should be zero). the result is 6 and fits into a decimal number.

thus the addition of the two values gives you a result of 62. (surprise!)



when you work with large binary numbers you do it almost identical as in the example above.. instead of "decimal numbers" you work with bytes... and the addition of two bytes overflows when the value exceeds 255. I guess that's enough to understand how addition of binary numbers works. (you can also do it bit by bit or dword by dword. the way to code it is all the same).

writing a addition algorithm for large binary numbers shouldn't be no problem anymore.


now to subtraction.. it's just like addition, but instead of setting your carry to one when the result is greater than 255 you set it to 1 when your result drops below zero. the carry is then subtracted from the next significant subtraction..

everything is identical to the way kids lern arithmetics in school.. the only difference is, that kids do it in decimal, and we work with bytes.


now you have to tackle the division.. there's one very important special case in division of binary numbers.. it's the case when you divide your number by two.. in this case you can simply shift all bits to the right by one bit position..

in binary the number 193 is:
 

   11000001

 shift it to the right by one gives you:

    1100000

 (the least significant bits just goes into nirvana..)

 the result of this value is (surprise!): 96

writing a shift by right for binary numbers shouldn't be a problem. you only have to make sure, that only the last bits goes into nirvana. the other bits move into the highest bit position of their less significant byte..

(take a look at my code.. it should make it clear how it works).


if you have these simple arithmetics you can build multiplication and division by any size numbers... I'll give you a pseudo-code how to do this in a couple of minutes.. ( I just have to call someone..)

back in a minute,
  Nils

So the array contains all 0's and 1's?

In this case do:

unsigned short sum = 0;

for (i = 0; i < 200; i++)
{
   sum <<= 1;
   sum += bit[i];
}

where bit[199] is msb and bit[0]=lsb

then div = sum / constant;

after this you must convert the 10-based number to binary.

pos = 1;
for (i = 0; i >= 0; i--)
{
   bit[i] = div & pos;
   pos *= 2;
}

ok, i forgot.

but he is doing 200bytes.
just split it into 8 longs of 32-bit

this means after every 32 bits start a new long

unsigned long sum[8];
int l = 0;
for (i = 0; i < 8; i++) sum[i] = 0;
for (i = 0; i < 200; i++)
{
   sum[l] <<= 1;
   sum[l] += bit[i];
   if (i & 31) l++;
}

Thanks Nils,

I understand it better now.  I think I almost have it done it code, just having a little trouble with the variable overflow, do you know of a bigger value i can use besides unsigned char that would work?  But i think i am just about done.  Thanks again.

Darts

jep..
unsigned long will also work..
and the bigest value you can express using unsigned long is 0xffffffff.

the problem is, that the addition generated by your c-compiler itself will overflow.

expressing bit numbers as bytes is no problem. you could gain some percent of performance with larger elements, but it's not worth the work.

nils