Multiplication algorithm and code for base 256 ?


S

Skybuck Flying

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.
 
Ad

Advertisements

K

Ken Smith

Skybuck Flying said:
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.

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.

Can you implement it ?

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.


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.
 
S

Skybuck Flying

Ken Smith said:
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.

Arithmetic on indexes is allowed.
Are we permitted a test for zero?
Yes.

Can we use as many tables as we want?

One table for addition.

One table for multiplication.

What more tables would you 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.

My mistake I shall correct the mistake:
Code can be in Delphi/Pascal or C/C++ with slightly modified prototypes,
example:
void BigMul( char A[], int LengthA, char B[], int LengthB );

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.
 
K

Ken Smith

Arithmetic on indexes is allowed.


One table for addition.

One table for multiplication.

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.

What more tables would you 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.

My mistake I shall correct the mistake:
Code can be in Delphi/Pascal or C/C++ with slightly modified prototypes,
example:
void BigMul( char A[], int LengthA, char B[], int LengthB );

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.
 
S

Skybuck Flying

Can we use as many tables as we want?
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.

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.
 
K

Ken Smith

All kinds of lookup tables are allowed to look up operations based on digits
only.

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

Advertisements

S

Skybuck Flying

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

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.
 
K

Ken Smith

I spent a whole day trying to solve the problem.

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

I finally succceeded by using subroutines that solved my problem.

In C++ you could make a class where the operators produce the normal
results by means of look ups.
 
S

Skybuck Flying

Ken Smith said:
A whole day on just this! I don't think so.

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.
 
A

Ancient_Hacker

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.
 
Ad

Advertisements

S

Skybuck

... snip ...



Please don't feed the troll.

Starving creatures is mean !

You are a mean guy Chuck !

I give trolls lot's of love, attention and food until they have had
enough of it.

Then they just go away...

Bye,
Skybuck.
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Top