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
