[Oberon] FPGA - RISC multiply/divide

[Tomas Kral]

Hi,

This example of binary multiply needs >>>fixed size font<<< to display
properly.

[a] Shift & addition

   0101    =5(4+1)
   0101 x  =5(4+1)
_________

   0101    
  0000     shift
 0101      shift
_________
           add above
 011001    =25(16+8+1)


[b] Repeated addition, 5+5+5+5+5

   0101
   0101  
   0101
   0101  
   0101
__________

 011001    =25(16+8+1)


To multiply 32 bit integers upto 32 cycles are needed. There is some
FPGA magic used, to complete each `MUL'tiply in two cycles only.

How many cycles does `DIV'require?
Looking for the above analogy.

Tomas  


On Tue, 23 May 2017 12:36:04 +0200
Tomas Kral <thomas.kral at email.cz> wrote:

> Hi Joerg,
> 
> Multiplication ~ repeated addition
> Division ~ repeated subtraction
> 
> That is a simplification but is not the way implemented in RISC.
> Consider 65536 DIV 1, that would require 65536 iterations.
> 
> Instead shift (left | right) + (add | sub) is used for DIV and MUL.
> This requires much fewer iterations.
> 
> My argument is right about the example given in the 16.2.3.
> 
> 14 DIV 4, is 3 with remainder 2
> 
> But the example gives 4 and the remainder 2
> 
> Tomas
> 
> 
> On Tue, 23 May 2017 11:23:14 +0200
> Jörg <joerg.straube at iaeth.ch> wrote:
> 
> > Tomas
> > 
> > http://www.homeschoolmath.net/teaching/md/division-repeated-subtraction.php
> > 
> > Jörg
> > 
> > > Am 23.05.2017 um 11:09 schrieb Tomas Kral <thomas.kral at email.cz>:
> > > 
> > > Hi,
> > > 
> > > I am reading chapters on RISC implementation. I managed to
> > > understand multiplication - `MUL' instruction, consisting of
> > > shifting x and adding y to the product.
> > > 
> > > I seem not understanding the division, chapter 16.2.3.
> > > In the example for x=14, y=4 gives quotient q=4, and the remainder
> > > r=2.
> > > 
> > > But...
> > > q = x DIV y = 3, r = x MOD y = 2
> > > ???
> > > 
> > > -- 
> > > Tomas Kral <thomas.kral at email.cz>
> > > --
> > > Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related
> > > systems https://lists.inf.ethz.ch/mailman/listinfo/oberon
> 
> 
> 



-- 
Tomas Kral <thomas.kral at email.cz>