Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #29381

Re: FFT Speeds

Show all headers | View raw

On 03/04/2020 10:29, Rick C wrote:
> On Friday, April 3, 2020 at 2:34:42 AM UTC-4, upsid...@downunder.com
> wrote:
>> On Thu, 2 Apr 2020 12:39:55 -0700 (PDT), Rick C 
>> <gnuarm.deletethisbit@gmail.com> wrote:
>> 
>>> On Thursday, April 2, 2020 at 2:33:20 PM UTC-4, Tauno Voipio
>>> wrote:
>>>> 
>>>> Booth's algorithm does handle signed operands in two's
>>>> complement notation.
>>> 
>>> Your mention of two's complement as if there were other choices
>>> these days made me recall that in the Forth language group there
>>> is a discussion of standardizing on 2's complement... finally.
>>> 
>>> Seems someone looked and there are literally no remaining
>>> hardware computers running anything other than 2's complement.
>>> There is an architecture running 1's complement, but it is no
>>> longer a hardware implementation but only simulated on other
>>> machines, lol.  There must be some commercial niche for software
>>> written for that machine.
>> 
>> The nice feature with 1究 complement is that you can negate a
>> number by simply inverting all bits in a word. Thus inserting the
>> inverters in one data path and both inverting and some other
>> operation can be used in a single instruction.
>> 
>> The problem with 2究 complement is that after inverting all bits,
>> "1" must be added to the result, requiring an adder and the ripple
>> carry can propagate through all bit positions. Thus complementing a
>> number needs an ADD instruction and takes as long as an ordinary
>> ADD, Of course these days with carry look-ahead logic, the ADD is
>> nearly as fast as AND/OR instructions.
> 
> Exactly, and the 2's complement doesn't have the various issues the
> 1's complement does.  It only has a single value for zero.  I can't
> recall how they deal with that.  If you subtract 2 from 1 you would
> get an all ones word which is zero, so you have to subtract another 1
> to get -1 which is all ones with the LSB zero.  So it's not really
> simpler, just messy in different ways.

Yes - ones' complement has several complications, and not many benefits. 
  Sign-magnitude also has the "negative zero" issue, but has nice 
symmetry and is good for multiplication and division.  These formats 
also avoid the asymmetry of having a larger negative range than positive 
range, and odd things like "abs(-128) == -128" (using 8-bit to keep the 
numbers small).

> 
> Actually the invert and add 1 is pretty easy to do in an ALU.  You
> already have the adder, just add a conditional inverter in front and
> you have a subtract, oh, don't forget to add the 1 through the carry
> in.  Easy and no different timing than the ALU without the inverter
> if it's done in the same LUT in an FPGA.  In fact, I've seen macros
> for add/sub blocks.

Generally the "borrow" flag for subtraction is the inversion of the 
"carry" flag for addition.  This means that a "subtract with borrow" 
instruction is implemented as an "add with carry" where the subtracted 
value is complemented first.  That is, to do "A - B - borrow" you do "A 
+ ~B + carry".  That is (another) nice feature of two's complement that 
lets you re-use existing hardware without having extra carry propagation 
delays.

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-03-30 12:11 -0700
  Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-03-30 21:50 +0200
    Re: FFT Speeds Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2020-03-31 09:33 +0200
  Re: FFT Speeds dalai lamah <antonio12358@hotmail.com> - 2020-03-31 16:14 +0200
    Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 12:07 +1100
      Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-03-31 18:41 -0700
        Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 13:40 +1100
          Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-03-31 20:53 -0700
            Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-01 18:45 +1100
            Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-01 17:32 +0100
              Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-01 12:20 -0700
                Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-02 09:40 +0100
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 02:00 -0700
                Re: FFT Speeds upsidedown@downunder.com - 2020-04-02 12:50 +0300
              Re: FFT Speeds Richard Damon <Richard@Damon-Family.org> - 2020-04-02 08:02 -0400
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 11:16 -0700
                Re: FFT Speeds Tauno Voipio <tauno.voipio@notused.fi.invalid> - 2020-04-02 21:33 +0300
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 12:39 -0700
                Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-04-02 20:33 -0700
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-02 20:43 -0700
                Re: FFT Speeds upsidedown@downunder.com - 2020-04-03 09:34 +0300
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 01:29 -0700
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 12:23 +0200
                Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-03 21:48 +1100
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 10:38 -0700
                Re: FFT Speeds Clive Arthur <cliveta@nowaytoday.co.uk> - 2020-04-04 11:50 +0100
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 09:12 +0200
                Re: FFT Speeds Rick C <gnuarm.deletethisbit@gmail.com> - 2020-04-03 01:30 -0700
                Re: FFT Speeds David Brown <david.brown@hesbynett.no> - 2020-04-03 12:39 +0200
          Re: FFT Speeds Paul Rubin <no.email@nospam.invalid> - 2020-04-01 10:43 -0700
            Re: FFT Speeds Clifford Heath <no.spam@please.net> - 2020-04-02 13:26 +1100
      Re: FFT Speeds Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2020-04-01 17:27 -0400

csiph-web