I think the result should be truncated, so that the nth bit is
interpreted as a sign bit but might be invalid (I expect this is what
you meant originally). With such an operation you would normally use it
only if you could be sure in advance that no overflow would result.
I don't think that's very useful (though the MH instruction in S\360
worked that way). nxn->2n is more useful.
Henry Rich
On 12/10/2011 9:25 PM, Kip Murray wrote:
> What do you recommend for the high-order bit? I am "off my reservation"
> here. Thought there might be a clever way to add positive numbers using
> / so partial results could be fun. Multiplication may be "men dok sai"
> (too much trouble).
>
> On 12/10/2011 8:03 PM, Henry Rich wrote:
>> 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
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
