1980년대에 학교를 다녔던 사람들은 계산의 효율을 위해서 '주판'이라고 하는 계산도구를 배웠다. 학창시절에는 암산을 잘하는 사람들이 '수학을 잘 한다'는 말을 배웠었고, 초등학교 수학과목이 '산수'라는 이름을 가졌을 정도로 계산이 중요하던 시기였다. 그래서 큰 숫자들도 수작업에 의해서 계산을 했었는데, 중학교 수준의 수학은 내용도 어려웠지만 그 계산법도 상당히 어려웠다. 계산기가 보편화되고 수학에 논리적 사고가 강조되면서 당시의 끔찍한 계산은 이제 교과과정에서 사라진지 오래다. 하지만, 당시의 계산은 프로그램화 하면 급하게 문제를 해결할 때 유용하게 사용할 수 있다.
여기서는 계산의 원리는 생략하고 과거에 했던 계산법과 그에 대응하는 소스코드를 소개한다.
1. 최대공약수, 최소공배수 구하기
요즘도 두 자리, 세 자리 수들 중에 약수를 알기 어렵지 않은 수를 가지고 최대공약수를 계산하는 문제는 흔히 볼 수 있다. 대체로는 다음과 같은 두 가지 방법을 배운다.
하지만, 숫자가 커져가면 이 작업은 긴 계산이 될 수 있다. 과거에는 이것을 유클리드 알고리즘을 이용해서 계산했다. 당시 교육과정에서 풀이를 쓰는 필기법이 통일되어 있지는 않았으나 아래 설명하려는 것과 크게 다르지는 않을 것이다.
수작업으로 최대공약수 구하기
1938과 304를 예로 든다. 우선은 다음과 같이 영역을 구분하고 두 숫자를 쓴다.
두 수중 작은 숫자로 큰 수를 나누는데, 몫과 나머지를 다음과 같은 형태로 쓴다.
이제, 114로 304를 나눈 몫과 나머지를 비슷한 방법으로 쓴다.
앞서 했던 방법으로 또 한번 하면 다음과 같고,
한 번 더하면 나누어 떨어지는 결과가 나온다.
이 경우 나누어 떨어지기 직전에 나왔던 나머지인 38이 두 수의 최대공약수이다.
Coding
위 계산도 숫자가 더 커지면 직접 계산하기에는 부담이 될 수 있다. 정수 크기에 제약이 없는 python을 이용해서 위 작업을 프로그램화 하면 다음과 같다.
def gcd(a,b):
return (b and gcd(b, a%b) or a)
a, b = map(int, input().split())
print(gcd(a,b))
2. 거듭제곱근 구하기
요즘은 제곱근의 근삿값을 손으로 구하는 일은 없다. 실제 계산해야 하는 경우에도 뉴튼방법과 같은 좋은 방법이 있어서 빠른 속도로 근삿값을 구해낼 수 있다. 하지만, 이것은 극한의 개념도 필요하고 해서 어린 학생들에게 가르치기에는 적당한 방법이 아니었다. 중학생들은 다음과 같은 방법으로 근삿값을 계산했다.
수작업으로 계산하기
제곱근의 근삿값은 중학교 과정에서 다음과 같은 방법을 써서 계산했다. $\sqrt{2}$를 예로 든다. 우선은 2보다 작은 제곱수가 1이므로 나눗셈을 하듯이 1을 2의 위, 아래를 적어주는데, 왼편에 1을 두 번 쓴다.
정수부분이 끝났으므로 나눗셈을 하는 것과 동일하게 소수점을 찍어주고, 왼편의 숫자는 더해서 그 결과를 밑에 적는다.
그리고, 2 뒤에 0을 두 개 추가해서 아래로 내려준다.
그리고, 아래 그림에 표시된 부분의 네모 안에 어떤 수를 넣어야(같은 수다) 100보다 작은지 그 최댓값을 생각해보면 4가 된다. 4를 제곱근기호와 왼쪽 네모 안에 차례로 써주고 곱한 결과는 100 아래에 써준다.
왼쪽은 더하고 오른쪽은 빼준다.
원하는 정밀도까지 앞의 과정을 반복한다.
이 방법은 뉴튼의 방법과 같은 계산보다 계산속도가 엄청나게 느리다는 단점이 있지만, 다른 근사법과는 달리 계산과정에서 이미 계산된 근삿값을 수정해야 할 필요가 없다.
활용
이 방법은 자릿수가 큰 정수가 제곱수인지 아닌지를 판단할 때 사용될 수 있다. 물론, 현대 프로그램 언어는 제곱근을 구하는 함수를 자체내장하고 있어서 불필요한 알고리즘 같아 보이지만, 입력자료에 제한이 있는 언어인 경우는 이 알고리즘을 활용하는 것도 생각해 볼 수 있다. 다음은 제곱수를 판별하는 C 소스코드다.
#include <stdio.h>
int isqrt (int num)
{
int isqrt = 0, digit = 1, temp, aux = 0, i;
while (digit <= num)
{
digit *= 100;
};
digit /= 100;
while(digit >= 1)
{
temp = num / digit;
aux = aux * 10;
i = 9;
while (temp < (aux + i) * i) i--;
isqrt = 10 * isqrt + i;
num = num - (aux + i) * i * digit;
digit /= 100;
aux = aux + 2 * i;
}
return isqrt;
}
int main()
{
int num, rt;
scanf("%d", &num);
rt = isqrt(num);
printf ((num == rt * rt) ? "yes\n" : "no\n");
return 0;
}
위 코드는 10진법을 사용해서 복잡해 보이지만, 이진법을 이용하면 2를 곱하는 것이 숫자의 자릿수 이동에 해당되므로 다음과 같은 코드도 가능하다. (위키피디아 참고)
#include <stdio.h>
int isqrt(int num)
{
int res = 0;
int bit = 1 << 30; // The second-to-top bit is set: 1 << 14 for 16 bits
// "bit" starts at the highest power of four <= the argument
while (bit > num)
bit >>= 2;
while (bit != 0)
{
if (num >= res + bit)
{
num -= res + bit;
res = (res >> 1) + bit;
}
else
res >>= 1;
bit >>= 2;
}
return res;
}
int main()
{
int num, rt;
scanf("%d", &num);
rt = isqrt(num);
printf ((num == rt * rt) ? "yes\n" : "no\n");
return 0;
}