Searching \ for ' Challenge: 8X8 multiplication' 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=multiplication
Search entire site for: 'Challenge: 8X8 multiplication'.

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

face
flavicon
face
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

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2001\11\13@200848 by M. Adam Davis

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

-Adam

Scott Dattalo wrote:

{Quote hidden}

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2001\11\13@224444 by Regulus Berdin

flavicon
face
I'll try:

clrf c

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

addwf b,w     ;w = b*2
btfsc a,1
 addwf c

movwf b       ;b = b*2
addwf b,w     ;w = b*4
btfsc a,2
 addwf c

movwf b       ;b = b*4
addwf b,w     ;w = b*8
btfsc a,3
 addwf c

.
.
.

movwf b       ;b = b*64
addwf b,w     ;w = b*128
btfsc a,7
 addwf c

rgds,
Reggie
{Original Message removed}

2001\11\14@045759 by Mike Blakey

flavicon
face
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.





spam_OUTscottTakeThisOuTspamDATTALO.COM on 13/11/2001 19:43:40
Please respond to .....PICLISTKILLspamspam@spam@MITVMA.MIT.EDUKILLspamspam@spam@INTERNETKILLspamspam@spam@wtgw

To:     PICLISTspamKILLspamMITVMA.MIT.EDUspamKILLspamINTERNETspamKILLspamwtgw
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

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads








********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
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


2001\11\14@091646 by Andy David

flavicon
face
>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}

2001\11\14@093542 by Scott Dattalo

face
flavicon
face
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


2001\11\14@204742 by Bob Ammerman

picon face
> 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...