Yes, you can do 2's-complement multiplication. I think you need to be
more precise about what happens in case of overflow: are you just
getting the low n bits of the 2n-bit result, which means that you have a
meaningless sign bit; or is the high-order bit of the product preserved?
The way you do it in hardware (or microcode, often) is, you implement an
nxn->2n-bit unsigned multiplier, then you correct the product by (for
each operand) subtracting the operand IF the other operand is negative.
The math of this is fun to work through: in 2's-comp a positive number
is 0.xxxx and a negative code 1.xxxx represents the number (1.xxxx - 2).
See what that means for products.
Cheap machines repeatedly add n-bit numbers together, which leads you to
Booth's algorithm (q. v.).
Now that gates are free the multiplier is implemented with a network of
full adders, which add 3 bits to produce a 2-bit total. This network is
called a carry-save adder, because the n^2 bits of the partial product
are combined, using full adders, with no explicit carry propagation: you
just keep adding bits of the same place value, reducing the number of
bits by a 3:2 ratio, until you end up with 2n bits, which you then
polish off with a carry-propagating adder (the art of design is in
deciding which bits of equal value should be added). The overall
operation is surprisingly fast, much faster than adding 64 n-bit numbers
one by one. Research continues on the best way to build the carry-save
adder, and the building blocks to use for it.
You could emulate any or all of that, but I'm not sure it's interesting
to do so.
Henry Rich
On 12/10/2011 7:48 PM, Kip Murray wrote:
> Cool. I think it is an improvement because it neatly avoids a case
> statement. Now I wonder if we could implement two's-complement addition
> and multiplication with overflow, basing these on bitwise operations
>
> 0 + 0 is 0, 0 + 1 is 1 + 0 is 1, and 1 + 1 is 1 0
>
> 0 * 0 is 0 * 1 is 1 * 0 is 0, and 1*1 is 1
>
> That is, I do not want hc and hcinv to be used except to produce data
> and check answers, and I want n-bit two's-complement answers for n-bit
> two's-complement data so some of them will be wrong because of overflow.
>
> Here for Linda is Henry's hcinv expressed without conjunctions other
> than " .
>
> hcinv =: ([: -/ [: #. (,: [: +: 1 {. ]))"1
>
> On 12/10/2011 10:00 AM, Henry Rich wrote:
>> Same idea, better implementation
>>
>> hcinv =. -/@:#.@:(,: +:@(1&{.))"1
>>
>> Henry Rich
>>
>> On 12/10/2011 10:48 AM, Henry Rich wrote:
>>> Maybe not an improvement, but this is how I would have done back in my
>>> hardware-design days:
>>>
>>> hcinv =. -~/@:#.@:(~:/\)@:((,1)&,:)"1
>>>
>>> Quite a bit more elegant in wires than in J!
>>>
>>> Henry Rich
>>>
>>> On 12/10/2011 1:01 AM, Kip Murray wrote:
>>>> Now we need an inverse for Raul's improved #: ("hash colon")
>>>>
>>>> hc NB. Raul's improved #:
>>>> {.@#:@(,: (2 * |))
>>>>
>>>> hc i: 2
>>>> 1 1 0
>>>> 1 1 1
>>>> 0 0 0
>>>> 0 0 1
>>>> 0 1 0
>>>>
>>>> hcinv NB. improvement sought
>>>> 2&#.`(2&#.@}. - 2 ^<:@#)@.{."1
>>>>
>>>> hcinv hc i: 2
>>>> _2 _1 0 1 2
>>>>
>>>> On 12/8/2011 2:41 PM, Raul Miller wrote:
>>>> ...
>>>> But this would work just as well, as a model:
>>>>
>>>> {.@#:@(,: 2 * |)i:2
>>>> 1 1 0
>>>> 1 1 1
>>>> 0 0 0
>>>> 0 0 1
>>>> 0 1 0
>>>> ----------------------------------------------------------------------
>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>>
>>> ----------------------------------------------------------------------
>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
