Connect with us

Multiplication algorithm and code for base 256 ?

Discussion in 'Electronic Design' started by Skybuck Flying, Mar 11, 2007.

Scroll to continue with content
  1. Hello,

    type
    Tbig = array of byte;

    vAddTable : array[0..255,0..255] of array[0..1] of byte;
    // [0] = value
    // [1] = transport/carry

    vMulTable : array[0..255,0..255] of array[0..1] of byte;
    // [0] = value
    // [1] = value

    procedure BigMul( const A : Tbig; const B : Tbig; var C : Tbig );

    The mission is to:

    1. Multiply A and B and store result in C.
    2. Use lookup tables only.
    3. Use bytes and words only. (8 bit and 16 bit)
    4. No native/cpu arithmetic is allowed.

    Can you implement it ?

    Code can be in Delphi/Pascal or C/C++ with slightly modified prototypes,
    example:

    void BigMul( char A[], int LengthA, char B[], int LengthB );

    Bye,
    Skybuck.
     
  2. Ken Smith

    Ken Smith Guest

    Since the indexing of an array involves an add operation this last
    requirement forbids the use of table unless you allow the address of the
    table to be forced and permit operations such as ORing and combining of
    bits.

    Are we permitted a test for zero? Can we use as many tables as we want?

    Your prototype below doesn't include the "C" argument you suggested as the
    place to put the results. Clear up these problems and the code is very
    easy.


     
  3. Arithmetic on indexes is allowed.
    One table for addition.

    One table for multiplication.

    What more tables would you want ?
    My mistake I shall correct the mistake:
    void BigMul( unsigned char A[], unsigned int LengthA, unsigned char B[],
    unsigned int LengthB, unsigned char *C[], unsigned int *LengthC )

    Allocate example inside routine:

    *C = (unsigned char *) malloc(100);

    Access example:

    (*C)[5] = 200;

    *LengthC = 100;

    Call example:

    unsigned char[100];
    // etc
    unsigned char *C;

    BigMul( A, LengthA, B, LengthB, &C, &LengthC );

    Free example outside routine:

    Free(C);

    That should help you along...

    Bye,
    Skybuck.
     
  4. Ken Smith

    Ken Smith Guest

    One for the multiply is wastefully large. With one for adding, perhaps
    one for subtracting and one with (X^2)/2 is enough to do it.

    The subtacting one is not needed if the logical compliment is also
    allowed.

     
  5. Can we use as many tables as we want?
    All kinds of lookup tables are allowed to look up operations based on digits
    only.

    As soon as you try to lookup multiple digits which are combined a number
    it's not allowed.

    So substracing table is allowed.

    So (X^2)/2 table is allowed, as long as X is in range: 0..255

    Bye,
    Skybuck.
     
  6. Ken Smith

    Ken Smith Guest

    This makes writing the program so trival, I'm not interested in the
    question.
     
  7. I spent a whole day trying to solve the problem.

    I finally succceeded by using subroutines that solved my problem.

    I am definetly interested in seeing your implementation...

    Also it would be interesting to benchmark all methods to see which
    look-up-table version is faster.

    Bye,
    Skybuck.
     
  8. CBFalconer

    CBFalconer Guest

    Please don't feed the troll.
     
  9. Ken Smith

    Ken Smith Guest

    A whole day on just this! I don't think so.

    In C++ you could make a class where the operators produce the normal
    results by means of look ups.
     
  10. Yes, I was having problems with the transport/carry.

    It's best to determine the transport/carry/overflow at the same time and
    store it for later use.

    Example:

    C := First digit of (C + A);

    Transport := Second digit of (C + A);

    ^^ problem, C already updated, transport result incorrect. (Using the tables
    directly in this way would cause this problem).

    I also searched the net for some inspiration and finally decided to work out
    a clean example by hand to determine patterns in the output and to see if it
    action.

    And finally by using a subroutine which solves the problem above,
    programming it was a piece of cake ;)

    Bye,
    Skybuck.
     
  11. BTW, the old IBM 1620 computer had no hardware adder or multiplier--
    it depended on a couple of addition and multiplication tables in low
    memory. This was core memory so that eliminated some of the cant-get-
    there-from-here problems.
     
  12. Jamie

    Jamie Guest

    Except for the pack leader!
     
  13. Jim P

    Jim P Guest

    very very true in this case

    Jim P.
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-