Carry (arithmetic)

In elementary arithmetic a carry is a digit that is transferred from one column of digits to another column of more significant digits during a calculation algorithm. When used in subtraction the operation is called a borrow. It is a central part of traditional mathematics, but is often omitted from curricula based on reform mathematics, which do not emphasize any specific method to find a correct answer.

Manual arithmetic

A typical example of carry is in the following pencil-and-paper addition:

```  ¹
27
+ 59
----
86
```

7 + 9 = 16, and the digit 1 is the carry.

The opposite is a borrow, as in

```  −1
47
− 19
----
28
```

Here, 7 − 9 = −2, so try (10 − 9) + 7 = 8, and the 10 is got by taking ("borrowing") 1 from the next digit to the left. There are two ways in which this is commonly taught:

1. The ten is moved from the next digit left, leaving in this example 3 − 1 in the tens column. According to this method, the term "borrow" is a misnomer, since the ten is never paid back.
2. The ten is copied from the next digit left, and then 'paid back' by adding it to the subtrahend in the column from which it was 'borrowed', giving in this example 4 − (1 + 1) in the tens column.

Mathematics education

Traditionally, carry is taught in the addition of multi-digit numbers in the 2nd or late first year of elementary school. However since the late 20th century, many widely adopted curricula developed in the United States such as TERC omitted instruction of the traditional carry method in favor of invented arithmetic methods, and methods using coloring, manipulatives, and charts. Such omissions were criticized by such groups as Mathematically Correct, and some states and districts have since abandoned this experiment, though it remains widely used.[citation needed]

Higher mathematics

When several random numbers of many digits are added, the statistics of the carry digits bears an unexpected connection with Eulerian numbers and the statistics of riffle shuffle permutations.[1][2][3][4]

In abstract algebra, the carry operation for two-digit numbers can be formalized using the language of group cohomology.[5][6][7] This viewpoint can be applied to alternative characterizations of the real numbers.[8][9]

Computing

When speaking of a digital circuit like an adder, the word carry is used in a similar sense. In most computers, the carry from the most significant bit of an arithmetic operation (or bit shifted out from a shift operation) is placed in a special carry bit which can be used as a carry-in for multiple precision arithmetic or tested and used to control execution of a computer program. The same carry bit is also generally used to indicate borrows in subtraction, though the bit's meaning is inverted due to the effects of two's complement arithmetic. Normally, a carry bit value of '1' signifies that an addition overflowed the ALU, and must be accounted for when adding data words of lengths greater than that of the CPU. Conversely, a subtraction operation will set this same bit to '0' in order to indicate that the subtraction resulted in a negative result, requiring a borrow from higher digits.

References

1. ^ Holte, John M. (February 1997), "Carries, Combinatorics, and an Amazing Matrix", The American Mathematical Monthly 104 (2): 138–149, doi:10.2307/2974981
2. ^ Diaconis, Persi; Fulman, Jason (August 2009), "Carries, shuffling, and symmetric functions", Advances in Applied Mathematics 43 (2): 176–196, doi:10.1016/j.aam.2009.02.002
3. ^ Borodin, Alexei; Diaconis, Persi; Fulman, Jason (October 2010), "On adding a list of numbers (and other one-dependent determinantal processes)", Bulletin of the American Mathematical Society 47 (4): 639–670, doi:10.1090/S0273-0979-2010-01306-9
4. ^ Nakano, Fumihiko; Sadahiro, Taizo (February 2014), "A generalization of carries processes and Eulerian numbers", Advances in Applied Mathematics 53: 28–43, doi:10.1016/j.aam.2013.09.005
5. ^ Hegland, M.; Wheeler, W. W. (January 1997), "Linear Bijections and the Fast Fourier Transform", Applicable Algebra in Engineering, Communication and Computing 8 (2): 143–163, doi:10.1007/s002000050059
6. ^ Isaksen, Daniel C. (November 2002), "A Cohomological Viewpoint on Elementary School Arithmetic", The American Mathematical Monthly 109 (9): 796–805, doi:10.2307/3072368, retrieved January 22, 2014
7. ^ Borovik, Alexandre V. (2010), Mathematics under the Microscope: Notes on Cognitive Aspects of Mathematical Practice, AMS, pp. 87–88, ISBN 978-0-8218-4761-9
8. ^ Metropolis, N.; Gian-Carlo, Rota; Tanny, S. (May 1973), "Significance Arithmetic: The Carrying Algorithm", Journal of Combinatorial Theory, Series A 14 (3): 386–421, doi:10.1016/0097-3165(73)90013-7
9. ^ Faltin, F.; Metropolis, N.; Ross, B.; Rota, G.-C. (June 1975), "The Real Numbers as a Wreath Product", Advances in Mathematics 16 (3): 278–304, doi:10.1016/0001-8708(75)90115-2