OT: PIC16 divide and/or multiply routines

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
..that WORK.
   Any references, please?

Re: OT: PIC16 divide and/or multiply routines
On Saturday, 31 October 2015 16:40:51 UTC+11, Robert Baer  wrote:
Quoted text here. Click to load it

Can't you write your own? I did it for a PDP-8 back in 1968, and don't reca
ll it being all that difficult.

Once you've tried to do it, you'll probably have learned enough to work why
 whatever it is you are complaining about didn't work.

Shift and add/subtract routines do work, but you do have to pay attention t
o the usual gottcha's - the one I put together a EMI Central research start
ed off doing an extra add when it shouldn't have, which wasn't to hard to f
ind or fix, but embarrassing all the same.

The much faster variation we put together in ECL at Cambridge Instruments a
 decade later had the nasty habit of stuffing leading zeros into downshifte
d numbers even when they were negative (when it should have stuffed them wi
th leading ones). Easy enough to fix, and the sub-contractor who'd made the
 error was long gone by the time we'd got the hardware to the point of work
ing almost correctly - doing enough arithmetic for us to see that it was so
metimes doing it wrong.  

--  
Bill Sloman, Sydney

Re: OT: PIC16 divide and/or multiply routines
On 31/10/2015 06:40, Robert Baer wrote:

Quoted text here. Click to load it

There are samples all over the place. But you have to specify what you  
want to do rather more clearly. The algorithm is pretty simple and I  
thought the support pages included reasonable sample code.

Can't say I have ever tested any since I nearly always can scale things  
so that divisions are by 2^N and fixed multiplies done by lookup table.

--  
Regards,
Martin Brown

Re: OT: PIC16 divide and/or multiply routines
Martin Brown wrote:
Quoted text here. Click to load it
* I have not found any "support pages" on this topic, am lucky that  
there is an add and a rotate (no shift) to use.
   A basic divide or a basic multiply is simple, but instead of wasting  
time to create both for code space comparison (eg: could multiply by  
multiplicative inverse in place of divide), working listings should  
allow that comparison.

Quoted text here. Click to load it
* Hmm.. that is a thought...instead of directly summing up to 5 values  
for divide, i could normalize (divide by 2 via rotate) after summing two  
each time.
   Sounds the code would be more compact and be faster..

   Thanks!


Re: OT: PIC16 divide and/or multiply routines
On 31/10/2015 20:20, Robert Baer wrote:
Quoted text here. Click to load it

First hit from google for microchip pic multiply

http://www.piclist.com/techref/microchip/math/mul/index.htm
http://www.piclist.com/techref/microchip/math/mul/tutorial.htm

The two I looked at looked basically sound.

Quoted text here. Click to load it


There are also shift and add tricks to do multiplies by smaller  
constants - you often see modern compliers generating load effective  
address as a way of multiplying by 2,4,8 and adding an offset fast.

--  
Regards,
Martin Brown

Re: OT: PIC16 divide and/or multiply routines
On 10/31/2015 2:40 AM, Robert Baer wrote:
Quoted text here. Click to load it

Do you want code-size optimized or speed optimized?

Surely Microchip has some documentation somewhere?

Re: OT: PIC16 divide and/or multiply routines
bitrex wrote:
Quoted text here. Click to load it
   Code size first, speed second.
   And how do i go about finding unknown-named documents that contain  
_relevant_ info concerning divide and/or multiply?

   I like the idea that Martin Brown hinted at (scale things so that  
divisions are by 2^N).
   Direct divide by five done by divide by 2 (rotate), accumulate next  
one, divide by 2, etc four times.


Re: OT: PIC16 divide and/or multiply routines
Quoted text here. Click to load it

It's just long division, they presumably taught you that in primary
school.  the only novelty is you get to do it in binary instead of
base 10. This makes the multiplication table short enough to hard-code
but increases the number of steps needed.

Quoted text here. Click to load it

yeah if it's a fixed divisor you can exploit reciprocals.

--  
  \_(?)_

Re: OT: PIC16 divide and/or multiply routines
On Saturday, October 31, 2015 at 1:03:43 PM UTC-7, Jasen Betts wrote:

[about PIC arithmetic algorithms]

Quoted text here. Click to load it

Better schemes for computation are available; instead of long division,
you multiply (with your fast  multiply routine) both numerator and denominator
by successively near-one numbers, and when the denominator is exactly 1,
the division is complete.   If you start with a tabulated best-guess for
the denominator's most significant bits,  use the approximation
1/(1-x)  ~=  1+ x
and the error drops very fast.    The old Pentium divide bug (if anyone
remembers) was due to a faulty transcription of the table for this kind of algorithm.

As for multiplication, a table of squares for five-bit numbers only has 32 elements.

(a + b) ^2 - (a - b) ^2  = 4 *  a * b

so some addition and a table of squares is a better approach than a one-bit
multiplication table; it takes more steps, but gets more bits per step.
A four-bit multiplication table has (ignoring operand order) 136 entries, isn't
as efficient.

Re: OT: PIC16 divide and/or multiply routines
On 10/31/2015 4:28 PM, Robert Baer wrote:
Quoted text here. Click to load it

You could take a look at this document for AVR uCs without hardware  
multiply and adapt the algorithms to the PIC ISA, probably.

http://www.atmel.com/Images/doc0936.pdf

Re: OT: PIC16 divide and/or multiply routines
On Fri, 30 Oct 2015 22:40:45 -0800, Robert Baer

Quoted text here. Click to load it

Aren't the PIC machines barbaric by modern standards? I don't think
PIC16 has any multiply instructions.

ARMs have integer mul/div, and the expensive ones ($7) have vector
floating point and good C compilers.



Re: OT: PIC16 divide and/or multiply routines
John Larkin wrote:
Quoted text here. Click to load it
   The PIC16F648A has add and rotate so mul/div can be programmed.
   Long and messy for generic use - but divide by two on a 2-byte value  
is fast and short (via the rotate).
   So i am using that after every add of 2 normalized values to give me  
anew normalized value (and rounding is simple).


Re: PIC16 divide and/or multiply routines

Quoted text here. Click to load it

I implemented a computed true-RMS over an arbitrarily long period by  
squaring 8-bit ADC values (using the Z180 MLT instruction), and adding them  
to a 64 bit (8 byte) register, and a corresponding 32 bit time value (with  
1200 or 2400 samples/sec). Then (IIRC) I performed bit shifts until I got 16  
significant bits for the amplitude (squared) and 8 bits for the time, then  
took the square root to get a true RMS value.

Here are parts of the (Z180) code:

AddOnCurr::
    LD        A,(ABSADC)
    LD        B,A
    LD     C,B
    MLT    BC
    LD        HL,ONCURR
    CALL    ADDCUR                ;Add Current Squared into ONCURR
;  c    OnSamples++;
    LD        HL,OnSamples
    INC    (HL)                    ;LSB
    JR        NZ,AddOnCurr90
    INC    HL
    INC    (HL)                    ;2SB
    JR        NZ,AddOnCurr90
    INC    HL
    INC    (HL)                    ;3SB
    JR        NZ,AddOnCurr90
    INC    HL
    INC    (HL)                    ;MSB

AddOnCurr90:
    RET

;ADDCUR ADDS VALUE IN BC TO THE 64 BIT VALUE STARTING AT HL

ADDCUR::
    LD      A,4                ;MAXIMUM ITERATIONS

AC10:
    PUSH    HL                ;SAVE ADDRESS
     LD        E,(HL)
     INC    HL
     LD        D,(HL)            ;DE has MSB of old sum
     INC    HL
     EX        DE,HL            ;HL NOW HAS OLD SUM, POINTER IN DE
     OR        A                ;Reset Carry Flag
     ADC    HL,BC            ;ADD NEW ADC DATA IN HL, ADJ CARRY
     EX        DE,HL            ;DE HAS NEW VALUE
    POP        HL                ;RESTORE ORIGINAL POINTER
    LD        (HL),E            ;STORE NEW VALUE
    INC        HL
    LD        (HL),D
    INC        HL                ;HL NOW POINTS TO NEXT LOCATION
;    JR        Z,AC20            ;If result is zero
    JR        NC,ACX            ;Based on result of ADD HL,BC

AC20:
    DEC        A
    JR        Z,ACX            ;OVERFLOW

    LD        BC,1
    JR        AC10            ;ADD 1 TO NEXT WORD

ACX:
    RET

This is really old code, and some of it was replaced with floating point C,  
but it might help.

Paul  


Re: PIC16 divide and/or multiply routines
Here is some really old Z80/180 code from about 1994:

    SUBTTL  Arithmetic Routines
    PAGE
;
; DIVBW divides a word by a byte and returns a word quotient and a
;       byte remainder
;       Entry:  B = divisor
;               DE= dividend
;       Exit:   C = remainder
;               DE= quotient
;
DIVBW:  ld      a,b
    or      a               ;IF divisor > 0
    jr      nz,divb1        ;THEN continue
    ld      a,ecparm        ;ELSE post error
    or      a
    ret                     ;and return
divb1:  push    hl
    push    bc
    ex      de,hl
    ld      de,80H
    ld      c,0
divb2:  bit     7,b             ;IF msb(B) = 1
    jr      nz,divb4        ;THEN exit scale loop
    sla     b               ;ELSE scale
    srl     d
    rr      e
    jr      divb2           ;loop till scaling complete
divb4:  call    cphlbc
    ccf
    rl      e
    rl      d               ;shift quotient bit into DE
    rla                     ;save carry for loop test
    bit     0,e             ;IF bit =0
    jr      z,divb6         ;THEN skip
    or      a               ;ELSE clear carry
    sbc     hl,bc           ;and perform subtraction
divb6:  srl     b
    rr      c               ;BC = BC/2
    bit     0,a
    jr      z,divb4         ;loop till process complete
    pop     bc
    ld      c,l             ;remainder to c
    pop     hl
    xor     a
    ret
;
    PAGE
;
; DIVWW divides a double word (32 bits) by a word and returns a
;       double word result
;       Entry:  DEHL = dividend (31 bits maximum)
;                 BC = divisor  (15 bits maximum)
;       Exit:   DEHL = quotient (31 bits maximum)
;
divww:  ld      a,b
    or      c               ;IF divisor > 0
    jr      nz,divw1        ;THEN continue
    ld      a,ecparm        ;ELSE post error
    or      a
    ret                     ;and return
divw1:  push    ix
    push    bc
    ld      ix,0
    push    ix
    push    ix              ;Initialize quotient
    add     ix,sp           ;point IX to quotient
    ld      a,17            ;minimum number of loops
    ex      de,hl           ;high order word to hl
divw2:  bit     6,b             ;IF 2nd msb of divisor = 1
    jr      nz,divw4        ;THEN exit scale loop
    sla     c               ;ELSE scale
    rl      b
    inc     a               ;and increment loop counter
    jr      divw2
divw4:  call    cphlbc
    ccf
    rl      (ix+0)          ;shift result bit into quotient
    rl      (ix+1)
    rl      (ix+2)
    rl      (ix+3)
    bit     0,(ix+0)        ;IF bit was 0
    jr      z,divw6         ;THEN skip
    or      a
    sbc     hl,bc           ;ELSE perform subtraction
divw6:  sla     e               ;Quotient = Quotient * 2
    rl      d
    rl      l
    rl      h
    dec     a               ;IF loop counter > 0
    jr      nz,divw4        ;THEN continue to loop
    pop     hl
    pop     de
    pop     bc
    pop     ix              ;ELSE results to DEHL
    ret
;
    PAGE
;
; MPYBW multiplies a byte by a word and returns a 3-byte product
;       Entry:  B   = multiplier
;               DE  = multiplicand
;       Exit:  CDE  = product
;
MPYBW:  push    bc
    push    hl
    ld      hl,0
    ld      a,8
mpyb2:  srl     b               ;if LSB of multiplier = 0
    jr      nc,mpyb6        ;THEN skip
    add     hl,de           ;ELSE perform addition
mpyb6:  srl     h               ;shift product right
    rr      l
    rr      c
    dec     a
    jr      nz,mpyb2        ;loop till count = 0
    ld      e,c
    ld      d,l
    ld      a,h
    pop     hl
    pop     bc
    ld      c,a             ;MSB to C
    xor     a
    ret
;
    PAGE
;
;MPYWW multiplies a word by a word and returns a 4-byte product
;       Entry:  BC = multiplier
;               DE = multiplicand
;       Exit: BCDE = product
;
MPYWW:  push    hl
    ld      hl,0
    ld      a,16
mpyw2:  bit     0,c             ;IF lsb of multiplier = 0
    jr      z,mpyw6         ;THEN skip
    add     hl,de           ;ELSE perform addition
mpyw6:  srl     h               ;shift product right
    rr      l
    rr      b
    rr      c
    dec     a
    jr      nz,mpyw2        ;loop till count = 0
    ld      e,c
    ld      d,b
    ld      c,l
    ld      b,h
    pop     hl
    xor     a
    ret
;

Paul  

Re: OT: PIC16 divide and/or multiply routines
On 31/10/2015 20:21, John Larkin wrote:
Quoted text here. Click to load it

They were OK in their day but their day was around year 2000 or so.
If all you wanted was a few IO pins and a very cheap simple CPU.

The 16F877 could be used to do a very low current direct drive LCD  
display as it provided all the right pins in almost the right places.

Quoted text here. Click to load it

I can't help feeling that in this case it is the wrong tool for the job  
and something like one of the ARM development boards would ace it with a  
free toolset and full USB connectivity to a PC included for free.

http://www.mouser.com/ds/2/389/DM00163449-770672.pdf

I have an earlier relative of this board lying around somewhere.
1M flash, 128k ram, 128Mbit SPI flash & stereo audio DAC.

--  
Regards,
Martin Brown

Re: OT: PIC16 divide and/or multiply routines
On Monday, November 2, 2015 at 3:52:35 AM UTC-5, Martin Brown wrote:
Quoted text here. Click to load it
  
Quoted text here. Click to load it
  
Quoted text here. Click to load it

It is hard to justify using some of the cruder devices in the PIC line for  
new designs, but I expect this is not a new design.  Who wants to redesign  
a board and/or retest and possibly rewrite code for a new processor?  

If redesign is an option I would encourage looking at the MSP340 which is a
 very nice low power family as well.  But yes, it is hard to want to work w
ith anything other than an ARM these days.  They cover a wide range of capa
bility although working with an application processor is so much different  
than working with a CM0 that the common points seem pretty limited.  So I'm
 not clear why that is an advantage I suppose.  

Rick C.  

Re: OT: PIC16 divide and/or multiply routines
On Fri, 30 Oct 2015 22:40:45 -0800, Robert Baer

Quoted text here. Click to load it

Gee Rob, just look it up!

Microchip AN526

The piclist also has a bunch of stuff too.

Cheers

Re: PIC16 divide and/or multiply routines
"Martin Riddle"  wrote in message  

Quoted text here. Click to load it




Try this:
http://ww1.microchip.com/downloads/en/AppNotes/00544d.pdf

And this:
http://www.piclist.com/techref/microchip/math/basic.htm

You should ask these questions on the Microchip Forum:
http://www.microchip.com/forums/tm.aspx?m23%3373&mpage=1&

A fixed point library AN617:
http://ww1.microchip.com/downloads/en/AppNotes/00617.pdf
http://ww1.microchip.com/downloads/en/AppNotes/00617.zip

Paul  


Re: PIC16 divide and/or multiply routines
P E Schoen wrote:
Quoted text here. Click to load it
   Thanks for the references; now added on my HD for use.


Re: OT: PIC16 divide and/or multiply routines
Martin Riddle wrote:
Quoted text here. Click to load it
   Thanks for the AN reference. "Piclist"? what is that?
   In any case,using rotate for divide by 2 normalization each time  
after summing 2 normalized numbers takes very little code and is fast.


Site Timeline