﻿ Multiplication!
24 May, 2013, 18:38:34
 OmnomIRC You must Register, be logged in and have at least 40 posts to use this shout-box! If it still doesn't show up afterward, it might be that OmnomIRC is disabled for your group or under maintenance.Note: You can also use an IRC client like mIRC, X-Chat or Mibbit to connect to an EFnet server and #omnimaga.

 Pages: [1]   Go Down
 Author Topic: Multiplication! -  (Read 546 times) 0 Members and 1 Guest are viewing this topic.
systwo
LV2 Member (Next: 40)

Offline

Last Login: 03 February, 2012, 10:16:24
Date Registered: 13 January, 2012, 07:06:05
Posts: 25

Topic starter
Total Post Ratings: +7

 « on: 22 January, 2012, 22:27:43 » 0

Hello everyone!

I've been looking into some 16 bit multiplication but I've come across with few problems. I could not understand much of the bitwise based multiplication and I'm guessing I need to do something like them in order to perform math with a 16 bit answer. Is there anyone who may be able to enlighten me?

Thanks!
 Logged
ralphdspam

Offline

Gender:
Last Login: 14 May, 2013, 09:10:11
Date Registered: 01 February, 2011, 07:58:40
Location: California, USA
Posts: 841

Total Post Ratings: +36

 « Reply #1 on: 23 January, 2012, 00:32:13 » 0

There are a bunch of routines on WikiTI.

http://wikiti.brandonw.net/index.php?title=Z80_Routines:Math:Multiplication

I'm not really sure what you're asking for, can you please elaborate?
 « Last Edit: 23 January, 2012, 00:32:28 by ralphdspam » Logged

ld a, 0
ld a, a
jacobly
LV4 Regular (Next: 200)

Offline

Date Registered: 09 October, 2011, 01:53:09
Posts: 199

Total Post Ratings: +149

 « Reply #2 on: 23 January, 2012, 00:46:29 » 0

An example may help:

11001100 = a
× 10010110 = b
----------
00000000
11001100
11001100
00000000
11001100
00000000
00000000
+ 00000000
-----------------
111011110001000

So as you can see, in binary, for each bit you add either 0 or a (shifted by some amount), depending on the corresponding bit in b.
The way this is usually done is:
1. shift the running total left one bit
2. check the msb of b
3. if set, add a to the running total
4. shift b left one bit
5. repeat steps 1-4 for each bit in b
6. the answer is the current running total
 Logged
chickendude
LV6 Super Member (Next: 500)

Offline

Gender:
Last Login: 21 May, 2013, 19:04:07
Date Registered: 06 September, 2008, 11:27:30
Posts: 435

Total Post Ratings: +66

 « Reply #3 on: 25 January, 2012, 01:23:13 » 0

Thanks for writing that out, jacobly. z80 arithmetic has always been a bit confusing for me (and i'm not very good at math to boot).
 Logged
ZippyDee

Offline

Gender:
Last Login: 12 May, 2013, 10:03:36
Date Registered: 21 March, 2011, 03:15:07
Location: Yes.
Posts: 704

Total Post Ratings: +73

 « Reply #4 on: 25 January, 2012, 02:09:46 » 0

An example may help:

11001100 = a
× 10010110 = b
----------
00000000
11001100
11001100
00000000
11001100
00000000
00000000
+ 00000000
-----------------
111011110001000

So as you can see, in binary, for each bit you add either 0 or a (shifted by some amount), depending on the corresponding bit in b.
The way this is usually done is:
1. shift the running total left one bit
2. check the msb of b
3. if set, add a to the running total
4. shift b left one bit
5. repeat steps 1-4 for each bit in b
6. the answer is the current running total
I think there is a mistake in that written out example...Shouldn't the last iteration be adding 10010110, not 00000000? Also, shouldn't step 4 be "shift b right one bit"?
 « Last Edit: 25 January, 2012, 02:11:19 by ZippyDee » Logged

Pushpins 'n' stuff...

Xeda112358
Xombie. I am it.
Coder Of Tomorrow
LV12 Extreme Poster (Next: 5000)

Offline

Date Registered: 31 October, 2010, 08:46:36
Location: Land of Little Cubes and Tea, NY
Posts: 3760

Total Post Ratings: +610

 « Reply #5 on: 25 January, 2012, 04:59:43 » 0

Jacobly has the best idea that I have seen and it is how I think of it. It really is pretty much like how you learned to multiply in school, but multiplying by one or zero is super easy
 Logged

Latest update (possibly incomplete)
My pastebin
Spoiler for FileSyst:
FileSyst is an application that provides a folder and filesystem for the TI-83+/84+ calculators. It is designed to be easy to access and use in BASIC, and it can be used to access game files and save data, or to create a command prompt, among other things:

Spoiler for Graphiti:
This is a graph explorer for graph theory. It will require lots of work to finish. Currently you can:
Add edges (direction not shown, but they are directed)
Arrange vertices in a circle (in the future, you will be able to define levels of rings and the number of nodes in each)
Create complete graphs quickly

Plans:
Deleting edges
Multiple graphs support
Arrows for directed graphs
Planarity testing
Matrix operations
Weighted edges
Chromatic polynomials
Chromatic numbers

Spoiler for Stats:

Samocal             [o---------]
Virtual Processor   [o---------]
EnG                 [oo--------]
Grammer             [ooo-------]
AsmComp             [ooo-------]
Partex              [oooo------]
BatLib              [oooooooo--]
Grammer82           [----------]
Grammer68000        [----------]

Pseudonyms:  Zeda, Xeda, Thunderbolt
Languages:   English, français
Programming: z80 Assmebly
Grammer
TI-BASIC (83/84/+/SE, 89/89t/92)
Known For:   -Creator of the Grammer programming language
(Winning program of zContest2011)
-BatLib- One of the most feature packed libraries for BASIC programmers available
with over 100 functions and a simple programming language
-Learning to program z80 in hexadecimal before using an assembler (no computer was
available!)
╔═╦╗░╠═╬╣▒║ ║║▓╚═╩╝█

systwo
LV2 Member (Next: 40)

Offline

Last Login: 03 February, 2012, 10:16:24
Date Registered: 13 January, 2012, 07:06:05
Posts: 25

Topic starter
Total Post Ratings: +7

 « Reply #6 on: 25 January, 2012, 07:33:00 » 0

Hmm... That never occurred to me. So its like reverse multiplication for me(I usually start on the right). Thank you so much for this! I have been thinking of how to do multiplication with just arithmetic on the a register and it drove me insane!
 Logged
ZippyDee

Offline

Gender:
Last Login: 12 May, 2013, 10:03:36
Date Registered: 21 March, 2011, 03:15:07
Location: Yes.
Posts: 704

Total Post Ratings: +73

 « Reply #7 on: 25 January, 2012, 07:48:05 » 0

Er...no, you should be starting on the right still...

I believe jacobly's post should have said:

11001100 = a
× 10010110 = b
----------
00000000
11001100
11001100
00000000
11001100
00000000
00000000
+ 11001100
-----------------
111011110001000

So as you can see, in binary, for each bit you add either 0 or a (shifted by some amount), depending on the corresponding bit in b.
The way this is usually done is:
1. shift the running total left one bit
2. check the lsb of b
3. if set, add a to the running total
4. shift b right one bit
5. repeat steps 1-4 for each bit in b
6. the answer is the current running total
 « Last Edit: 25 January, 2012, 07:53:26 by ZippyDee » Logged

Pushpins 'n' stuff...

systwo
LV2 Member (Next: 40)

Offline

Last Login: 03 February, 2012, 10:16:24
Date Registered: 13 January, 2012, 07:06:05
Posts: 25

Topic starter
Total Post Ratings: +7

 « Reply #8 on: 25 January, 2012, 07:53:46 » 0

Wouldn't step 2 be check the lsb then? Or is this an endian thing? Also wouldn't shifting the running total left result in the backwards answer? Sorry if these questions are simple, I'm still getting the hang of bitwise operations.

Edit: Oops, didn't see your edit there ZippyDee!
 « Last Edit: 25 January, 2012, 07:54:35 by systwo » Logged
Runer112
LV10 31337 u53r (Next: 2000)

Online

Gender:
Date Registered: 02 July, 2009, 06:38:05
Posts: 1680

Total Post Ratings: +493

 « Reply #9 on: 25 January, 2012, 07:59:06 » 0

I'm pretty sure the algorithm jacobly wrote is correct for how multiplication is usually done on z80 systems. Shifting left in situations like this is usually easier and faster on the z80. What may be confusing is that the math printed out above the algorithm steps is not actually showing the algorithm, it's just showing the elementary school multiplication method in binary.

However, you are correct that the last number added to the result of the long-hand multiplication should be 11001100.
 « Last Edit: 25 January, 2012, 08:01:16 by Runer112 » Logged
ZippyDee

Offline

Gender:
Last Login: 12 May, 2013, 10:03:36
Date Registered: 21 March, 2011, 03:15:07
Location: Yes.
Posts: 704

Total Post Ratings: +73

 « Reply #10 on: 25 January, 2012, 08:03:05 » 0

Hmm... I guess that does make sense. Looking back over that I realize that I was thinking of shifting the multiplicand (like the example shows) rather than the running total.
 Logged

Pushpins 'n' stuff...

Xeda112358
Xombie. I am it.
Coder Of Tomorrow
LV12 Extreme Poster (Next: 5000)

Offline

Date Registered: 31 October, 2010, 08:46:36
Location: Land of Little Cubes and Tea, NY
Posts: 3760

Total Post Ratings: +610

 « Reply #11 on: 25 January, 2012, 14:42:22 » 0

As a note that I am sure everybody realises (but I will still go into some detail), the shifting left occurs because in binary that is multiplying by 2 (you can also add it to itself) and this is because it is base 2. When you do that, you are just adding a zero to the end of the number. In the more familiar base of base 10 (or any base above 2), you have to worry about intermediate carry stuff, but it is pretty much the same. If I wanted to do 367*183, it would look like this
183 shift left is 83 with 1 as the digit to use
1*367=367, this is what we add to the accumulator
Shift the 83 left and we have 3 (well, 300), and 8 is the digit to check
Shift the accumulator left to multiply by 10
8*367=2936, this we add to the accumulator
Acc=6606
Acc shifted left to multiply by 10
shift left to get the 3
3*367=1101, add this to the accumulator
Acc=67161

Check it and it works Pretty much, you are doing multiplication "the normal way", but backwards (last digit first). If you notice, the first result was multiplied by a total of 100 which fits (we did 1*367 for 100*367).
 Logged

Latest update (possibly incomplete)
My pastebin
Spoiler for FileSyst:
FileSyst is an application that provides a folder and filesystem for the TI-83+/84+ calculators. It is designed to be easy to access and use in BASIC, and it can be used to access game files and save data, or to create a command prompt, among other things:

Spoiler for Graphiti:
This is a graph explorer for graph theory. It will require lots of work to finish. Currently you can:
Add edges (direction not shown, but they are directed)
Arrange vertices in a circle (in the future, you will be able to define levels of rings and the number of nodes in each)
Create complete graphs quickly

Plans:
Deleting edges
Multiple graphs support
Arrows for directed graphs
Planarity testing
Matrix operations
Weighted edges
Chromatic polynomials
Chromatic numbers

Spoiler for Stats:

Samocal             [o---------]
Virtual Processor   [o---------]
EnG                 [oo--------]
Grammer             [ooo-------]
AsmComp             [ooo-------]
Partex              [oooo------]
BatLib              [oooooooo--]
Grammer82           [----------]
Grammer68000        [----------]

Pseudonyms:  Zeda, Xeda, Thunderbolt
Languages:   English, français
Programming: z80 Assmebly
Grammer
TI-BASIC (83/84/+/SE, 89/89t/92)
Known For:   -Creator of the Grammer programming language
(Winning program of zContest2011)
-BatLib- One of the most feature packed libraries for BASIC programmers available
with over 100 functions and a simple programming language
-Learning to program z80 in hexadecimal before using an assembler (no computer was
available!)
╔═╦╗░╠═╬╣▒║ ║║▓╚═╩╝█

 Pages: [1]   Go Up

Page created in 0.308 seconds with 31 queries.
Skin by DJ Omnimaga edited from SMF default theme with the help of tr1p1ea.
All programs, games and songs avaliable on this website are property of their respective owners.
Best viewed in Opera, Firefox, Chrome and Safari with a resolution of 1024x768 or above.