# Multiplication algorithm and code for base 256 ?

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

1. ### Skybuck FlyingGuest

Hello,

type
Tbig = array of byte;

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

vMulTable : array[0..255,0..255] of array[0..1] of byte;
//  = value
//  = 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 SmithGuest

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. ### Skybuck FlyingGuest

Arithmetic on indexes is allowed.

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) = 200;

*LengthC = 100;

Call example:

unsigned char;
// etc
unsigned char *C;

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

Free example outside routine:

Free(C);

Bye,
Skybuck.

4. ### Ken SmithGuest

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. ### Skybuck FlyingGuest

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 SmithGuest

This makes writing the program so trival, I'm not interested in the
question.

7. ### Skybuck FlyingGuest

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.

9. ### Ken SmithGuest

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. ### Skybuck FlyingGuest

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. ### Ancient_HackerGuest

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. ### JamieGuest  