Struggling with a simple method for doing digital division (beginner)

Copper · 2012-06-26 20:16

Disclaimer: I have had zero formal programming education, and only recently began experimenting with it myself. I decided to go with the propeller based on a friends recommendation. Generally, I've enjoyed the experience, but I have struggled with a few basic concepts, and suspect I may have run into another.

Basically I'm looking for some help with a simple approach to doing digital division. What I have thus far is largely based on Wikipedia's "digital division" article.

I think I've identified two problems with my code. First: I haven't really nailed down how to deal with the quotient; I figured I'd solve my first problem second as my second problem is considerably more confounding. Second: my 'If statement" seems to be running when it shouldn't...

[B]CON[/B]


_CLKMODE = XTAL1 + PLL16X
_XINFREQ = 5_000_000


D=16
N=4
  
[B]OBJ[/B]

pst   : "Parallax Serial Terminal"

[B]DAT[/B]

Q long 0
R long 0


[B]PUB main | i[/B]                    'Divide "D"(dividend) by "N"(numerator) and report "Q"(quotient) and "R"(remainder)


pst.start(57600)
waitcnt(clkfreq*5+cnt)


pst.Str(String(13, " ***inputs*** "))
pst.Str(String(13, " D    == "))
pst.bin(D, 32)
pst.Str(String(13, " N    == "))
pst.bin(N, 32)
pst.Str(String(13, " Q    == "))
pst.bin(Q, 32)
pst.Str(String(13, " R    == "))
pst.bin(R, 32)
pst.Newline
pst.Str(String(13, " ***Begin*** "))
    
if N==0
   pst.Str(String(13, " Q = UNDEFINED  "))
   abort
      
repeat i from 31 to 0
   pst.Newline
   pst.Newline
   pst.Str(String(13, " i = "))
   pst.Dec(i)
            
   Values
      
   R<<=1
   R|=((D and (1<<i))>>i)
   if R>=D
      pst.Str(String(13, " R>=D "))
      R-=D
      Q|=(1<<i)
        
[B]PUB Values[/B]                                       'Display all Variables and their Values


pst.Str(String(13, "                 ***Values*** "))
pst.Str(String(13, " D    == "))
pst.bin(D, 32)
pst.Str(String(13, " N    == "))
pst.bin(N, 32)
pst.Str(String(13, " Q    == "))
pst.bin(Q, 32)
pst.Str(String(13, " R    == "))
pst.bin(R, 32)
pst.Newline
pst.Newline

Things seem to work as expected until the 5th run through the loop, or when i=27

$03_fraction_SCRNSHT.PNG$

So I suppose I'm looking for any help or suggestions anyone has to offer; on this code; learning to code; troubleshooting code; posting on the forums; life.

Thanks for your time.

ElectricAye · 2012-06-26 22:42

I'm sorry I'm not much help (I know next to nothing about running operations with binary) but I just wanted to check that you are performing the type of functions you really want to be performing. For example, when you say, "Divide "D"(dividend) by "N"(numerator)", I'm wondering if that should read "Divide "N"(numerator) by "D"(divisor)" since the numerator is usually on the "top" of a fraction and the divisor is what's "on the bottom".

pik33 · 2012-06-26 23:18

This is Spin. This is strange

if R>=D

should be

if R=>D

Copper · 2012-06-27 08:12

ElectricAye wrote: »

I'm sorry I'm not much help (I know next to nothing about running operations with binary) but I just wanted to check that you are performing the type of functions you really want to be performing. For example, when you say, "Divide "D"(dividend) by "N"(numerator)", I'm wondering if that should read "Divide "N"(numerator) by "D"(divisor)" since the numerator is usually on the "top" of a fraction and the divisor is what's "on the bottom".

Good catch. I switched my variable names several times (dividend, divisor, denominator, numerator) depending on which resource I was looking at; guess I got carried away. I'll be sure to sort that out when next I have some time to look at it; but I was in fact attempting to divide D by N, even were it written backwards, I don't think it should be going through the if statement until "i" equals the position of the first 1 in "D"

Copper · 2012-06-27 17:55

Just an update:
pik33 was right about the "if R is equal or greater operator."
Unfortunately, I seem to be in even more trouble than I thought I was.
I went through and commented everything to help highlight any foolish errors I may have made.

CON

  _CLKMODE = XTAL1 + PLL16X         'set clock mode
  _XINFREQ = 5_000_000              'crystal freq


  N=16  'numerator
  D=4   'divisor
  
OBJ


  pst           : "Parallax Serial Terminal"


DAT


        Q long 0         'quotient
        R long 0         'remainder


PUB main | i                       'Divide "N"(numerator) by "D"(divisor) and report "Q"(quotient) and "R"(remainder)


    pst.start(57600)                              'start "pst"
    waitcnt(clkfreq*5+cnt)                        'wait 5 sec


    Values                                        'Display input values
    
    pst.Str(String(13, " ***Begin*** "))          'Indicate begining of calculation
    
    if D==0                                       'if D is 0
      pst.Str(String(13, " Q = UNDEFINED  "))     'report Q as "UNDEFINED"
      abort                                       'end program
      
    repeat i from 31 to 0                    'to address all 32 bits
    
      pst.Newline                                 'pst.newline           ''I don't think I can write this into its 
      pst.Newline                                 'pst.newline           ''own method because i is a local variable
      pst.Str(String(13, " i = "))                                       ''
      pst.Dec(i)                                  'Display value in i    ''
                                                  
      Values                                      'display values
      
      R<<=1                                       'Set R to R shift left 1 time
      R|=((N and (1<<i))>>i)                      'Set R to R OR ((N AND ("1" shift left i times)) shift right i times)


      if R=>N                                     'if R is equal to or greater than N
        pst.Str(String(13, " R>=D "))             'indicate R is equal to or greater than D
        R-=N                                      'Set R to R - N
        Q|=(1<<i)
        




PUB Values                                       'Display all Variables and their Values


    pst.Str(String(13, "                 ***Values*** "))
    pst.Str(String(13, " N    == "))
    pst.bin(N, 32)
    pst.Str(String(13, " D    == "))
    pst.bin(D, 32)
    pst.Str(String(13, " Q    == "))
    pst.bin(Q, 32)
    pst.Str(String(13, " R    == "))
    pst.bin(R, 32)
    pst.Newline
    pst.Newline

Now I'm running into trouble in the second loop ( i = 30 ).
R should remain 0 until loop 28 when it should be set to 1, then shifted left as the remaining bits are examined until R is greater than or equal to N

$04_fraction_SCRNSHT.PNG$

Any suggestions would be much appreciated.

kuroneko · 2012-06-27 18:06

The and operator you're using ATM is a logical AND which propagates any non-zero operand to TRUE (-1) and goes from there. Context suggests that you want a bitwise AND which is & (ampersand).

TrapperBob · 2012-06-28 11:40

You do want to use the & in place of AND for the reason kuroneko mentions above. You also need to change the section of code below:

if R=>N                                        'if R is equal to or greater than N       
   pst.Str(String(13, " R>=D "))               'indicate R is equal to or greater than D        
   R-=N                                        'Set R to R - N       
   Q|=(1<<i)

to:

 if R=>D                                       'if R is equal to or greater than D        
    pst.Str(String(13, " R>=D "))              'indicate R is equal to or greater than D        
    R-=D                                       'Set R to R - D         
    Q|=(1<<i)

TrapperBob · 2012-06-28 12:48

One more thing. You want to move your call of Values to the end after you have checked the remainder against the divisor.

 repeat i from 31 to 0                    'to address all 32 bits
    
      pst.Newline                                 'pst.newline           ''I don't think I can write this into its 
      pst.Newline                                 'pst.newline           ''own method because i is a local variable
      pst.Str(String(13, " i = "))                                       ''
      pst.Dec(i)                                  'Display value in i    
     
      R <<=  1                                    'Set R to R shift left 1 time
      R|=((N & (1<<i))>>i)                        'Set R to R OR ((N AND ("1" shift left i times)) shift right i times)

      if R=>D                                     'if R is equal to or greater than D
         pst.Str(String(13, " R>=D "))            'indicate R is equal to or greater than D
         R-=D                                     'Set R to R - D 
         Q|=(1<<i)
       
      Values

Mark_T · 2012-06-28 16:28

ElectricAye wrote: »

I'm sorry I'm not much help (I know next to nothing about running operations with binary) but I just wanted to check that you are performing the type of functions you really want to be performing. For example, when you say, "Divide "D"(dividend) by "N"(numerator)", I'm wondering if that should read "Divide "N"(numerator) by "D"(divisor)" since the numerator is usually on the "top" of a fraction and the divisor is what's "on the bottom".

Not quite - for division: quotient = dividend / divisor. (Or for integer division: divisor * quotient + remainder = dividend, where the 0 <= remainder < |divisor| )

When talking of a fraction (as a number, not as a calculation) then its numerator / denominator

Andrew E Mileski · 2012-06-28 17:19

Of course you can just use the / operator in SPIN for signed division, but here are the mechanics of division:

        'Unsigned division of two 32 bit numbers
        remainder := 0
        repeat 32
                '64 bit dividend (remainder_dividend) multiplied by 2
                carry_out := dividend >> 31
                dividend += dividend
                remainder += remainder + carry_out

                if (divisor >= remainder)
                        remainder -= divisor
                        dividend |= 1
        quotient = dividend

        'Signed division of two 32 bit numbers
        dividend <<= 1
        repeat 32
                quotient <<= 1
                dividend -= divisor
                if (dividend >= 0)
                        quotient |= 1
                else
                        dividend += divisor

                'Divide the divisor by 2 (arithmetic shift right)
                sign := divisor & (1 << 31)
                divisor >>= 1
                divisor |= sign
        remainder = dividend

Tymkrs · 2012-06-28 17:36

Hi! First, wanted to point you in the direction of First Spin - it's a podcast where I go through the Propeller/Spin from a noobie's perspective, ask questions, get answers etc (for future reference). We did cover some binary math in this one: http://www.firstspin.tv/2012/04/10/first-spin-episode-020/

And a personal post about binary math/bit shifting/dividing: http://tymkrs.tumblr.com/post/19346713047/xbee-led-buzzer-code-analysis-part-5

Beau Schwabe · 2012-06-28 22:08

Copper,

I couldn't get Wikipedia's "digital division" method to work quite right... based on your original code, in the code section below there is a method implementing a longhand binary division technique that can be found here...

http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

...depending on the size of the divisor and the size of the dividend, the number of itterations will vary to solve the quotent, but will never be more than 31 itterations.

CON

  _CLKMODE = XTAL1 + PLL16X         'set clock mode
  _XINFREQ = 5_000_000              'crystal freq


OBJ


  pst           : "Parallax Serial Terminal"

VAR
long    DdA,DsA,i  


DAT
        Dd long %00000000_01000000_10000000_00010111    'dividend
        Ds long %00000000_00000000_00000000_00000100    'divisor

        Q  long 0       'quotient
        R  long 0       'remainder


PUB main                       'Divide "Dd"(dividend) by "Ds"(divisor) and report "Q"(quotient) and "R"(remainder)


    pst.start(19200)                              'start "pst"
    waitcnt(clkfreq*5+cnt)                        'wait 5 sec


    Values                                        'Display input values
    
    pst.Str(String(13, " ***Begin*** "))          'Indicate begining of calculation
    
    if Dd==0                                      'if Dd is 0
      pst.Str(String(13, " Q = UNDEFINED  "))     'report Q as "UNDEFINED"
      abort                                       'end program

'Long hand binary division routine:
'--------------------------------------------------------------------------
    i   := 0                    ''Clear i
    Q   := 0                    'Clear quotient 
    DsA := >|Ds                 'Get MSB position of divisor
    DdA := >|Dd                 'Get MSB position of dividend
    Dd  ->= DdA-DsA             'Align left most digits in dividend with divisor
    R   := Dd & (|<DsA-1)       'initialize the remainder (Note: remainder also serves as
                                '  the 'compared' portion of the dividend 
    repeat DdA-DsA+1            'Only process the bit difference between the dividend and divisor
      i++                       ''increment i
      Q<<=1                     'Shift quotient left by one  
      if R => Ds                'OR a "1" into quotient if the aligned dividend
        Q|=1                    '  is equal or greater than the divisor
        R := R-Ds               'calculate the next remainder
      Values                    ''display values
      Dd<-= 1                   'rotate dividend left by one
      R := R<<1|Dd&1            'shift remainder left and OR next dividend bit
'--------------------------------------------------------------------------      

PUB Values                                       'Display all Variables and their Values
    pst.Newline
    pst.Newline
    pst.str(String(13," i = "))
    pst.dec(i)
    pst.Str(String(13, "                 ***Values*** "))
    pst.Str(String(13, " Dd   == "))
    pst.bin(Dd, 32)
    pst.char(9)
    pst.dec(Dd)
    pst.Str(String(13, " Ds   == "))
    pst.bin(Ds, 32)
    pst.char(9)
    pst.dec(Ds)
    pst.Str(String(13, " Q    == "))
    pst.bin(Q, 32)
    pst.char(9)
    pst.dec(Q)
    pst.Str(String(13, " R    == "))
    pst.bin(R, 32)
    pst.char(9)
    pst.dec(R)

Copper · 2012-06-29 14:08

I just wanted to say thanks for all the responses to what I presumed would be an UN-interesting thread. I really appreciate the help. This has been a terribly busy week for me and I've had little time to absorb everything here; but I wanted to make sure you all knew how much more pleasant you have made this experience for me.
and again, Thank you for your time.

Struggling with a simple method for doing digital division (beginner)

Comments