Multiplication algorithm and code for base 256 ?

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

[Ken Smith]

In article <et**********@news4.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:
[....]

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

--
--
ke******@rahul.net forging knowledge

[Skybuck Flying]

"Ken Smith" <ke******@green.rahul.netwrote in message
news:et**********@blue.rahul.net...

In article <et**********@news4.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:
[....]

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

Arithmetic on indexes is allowed.

>>Can you implement it ?

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.

[Ken Smith]

In article <et**********@news4.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:

>
"Ken Smith" <ke******@green.rahul.netwrote in message
news:et**********@blue.rahul.net...

>In article <et**********@news4.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:
[....]

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

Arithmetic on indexes is allowed.

>>>Can you implement it ?

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.

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.

--
--
ke******@rahul.net forging knowledge

[Skybuck Flying]

>>Can we use as many tables as we want?

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

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.

[Ken Smith]

In article <et**********@news5.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:

>>>Can we use as many tables as we want?

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.

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.
--
--
ke******@rahul.net forging knowledge

[Skybuck Flying]

"Ken Smith" <ke******@green.rahul.netwrote in message
news:et**********@blue.rahul.net...

In article <et**********@news5.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:

>>>>Can we use as many tables as we want?

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.

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.

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.

[CBFalconer]

Ken Smith wrote:

Skybuck Flying <sp**@hotmail.comwrote:

.... snip ...

>

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

Please don't feed the troll.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

[Ken Smith]

In article <et**********@news4.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:

>
"Ken Smith" <ke******@green.rahul.netwrote in message
news:et**********@blue.rahul.net...

>In article <et**********@news5.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:

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

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.

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.
--
--
ke******@rahul.net forging knowledge

[Skybuck Flying]

"Ken Smith" <ke******@green.rahul.netwrote in message
news:et**********@blue.rahul.net...

In article <et**********@news4.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:

>>
"Ken Smith" <ke******@green.rahul.netwrote in message
news:et**********@blue.rahul.net...

>>In article <et**********@news5.zwoll1.ov.home.nl>,
Skybuck Flying <sp**@hotmail.comwrote:
>>Can we use as many tables as we want?
>>
>>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.

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.

I spent a whole day trying to solve the problem.

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.

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

[Skybuck]

On Mar 12, 3:18 am, CBFalconer <[e-mail]:

Ken Smith wrote:

SkybuckFlying <[e-mail]:

... snip ...

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.

Please don't feed the troll.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account fromhttp://www.teranews.com

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.