Multiplication and BCD conversion routines for the PIC16LF1823

Thread Starter

cmartinez

Joined Jan 17, 2007
8,218
I need to write two routines for the PIC16LF1823:
  • Non-signed three byte by three byte multiplication
  • Non-signed 6-byte number to BCD conversion
The thing is that the MCU I've just mentioned has no multiplication nor division functions available. I do, however, understand the basics and know how to add and substract multiple byte numbers, plus shift their bits to execute a multiplication or division operation in powers of two. Also, I wrote a routine a while ago that converts a single byte value into a three digit ascii number. i.e. A3H -> "163"

Any general ideas as to where to start, or the logic steps that I should use?

@MrChips @Papabravo
 
Last edited:

MrChips

Joined Oct 2, 2009
30,708
Let's tackle one problem at a time.

24 x 24 multiplication -> 48-bit result

I assume that you want to do this in assembler.
Assume you want (r5, r4, r3, r2, r1, r0) = (m2, m1, m0) x (n2, n1, n0)

We will call
(r5, r4, r3, r2, r1, r0) = R
(m2, m1, m0) = M
(n2, n1, n0) = N
carry bit = C

Step 1 - Set R = 0, set counter = 24
Step 2 - Shift M left by 1 bit into C
Step 3 - If C = 1, R <= R + N
Step 4 - Decrement counter, if counter = 0, done. Else go to step 5.
Step 5 - Shift R left by 1 bit, go to step 2
 

MrSalts

Joined Apr 2, 2020
2,767
I hope you have a fast processor or the freedom to round to some significant digits.
Your 6-byte number is 281 trillion or about...
281,474,976,710,656
Which will take a lot of clock cycles.
My first logic step would be to use a different processor or off-load the calculation to a bigger processor via a wifi board.
Rounding will be your friend - handling numbers this big without rounding will take hours to days depending on the two numbers being processed with an 8-bit processor.

Alternatively, I would handle everything as 4-bit BCD values and make a 4-bit x 4-bit multiply function that keeps getting called.
 

JohnInTX

Joined Jun 26, 2012
4,787
Here are some ap-notes that may be helpful. Once you get the idea, you can expand them to the necessary width. They're mostly for original midrange which should be more or less portable to Enhanced midrange.
I have a general bin-BCD routine based on double-dabble that I can dig up and PM you if you like but most of my polished stuff is 18F.

Early math routines for 16xxx including BCD-BIN-BCD:
https://ww1.microchip.com/downloads/en/Appnotes/00526e.pdf

Later stuff:
Fixed point:
https://ww1.microchip.com/downloads/en/Appnotes/00617.pdf
Floating point:
https://ww1.microchip.com/downloads/en/Appnotes/00660.pdf
Float to ASCII:
https://ww1.microchip.com/downloads/en/Appnotes/00670b.pdf
Older floating point for a 17Cxx - ports OK to an 18F
https://ww1.microchip.com/downloads/en/Appnotes/00575.pdf

Any uCHIP ap-note written by Frank J. Testa is a good read.

Good luck!
 

MrChips

Joined Oct 2, 2009
30,708
Instead of shifting into a carry register, we can test the MSB of m2.

Step 1 - Set R = 0, set counter = 24
Step 2 - Test MSB of m2
Step 3 - If MSB of m2 = 1, R <= R + N
Step 4 - Decrement counter, if counter = 0, done. Else go to step 5.
Step 5 - Shift M left by 1 bit. Shift R left by 1 bit. Go to step 2
 

Papabravo

Joined Feb 24, 2006
21,159
I know how to do the multiplication by "brute force" using a 6-byte accumulator, a 6-byte multiplicand shift register, and a 3-byte multiplier shift register. I don't know the details of any more efficient multiplication algorithms.
  1. Clear the Accumulator
  2. Repeat steps 3-6 24 times, goto 7
  3. Test the LSB of the multiplier, if it is a 1, add the multiplicand register to the accumulator
  4. Shift the multiplicand register left 1 bit
  5. Shift the multiplier right 1 bit
  6. If the multiplier is equal to 0, then DONE, else goto 3.
  7. DONE

To convert 6 ASCII digits belonging to the set [0-9], you clear a 3 byte shift register. Then you start with the most significant byte, subtract '0' and OR that into the least significant byte of a 3-byte shift register. Shift the 3 byte shift register to the left by 4 bits. Repeat for the remining 5 characters.
 

MrChips

Joined Oct 2, 2009
30,708
PB's algorithm and mine are very similar. In his case he is shifting the multiplier to the right.
His algorithm is faster because it ends when the multiplier is zero. Mine will always take 24 loops.
 

Papabravo

Joined Feb 24, 2006
21,159
PB's algorithm and mine are very similar. In his case he is shifting the multiplier to the right.
His algorithm is faster because it ends when the multiplier is zero. Mine will always take 24 loops.
Mine is colloquial heuristic hand waving, but yours is more formal. For pedagogical purposes I think yours is the winner. There may be additional coding optimizations that are discovered along the way.
 

MrSalts

Joined Apr 2, 2020
2,767
Here are some ap-notes that may be helpful. Once you get the idea, you can expand them to the necessary width. They're mostly for original midrange which should be more or less portable to Enhanced midrange.
I have a general bin-BCD routine based on double-dabble that I can dig up and PM you if you like but most of my polished stuff is 18F.

Early math routines for 16xxx including BCD-BIN-BCD:
https://ww1.microchip.com/downloads/en/Appnotes/00526e.pdf

Later stuff:
Fixed point:
https://ww1.microchip.com/downloads/en/Appnotes/00617.pdf
Floating point:
https://ww1.microchip.com/downloads/en/Appnotes/00660.pdf
Float to ASCII:
https://ww1.microchip.com/downloads/en/Appnotes/00670b.pdf
Older floating point for a 17Cxx - ports OK to an 18F
https://ww1.microchip.com/downloads/en/Appnotes/00575.pdf

Any uCHIP ap-note written by Frank J. Testa is a good read.

Good luck!
Your fixed-point suggestion is a gold nugget...
https://ww1.microchip.com/downloads/en/Appnotes/00617.pdf
 
Last edited:

Thread Starter

cmartinez

Joined Jan 17, 2007
8,218
My head is spinning... thanks all for your suggestions.

I'm going to pay close attention and try to visualize both PPB and Chips' (for pedagogical purposes, no kidding) algorithms and see if I can understand how they work.

Many, many thanks .... *off to do my homework*
 
Last edited:

Papabravo

Joined Feb 24, 2006
21,159
My head is spinning... thanks all for your suggestions.

I'm going to pay close attention and try to visualize both PPB and Chips' (for pedagogical purposes, no kidding) algorithms and see if I can understand how thy work.

Many, many thanks .... *off to do my homework*
It is the identical process for doing decimal multiplication using pencil and paper except in binary, and the additions are done at each step instead of AFTER all the partial products have been computed
 

Thread Starter

cmartinez

Joined Jan 17, 2007
8,218
If you are still having trouble I can elaborate tomorrow.
No need for that. I think I understand it now.

I'm gonna write the detailed code and post it here for posterity. It's the least that I can do for this place and its members after they've done so much for me.
 

MrSalts

Joined Apr 2, 2020
2,767
I think not. Words are frequently adopted from one language to another. You must be uber sensitive.
Or, you might be poking fun at someone or drawing unnecessary attention to someone's differences from the rest of the community without any need.
 
Top