Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[ein]

I was wondering if someone could show me how to multiply with binary.
I've figured out how to do it with the powers of two.
You just take however many zeros there are and put them on the end of the other number.
Two (10) has one zero, and when you multiply it with three (11), you get six (110).
What I want to know is, how do you get 11 and 11 to be 1001? 'N' stuff.

[eerr]

How to do it fast, or how to do it.

[ein]

Both.
If I understand how to do it, then I'll be able to learn how to do it faster.
Or something.

[Cheddarius]

Just multiply normally.

Code: [Select]

   11
   11
-----
   11
  110
-----    
  121
-----
  201
-----
 1001


[Ampersand]

Cheddarius, if he doesn't understand how to do Binary multiplication, I'm not sure he'll comprehend that without an explanation of why you have a 2 in there.

[Cheddarius]

Ah, sorry.
Okay, so you know how you "carry the 10" and such in normal multiplication or addition? This is like that. The 1 and the 1 add up to 2; you "carry the 2" over to the hundreds (or rather, fours) place.

[eerr]

A*B=C
Multiply the first binary digit of A with All the digits of B.
Mulitply the second binary digit of A with All the digits of B.
Multiply the third binary...

(integers have more, chars/ bytes I'm not sure)
... the second last binary digit of A with B.
Multiply the last binary digit of A with B.

Sum All  multiplication. Note that in binary you can end up with a very large remainder which carries over very far.
 1+1=10, 10+10=100, 100+100=1000.



Whether or not this overflows depends on how much space is allocated vs how big the two operands are.

Code: [Select]

   00001000
*  00010000
= 100000000???
Note that my calculation ignores the negative digit, so the exact result would be machine dependant, and contain alot of code I've never studied.

[qwertyuiopas]

Don't know if this was expressed before, but using the earlier multiplication by a power of two...
(Syntax a<<b means add b zeroes onto the end of a)
Example of one way:
100101*11010

b        a
0 * 100101 << 0+
1 * 100101 << 1+
0 * 100101 << 2+
1 * 100101 << 3+
1 * 100101 << 4=

b        a
1 * 100101 << 1+
1 * 100101 << 3+
1 * 100101 << 4=

b        a
1 * 1001010 << 0 +
1 * 100101000 << 0 +
1 * 1001010000 << 0 =

___1001010+
_100101000+
1001010000=

1111000010

You can reduce it to multiplying a digit, and a << for each digit in one number, then sum the result.

[ein]

Awesome, thanks.
Also, « is the symbol you're referring to, right?
As in a«b.

[Siquo]

No, I think querty means <<, not as a mathematic symbol but as a shift-operator in a number of programming languages.

[eerr]

I would put money that this will be slower than letting the machine handle it.

[sproingie]

The shift technique is pretty close to how ALUs used to do it in hardware, and it would often take many cycles to execute.  How they do it now is probably way over my head, suffice to say that multiplication is plenty fast these days, especially if you use the FPU.

[ein]

Yeah, I've decided that this is one of those useless skills that you only use for showing off.

[Vector]

Yeah, I've decided that this is one of those useless skills that you only use for showing off.

Not true.  Look up the game of Nim.

Okay, maybe it's useless and you only use it for showing off, but it's an application.


Oh, and all kinds of crap when it comes to taking the power of some number modulo n.  Really useful in algorithms for discrete math and cryptography.

[G-Flex]

Just multiply normally.

Code: [Select]

   11
   11
-----
   11
  110
-----    
  121
-----
  201
-----
 1001


... You're seriously using a digit that doesn't even exist in the given number system in order to do arithmetic?

That's kind of like explaining to a third-grader how to multiply numbers and using the digit A in addition to 0-9 in order to do it.

"2" simply doesn't exist as a numeral in binary. 0 does, and 1 does, and "2" in decimal has the same value as "10" in binary, but there's no more a "2" in binary than there is an "A" in decimal or a "Q" in hexadecimal.