GN⁺: 계산기 앱? 누구나 만들 수 있는 거자나요?
(chadnauseam.com)"계산기 앱? 누구나 만들 수 있는거자나" → 사실이 아님
- 계산기는 수학적 표현의 결과를 정확히 보여줘야 하고, 생각보다 훨씬 어려운 일임
- iOS의 계산기에서
(10^100) + 1 − (10^100)은0으로 잘 못 계산함 - 하지만 안드로이드는 올바르게 1이라고 나오는데, 이걸 어떻게 했는지는 정말 말도 안됨
Google과 Hans-J. Boehm
- Google은 유명한 프로그래머 Hans-J. Boehm을 고용함
- Boehm은 C++의 공유 변수 의미론을 정의한 전문가
- 하지만 그에게 주어진 임무는 예상 밖으로 계산기 앱 개발이었음
부동소수점의 문제
- 부동소수점 숫자는
0.3이나10^100같은 값을 정확히 표현할 수 없음 - 즉, 부동소수점을 기반으로 한 계산기는 신뢰할 수 없음
- 정확한 계산을 위해서는 다른 접근 방식이 필요함
Bignum을 이용한 해결책
- 정수 계산 문제는 Bignum(무한 정수)을 사용하여 해결 가능
- Bignum은 메모리 크기에 따라 동적으로 확장되는 정수 타입
-
(10^100) + 1 - (10^100)문제는 Bignum을 사용하면 해결됨 - 하지만 분수 연산은 해결되지 않음
분수와 대수적 숫자
- 분수(
3/4같은 값)는 Bignum을 사용하여 분자와 분모를 저장하면 해결 가능 - 그러나 원주율(π)이나 제곱근(√2) 같은 무리수는 표현할 수 없음
- Boehm은 다항식 기반의 표현을 시도함
- 예:
√2는x² - 2 = 0이라는 방정식으로 표현 가능 - 하지만 π는 이 방식으로도 표현할 수 없음
- 예:
구성적 실수(Constructive Real Numbers)
- Boehm은 "재귀적 실수 연산(RRA)" 개념을 탐구함
- 사용자가 원하는 정확도를 입력하면, 그 정확도 내에서 값을 계산하는 방식
- 예: π를
0.01오차 내에서 표현하면3.14를 반환함 - 하지만 이 방식은 정확한 비교를 어렵게 만듦
정확한 0을 표현하는 문제
- RRA 방식은
1 - 1을0이 아니라0.0000000001로 표현할 수도 있음 - 이는 사용자 경험(UX) 측면에서 문제가 됨
- Boehm은 다른 연구자들과 협력하여 해결책을 찾기 시작함
Richardson-Fitch 알고리즘
- 1994년 Dan Richardson과 John Fitch는 특정 연산 내에서 숫자 비교 문제를 해결함
- 하지만 이 알고리즘은 너무 느려서 현실적으로 사용 불가능함
- 예를 들어
1 ≠ 1 - e^(-e^1000)을 판별하는 데 우주의 원자 개수보다 많은 연산이 필요함
RRA와 유리수 연산의 조합
- Boehm은 RRA와 유리수 연산의 장점을 결합하는 아이디어를 떠올림
- 단순한 연산(예:
6 × 9또는8 / 3)에는 유리수 연산을 사용 - 무리수가 포함될 때만 RRA를 사용
- 결과적으로 숫자를 유리수 × 실수의 형태로 표현
기호적 표현(Symbolic Representation)
- π, √2 같은 특수 숫자는 RRA 대신 기호적 표현을 사용
- 예: π는 "π"라는 기호로 저장하고 필요할 때만 숫자로 변환
- 사칙연산뿐만 아니라, 삼각함수(sin, cos, tan), 로그, 지수 함수도 기호적 표현을 활용
최종 해결책
- 모든 숫자는 유리수 × 실수(기호적 표현 또는 RRA) 형태로 저장
- 가능한 경우 유리수 연산을 사용하여 정확도를 유지
- 기호적 표현을 최대한 활용하여 RRA 연산을 최소화
- 결과적으로 속도와 정확성의 균형을 맞춘 완벽한 계산기 시스템이 완성됨
결론
- Boehm과 그의 팀이 만든 Android 계산기는 단순한 프로그램이 아님
- 정확한 결과를 제공하면서도 빠르고 효율적인 알고리즘을 적용함
- "그냥 계산기 앱"이 아니라, 수학적으로 정교한 시스템임
"다음번에 Android 계산기를 사용할 때, 이 노력을 떠올려 보자!"
여담이지만 AI인 neo가 '거자나'로 번역했다는 게 흥미롭네요. 원문은 'Anyone could make that' 이라 장난스런 어감은 없는데 ㅎㅎ 찰떡이네요.
제가 학부생일때 8086보드를 손으로 납땜해서 만들고 숫자 자판과 텍스트 LCD를 연결해서 8086 어셈블리로 계산기(사칙연산만하는)까지 만드는 수업이 있었습니다.
보드만들고 자판과 LCD까지 연결해서 동작은 시켰지만 계산기는 못만들었어요.
그때는 제가 소프트웨어에 재능이 없다고 생각해서 하드웨어 엔지니어로 취직했는데 어쩌다보니 소프트웨어 개발을 하고 있습니다.
계산기 진짜 어려웠어요.
계산기 하면 저는 윈도우즈의 기본 계산기가 생각나네요. 2+2*2를 계산하면 6이 아니라 8이 나옵니다. 일부러 이렇게 만든 것 같긴 하지만 전혀 이해가 안 갑니다. 예전에 칵테일에 들어간 알콜 양을 계산했더니 알콜이 음료 총량보다 많이 나와서 당황한 기억이 있거든요
"계산기 앱? 누구나 만들 수 있는거자나" → 사실이 아님
이거 응용할 데가 무궁무진해 보이는데요 ㅋㅋㅋ
"파이썬? 완전 쉽자나" → 사실이 아님
"(10^100)+1−(10^100)"
오 정말 아이폰 계산기는 0, 안드로이드 계산기는 1로 뜨네요.
근데 정작 구글에 검색하면 0이라 뜨는군요...
Hacker News 의견
- 흥미로운 이야기임. 숫자를 표현하는 더 강력한 방법은 연분수로 표현하는 것임. 연분수는 실수와 유리수를 효율적으로 표현할 수 있음
- 재미있는 사실로, 오래되지 않은 수학 교과서에 따르면 연분수의 덧셈/곱셈 알고리즘은 존재하지 않을 가능성이 높다고 함. 그러나 1972년 Bill Gosper가 연분수는 산술에 완벽하게 적합하다고 증명했음
- 나는 reals라는 Python 라이브러리를 작업 중임. 이 라이브러리는 Decimal이나 Fraction 타입을 대체할 수 있도록 설계되었음. Bill Gosper의 기술을 사용하여 연분수를 조작함
- 링크가 짧아져서 클릭할 수 없는 것은 불행한 일임. 여기에 논문에 대한 실제 링크가 있음
- 제목을 읽자마자 웃음이 나왔음. IEEE 754는 최악이지만 다른 모든 것보다는 나음. 예제를 보자마자 Kahan summation이나 전체 컴퓨터 대수 시스템일 것이라고 생각했음. Recursive Real Arithmetic는 들어본 적이 없었음
- 초기 C++ 영웅 중 한 명에 대한 통찰력을 얻었음. 간단해 보이는 것들이 얼마나 깊을 수 있는지 상기시켜줌
- NYC 지하철 요금은 $2.90임. iOS에서 PCalc를 사용하여 남은 MetroCard 값을 계산했을 때 0이 아닌 -8.881784197E-16이 나왔음. Apple의 계산기를 사용할 때는 이런 일이 발생하지 않음
- 개발자에게 문의했더니 Apple은 자체 수학 라이브러리를 사용하고 있으며, 이를 대체할 다른 라이브러리를 찾아야 한다고 답변받음
- 거의 모든 사람이 완전한 계산기 앱을 만들지 않았음. TI-89 같은 완전한 계산기를 의미함
- Android에서 TI-89 계산기 에뮬레이터를 사용 중임. Android 앱 중 절반의 기능도 없고 잘 작동하지 않음
- RRA로 전환하는 것의 단점은 사용자 경험뿐만이 아님. 결과가 0.0000000...일 때, 계산기는 그 숫자의 역수를 계산할 수 있는지 결정할 수 없음
- 예를 들어, 1/(atan(1/5)-atan(1/239)-pi/4)는 "계산할 수 없음"을 출력함. 1/(atan(1/5)-atan(1/239)-pi/4+10^(-100000))을 시도해도 여전히 "계산할 수 없음"을 출력함
- 거의 모든 숫자는 IEEE 부동 소수점으로 표현할 수 없음. 무작위 숫자가 이론적으로 설명할 수 없는 확률이 약 100%일 수 있음
- 일부 문제는 bignums를 사용하면 피할 수 있음. 순간적인 존재적 불안이 해소됨
- 고급 TI 계산기, 예를 들어 TI-92가 이 시스템을 사용했는지 아는 사람 있음? '유리수' 모드가 있었고 RRA를 사용했을 가능성이 있음
- "recursive real arithmetic" (RRA)를 사용하는 방식이 Conal Elliot과의 훌륭한 토론을 떠올리게 함. 사물을 이산적으로 표현하는 것에서 연속적으로 표현하는 것으로 이동하는 것에 대해 이야기했음
- 예를 들어, 이전에는 글꼴을 픽셀 블록으로 표현했지만, 이제는 선/벡터로 인식됨. 컴퓨터 과학은 최신 상업 도구를 배우는 것뿐만 아니라 진실을 추구하는 것이어야 함
- Android Open Source Project의 계산기 소스 코드를 가지고 놀아봤음. Google이 이를 Google Play Services로 이전했지만, 오래된 소스는 여전히 사용 가능함
- 몇 가지 실제 문제를 해결하며, 라이브러리에서 사용할 수 있기를 바람. 이전 기사에서 몇 가지 라이브러리에 대한 논의가 있었음