Searching \ for '10 bit maths' in subject line. () 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.
'10 bit maths'
1996\11\01@055440 by  Guys,

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

- Andy.

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

Ultronics Division         Andy Ultronics.co.uk
Ultra Hydraulics Ltd.
Staverton
Glos. GL2 9QN

Tel.: (01452) 858376 (Direct)  Ultronics Fax.: (01452) 858377
*************************************************************  > 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  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   Stuart Taylor <PICLIST 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

rlf x
btfsc x,2

rlf x
btfsc x,4

rlf x
btfsc x,6

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

doc:
btfss x,1
goto dob

btfsc x,3

btfsc x,2

dob:
btfss x,2
goto doa

btfsc x,3

doa:
btfsc x,3

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 - fastfwd ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499  >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: kdowsett rpms.ac.uk
WWW:    http://kd.rpms.ac.uk/index.html  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.
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         Andy Ultronics.co.uk
Ultra Hydraulics Ltd.
Staverton
Glos. GL2 9QN

Tel.: (01452) 858376 (Direct)  Ultronics Fax.: (01452) 858377
*************************************************************   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? :)   Keith Dowsett <PICLIST MITVMA.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 - fastfwd ix.netcom.com                 ===
=== Fast Forward Engineering - Vista, California          ===
===                                                       ===
=== Custodian of the PICLIST Fund -- For more info, see:  ===
=== http://www.geocities.com/SiliconValley/2499/fund.html ===   Andy David <PICLIST MITVMA.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 - fastfwd ix.netcom.com                 ===
=== Fast Forward Engineering - Vista, California          ===
===                                                       ===
=== Custodian of the PICLIST Fund -- For more info, see:  ===
=== http://www.geocities.com/SiliconValley/2499/fund.html ===  > 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         Andy Ultronics.co.uk
Ultra Hydraulics Ltd.
Staverton
Glos. GL2 9QN

Tel.: (01452) 858376 (Direct)  Ultronics Fax.: (01452) 858377
*************************************************************  > > > 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
rrf     DstM
rrf     DstL
btfss   Src,5
rrf     DstM
rrf     DstL
btfss   Src,6
rrf     DstM
rrf     DstL
btfss   Src,7
call    Sqr4
swapf   SrcL
andlw   \$0F
call    Sqr4
; 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
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
rlf     SrcL,w
btfsc   C
incf   DstH
btfsc   C
incf   DstH
btfsc   C
incf   DstH
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:
db      0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225  >> > 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...