Here's a summary of Dimitris Andreou's link.
Remember sum of i-th powers, where i=1,2,..,k. This reduces the problem to solving the system of equations
a1 + a2 + ... + ak = b1
a12 + a22 + ... + ak2 = b2
...
a1k + a2k + ... + akk = bk
Using Newton's identities, knowing bi allows to compute
c1 = a1 + a2 + ... ak
c2 = a1a2 + a1a3 + ... + ak-1ak
...
ck = a1a2 ... ak
If you expand the polynomial (x-a1)...(x-ak) the coefficients will be exactly c1, ..., ck - see Viète's formulas. Since every polynomial factors uniquely (ring of polynomials is an Euclidean domain), this means ai are uniquely determined, up to permutation.
This ends a proof that remembering powers is enough to recover the numbers. For constant k, this is a good approach.
However, when k is varying, the direct approach of computing c1,...,ck is prohibitely expensive, since e.g. ck is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp or Cantor-Zassenhaus.
High level pseudocode for constant k:
- Compute i-th powers of given numbers
- Subtract to get sums of i-th powers of unknown numbers. Call the sums bi.
- Use Newton's identities to compute coefficients from bi; call them ci. Basically, c1 = b1; c2 = (c1b1 - b2)/2; see Wikipedia for exact formulas
- Factor the polynomial xk-c1xk-1 + ... + ck.
- The roots of the polynomial are the needed numbers a1, ..., ak.
For varying k, find a prime n <= q < 2n using e.g. Miller-Rabin, and perform the steps with all numbers reduced modulo q.
EDIT: The previous version of this answer stated that instead of Zq, where q is prime, it is possible to use a finite field of characteristic 2 (q=2^(log n)). This is not the case, since Newton's formulas require division by numbers up to k.
1.How do computers represent negative numbers?
Take the positive value, invert all bits and add one.
2.Why do computers represent negative numbers this way?
It makes easy to add 7 in -7 and came up with a zero. The bit operations are fast.
How does it make it easy?
Take the 7 and -7 example. If you represent 7 as 00000111
, to find -7 invert all bits and add one:
11111000 -> 11111001
Now you can add following standard math rules:
00000111
+ 11111001
-----------
00000000
For the computer this operation is relatively easy, as it involves basically comparing bit by bit and carrying one.
If instead you represented -7 as 10000111
, this won't make sense:
00000111
+ 10000111
-----------
10001110 (-14)
To add them, you will involve more complex rules like analyzing the first bit, and transforming the values.
And don't forget what @trashgod said, in 2's complement you have only one zero. To check it:
00000000
11111111
(invert all bits)
00000000
(add one)
Differently from 00000000
(0) being equal to 10000000
(-0)
Best Answer
It's done so that addition doesn't need to have any special logic for dealing with negative numbers. Check out the article on Wikipedia.
Say you have two numbers, 2 and -1. In your "intuitive" way of representing numbers, they would be
0010
and1001
, respectively (I'm sticking to 4 bits for size). In the two's complement way, they are0010
and1111
. Now, let's say I want to add them.Two's complement addition is very simple. You add numbers normally and any carry bit at the end is discarded. So they're added as follows:
0001
is 1, which is the expected result of "2+(-1)".But in your "intuitive" method, adding is more complicated:
Which is -3, right? Simple addition doesn't work in this case. You need to note that one of the numbers is negative and use a different algorithm if that's the case.
For this "intuitive" storage method, subtraction is a different operation than addition, requiring additional checks on the numbers before they can be added. Since you want the most basic operations (addition, subtraction, etc) to be as fast as possible, you need to store numbers in a way that lets you use the simplest algorithms possible.
Additionally, in the "intuitive" storage method, there are two zeroes:
Which are intuitively the same number but have two different values when stored. Every application will need to take extra steps to make sure that non-zero values are also not negative zero.
There's another bonus with storing ints this way, and that's when you need to extend the width of the register the value is being stored in. With two's complement, storing a 4-bit number in an 8-bit register is a matter of repeating its most significant bit:
It's just a matter of looking at the sign bit of the smaller word and repeating it until it pads the width of the bigger word.
With your method you would need to clear the existing bit, which is an extra operation in addition to padding:
You still need to set those extra 4 bits in both cases, but in the "intuitive" case you need to clear the 5th bit as well. It's one tiny extra step in one of the most fundamental and common operations present in every application.