Carry (arithmetic)

기본 산술(elementary arithmetic)에서, 올림(carry)은 자릿수의 한 열(column)에서 더 많은 유효 자릿수의 또 다른 열로 전달하는 자릿수(digit)입니다. 그것은 가장 오른쪽 자릿수부터 시작하여 왼쪽으로 연산함으로써 숫자를 함께 더하기(add) 위한 표준 알고리듬(algorithm)의 일부입니다. 예를 들어, 6과 7이 더해져서 13을 만들 때, "3"은 같은 열에 쓰고 "1"은 왼쪽으로 올리게 됩니다. 빼기에 사용될 때, 그 연산은 빌림(borrow)이라고 불립니다.

올림은 전통적 수학(traditional mathematics)에서 강조되고, 반면에 개정 수학(reform mathematics)을 기반으로 하는 교과과정은 정답을 찾기 위한 임의의 구체적인 방법을 강조하지 않습니다.

올림은 고등 수학에서 마찬가지로 몇 번 모습을 보입니다. 컴퓨팅에서, 올림은 덧셈기(adder) 회로의 중요한 함수입니다.

Manual arithmetic

Example: The addition of two decimal numbers

올림의 전형적인 예제는 다음과 같은 연필-과-종이 덧셈에 있습니다:

  ¹
  27
+ 59
----
  86

7 + 9 = 16이고, 자릿수 1은 올림입니다.

그 반대는 다음에서 처럼 빌림입니다:

 ⁻¹
  47
− 19
----
  28

여기서, 7 − 9 = −2이므로, (10 − 9) + 7 = 8를 시도하고, 10은 왼쪽에 다음 자릿수에서 1 ("빌림")을 취함으로써 얻습니다. 이것을 일반적으로 가르치는 두 가지 방법이 있습니다:

십은 왼쪽 다음 자릿수에서 이동되고, 이 예에서 십-열에 3 − 1을 남깁니다. 이 방법에 따르면, 용어 "빌림"은 오명칭(misnomer)인데, 왜냐하면 십은 결코 갚지 않기 때문입니다.
십은 왼쪽 다음 자릿수에서 복사되고, 그런-다음 '빌려온' 열에서 감수에 그것을 더함으로써 '되 갚게' 됩니다. 이 예제에서 십 열에 4 − (1 + 1)을 제공합니다.

Mathematics education

전통적으로, 올림은 초등학교 2학년 또는 1학년 말에 여러-자릿수 숫자의 덧셈에서 가르칩니다. 어쨌든, 20세기 후반부터, 미국에서 개발된 TERC와 같이 널리 채택된 많은 교육 과정은 전통적인 올림 방법의 지침서를 생략하고 발명된 산술(invented arithmetic) 방법과 색칠, 조작, 및 차트를 사용하는 방법을 선호합니다. 이러한 누락은 Mathematically Correct와 같은 그룹에서 비판을 받았었고, 일부 주와 지역에서는 이 실험을 포기했지만, 그것은 여전히 널리 사용됩니다.

Higher mathematics

쿠머의 정리(Kummer's theorem)는 밑수 $p$ 에서 두 숫자를 더하는 것과 관련된 올림의 숫자는 특정 이항 계수(binomial coefficient)를 나누는 $p$ 의 가장 높은 거듭제곱의 지수와 같다고 말합니다.

많은 자릿수의 여러 무작위 숫자가 더해질 때, 올림 자릿수의 통계는 오일러 숫자(Eulerian number)와 리플 셔플 순열(riffle shuffle permutation)의 통계와 예기치 않은 연결을 갖습니다.^[1]^[2]^[3]^[4]

추상 대수학(abstract algebra)에서, 두-자릿수 숫자에 대해 올림 연산은 그룹 코호몰로지(group cohomology)의 언어를 사용하여 공식화될 수 있습니다.^[5]^[6]^[7] 이 관점은 실수(real number)의 대안적인 특성화에 적용될 수 있습니다.^[8]^[9]

Mechanical calculators

올림은 기계식 계산기(mechanical calculator)의 설계자와 제작자에게 직면된 기본 과제 중 하나입니다. 그들은 두 가지 기본적인 어려움에 직면해 있습니다: 첫 번째 문제는 올림은 변경하기 위해 여러 자릿수를 요구할 수 있다는 사실에서 비롯됩니다: 1에 999를 더하기 위해, 그 기계는 4 다른 자릿수를 증가해야 합니다. 또 다른 문제는 다음 자릿수가 덧셈 연산을 완료하기 전에 올림이 "발현될" 수 있다는 사실입니다.

대부분의 기계식 계산기는 덧셈 자체 후에 별도의 올림 주기를 함으로써 올림을 구현합니다. 덧셈 동안, 각 올림은 수행되는 것이 아니라 "신호"되고, 올림 주기 동안, 기계는 "촉발된" 자릿수 위로 자릿수를 증가시킵니다. 이 연산은 일 자릿수부터 시작하여, 그런-다음 십, 백, 등의 순차적으로 수행되어야 하는데, 왜냐하면 올림을 더하면 다음 자릿수에 새로운 올림을 생성할 수 있기 때문입니다.

일부 기계는, 특히 파스칼의 계산기(Pascal's calculator)는 두 번째로 제작된 것으로 알려진 계산기이자 가장 오래 살아남은 것이며, 다른 방법을 사용합니다: 자릿수를 0에서 9로 증가시키고, 에너지를 저장하기 위해 기계 장치를 작동시키고, 자릿수를 9에서 0으로 이동하는 다음 증가는 다음 자릿수를 1씩 증가시키기 위해 이 에너지를 방출합니다. 파스칼은 그의 기계에서 추와 중력을 사용했습니다. 유사한 방법을 사용하는 또 다른 주목할만한 기계는 매우 성공적인 19세기 캄토미터(Comptometer)로, 이것은 추를 스프링으로 대체했습니다.

일부 혁신적인 기계는 연속 전송을 사용합니다: 임의의 자릿수에 1을 더하고, 다음 자릿수를 1/10만큼 전진시킵니다 (이것은 차례로 다음 숫자를 1/100로 전진시키고, 이런 식으로 계속됩니다). 일부 혁신적인 초기 계산기, 특히 1870년에서 체비쇼프(Chebyshev) 계산기와,^[10] 1886년의 셀링(Selling)에^[11] 의한 디자인이 이 방법을 사용했지만 둘 다 성공하지 못했습니다. 1930년 초, 마숑 계산기(Marchant calculator)는 적절한 이름-지은 "Silent Speed" 계산기를 시작으로 연속 전송을 크게 성공적으로 구현했습니다. 마숑 (나중에 SCM Corporation이 됨)은 1960년대 후반부터 기계식 계산기 시대가 끝날 때까지 이를 계속 사용하고 개선하여 타의 추종을 불허하는 속도로 연속 전송 계산기를 만들었습니다.

Computing

덧셈기와 같은 디지털 회로를 말할 때, 단어 캐리(carry)는 역시 비슷한 의미로 사용됩니다.

대부분의 컴퓨터(computer)에서, 산술 연산의 최상위 유효 비트로부터의 올림 (또는 시프트 연산에서 시프트된 비트)는 다중 정밀도 산술을 위한 캐리-인으로 사용되거나 컴퓨터 프로그램의 실행을 제어하기 위한 테스트와 사용될 수 있는 특수 캐리 비트에 배치됩니다. 같은 캐리 비트는 일반적으로 뺄셈에서 빌림을 나타내기 위해 사용되지만, 이의 보수(two's complement) 산술의 영향으로 인해 비트의 의미가 반전됩니다. 통상적으로, "1"의 캐리 비트 값은 덧셈이 ALU를 오버플로했음을 의미하고, CPU의 그것보다 긴 길이의 데이터 워드를 추가할 때 고려되어야 합니다. 빼는 연산에 대해, 대부분의 기계가 빌릴 때 캐리 플래그를 설정하고 반면에 일부 기계 (예를 들어 6502와 PIC)는 대신에 빌릴 때 캐리 플래그를 재설정하기 때문에 (반대의 경우도 마찬가지) 두 가지 (반대) 규칙이 사용됩니다.

References

^ Holte, John M. (February 1997), "Carries, Combinatorics, and an Amazing Matrix", The American Mathematical Monthly, 104 (2): 138–149, doi:10.2307/2974981, JSTOR 2974981
^ Diaconis, Persi; Fulman, Jason (August 2009), "Carries, shuffling, and symmetric functions", Advances in Applied Mathematics, 43 (2): 176–196, arXiv:0902.0179, doi:10.1016/j.aam.2009.02.002
^ 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, arXiv:0904.3740, doi:10.1090/S0273-0979-2010-01306-9
^ 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
^ 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
^ Isaksen, Daniel C. (November 2002), "A Cohomological Viewpoint on Elementary School Arithmetic" (PDF), The American Mathematical Monthly, 109 (9): 796–805, doi:10.2307/3072368, JSTOR 3072368, archived from the original (PDF) on January 16, 2014, retrieved January 22, 2014
^ 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
^ 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
^ 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
^ Roegel, Denis (2015). "Chebyshev's continuous adding machine" (PDF). Archived (PDF) from the original on 2017-08-09.
^ Ernst, Martin (1925). The Calculating Machines (PDF). Charles Babbage Institute. p. 96.

External links

Weisstein, Eric W. "Carry". MathWorld.
Weisstein, Eric W. "Borrow". MathWorld.
Carrying - nLab

[1] Holte, John M. (February 1997), "Carries, Combinatorics, and an Amazing Matrix", The American Mathematical Monthly, 104 (2): 138–149, doi:10.2307/2974981, JSTOR 2974981

[2] Diaconis, Persi; Fulman, Jason (August 2009), "Carries, shuffling, and symmetric functions", Advances in Applied Mathematics, 43 (2): 176–196, arXiv:0902.0179, 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, arXiv:0904.3740, 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" (PDF), The American Mathematical Monthly, 109 (9): 796–805, doi:10.2307/3072368, JSTOR 3072368, archived from the original (PDF) on January 16, 2014, 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

[10] Roegel, Denis (2015). "Chebyshev's continuous adding machine" (PDF). Archived (PDF) from the original on 2017-08-09.

[11] Ernst, Martin (1925). The Calculating Machines (PDF). Charles Babbage Institute. p. 96.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]