자바스크립트 숫자 알고리즘

자바스크립트로하는 자료 구조와 알고리즘 - 배세민

자바스크립트의 숫자 체계 - 소수

소수 인수분해는 암호화에 기본이 되는 요소다.
자바스크립트는 숫자에 대해 64비트 부동소수점 표현을 사용한다.
(double-precision-numbers)
부호 비트(63번째 비트)가 1이면 해당 숫자는 음수다.
(0부터 시작하기에 63이 마지막 비트)
11개의 비트(62~52번째비트)는 지수 값 e를 나타낸다.
마지막으로 나머지 52비트가 분수 값을 나타낸다.

소수 값을 계산하는데에 있어 십진분수로 인해 자바스크립트의 부동소수점 체계가 반올림 오류를 일으킬 수 있다.

EX) 0.1 + 0.2 === 0.3 // output : false

0.1을 64비트 부동소수점 숫자로 제대로 표현할 수 없는 이유를 이해하기 위해서는 이진 표기법을 이해해야 한다. 이진 표기법으로 십진수를 표현할 때 무한 개의 수가 필요한 경우가 많기 때문이다.

이로 인해 이진수가 2의 n승으로 표현되는 것이다.
여기서 n은 정수다.
이진수로 0.1을 계산하려 할 때 긴 나눗셈이 끝나지 않고 계속될것이다.

자바스크립트 숫자 객체

다행히 자바스크립트에는 위와 같은 문제를 해결하는데 도움이 되는
Number 객체의 내장된 속성들이 있다.

Number.EPSILON

두 개의 표현 가능한 숫자 사이의 가장 작은 간격을 반환한다.
이는 부동소수점 근사치를 활용해 분수가 제대로 표현되지 않는
문제를 해결하는데 유용하다.

지수 뒤의 -number가 클수록 더 작은 숫자다.
EPSILON의 지수 뒤 -number는 -16이다.
0.1+0.2-0.3 === 0 은 false지만
0.1+0.2-0.3 === Number.EPSILON은 true이다.

어떤 계산식이 0이라는 결과가 나왔을 때, 직접적으로 0으로 비교하는것보다는
Number.EPSILON을 통해 비교하는것이 부동소수점을 사용하는 자바스크립트에서 더 정확하다.

숫자 크기의 순서

-Infinity < Number.Min.SAFE_INTEGER < 0 < Number.MIN_VALUE
 < Number.MAX_SAFE_INTEGER < Number.MAX_VALUE < Infinity

• Number.Min/Max.SAFE_INTEGER ?
  Infinity 이전의 표기할 수 있는 가장 크거나 작은 정수를 뜻한다.

• Min/Max_VALUE ?
  Infinity 이전의 표기할 수 있는 가장 크거나 작은 부동소수점을 뜻한다.

• MIN_VALUE가 0보다 큰 이유
  가능한 가장 작은 부동소수점이기 때문에 음수로 표현할 수 없다.

숫자 알고리즘 (소수 판별기)

소수의 정의

소수의 정의는 '1과 자기 자신으로밖에 나누어 떨어지지 않고 , 자기 자신의 곱셈의 역수가 없는 수'이다.

숫자가 소수인지 판단하는 알고리즘은 숫자와 관련된 가장 많이 논의된 알고리즘 중 하나이다.

소수 판별기

function isPrime(n){
    if(n <= 1){
	return false;
	}
for(let i = 2; i < n; i++){
	if( n % i == 0){
	return false;
	}
    }
    return true;
    }

위 코드의 시간 복잡도는 O(n)이다.
0부터 n까지의 모든 수를 확인하는 알고리즘이기 때문이다.

위의 알고리즘은 쉽게 개선이 가능한 알고리즘의 한 예다.
위의 함수가 2부터 n까지 어떤 식으로 순회하는지 생각해보자.
위의 알고리즘 수행 방식에서 패턴을 찾아 더 빠르게 만들 수 있지 않을까?
우선 2의 배수는 무시해도 된다.
하지만 이뿐만 아니라 최적화 가능한 부분이 더 있다

우선 소수를 나열해보자

소수

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 ...

2와 3을 제외하고, 모든 소수는 6k±1의 형태를 지닌다.(여기서 k는 정수다.) 확인

(6k±1) 5 = (6-1)

(6k±1) 7 = 1 * 6 +1

(6k±1) 13 = 2*6 + 1

또한 n이 소수인지 알아보기 위해 반복문을 n의 제곱근까지만 확인해보면 된다.
n의 제곱근이 소수가 아니면, n은 수학 정의에 의해 소수가 아니기 때문이다.

function isPrime(n){
	if(n <= 1) return false; //n은 자연수만 들어올 수 있다.
	if(n <= 3) return true; // 2,3은 소수이기에 true이다.

	if(n%2 == 0 || n%3 == 0 ){
		return false; 
    }

	//입력된 수가 2 또는 3인 경우 아래 반복문에서
 	//5개의 숫자를 건너 뛸 수 있다.

	for (let i = 5; (i * i) <= n; i = i + 6){
	if (n % i == 0 || n % ( i + 2 ) == 0){
		return false;
   		}
    }
   return true;
  }

for (let i = 5; (i * i) <= n; i = i + 6){
if(n % i == 0 || n % ( i + 2 ) == 0)

이러한 반복문을 대입한 이유는 모든 소수는 6k ± 1의 형태를 갖고 있기 때문에
풀어 쓴다면 위와 같이 나타낼 수 있기 때문이다.

• Math.abs() 절대값을 반환한다