445,898 Members | 2,006 Online
Need help? Post your question and get tips & solutions from a community of 445,898 IT Pros & Developers. It's quick & easy.

# Multiplication algorithm and code for base 256 ?

 P: n/a 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. Mar 11 '07 #1
11 Replies

 P: n/a In article , Skybuck Flying 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 Mar 11 '07 #2

 P: n/a "Ken Smith" , Skybuck Flying >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. Mar 11 '07 #3

 P: n/a In article , Skybuck Flying "Ken Smith" In article ,Skybuck Flying >>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 lastrequirement forbids the use of table unless you allow the address of thetable to be forced and permit operations such as ORing and combining ofbits. 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 theplace to put the results. Clear up these problems and the code is veryeasy. 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];// etcunsigned 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 Mar 11 '07 #4

 P: n/a >>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. Mar 11 '07 #5

 P: n/a In article , 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, perhapsone for subtracting and one with (X^2)/2 is enough to do it.The subtacting one is not needed if the logical compliment is alsoallowed. All kinds of lookup tables are allowed to look up operations based on digitsonly. This makes writing the program so trival, I'm not interested in the question. -- -- ke******@rahul.net forging knowledge Mar 11 '07 #6

 P: n/a "Ken Smith" , 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, perhapsone for subtracting and one with (X^2)/2 is enough to do it.The subtacting one is not needed if the logical compliment is alsoallowed. All kinds of lookup tables are allowed to look up operations based ondigitsonly. 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. Mar 12 '07 #7

 P: n/a Ken Smith wrote: Skybuck Flying >All kinds of lookup tables are allowed to look up operationsbased 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. -- Posted via a free Usenet account from http://www.teranews.com Mar 12 '07 #8

 P: n/a In article , Skybuck Flying "Ken Smith" In article ,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, perhapsone for subtracting and one with (X^2)/2 is enough to do it.The subtacting one is not needed if the logical compliment is alsoallowed.All kinds of lookup tables are allowed to look up operations based ondigitsonly. This makes writing the program so trival, I'm not interested in thequestion. 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 Mar 12 '07 #9

 P: n/a "Ken Smith" , Skybuck Flying >"Ken Smith" >In article ,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,perhapsone for subtracting and one with (X^2)/2 is enough to do it.>The subtacting one is not needed if the logical compliment is alsoallowed.All kinds of lookup tables are allowed to look up operations based ondigitsonly.This makes writing the program so trival, I'm not interested in thequestion. 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. Mar 12 '07 #10

 P: n/a 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. Mar 12 '07 #11

 P: n/a On Mar 12, 3:18 am, CBFalconer -- 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. Mar 13 '07 #12

### This discussion thread is closed

Replies have been disabled for this discussion.