So let's go with n+n->n and nxn->2n .
On 12/10/2011 8:35 PM, Henry Rich wrote:
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
