Searching \ for ' Challenge: 8X8 multiplication' in subject line. ()
Help us get a faster server
FAQ page: www.piclist.com/techref/method/math.htm?key=multiplication
Search entire site for: 'Challenge: 8X8 multiplication'.

No exact or substring matches. trying for part
'[PICLIST] Challenge: 8X8 multiplication'
2001\11\13@144535 by

Suppose you have:

c = a * b

and all three are bytes.

Minimize execution time (on a mid-range core).

Trashing a (or b) I have a routine that is 31 instructions/cycles long.

Any takers?

Scott

--

I'm sure I could make one with fewer instructions, but it would take
about 70 cycles on average!  :-)

Scott Dattalo wrote:

{Quote hidden}

--

I'll try:

clrf c

movf b,w      ;b = w
btfsc a,0

btfsc a,1

movwf b       ;b = b*2
btfsc a,2

movwf b       ;b = b*4
btfsc a,3

.
.
.

movwf b       ;b = b*64
btfsc a,7

rgds,
Reggie
{Original Message removed}
Hi Scott, my 8x8 is 42 cycles, I would like to see how you have done this, would
you like to post it to the group?

Thanks.

scottDATTALO.COM on 13/11/2001 19:43:40

To:     PICLISTMITVMA.MIT.EDUINTERNETwtgw
cc:
Paper Mail:
Subject:        Challenge: 8X8 multiplication

*** WARNING ***

This mail has originated outside your organization,
either from an external partner or the Global Internet.
Keep this in mind if you answer this message.

Suppose you have:

c = a * b

and all three are bytes.

Minimize execution time (on a mid-range core).

Trashing a (or b) I have a routine that is 31 instructions/cycles long.

Any takers?

Scott

--

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

>Suppose you have:
>
> c = a * b
>
>and all three are bytes.

What about overflow? I think there might also be
a slight hint-ette in Scott's post...

- Andy.
---------------------------------------------
Andrew David, Software Manager, Ultronics Ltd
http://www.Ultronics.com

{Original Message removed}
On Wed, 14 Nov 2001, Regulus Berdin wrote:

{Quote hidden}

Bingo! Thanks Reggie, you saved me some typing :).

Now for Andy's concern about overflow. Yes it does have that problem. But
the challenge said that all three variables are bytes. So the implicit
hint was that overflows were to be ignored.

I came across this in developing SDCC. If you have a C expression:

unsigned char a,b,c;

...

c = a*b;

It's your responsibility and not the compiler's to ensure the product fits
into the destination.

If that's a problem, then you can do this (in C):

unsigned char a,b,c;
unsigned int t;

...

t = ((int)a) * b;  /* cast product to an int */
if(t>=256)
overflowed();
c = t;

Note that at least one of the multiplicands need to be cast to an int.
I.e. this doesn't work:

t = a*b;   /* same as t = (a*b) & 0xff; */

---

If you want to handle products greater than 255, then that can be
accomodated with 4 additional cycles (but the code is totally different).

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

> If that's a problem, then you can do this (in C):
>
> unsigned char a,b,c;
> unsigned int t;
>
> ...
>
> t = ((int)a) * b;  /* cast product to an int */
> if(t>=256)
>   overflowed();
> c = t;
>
> Note that at least one of the multiplicands need to be cast to an int.
> I.e. this doesn't work:
>
> t = a*b;   /* same as t = (a*b) & 0xff; */
>

Scott,

Actually, ANSI "C" _must_ perform all arirthmetic "AS IF" all operands were
promoted to at least 'int' precision.

This means that

unsigned char a, b;
unsigned int c;

c = a*b;

MUST do an 8x8 -> 16 multiply

However,

unsigned char a, b;
unsigned char c;

c = a*b;

Needs to work "as if" it did 8x8->16 and then truncated, which is of course
what the code above does.

Bob Ammerman, Language Lawyer
RAm Systems

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics

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