Searching \ for '10 bit maths' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/method/math.htm?key=math
Search entire site for: '10 bit maths'.

Truncated match.
PICList Thread
'10 bit maths'
1996\11\01@055440 by Andy David

flavicon
face
Guys,


What's the fastest way to square a 10-bit number?




- Andy.

*************************************************************
Andrew David               Senior Project Engineer - Software

Ultronics Division         spam_OUTAndyTakeThisOuTspamUltronics.co.uk
Ultra Hydraulics Ltd.
Anson Business Park
Cheltenham Road East
Staverton
Glos. GL2 9QN

Tel.: (01452) 858376 (Direct)  Ultronics Fax.: (01452) 858377
*************************************************************

1996\11\01@130101 by Chuck McManis

flavicon
face
> What's the fastest way to square a 10-bit number?

Look it up in a table. Given a 20 bit result, 10 bits is 1024
possible answers, a 32K bit eprom (2732) could hold the
result.

Actually squaring the number in PIC assembly, no idea. :-)
--Chuck

1996\11\04@031818 by Stuart Taylor

flavicon
face
Hi

>
> > What's the fastest way to square a 10-bit number?
>

Try looking in the applications handbook, the maths routines include
8 and 16 bit multiplies. Use the 16 bit one but limit the first byte to
a 2 bit multiply.

Stuart Taylor

1996\11\04@040504 by fastfwd

face
flavicon
face
Stuart Taylor <.....PICLISTKILLspamspam@spam@MITVMA.MIT.EDU> wrote:

> > > What's the fastest way to square a 10-bit number?
>
> Try looking in the applications handbook, the maths routines include
> 8 and 16 bit multiplies. Use the 16 bit one but limit the first byte
> to a 2 bit multiply.

Yeah, but those routines are really slow... For a specialized case
like this, a better choice (barring some clever squaring algorithm of
which I'm unaware) would be one of the following.  Note that I've
only worked these out for 4-bit numbers; the 10-bit equivalents will
be a lot messier, but these examples'll give you the idea:

SOLUTION 1 -- Real fast for 4-bit numbers, probably slower than
solution #2 for 10-bit numbers:

   ; Enter with 4-bit number to be squared in register "X".
   ; Exits with X*X in the W register.

   movlw 0
   clrc

   btfsc x,0
   addwf x,w

   rlf x
   btfsc x,2
   addwf x,w

   rlf x
   btfsc x,4
   addwf x,w

   rlf x
   btfsc x,6
   addwf x,w

SOLUTION #2:  Slower than #1 for 4-bit numbers, but with
sufficiently-good ordering of instructions, could be pretty fast for
10-bit numbers:

   BASIC version first, showing the results of squaring all
   possible 4-bit numbers:

   for a = 0 to 1
   for b = 0 to 1
   for c = 0 to 1
   for d = 0 to 1

   n = a*8 + b*4 + c*2 + d

   w = 0
   x = 0
   y = 0
   z = 0

   if d then z = a*16 + b*8 + c*4 + 1
   if c then y = a * 32 + b*16 + 4
   if b then x = a*64 + 16
   if a then w = 64

   r = w+x+y+z
   s = n*n

   print n,s,r,: if s <> r then print "Error" else print "OK"

   next:next:next:next


   Now the PIC version:

   ; Enter with number to be squared in X.
   ; Exits with X*X in the W-register.

       btfss x,0
       goto doc

       clrc
       rlf x,w
       addlw -1

   doc:
       btfss x,1
       goto dob

       btfsc x,3
       addlw 32

       btfsc x,2
       addlw 16

   dob:
       btfss x,2
       goto doa

       btfsc x,3
       addlw 64
       addlw 16

   doa:
       btfsc x,3
       addlw 64

Personally, I'd go with Solution #1... As I was working out the
assembly code for Solution #2, it was quickly becoming unmanageable
even for only 4 bits.

-Andy

Andrew Warren - fastfwdspamKILLspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\11\04@043859 by Keith Dowsett
flavicon
face
>Guys,
>
>
>What's the fastest way to square a 10-bit number?
>
>
Is there scope to break it down into three simpler multiplications?

(a+b)^2 = a^2 + b^2 + 2ab

This gives one two bit multiply (trivial) one 2 bit x 8 bit multiply
(straightforward) and one eight bit multiply (conventional but still a bit slow)

If you are subsequently re-scaling the result to fit in 16-bits you can save
a couple of cycles on the eight bit multiply too.

Keith.

==========================================================
Keith Dowsett         "Variables won't; constants aren't."

E-mail: .....kdowsettKILLspamspam.....rpms.ac.uk
WWW:    http://kd.rpms.ac.uk/index.html

1996\11\04@100333 by Andy David

flavicon
face
Stuart Taylor suggested...
>
> > > > What's the fastest way to square a 10-bit number?
> >
> > Try looking in the applications handbook, the maths routines include
> > 8 and 16 bit multiplies. Use the 16 bit one but limit the first byte to
> > a 2 bit multiply.

Thanks, Stuart.
The apps handbook is always a good place to start, but those routines
are way too slow.
I was thinking that a 10 bit by 10 bit multiply is faster than a
16 by 16, and there might be a more efficient algorithm for squaring
than multiplying... I'm a little short of general reference material
maybe I'll ask my wife for some of Knuth's book for Christmas...


Keith Dowsett offered...
{Quote hidden}

Thanks Keith.
I hadn't thought about this type of appproach, but I expect that taking
the calculation 'head on' will be quicker. Time permitting I'll compare
this
approach to below and let you know how it works out.


Andrew Warren worked out...
>
> SOLUTION 1 -- Real fast for 4-bit numbers, probably slower than
> solution #2 for 10-bit numbers:
>
...[snip some lines of code]...
>
> SOLUTION #2:  Slower than #1 for 4-bit numbers, but with
> sufficiently-good ordering of instructions, could be pretty fast for
> 10-bit numbers:
>
...[snip a few more lines of code]...
>
> Personally, I'd go with Solution #1...

thanks, Andy, that's very helpful. I'll complete these for 10-bits and
if anyone is interested I'll post the code. As usual I've been sidetracked
today so it might be a day or 2.


For things like this, what reference material would you suggest?


- Andy.

*************************************************************
Andrew David               Senior Project Engineer - Software

Ultronics Division         EraseMEAndyspam_OUTspamTakeThisOuTUltronics.co.uk
Ultra Hydraulics Ltd.
Anson Business Park
Cheltenham Road East
Staverton
Glos. GL2 9QN

Tel.: (01452) 858376 (Direct)  Ultronics Fax.: (01452) 858377
*************************************************************

1996\11\04@134244 by Scott Dattalo

face
flavicon
face
Keith Dowsett wrote:
>
> >Guys,
> >
> >
> >What's the fastest way to square a 10-bit number?
> >
> >
> Is there scope to break it down into three simpler multiplications?
>
> (a+b)^2 = a^2 + b^2 + 2ab
>

Precisely what I was thinking. However, let me expand upon a
couple different branches.


Branch 1.

Suppose you divide the number you wish to square in half, that
is into 5 most significant bits and 5 lsb's:

N = a*32 + b

a = 5 msb's
b = 5 lsb's

Now using Keith's observation:

N^2 = 32^2 * a^2 + 64*a*b + b^2

    =  (a^2)<<10 + (a*b)<<5 + b^2

And the 10-bit multiplication has been broken down into
three 5-bit multiplications. However, with a little work
the 5-bit squares may be evaluated via a table-look-up.
This would leave you with one general purpose 5-bit
multiplication.


Branch 2.

Suppose you divide the number into three nibbles. The most
significant nibble would only be 2 bits wide.

 N = a*256 + b*16 + c
N^2 = (a*256)^2 + (b*16)^2 + c^2 +
      2*(a*256*b*16 + a*256*c + b*16*c)
    = (a^2)<<16 + (b^2)<<8 + c^2 +
      ((a*b)<<12 + (a*c)<<8 + b*c<<4))<<1

Squaring the nibbles can be done trivially with a look up
table. The other three 4X4 bit multiplications can be
quickly computed with Andy W's 13 instruction suggestion.

If you wish to take advantage of 'a' being only 2-bits
wide, then investigate

N^2 = (a^2)<<16 + (b^2)<<8 + c^2 +
      ((a*(b*16 + c)<<8 + b*c<<4))<<1

This reduces to: 3 table look-ups, one 4X4 bit multiplication
and one 2X8 bit multiplication. My guess is that this could
be coded to execute in less than 60 cycles.


Scott

P.S. Have you considered running the square root routine
backwards? :)

1996\11\04@134451 by fastfwd

face
flavicon
face
Keith Dowsett <PICLISTspamspam_OUTMITVMA.MIT.EDU> wrote:

> > What's the fastest way to square a 10-bit number?
>
> Is there scope to break it down into three simpler multiplications?
>
> (a+b)^2 = a^2 + b^2 + 2ab
>
> This gives one two bit multiply (trivial) one 2 bit x 8 bit multiply
> (straightforward) and one eight bit multiply (conventional but still
> a bit slow)

Keith:

Have you coded this into PIC assembly language?  I have a feeling
that, in practice, it'll be slower than a standard 10-bit x 10-bit
multiplication.

-Andy

=== Andrew Warren - @spam@fastfwdKILLspamspamix.netcom.com                 ===
=== Fast Forward Engineering - Vista, California          ===
===                                                       ===
=== Custodian of the PICLIST Fund -- For more info, see:  ===
=== http://www.geocities.com/SiliconValley/2499/fund.html ===

1996\11\04@142417 by fastfwd

face
flavicon
face
Andy David <KILLspamPICLISTKILLspamspamMITVMA.MIT.EDU> wrote:

> The apps handbook is always a good place to start, but those
> routines are way too slow. I was thinking that a 10 bit by 10 bit
> multiply is faster than a 16 by 16, and there might be a more
> efficient algorithm for squaring than multiplying... I'm a little
> short of general reference material maybe I'll ask my wife for some
> of Knuth's book for Christmas...
> ....
> For things like this, what reference material would you suggest?

Andy:

A 10x10 multiply IS faster than 16x16, mostly because the result is
guaranteed to fit in three bytes rather than 4.  If you don't have
the code space to unroll the whole multiplication into inline code
(as I showed in my "Solution #1"), looped code can still be made
pretty fast by writing three loops:

   One for the first few bits of the multiplier, where the result
   of each addition of the multiplicand to the intermediate result
   is guaranteed to fit in the least-significant two bytes,

   one for the next group of bits, where the addition may affect
   all three bytes of the result, and

   one for the final few bits, where the addition is guaranteed to
   only affect the two most-significant bytes of the result.

As for reference books... I don't know; I looked through Knuth and a
couple of other books, but didn't find any really fast squaring
algorithms.

As usual, though, I'll probably discover a month from now, while
investigating some other problem, that Knuth's book DOES have a good
squaring algorithm.

-Andy

P.S.  By the way, the "Solution #1" algorithm I posted earlier is
very similar to Keith Dowsett's suggestion; I just took it a little
farther and (for 4-bit numbers) factored the problem into:

   (a + b + c + d)^2
   = a^2 + b^2 + c^2 + d^2 + 2ab + 2ac + 2ad + 2bc + 2bd + 2cd.

This removes ALL multiplications from the algorithm; each term just
reduces to either "0" or a single bit.

=== Andrew Warren - RemoveMEfastfwdTakeThisOuTspamix.netcom.com                 ===
=== Fast Forward Engineering - Vista, California          ===
===                                                       ===
=== Custodian of the PICLIST Fund -- For more info, see:  ===
=== http://www.geocities.com/SiliconValley/2499/fund.html ===

1996\11\05@063301 by Andy David

flavicon
face
> Keith Dowsett wrote:
> >
> > >
> > Is there scope to break it down into three simpler multiplications?
> >
> > (a+b)^2 = a^2 + b^2 + 2ab
> >
>
Scott Dattalo wrote:

> Precisely what I was thinking. However, let me expand upon a
> couple different branches.
>

hmmmm ...methinks I need an intuition implant...
my gut feel was that something like Andy W's "straight line"
solution would be a bit quicker than a few smaller calculations
whose results are combined. My gut feel isn't the most reliable
indication of anything, though :-) I'm working on improving it.

Thanks to Keith, Andy and Scott for excellent suggestions
and examples... looks like I've got a few routines to
write! If I'm brave enough, I'll post the fastest one I can
come up with this week.


- Andy.

*************************************************************
Andrew David               Senior Project Engineer - Software

Ultronics Division         spamBeGoneAndyspamBeGonespamUltronics.co.uk
Ultra Hydraulics Ltd.
Anson Business Park
Cheltenham Road East
Staverton
Glos. GL2 9QN

Tel.: (01452) 858376 (Direct)  Ultronics Fax.: (01452) 858377
*************************************************************

1996\11\05@111351 by John Payson

picon face
> > > Is there scope to break it down into three simpler multiplications?
> > >
> > > (a+b)^2 = a^2 + b^2 + 2ab

> hmmmm ...methinks I need an intuition implant...
> my gut feel was that something like Andy W's "straight line"
> solution would be a bit quicker than a few smaller calculations
> whose results are combined. My gut feel isn't the most reliable
> indication of anything, though :-) I'm working on improving it.
>
> Thanks to Keith, Andy and Scott for excellent suggestions
> and examples... looks like I've got a few routines to
> write! If I'm brave enough, I'll post the fastest one I can
> come up with this week.

Something like this? [warning: untested]

       clrf    DstH
       clrf    DstM
       clrf    DstL
       movf    SrcL,w
       andlw   $0F
       btfss   Src,4
        addwf  DstM
       rrf     DstM
       rrf     DstL
       btfss   Src,5
        addwf  DstM
       rrf     DstM
       rrf     DstL
       btfss   Src,6
        addwf  DstM
       rrf     DstM
       rrf     DstL
       btfss   Src,7
        addwf  DstM
       call    Sqr4
       addwf   DstL
       swapf   SrcL
       andlw   $0F
       call    Sqr4
       addwf   DstM
                       ; At this point, 16-bit result is in DstM:DstH
                       ; 25 words of code prior to this point (plus a
                       ; 17-word table-lookup).  Total execution time:
                       ; 35 cycles up to this point.
       btfss   SrcH,0
        goto   NoBit8
       movf    SrcL,w
       btfsc   C
        incf   DstH
       addwf   DstM
       btfsc   C
        incf   DstH
       incf    DstH
                       ; Another 9 words for bit 8; 3 or 9 cycles to exec.
NoBit8:
       btfss   SrcH,1
        goto   NoBit9
       movlw   4
       btfss   SrcH,0
        movlw  8
       addwf   DstH
       rlf     SrcL,w
       btfsc   C
        incf   DstH
       btfsc   C
        incf   DstH
       addwf   DstM
       btfsc   C
        incf   DstH
       addwf   DstM
       btfsc   C
        incf   DstH
                       ; Another 17 words for bit 9; 3 or 17 cycles to execute
                       ; Total worst-case time: 35+26 = 61 cycles.
NoBit9:
       retlw   0       ; All done!
Sqr4:
       addwf   PC
       db      0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225

1996\11\05@152500 by Matthew Mucker

flavicon
face
>> > What's the fastest way to square a 10-bit number?
>
>Try looking in the applications handbook, the maths routines include
>8 and 16 bit multiplies. Use the 16 bit one but limit the first byte to
>a 2 bit multiply.
>
>Stuart Taylor

What is this "applications handbook?"  Could you please elaborate a little
more about whait it is, what's in it, and where to get it?

Thanks,

       -Matt


 "DOS Computers manufactured by companies such as IBM, Compaq, Tandy, and
millions of others are by far the most popular, with about 70 million
machines in use wordwide. Macintosh fans, on the other hand, may note that
cockroaches are far more numerous than humans, and that numbers alone do
not denote a higher life form."

More... (looser matching)
- Last day of these posts
- In 1996 , 1997 only
- Today
- New search...