Thread: Efficient basic arithmetic algorithms (8 bit)

  1. #1
    Unregistered
    Guest

    Question Efficient basic arithmetic algorithms (8 bit)

    Hi,

    Does anyone here know of, or can supply algortihms to provide, add, subtract, divide and multiply for 16/32/64 bit numbers using only 8 bit registers (chars?). I can do it the old schoolboy maths way, but this seems to be really slow. Are there any good tricks to provide lots of speed for this soprt of thing?

    Cheers,

    Dan ([email protected])

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Hmm... you know, this is kinda processor-level stuff.. but here goes.

    Addition is trivial because the worst you can do is add two eight bit values to get a nine bit value. So just add the two values and detect overflow (I have no idea of how one would do this in C...), carry the overflow to the next 8-bits, repeat.

    Subtraction is addition.

    Multiplication is where it gets funky... I'm inclined to say use shift-addition, but suspect that it might be better to just use 8-bit multiplication with a lot of funky additions. This also depends on how your computer would handle 8-bit multiplication. Typically, it will allow you to multiply two 8-bit values to obtain a 16-bit value, the two halves of which would be stored in seperate registers.
    Code:
    #define SHIFTVAL 8
    #define MASK 0xFF
    short a, b; // 16-bit multiplicands
    char c, d; // 8-bit handlers
    char result[4] = {}; // 32-bit result, initialized to 0.
    int i; // Count
    char carry = 0; // carry bit.
    
    for (i = 4; i > 0; i--)
    {
     mult8(a & MASK,  b & MASK, &c, &d);
     carry = oFlowAdd (&result[i], c + carry);
     carry = oFlowAdd (&result[i-1], d + carry);
     a >>= SHIFTVAL
     b >>= SHIFTVAL
    }
    return result;
    Of course, oFlowAdd is a function I imagined that would prolly have to be implemented in assembly to be efficient. Really, this does belong in the realm of assembly/microprocessor design.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bit Manipulation Questions
    By CPPNewbie in forum C++ Programming
    Replies: 7
    Last Post: 08-12-2003, 02:17 PM
  2. Copy bit to bit
    By Coder2Die4 in forum C Programming
    Replies: 15
    Last Post: 06-26-2003, 09:58 AM
  3. binary numbers
    By watshamacalit in forum C Programming
    Replies: 4
    Last Post: 01-14-2003, 11:06 PM
  4. 16 bit or 32 bit
    By Juganoo in forum C Programming
    Replies: 9
    Last Post: 12-19-2002, 07:24 AM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM