El-Gamal Encryption

ENCRYPTION 2018. 12. 5. 02:09

El-Gamal.zip


일단 해당 프로젝트에는 문제가 좀 있다. 주어진 h' 은 소수인데다가 그에 맞는 X'a  를 구하라니.... X'a = Xa mod q 값이라고 하는데,

문제에서의 Xa 값은 log 정리에 의할경우 g의 Xa 승 = h 로 기반이 되는데...



로그 3의 ....... 하면

39.99 가 나온다.... Secret Key 로 근사값을 사용하는가...?


모순 덩어리인 문제이다.

'ENCRYPTION' 카테고리의 다른 글

El-Gamal Encryption  (0) 2018.12.05
machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
C Program to Implement Sieve of eratosthenes to Generate Prime Numbers Between Given Range  (0) 2018.12.03
블로그 이미지

remoted

Remoted's IT LAB & POST DATABASE

댓글을 달아 주세요

machine epsilon

ENCRYPTION 2018. 12. 5. 02:05

85.4 실수 자료형의 오차

부동소수점 방식은 실수를 정확히 표현할 수 없는 문제가 있습니다. 다음 내용을 소스 코드 편집 창에 입력하고 실행해봅니다.

float_rounding_error.c

#include <stdio.h>

int main()
{
    float num1 = 0.0f;
    float num2 = 0.1f;

    // 0.1을 10번 더함
    for (int i = 0; i < 10; i++)
    {
        num1 = num1 + num2;
    }

    printf("%.15f\n", num1);    // 1.000000119209290: 1.0이 나와야 하지만 반올림 오차 발생

    return 0;
}

실행 결과

1.000000119209290

분명 0.1을 10번 더했으므로 1.0이 나와야 하는데 1.000000119209290이 나왔습니다. 왜냐하면 수학적으로 실수는 무한히 많은데 이 실수를 유한 개의 비트로 표현하기 위해서는 근삿값으로 표현해야 하기 때문입니다. 이런 문제를 부동소수점 반올림 오차(rounding error)라고 합니다.

printf에서 소수의 자릿수를 좀 더 많이 표시하고 싶다면 %.15f처럼 서식 지정자에 자릿수를 지정해주면 됩니다. 여기서는 15를 지정했으므로 소수점 이하 15자리를 표시합니다.

다음과 같이 실수는 연산한 값을 == (같음)으로 직접 비교하면 안 됩니다. 이 부분은 초보들이 흔히 하는 실수입니다. 꼭 기억해두세요.

float_equality_comparison.c

#include <stdio.h>

int main()
{
    float num1 = 0.0f;
    float num2 = 0.1f;

    // 0.1을 10번 더함
    for (int i = 0; i < 10; i++)
    {
        num1 = num1 + num2;
    }

    // num1: 0.100000001490116
    if (num1 == 1.0f)         // 반올림 오차가 발생하므로 실수는 ==로 비교하면 안됨
        printf("true\n");
    else
        printf("false\n");    // num1은 1.0이 아니므로 false 출력

    return 0;
}

실행 결과

false

이미 연산한 결과에서 반올림 오차가 발생해버렸기 때문에 등호로 직접 비교하면 잘못된 결과가 나오게 됩니다.

오차를 감안하여 실수를 비교하려면 다음과 같이 FLT_EPSILON을 사용해야 합니다.

float_epsilon_comparison.c

#include <stdio.h>
#include <float.h>    // float의 머신 엡실론 값 FLT_EPSILON이 정의된 헤더 파일
#include <math.h>     // float의 절댓값을 구하는 fabsf 함수를 위한 헤더 파일

int main()
{
    float num1 = 0.0f;
    float num2 = 0.1f;

    // 0.1을 10번 더함
    for (int i = 0; i < 10; i++)
    {
        num1 = num1 + num2;
    }

    // num1: 1.000000119209290
    if (fabsf(num1 - 1.0f) <= FLT_EPSILON)    // 연산한 값과 비교할 값의 차이를 구하고 절댓값으로
                                              // 만든 뒤 FLT_EPSILON보다 작거나 같은지 판단
                                              // 오차가 머신 엡실론 이하라면 같은 값으로 봄

        printf("true\n");    // 값의 차이가 머신 엡실론보다 작거나 같으므로 true
    else
        printf("false\n");

    return 0;
}

실행 결과

true

먼저 연산한 값과 비교할 값의 차이를 구한 뒤 FLT_EPSILON보다 작거나 같은지 판단합니다. 값의 차이는 math.h헤더 파일의 fabsf 함수를 사용하여 절댓값으로 만들면 음수가 나오더라도 정상적으로 판단할 수 있습니다.

FLT_EPSILON은 float.h 헤더 파일에 정의되어 있으며 이 값을 머신 엡실론(machine epsilon)이라 부릅니다. 어떤 실수를 가장 가까운 부동소수점 실수로 반올림하였을 때 상대 오차는 항상 머신 엡실론 이하입니다. 즉, 머신 엡실론은 반올림 오차의 상한값이며 연산한 값과 비교할 값의 차이가 머신 엡실론보다 작거나 같다면 두 실수는 같은 값이라 할 수 있습니다. 만약 doublelong double을 사용한다면 머신 엡실론은 DBL_EPSILONLDBL_EPSILON을 사용합니다.

읽을거리

엑셀 2007에서는 850 *77.1을 계산하면 65535가 나와야 하지만 100000이라는 수가 나오는 버그가 있습니다. 부동소수점의 특성으로 인해 숫자를 문자로 바꾸는 도중 버그가 발생한 재미있는 사례입니다. 버그에 대한 자세한 분석 내용은 조엘 온 소프트웨어 웹 사이트에서 볼 수 있습니다.


'ENCRYPTION' 카테고리의 다른 글

El-Gamal Encryption  (0) 2018.12.05
machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
C Program to Implement Sieve of eratosthenes to Generate Prime Numbers Between Given Range  (0) 2018.12.03
블로그 이미지

remoted

Remoted's IT LAB & POST DATABASE

댓글을 달아 주세요

C round-off problem

ENCRYPTION 2018. 12. 5. 02:04

C 프로그래밍 입문/부동소수형 데이터

둘러보기로 가기검색하러 가기

부동소수형 데이터[+/-]

부동소수형(floating point number type)을 일반적으로 수학에서 사용되는 용어로 바꾼다면 '실수'-소수점이 있는 숫자를 말한다. 가장 익숙한 실수의 예는 '3.141592' 일 것이다. 컴퓨터에서 소수점을 갖는 실수를 다루는 방법은 두 가지가 있다. '고정소수형'과 '부동소수형'인데, 고정 소수형은 소수점의 위치가 정해져 있어서 소수점 이상의 자릿수와 소수점 이하 자릿수가 제한 되어있는 방법이고, 부동소수형은 소수점 위치가 정해져있지 않고, 소수점이 없는 값과 소수점의 위치를 표기하는 방법이다.[1]사실 '부동소수형'이라는 단어는 사람을 헷갈리게 만드는 단어중 하나 인데, '부동(浮動)'이라는 거의 사용되지 않는 단어를 사용하기 때문 일 것이다.[2] '부동소수형'이라는 단어를 들으면 마치 소수점이 꼼짝 않고 제자리에 있다는 의미로 이해 될 텐데, 실제는 '소수점이 떠다니는'이라는 의미이다.

C에서 사용할 수 있는 부동 소수형은 다음과 같다:

타입바이트수유효자리수(정수부)[3]최소허용값/최대허용값[4]설명
float424 (6)1.175494351 E - 38
3.402823466 E + 38
단일 정밀도 부동소수 (single precision)
double853 (15)2.2250738585072014 E - 308
1.7976931348623158 E + 308
두배 정밀도 부동소수 (double precision)
long double16[5]113 (33)3.36210314311209350626267781732175260 E - 4932
1.18973149535723176508575932662800702 E + 4932
사배 정밀도 부동소수 (quadruple precision)
float _Complex[6]8단일 정밀도 복소수
double _Complex16두배 정밀도 복소수
long double _Complex32사배 정밀도 복소수
float _Imaginary단일 정밀도 허수
double _Imaginary두배 정밀도 허수
long double _Imaginary사배 정밀도 허수

부동소수형 데이터와 관련된 정의는 <float.h>파일에 있으며, 관련된 구체적인 값을 알고 싶다면 이 파일을 확인해 보면 된다. 실제로 부동소수형은 지수부와 가수부로 나뉘어 저장되고 처리 되기 때문에 자리수나 최소/최대값은 의미가 없다. 중요한 것은 소수점 이하 몇자리 까지 정확하게 연산이 되는가 하는 점 인데, 실상은 C 컴파일러/라이브러리에서 제공하는 연산능력은 그다지 정밀하지 않기 때문에 보통은 별도의 연산 라이브러리를 사용하는 경우가 다반사이다.

수학연산을 위한 함수들의 정의는 <math.h>에 정의되어 있으며, 자릿수가 많은 연산을 해야 하는 경우에는 별도의 라이브러리를 사용한다. 대표적인 큰 수 연산을 위한 라이브러리로는 GMP(GNU MP Bignum Library)가 있다.

복소수 표기는 수학에서 표기하는 것과 동일하게 '1.0 + 2.0i'라는 형식으로 표기한다. 추가적으로 일관성 있는 표기를 위해 _Complex_I와 I 라는 매크로가 제공된다. 이 매크로는 <complex.h>에 정의되어 있기 때문에 매크로를 사용 하려면 이 헤더 파일을 소스에 포함 시켜야 한다. <complex.h>가 제대로 포함되어 있다면 '1.0 + 2.0i'를 '1.0 + 2.0 * _Complex_I' 혹은 '1.0 + 2.0 * I' 라는 형태로 사용할 수 있다. 복소수나 허수를 위한 수학연산 함수는 별도로 존재한다. 복소수를 위한 연산 함수들은 <complex.h>에 정의되어 있다.

허수(imagenary)는 실제로 복소수에서 실수부가 없는 수를 말하기 때문에 _Imaginary 타입이 정의되어 있지 않은 컴파일러도 있다[7]. 다음은 복소수를 사용한 연산의 예이다:

 1 #include <stdio.h>
 2 #include <float.h>
 3 
 4 int main(int argc, char *argv[])
 5 {
 6 	double _Complex a = 3.4 + 2.7i;
 7 	double _Complex b = 0.0 + 2.0i;
 8 
 9 	printf("The complex number: (%6.4f, %6.4f)\n", a);
10 	printf("The imaginary number: (%6.4f, %6.4f)\n", b * b);
11 	return 0;
12 }
참고:

C++ 에서는 복소수를 표현하기 위해 complex 라는 타입을 별도로 가지고 있습니다.

부동소수형 상수를 표기할 때 표기 방법은 두 가지 방법이 있다. 하나는 일반적으로 쓰는 부동소수점 표기 방법과 과학에서 표기할 때 쓰는 표기 방법이다. 다음의 두 수는 같은 값을 다른 방법으로 표기한 것이다.

0.0012
1.2e-3

기본적으로 부동소수형 상수는 double 타입으로 간주되며, float 타입의 상수가 필요한 경우에 f나 F접미사를 사용하여 해당 상수가 float 타임임을 분명히 할 수 있다. 마찬가지로 long double 타입의 상수가 필요한 경우에는 l혹은 L접미사를 지정함으로서 해당 상수가 long double 타입으로 다루어 지도록 할 수 있다. 다음은 각각의 타입에 해당되는 접미사를 사용하여 상수의 타입을 변환하는 것을 확인할 수 있는 프로그램이다.

 1 #include <stdio.h>
 2 int main(int argc, char * argv[])
 3 {
 4     printf("The size of float constant: %d\n", sizeof(1.2f));
 5     printf("The size of double constant: %d\n", sizeof(1.2));
 6     printf("The size of long double constant: %d\n", sizeof(1.2l));
 7     printf("The size of float complex constant: %d\n", sizeof(1.2f + 1.2if));
 8     printf("The size of double complex constant: %d\n", sizeof(1.2 + 1.2i));
 9     printf("The size of long complex constant: %d\n", sizeof(1.2l + 1.2il));
10     return 0;
11 }
참고: 부동소수의 오버플로우와 언더플로우

float형의 최대값이 3.402823466E+38 라고 위에서 언급 했는데 만약 그 값에 10을 곱하면 어떻게 될 것인가? 라는 의문을 가진 독자가 혹시 있을지 모르겠다. 이런 경우를 overflow라고 하며, 반대의 경우 underflow가 발생한다. 컴파일러에 따라 반응 방식이 다르긴 하겠지만 underflow인 경우에는 일반적으로 0으로 대체한다. overflow의 경우에는 최근의 컴파일러들은 무한대 값을 나타내는 inf(infinite)상수로 값이 지정되며, 이전의 컴파일러 들은 실행시간 에러를 발생시키며 프로그램을 정지시킨다.

무한대를 나타내는 inf상수는 inf와 -inf 두 가지가 있다.

참고: 반올림 오차(round-off error)

먼저 다음 프로그램을 보자, 입력해서 실행하기 전에 출력결과가 무엇이 나올지 예측해 본 후 실행해서 결과를 보자:

#include <stdio.h>
int main (int argc, char *argv[]) {
        volatile float a, b;
        a = 3402823466.0 + 1.0;
        b = a - 3402823466.0;
        printf ("%f\n", b);
        return 0;
}
  • 지정자 volatile은 궂이 입력하지 않아도 정상적으로 동작하겠지만, 혹시라도 출력결과가 1.0이 나온 독자는 volatile을 넣고 다시 실행시켜 보기를 바랍니다.[8]

float 아마 예측한 출력값은 1.0이었겠지만 실제 출력값은 전혀 예측하지 못한 값이 출력되었을 것 이다. 그 이유는 부동소수를 컴퓨터 내부에 표기하기 위해 부동소수의 값을 지수부와 가수부로 나누어 저장하도록 되어있는데, 일반적으로 float 타입은 가수부를 위해 10진수를 기준으로 6자리에서 7자리 정도를 저장할 공간만을 할애하고 나머지는 지수부와 부호를 표시하기 위해 사용된다. 그렇기 때문에 그 한계를 넘어가는 연산을 수행하려고 한 경우 연산결과가 가수부에서 표현 불가능한 값이 되어버리고 만다. 부동소수형의 연산결과가 전혀 예상치 못한 결과를 낳게되는 다른 원인도 있는데, 지수부에 사용될 메모리 공간이 부족한 경우 가수부의 공간 일부를 가져다 쓰는 경우도 있기 때문에 부동소수 연산을 어떻게 구현했느냐에 따라 같은 자리올림 에러에 의한 값이라 해도 다르게 나올 수 있다.

실제로 C라는 언어는 정밀한 연산을 위해 만들어진 언어가 아니라 기계 -- 컴퓨터 하드웨어를 가능하면 효율적으로 동작하는 프로그램을 만들기 위해 만들어진 언어이기 때문에 정확한 실수연산을 하고자 한다면 다른 언어 - 예를 들자면 과학기술 계산용으로 만들어진 포트란(Fortran)을 이용해야 정확한 연산 결과를 얻을 수 있다. C에서 포트란이 제공하는 정밀한 실수연산 기능을 사용하고 싶다면 포트란으로 만들어진 함수를 C에서 호출해서 사용하는 방법도 있다. 포트란 함수를 C에서 호출하는 방법을 알고자 하는 사람은 포트란 함수를 C에서 호출하는 방법을 참조하기 바란다.

주석 및 참고 자료[+/-]

  1.  엄밀하게 말하면 정확한 설명은 아닙니다만 이해를 돕기 위해 대략적인 이야기만 썼습니다. 또한 부동소수형 표기법에 관한 자세한 내용을 알기 원한다면 표준 문서 IEC 60559:1989, Binary floating-point arithmetic for microprocessor systems (previously designated IEC 559:1989)를 찾아 보거나, IEEE 754와 관련된 내용을 인터넷에서 찾아 보시기 바랍니다.
  2.  아마도 이는 일본에서 건너온 잔재가 남아있는 것 이거나 오래전에 수학 교재들이 번역되어야 했던 시절에 선택된 단어가 그대로 사용되기 때문이 아닐까 합니다.
  3.  정수부와 소수부 모두를 합한 자리수를 의미하며, 유효자리수는 시스템마다, 컴파일러마다 다릅니다.
  4.  최소허용값이나 최대 허용값은 실제로 큰 의미는 없습니다.
  5.  long double 타입은 시스템마다 정의된 자리수가 약간씩 다릅니다. 경우에 따라 double과 동일하게 8 바이트로 처리하는 경우도 있고, 10 바이트로 처리 하는 경우도 있고, 3배 정밀도 부동소수라 하여 12 바이트로 처리하는 경우도 있습니다.
  6.  _Complex와 _Imaginary 타입은 C99에서 도입 되었습니다.
  7.  joshuajh: 제 경우에는 아직 _Imagenary를 구현한 컴파일러를 확인한 적은 없습니다. 수학연산에 관한 관심은 대부분 정수쪽에 집중되어 있는 관계로 지금 당장 테스트 해 볼 수 없는, 이전에 사용했던 컴파일러들이 _Imaginary 타입을 구현 했는지 아닌지에 대해 아는바가 없습니다.
  8.  volatile은 필요없는 코드 이지만 혹시라도 컴파일러가 최적화를 수행하면서 의미 의미 없다고 보여지는 코드를 제거하는 경우를 배제하기 위해, 노파심에서 코드를 끼워 넣었습니다. 개인적으로 알고있는 컴파일러 중 volatile을 넣어야 하는 컴파일러는 없지만 그래도 혹시나 하는 마음에 끼워 넣었습니다.


'ENCRYPTION' 카테고리의 다른 글

El-Gamal Encryption  (0) 2018.12.05
machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
C Program to Implement Sieve of eratosthenes to Generate Prime Numbers Between Given Range  (0) 2018.12.03
블로그 이미지

remoted

Remoted's IT LAB & POST DATABASE

댓글을 달아 주세요

출처: http://www-128.ibm.com/developerworks/kr/library/l-memory/

메모리 관리

구현 선택, 구현의 모순, 동적 할당
난이도 : 중급

Jonathan Bartlett, 기술 디렉터, New Media Worx

2004 년 11 월 16 일

리눅스 프로그래머들이 사용할 수 있는 메모리 관리 기술을 살펴본다. C 언어 중심으로 설명 하겠지만 다른 언어들에도 적용할 수 있다. 메모리 관리가 어떻게 수행되는지, 메모리를 수동으로 관리하는 방법, 카운팅(counting) 또는 풀링(pooling)을 반-수동으로 관리하는 방법, 가비지 컬렉션을 사용하여 메모리를 자동으로 관리하는 방법을 설명한다.

메모리가 관리되어야 하는 이유

메모리 관리는 컴퓨터 프로그래밍의 가장 근본적인 분야 중 하나이다. 스크립팅 언어의 경우 메모리가 관리되는 방법을 신경 쓸 필요는 없지만 그것이 메모리 관리가 덜 중요하다는 것을 의미하는 것은 아니다. 메모리 매니저의 능력과 한계를 아는 것이 효과적인 프로그래밍에 있어 중요하다. C와 C++ 같은 시스템 언어들 경우, 메모리 관리가 필요하다. 이 글에서는 수동, 반자동, 자동 메모리 관리 방법의 기초를 설명하겠다.

Apple II에서 어셈블리 언어 프로그래밍을 하던 시절, 메모리 관리는 큰 문제가 아니었다. 기본적으로 전체 시스템을 실행했다. 시스템이 어떤 메모리를 갖고 있는지는 문제가 아니었다. 얼마나 많은 메모리가 남아있는지 파악할 필요도 없었다. 모든 컴퓨터는 같은 양의 메모리를 갖고 있었기 때문이다. 따라서 메모리 요구사항에 거의 변화가 없다면 사용할 메모리 영역을 선택하여 사용했다

하지만 프로그램의 각 부분에 얼마나 많은 메모리가 필요한지 알지 못한다면 간단한 컴퓨터일지라도 문제가 있었다. 제한된 공간과 메모리 요구가 다양하다면 다음의 요구사항을 충족시킬 방법이 필요하다:

  • 데이터를 처리할 메모리의 양을 결정한다.
  • 사용할 수 있는 메모리에서 메모리 섹션을 확보한다.
  • 메모리 섹션을 사용 가능한 메모리 풀로 리턴하여 프로그램의 다른 부분 또는 다른 프로그램에서 사용할 수 있도록 한다.

이러한 요구사항을 해결하는 라이브러리를 할당자(allocators)라고 한다. 문제가 동적일수록 메모리 관리는 더욱 중요하고 메모리 할당자의 선택이 더욱 중요해진다. 메모리 관리에 사용할 수 있는 다른 방법을들 보도록 하자.




위로



C-스타일의 메모리 할당자(allocator)

C 프로그래밍 언어는 위 세 가지 요구사항을 수행하기 위해서 두 개의 함수를 제공한다:

  • malloc: 주어진 바이트 수를 할당하고 여기에 포인터를 리턴한다. 사용할 수 있는 충분한 메모리가 없다면 null 포인터를 리턴한다.
  • free: malloc에 의해 할당된 메모리 조각에 대한 포인터를 취해, 프로그램이나 OS가 나중에 사용할 수 있도록 이를 리턴한다. (실제로, 몇몇 malloc 구현은 메모리를 OS가 아닌 프로그램으로 리턴할 수 있다.)

물리적 메모리와 가상 메모리

자신의 프로그램 안에서 메모리가 할당되는 방법을 이해하려면 OS로 부터 프로그램으로 메모리가 어떻게 할당되는 지를 이해해야 한다. 컴퓨터 상의 각 프로세스는 모든 물리적 메모리에 액세스 했다고 생각한다. 분명, 동시에 다중의 프로그램을 실행하기 때문에 각 프로세스는 모든 메모리를 가질 수 없다. 프로세스는 가상 메모리를 사용하고 있다.

예를 들어, 프로그램이 메모리 주소 629에 액세스한다고 해보자. 하지만 가상 메모리 시스템은 629 RAM 위치에 이를 반드시 저장할 필요는 없다. 사실 RAM에 존재할 필요도 없다. 물리적 RAM이 꽉 찼다면 디스크로 옮겨질 수도 있다. 주소가 메모리가 할당된 물리적 장소를 반드시 반영할 필요는 없기 때문에 이를 가상 메모리라고 한다. OS는 가상 주소 대 물리적 주소 테이블을 관리하여 컴퓨터 하드웨어가 주소 요청에 적절히 대응할 수 있도록 한다. 그리고, 주소가 RAM이 아닌 디스크상에 있다면 OS는 일시적으로 프로세스를 중지하고 메모리를 디스크에서 언로드(unload)하고 디스크에서 그 요청된 메모리에 로딩하고 프로세스를 재시작 한다. 이러한 방식으로 각 프로세스는 고유의 주소 영역을 갖고 실행하고 물리적으로 설치된 것 보다 많은 메모리에 액세스 할 수 있다.

32-bit x86 시스템상에서, 각 프로세스는 4 GB 메모리에 액세스 할 수 있다. 요즘, 대부분의 사람들은 자신들의 시스템에 4GB 메모리를 갖추고 있지 않다. swap을 포함하더라도 프로세스 당 4GB 이하이다. 따라서, 프로세스가 로딩되면 특정 주소로 초기 메모리 할당이 이루어지고 시스템 브레이크(system break)를 호출한다. 과거에 이것은 언매핑(unmapped) 메모리이다. 즉 RAM 또는 디스크에 상응하는 물리적 위치를 할당 받지 못한 메모리이다. 따라서 프로세스가 초기 할당부터 메모리가 부족하면 OS가 더 많은 메모리를 매핑하도록 요청해야 한다. (매핑은 수학용어로 일대일(one-to-one) 대응을 의미한다-메모리는 가상 주소가 상응하는 물리적 위치를 갖고 있을 경우 "매핑"되어 그곳에 저장된다.)

유닉스 기반 시스템은 추가 메모리로 매핑되는 두 개의 기본적인 시스템 호출을 갖고 있다:

  • brk: brk()는 매우 간단한 시스템 호출이다. 이 프로세스를 위한 매핑된 메모리의 끝에 있는 위치인 시스템 브레이크를 기억하는가? 프로세스에 메모리를 추가 또는 제거하기 위해 brk()는 그 위치를 단순히 앞뒤로 이동한다.
  • mmap: mmap() 또는 "memory map"은 brk() 비슷하지만 훨씬 유연하다. 우선, 프로세스의 끝 뿐만 아니라 어디에나 메모리를 매핑할 수 있다. 그리고 가상 주소를 물리적 RAM 또는 swap에 매핑할 수 있고 파일과 파일 위치로 매핑하여 읽고 쓰는 메모리 주소가 파일에서 데이터를 읽고 쓸 것이다. 하지만 여기서는 mmap의 기능에 초점을 맞춰 매핑된 RAM을 프로세스에 추가하는 것을 설명하겠다. munmap()은 mmap()와 반대되는 작동을 수행한다.

brk() 또는 mmap()은 가외의 가상 메모리를 프로세스에 추가하는데 사용될 수 있다. 우리 예제에서는 보다 간단하고 일반적인 brk()를 사용할 것이다.


할당자(allocator) 구현하기

C 프로그래밍을 많이 사용했다면 malloc()과 free()를 상당히 많이 사용했을 것이다. 하지만 이들이 OS에서 어떻게 구현되는지에 대해서는 많이 생각하지 못했을 것이다. 이 섹션에서는 malloc과 free의 간단한 구현 코드를 소개하겠다.

이 예제를 실행하려면, 코드를 복사하여 malloc.c 파일에 붙인다.

대부분의 OS에서 메모리 할당은 두 개의 함수로 핸들된다:

  • void *malloc(long numbytes): 메모리의 numbytes를 할당하여 포인터를 파일 바이트로 리턴한다.
  • void free(void *firstbyte): 이전 malloc에 의해 리턴된 포인터가 있다면, 할당된 공간을 프로세스의 "유휴 공간(free space)"에 준다.

malloc_init은 메모리 할당자를 초기화 할 함수가 될 것이다. 세 가지 일을 수행한다: 초기화되는 할당자를 확인하고, 시스템 상에 유효 메모리 주소를 찾고, 관리되는 메모리의 앞에 포인터를 설정한다. 이 세 변수는 글로벌 변수이다:


Listing 1. 글로벌 변수



int has_initialized = 0; 

void *managed_memory_start; 

void *last_valid_address; 


앞서 언급했듯이 매핑된 메모리의 끝-마지막 유효 주소-는 시스템 브레이크 또는 커런트 브레이크로 알려져 있다. 대부분의 유닉스 시스템 상에서 커런트 시스템 브레이크를 찾으려면 sbrk(0)함수를 사용한다. sbrk은 인자에 있는 바이트의 수 만큼 커런트 시스템 브레이크를 움직이고 새로운 시스템 브레이크를 리턴한다. 인자 0으로 이것을 호출하면 커런트 브레이크를 리턴한다. 다음은 malloc초기화 코드이다. 커런트 브레이크를 찾고 변수를 초기화한다:


Listing 2. 할당자 초기화 함수



/* Include the sbrk function */ 

#include 

void malloc_init() 



/* grab the last valid address from the OS */ 

last_valid_address = sbrk(0); 


/* we don't have any memory to manage yet, so 
*just set the beginning to be last_valid_address 
*/ 

managed_memory_start = last_valid_address; 

/* Okay, we're initialized and ready to go */ 

has_initialized = 1; 



이제 메모리를 올바르게 관리하기 위해 무엇을 할당하고 무엇을 할당 해제하는지를 트래킹할 수 있어야 한다. free가 호출된 후에 mark block 같은 사용되지 않은 것을 실행해야 한다. 그리고 malloc이 호출되면 사용되지 않은 block의 위치를 정할 수 있다. 따라서 malloc에 의해 리턴된 모든 메모리 조각의 시작에는 이 구조를 갖게 된다:


Listing 3. Memory Control Block 구조 정의



struct mem_control_block { 

int is_available; 

int size; 

}; 


이제, malloc을 호출하는 프로그램에 문제를 일으킬 것이라고 생각할 수도 있다. 이들이 어떻게 구조를 알 수 있겠는가? 답은 '그것에 대해 알 필요가 없다' 이다; 이것을 리턴하기 전에 구조 뒤에 포인터를 움직임으로서 숨길 수 있다. 이는 리턴된 포인터가 어떤 목적으로도 사용되지 않은 메모리를 지적하도록 할 것이다. 이러한 방식으로, 호출 프로그램의 관점에서 볼 때, 그들이 얻는 모든 것은 유휴의 개방 메모리 이다. free()를 통해 포인터를 뒤로 전달하면 얼마간의 메모리 바이트를 저장하여 이 구조를 다시 찾는다.

이제 메모리 할당에 대해 논하기 전에 메모리를 비우는 것에 대해 이야기하려고 한다. 이것이 보다 간단하기 때문이다. 메모리를 비우기 위해 해야 할 일은 주어진 포인터를 취해서 sizeof(struct mem_control_block) 바이트를 백업하고 이를 사용 가능한 것으로 표시하는 것이다:


Listing 4. 할당 해제 함수



void free(void *firstbyte) { 

struct mem_control_block *mcb; 

/* Backup from the given pointer to find the 
* mem_control_block 
*/ 

mcb = firstbyte - sizeof(struct mem_control_block); 

/* Mark the block as being available */ 

mcb->is_available = 1; 

/* That's It! We're done. */ 

return; 


여러분도 보다시피 이 할당자에서 메모리 비우기는 매우 간단한 방식을 사용하여 일정한 시간에 수행된다. 메모리 할당은 약간 더 어렵다. 다음은 알고리즘의 아웃라인이다:


Listing 5. 주 할당자용 가상 코드




1. If our allocator has not been initialized, initialize it. 

2. Add sizeof(struct mem_control_block) to the size requested. 

3. Start at managed_memory_start. 

4. Are we at last_valid address? 

5. If we are: 

A. We didn't find any existing space that was large enough 
-- ask the operating system for more and return that. 

6. Otherwise: 

A. Is the current space available (check is_available from 
the mem_control_block)? 

B. If it is: 

i) Is it large enough (check "size" from the 
mem_control_block)? 

ii) If so: 

a. Mark it as unavailable 

b. Move past mem_control_block and return the 
pointer 

iii) Otherwise: 

a. Move forward "size" bytes 

b. Go back go step 4 

C. Otherwise: 

i) Move forward "size" bytes 

ii) Go back to step 4 


오픈 청크를 찾고 있는 링크 된 포인터를 사용하여 메모리를 검사하고 있다. 다음은 코드이다:


Listing 6. 주 할당자



void *malloc(long numbytes) { 

/* Holds where we are looking in memory */ 

void *current_location; 

/* This is the same as current_location, but cast to a 
* memory_control_block 
*/ 

struct mem_control_block *current_location_mcb; 

/* This is the memory location we will return. It will 
* be set to 0 until we find something suitable 
*/ 

void *memory_location; 

/* Initialize if we haven't already done so */ 

if(! has_initialized) { 

malloc_init(); 



/* The memory we search for has to include the memory 
* control block, but the users of malloc don't need 
* to know this, so we'll just add it in for them. 
*/ 

numbytes = numbytes + sizeof(struct mem_control_block); 

/* Set memory_location to 0 until we find a suitable 
* location 
*/ 

memory_location = 0; 

/* Begin searching at the start of managed memory */ 

current_location = managed_memory_start; 

/* Keep going until we have searched all allocated space */ 

while(current_location != last_valid_address) 



/* current_location and current_location_mcb point 
* to the same address. However, current_location_mcb 
* is of the correct type, so we can use it as a struct. 
* current_location is a void pointer so we can use it 
* to calculate addresses. 
*/ 

current_location_mcb = 

(struct mem_control_block *)current_location; 

if(current_location_mcb->is_available) 



if(current_location_mcb->size >= numbytes) 



/* Woohoo! We've found an open, 
* appropriately-size location. 
*/ 

/* It is no longer available */ 

current_location_mcb->is_available = 0; 

/* We own it */ 

memory_location = current_location; 

/* Leave the loop */ 

break; 





/* If we made it here, it's because the Current memory 
* block not suitable; move to the next one 
*/ 

current_location = current_location + 

current_location_mcb->size; 



/* If we still don't have a valid location, we'll 
* have to ask the operating system for more memory 
*/ 

if(! memory_location) 



/* Move the program break numbytes further */ 

sbrk(numbytes); 

/* The new memory will be where the last valid 
* address left off 
*/ 

memory_location = last_valid_address; 

/* We'll move the last valid address forward 
* numbytes 
*/ 

last_valid_address = last_valid_address + numbytes; 

/* We need to initialize the mem_control_block */ 

current_location_mcb = memory_location; 

current_location_mcb->is_available = 0; 

current_location_mcb->size = numbytes; 



/* Now, no matter what (well, except for error conditions), 
* memory_location has the address of the memory, including 
* the mem_control_block 
*/ 

/* Move the pointer past the mem_control_block */ 

memory_location = memory_location + sizeof(struct mem_control_block); 

/* Return the pointer */ 

return memory_location; 



그리고 이것은 우리의 메모리 매니저이다. 이제 이를 구현하여 우리의 프로그램에서 실행시키도록 한다.

malloc 호환의 할당자를 구현하려면 (realloc()같은 몇몇 함수는 다루지 않았지만, malloc()과 free()도 주요 함수이다.) 다음 명령어를 실행한다:


Listing 7. 할당자 컴파일 하기




gcc -shared -fpic malloc.c -o malloc.so 


이것은 malloc.so라는 파일을 만들어낸다. 이것이 우리 코드를 포함하고 있는 공유 라이브러리이다.

다음과 같이 유닉스 시스템에서 시스템 malloc() 대신 본인의 할당자를 사용할 수 있다:


Listing 8. 표준 malloc 대체



LD_PRELOAD=/path/to/malloc.so 

export LD_PRELOAD 


LD_PRELOAD 환경 변수는 동적 링커가 로딩할 실행 파일에 전에 주어진 공유 라이브러리의 심볼을 로딩하게 한다. 지정된 라이브러리에서 그 심볼에 우선순위를 준다. 따라서 이 세션에서 지금부터 우리가 시작하는 모든 애플리케이션은 시스템이 아닌 우리의 malloc()을 사용할 것이다. 몇몇 애플리케이션들 malloc()을 사용하지 않지만 이들은 예외인 경우이다. realloc() 같은 메모리 관리 함수를 사용하거나 malloc()의 내부 작동에 대한 어설픈 추측을 한다면 분명 충돌이 일어날 것이다. ash 쉘은 우리의 새로운 malloc()을 사용하면 작동이 잘 될 것이다.

malloc()이 사용되고 있다는 것을 확인하려면 함수의 엔트리 포인트에 있는 write()에 호출을 추가하여 이를 테스트해야 한다.

우리의 메모리 매니저는 보완되어야 할 것이 많이 있다. 다음과 같은 단점들이 있다:

  • 시스템 브레이크(글로벌 변수)에서 작동하기 때문에 다른 할당자 또는 mmap와 공존할 수 없다.
  • 메모리를 할당할 때, 최악의 시나리오는 모든 프로세스의 메모리를 거쳐야 한다는 것이다: 여기에는 디스크상에 위치한 많은 메모리가 포함되어 있다. 이는 OS가 데이터를 디스크에서 이동시켜야 한다는 것을 의미한다.
  • 메모리 부족 에러를 핸들링 할 방도가 없다.(malloc은 에러가 아닌 경우만 취급한다.)
  • realloc()같은 다른 많은 메모리 함수들을 구현하지 않는다.
  • sbrk() 요청한 것 보다 많은 메모리를 주기 때문에 힙의 끝에 메모리를 유출하게 된다.
  • is_available 플래그는 4-byte 단어를 사용한다. 1 bit 정보를 포함할 때에도 그렇다.
  • 할당자는 쓰레드 보안이 되지 않는다.
  • 할당자는 유휴 공간을 더 큰 블록으로 합체할 수 없다.
  • 할당자의 간단한 적합(fitting) 알고리즘이 잠재적인 메모리 단편화를 만든다.
  • 이외에도 많은 문제들이 남아있다.

기타 malloc 구현

malloc()의 여러 구현이 있고 저마다의 장단점이 있다. 할당자를 디자인할 때 다음 사항을 고려해야 한다:

  • 할당 속도
  • 할당 해제 속도
  • 쓰레디드 환경에서의 작동
  • 메모리가 파일링(filing)에 가까웠을 때의 작동
  • 캐시 지역성
  • 메모리 오버헤드 기록
  • 가상 메모리 환경에서의 작동
  • 크고 작은 객체들
  • 실시간 게런티

각 구현 마다 장단점이 있다. 우리의 단순한 할당자의 경우 할당이 매우 느리지만 할당 해제는 매우 빠르다. 가상 메모리 시스템을 사용한 빈약한 작동 때문이다. 큰 객체에 적합하다.

이외에도 다른 할당자들을 사용할 수 있다:

  • Doug Lea Malloc: Doug Lea Malloc은 Doug Lea의 원래 할당자, GNU libc 할당자 ptmalloc을 포함한 전체 할당자군이다. Doug Lea의 할당자는 기본적인 구조가 우리 버전과 매우 비슷하지만 인덱스를 결합하여 검색이 훨씬 빠르고 여러 사용되지 않는 청크들을 하나의 큰 청크로 결합하는 기능도 있다. 또한 캐싱을 활용하여 최근에 비워진 메모리를 빠르게 재사용할 수 있도록 한다. ptmalloc은 다중 쓰레드를 지원하도록 확장된 Doug Lea Malloc의 한 버전이다. (참고자료)
  • BSD Malloc: 4.2 BSD와 함께 배포되고 FreeBSD에 포함된 구현인 BSD Malloc은 사전 결정된 크기의 객체 풀(pool)로부터 객체를 할당하는 할당자이다. 객체 사이즈를 위한 사이즈 클래스를 갖고 있다. 따라서 일정 사이즈의 객체를 요구한다면 객체에 맞는 어떤 사이즈의 클래스든지 할당할 것이다. 빠른 구현이라는 장점이 있지만 메모리를 낭비할 수 있다. (참고자료)
  • Hoard: Hoard는 멀티쓰레디드 환경에서 빠르게 작동할 목적으로 작성되었다. 따라서 어떤 프로세스라도 메모리 할당을 기다리지 않도록 잠금(locking)을 최대한 활용하도록 설계되었다. 많은 할당과 할당 해제를 수행하는 멀티쓰레디드 프로세스의 속도를 크게 높일 수 있다. (참고자료)

이것들은 많은 할당자들에 대해 잘 알려진 것들이다. 여러분의 프로그램이 할당에 대해 특별한 필요가 있다면 그 프로그램이 메모리를 할당하는 방식에 맞는 커스텀 할당자를 작성하는 것이 더 낫다. 하지만 할당자 디자인이 익숙하지 않다면 커스텀 할당자는 더 많은 문제를 만들어 낼 수 있다. 이 문제에 관해서는 Donald Knuth의 저서 The Art of Computer Programming Volume 1: Fundamental Algorithms in section 2.5, "Dynamic Storage Allocation"을 참조하기 바란다. (참고자료)

C++에서, operator new()를 오버로드하여 클래스 기반 또는 템플릿 기반의 할당자를 구현할 수 있다. Andrei Alexandrescu의 Modern C++ Design의 4장("Small Object Allocation")에서는 작은 객체 할당자에 대해 설명하고 있다. (참고자료)

malloc()기반 메모리 관리의 단점

우리의 메모리 매니저 뿐만 아니라 malloc() 기반의 메모리 관리에도 단점은 있다. malloc()으로 메모리를 관리하는 것은 장기 실행하는 스토리지를 관리해야 하는 프로그램에게는 쥐약이다. 메모리 여유(floating)에 대한 레퍼런스가 많다면 언제 릴리즈 되어야 하는지 알기 힘들다. 수명주기가 현재 함수까지로 제한되어 있는 메모리는 관리가 쉽지만 그 이상의 수명주기를 가진 메모리는 훨씬 더 어렵다. 또한 많은 API들은 메모리 관리에 대한 책임이 호출 프로그램에 있는지 아니면 호출된 함수에 있는지에 대해 모호하다.

메모리를 관리할 때의 문제들 때문에 많은 프로그램들은 각자의 메모리 관리 규칙을 따르고 있다. C++의 예외 핸들링은 이 일을 더욱 복잡하게 한다. 가끔, 실제 연산 태스크를 수행 하는 것 보다 메모리 할당 및 클린업 관리에 더 많은 코드가 집중되어 있는 것 같다. 따라서 메모리 관리에 대한 다른 대안을 모색하고자 한다.




위로



반자동 메모리 관리 전략

Reference counting

Reference counting은 반자동 메모리 관리 기술로서 어느 정도의 프로그래머 지원이 필요하다. 하지만 객체가 더 이상 사용되지 않는 다는 것 까지 알 필요는 없다. reference counting 방식은 여러분을 위한 것이다.

reference counting에서 공유된 모든 데이터 구조는 그 구조에 현재 활성화된 '레퍼런스'의 수를 포함하는 필드를 갖고 있다. 프로시저가 포인터에서 데이터 구조로 전달되면 레퍼런스 카운트(reference count)에 추가한다. 기본적으로 데이터 구조에 어떻게 위치들이 저장되는지를 명령하고 있는 것이다. 프로시저가 이것을 사용하는 것을 끝마치면 레퍼런스 카운트가 감소한다. 이와 동시에 카운트가 0으로 떨어졌는지를 확인한다. 그렇다면 메모리가 비워진 것이다.

이것의 장점은 주어진 데이터 구조가 따라야 하는 프로그램의 모든 경로를 따라갈 필요가 없다는 것이다. 이것에 대해 각 지역화된 레퍼런스는 카운트를 적절히 감소 또는 증가시킨다. 이로서 메모리를 사용중일 때 비워지게 되는 현상을 막는다. 하지만 레퍼런스 카운팅 방식의 데이터 구조를 사용할 때마다 reference counting 함수를 실행해야 한다. 또한, 빌트인 함수와 삼자 라이브러리는 reference counting 방식을 모르거나 사용할 수 없다. reference counting은 순환식 레퍼런스를 가진 구조에는 어려움을 겪는다.

reference counting을 구현하려면 두 개의 함수가 필요하다. 하나는 레퍼런스 카운트를 증가시키는 함수이고 하나는 레퍼런스 카운트를 감소시켜 0에 도달했을 때 메모리를 비우는 함수이다.

다음은 reference counting 예제이다:


Listing 9. 기본적인 reference counting 함수



/* Structure Definitions*/ 

/* Base structure that holds a refcount */ 

struct refcountedstruct 



int refcount; 



/* All refcounted structures must mirror struct 
* refcountedstruct for their first variables 
*/ 

/* Refcount maintenance functions */ 

/* Increase reference count */ 

void REF(void *data) 



struct refcountedstruct *rstruct; 

rstruct = (struct refcountedstruct *) data; 

rstruct->refcount++; 



/* Decrease reference count */ 

void UNREF(void *data) 



struct refcountedstruct *rstruct; 

rstruct = (struct refcountedstruct *) data; 

rstruct->refcount--; 

/* Free the structure if there are no more users */ 

if(rstruct->refcount == 0) 



free(rstruct); 





무엇을 하고자 하느냐에 따라 REF와 UNREF 가 상황을 복잡하게 할 수 있다. 예를 들어 멀티쓰레디드 프로그램에 잠금을 추가하고자 한다면 refcountedstruct를 확장하여 메모리를 비우기 전에 호출 할 함수에 대한 포인터를 추가하고 싶을 것이다. (객체 지향 언어의 디스트럭터(destructor)와 같다-구조에 포인터가 포함되어 있을 때에만 필요하다.)

REF와 UNREF를 사용할 때, 포인터 할당에 있어 다음 규칙을 준수해야 한다:

  • UNREF 할당 전에 왼쪽 포인터가 가르키는 값
  • REF 할당 후에 왼쪽 포인터가 가르키는 값

refcounted 구조로 전달된 함수의 경우 다음 규칙을 따라야 한다:

  • REF 함수의 시작에 있는 모든 포인터
  • UNREF 함수의 끝에 있는 모든 포인터

다음은 reference counting을 사용하는 코드 예제이다:


Listing 10. reference counting 예제



/* EXAMPLES OF USAGE */ 


/* Data type to be refcounted */ 

struct mydata 



int refcount; /* same as refcountedstruct */ 

int datafield1; /* Fields specific to this struct */ 

int datafield2; 

/* other declarations would go here as appropriate */ 

}; 


/* Use the functions in code */ 

void dosomething(struct mydata *data) 



REF(data); 

/* Process data */ 

/* when we are through */ 

UNREF(data); 




struct mydata *globalvar1; 

/* Note that in this one, we don't decrease the 
* refcount since we are maintaining the reference 
* past the end of the function call through the 
* global variable 
*/ 

void storesomething(struct mydata *data) 



REF(data); /* passed as a parameter */ 

globalvar1 = data; 

REF(data); /* ref because of Assignment */ 

UNREF(data); /* Function finished */ 



reference counting은 다소 간단하기 때문에 대부분의 프로그래머들은 라이브러리를 사용하기 보다는 이들 자체를 구현한다. 하지만 malloc과 free 같은 저급의 할당자들을 의존하여 메모리를 할당 및 릴리스 하고 있다.

reference counting은 Perl 같은 고급 언어에서 많이 사용된다. 그러한 언어에서 레퍼런스 카운팅은 언어에 의해 자동으로 핸들 되어 확장 모듈을 작성하는 것 외에는 걱정할 것이 없다. 모든 것이 레퍼런스 카운팅 되어야 하기 때문에 속도는 느리지만 안전성이 높고 프로그래밍이 쉽다:

  • 간단한 구현
  • 사용이 쉬움
  • 레퍼런스가 데이터 구조의 일부이기 때문에 캐시 지역성이 우수함

하지만 단점도 있다:

  • 레퍼런스 카운팅 함수를 호출하는 것을 절대 잊어서는 안된다.
  • 순환 데이터 구조의 일부인 구조를 릴리스 하지 않는다.
  • 거의 모든 포인터 할당이 느리다.
  • 레퍼런스 카운팅 된 객체를 사용하는 동안 예외 핸들링 (try 또는 setjmp()/longjmp())을 사용할 때 추가 조치를 취해야 한다.
  • 레퍼런스를 핸들 할 여분의 메모리가 필요하다.
  • 레퍼런스 카운터는 구조 내에서 첫 번째 위치를 차지한다. 이는 대부분의 머신에서 가장 빠르게 액세스 할 수 있다.
  • 멀티쓰레디드 환경에서 수행할 때 느리고 어렵다.

C++는 reference counting 같은 상세한 포인터 핸들링을 핸들 할 수 있는 스마트 포인터(smart pointers)를 사용하여 프로그래머 오류를 줄일 수 있다. 하지만 스마트 포인터(C 라이브러리로의 링크)를 핸들 할 수 없는 레거시 코드를 사용해야 한다면 이를 사용하지 않는 것이 낫다. 따라서 이는 C++ 전용 프로젝트에만 유용하다. 스마트 포인터를 사용하려면 Alexandrescu의 Modern C++ Design의 "Smart Pointers"를 참조하기 바란다.

메모리 풀(pool)


메모리 풀은 메모리 관리를 반자동화 할 수 있는 또 하나의 방식이다. 메모리 풀은 특정 단계를 거쳐야 하는 프로그램을 위해 메모리 관리를 자동화한다. 예를 들어, 많은 네트워크 서버 프로세스들은 커넥션 당 할당된 메모리를 갖고 있다. 최대 수명은 현재 커넥션의 수명이다. 풀링 메모리를 사용하는 Apache는 고유의 메모리 풀을 갖고 있는 단계로 나뉘어진 연결을 갖고 있다. 이 단계의 끝에, 전체 메모리 풀은 한번에 비워진다.

풀링 메모리를 관리 할 때, 각 할당은 할당되어야 하는 곳부터 메모리의 풀을 지정해야 한다. 각 풀은 다른 수명을 갖고 있다. Apache에서 서버의 수명을 지속시키는 풀이 있다. 하나는 연결의 수명을 지속시키는 것이고 하나는 요청의 수명을 지속시키는 것이다. 따라서 연결 보다 오래 지속되는 데이터를 만들지 않는 일련의 함수를 갖고 있다면 커넥션 풀에서 이 모든 것을 할당하면서 연결 끝에는 자동으로 비워진다는 것을 알 수 있다. 게다가 어떤 구현은 메모리 풀이 비워지기 비로 직전에 호출되는 레지스터링 클린업 함수로 하여금 메모리가 비워지기 전에 수행되어야 하는 추가 태스크를 수행하도록 한다. (객체 지향의 디스트럭터와 비슷하다.)

자신이 프로그램에서 풀을 사용하려면 GNU libc의 obstack 구현 또는 Apache의 Apache Portable Runtime을 사용할 수 있다. GNU obstack는 GNU 기반 리눅스 배포판에 기본적으로 포함되기 때문에 유용하다. Apache Portable Runtime은 멀티플랫폼 서버 소프트웨어를 작성하는 모든 측면들을 핸들 할 수 있는 유틸리티가 많아서 좋다. (참고자료).

다음의 가상 코드는 obstack의 사용법을 보여준다:


Listing 11. obstack 코드 예제



#include 

#include 

/* Example code listing for using obstacks */ 

/* Used for obstack macros (xmalloc is 
a malloc function that exits if memory 
is exhausted */ 

#define obstack_chunk_alloc xmalloc 

#define obstack_chunk_free free 

/* Pools */ 

/* Only permanent allocations should go in this pool */ 

struct obstack *global_pool; 

/* This pool is for per-connection data */ 

struct obstack *connection_pool; 

/* This pool is for per-request data */ 

struct obstack *request_pool; 

void allocation_failed() 



exit(1); 



int main() 



/* Initialize Pools */ 

global_pool = (struct obstack *) 

xmalloc (sizeof (struct obstack)); 

obstack_init(global_pool); 

connection_pool = (struct obstack *) 

xmalloc (sizeof (struct obstack)); 

obstack_init(connection_pool); 

request_pool = (struct obstack *) 

xmalloc (sizeof (struct obstack)); 

obstack_init(request_pool); 

/* Set the error handling function */ 

obstack_alloc_failed_handler = &allocation_failed; 

/* Server main loop */ 

while(1) 



wait_for_connection(); 

/* We are in a connection */ 

while(more_requests_available()) 



/* Handle request */ 

handle_request(); 

/* Free all of the memory allocated 

* in the request pool 

*/ 

obstack_free(request_pool, NULL); 



/* We're finished with the connection, time 

* to free that pool 

*/ 

obstack_free(connection_pool, NULL); 





int handle_request() 



/* Be sure that all object allocations are allocated 
* from the request pool 
*/ 

int bytes_i_need = 400; 

void *data1 = obstack_alloc(request_pool, bytes_i_need); 

/* Do stuff to process the request */ 

/* return */ 

return 0; 



기본적으로 작동의 주요 단계가 끝나면 그 단계에 대한 obstack이 비워진다. 하지만 프로시저가 현재 단계 보다 더 길게 지속될 메모리를 할당하려면 커넥션 또는 글로벌 같은 장기 obstack을 사용할 수 있다. obstack_free()로 전달된 NULL은 obstack의 전체 내용을 비워야 한다는 것을 나타낸다. 다른 값들은 사용할 수 있지만 유용하지 않다.

다음은 메모리 풀링의 장점들이다:

  • 애플리케이션의 메모리를 관리하기가 수월하다.
  • 풀에서 한번에 되기 때문에 메모리 할당과 할당 해제가 훨씬 빠르다. 할당은 O(1) 시간에 수행될 수 있고 풀 릴리스는 끝난다. (실제로 O(n) 시간이지만 대부분의 경우 O(1)로 만드는 거대한 요소에 의해 나뉘어진다.)
  • 에러 핸들링 풀은 사전 할당되어 정규 메모리가 소진되면 프로그램이 복구할 수 있도록 한다.
  • 사용하기 쉬운 표준 구현들이 있다.

다음은 메모리 풀링의 단점들이다:

  • 메모리 풀은 단계 별로 작동하는 프로그램에만 유용하다.
  • 메모리 풀은 삼자 라이브러리로는 잘 작동하지 않는다.
  • 프로그램 구조가 바뀌면 풀이 변경되어야 하는데, 이로 인해 메모리 관리 시스템을 재디자인 해야 한다.
  • 할당하고 싶은 풀이 어떤 것인지를 기억해야 한다. 이것이 잘못되면 회복이 불가능하다.




위로



가비지 컬렉션

가비지 컬렉션은 더 이상 사용하지 않는 데이터 객체들을 완전 자동으로 탐지 및 제거하는 것이다. 가비지 컬렉터는 사용 가능한 메모리가 특정 임계치로 떨어지면 자동으로 실행된다. 일반적으로 프로그램에서 사용할 수 있는 "기본" 설정-스택 데이터, 글로벌 변수, 레지스터-으로 시작한다. 그런 다음 서로 링크 된 데이터의 모든 조각들을 트레이스한다. 컬렉터가 찾는 모든 것은 좋은 데이터이다. 찾지 못하는 모든 것은 가비지(쓰레기)이고 파괴 및 재사용될 수 있다. 메모리를 효과적으로 관리하려면 많은 유형의 가비지 컬렉터들이 데이터 구조 내의 포인터 레이아웃을 알 필요가 있다. 그리고 올바로 작동하는 언어의 일부가 되어야 한다.

컬렉터 유형

  • 복사(Copying): 메모리 스토리지를 두 부분으로 나누고 데이터가 오직 한 쪽에만 있도록 한다. "기본" 요소들을 갖고 시작하면서 주기적으로 한 쪽에서 다른 쪽으로 데이터를 복사하기 시작한다. 새롭게 채워진 메모리 섹션은 활성이 되고 다른 쪽의 모든 것은 쓰레기로 간주된다. 또한 복사가 발생하면 모든 포인터들은 각 메모리 아이템의 새로운 위치를 가르키도록 업데이트 되어야 한다. 따라서 이 방식의 가비지 컬렉션을 사용하려면 컬렉터는 프로그래밍 언어로 통합되어야 한다.
  • 표시와 청소(Mark and sweep): 데이터의 각 조각은 태그로 표시된다. 가끔 모든 태그들은 0으로 설정되고 컬렉터는 "기본" 요소들로 시작하는 데이터부터 검사한다. 메모리를 만나면 태그를 1로 표시한다. 끝에 1로 태그가 붙지 않는 모든 것은 쓰레기로 간주되어 나중에 재사용된다.
  • 증가(Incremental): 증가 가비지 컬렉터는 모든 데이터 객체들을 전체적으로 실행할 필요가 없다. 모든 메모리를 실행하면 모으는 기간 동안 한꺼번에 멈춰야 하고 현재의 모든 데이터에 액세스하는 것과 관련한 캐시 문제 때문이다. 증가 컬렉터는 이러한 문제들을 방지한다.
  • Conservative: Conservative 가비지 컬렉터는 메모리를 관리하는 데이터 구조에 대해 알 필요가 없다. 단순히 모든 데이터 바이트를 보고 이들이 모두 포인터를 갖고 있다는 것으로 간주한다. 따라서 바이트의 시퀀스가 할당된 메모리 조각에 대한 포인터가 되면 이를 레퍼런스 된 것으로 표시한다. 이는 정수 필드가 할당된 메모리의 주소인 값을 포함한다면 레퍼런스 되지 않은 메모리가 모아질 때 문제가 될 수 있다. 하지만 이는 매우 드문 경우이고 적은 메모리만을 쓴다. Conservative 컬렉터는 모든 프로그래밍 언어로 통합될 수 있는 장점이 있다.

Hans Boehm's conservative 가비지 컬렉터는 가장 대중적인 가비지 컬렉터 중 하나이다. 무료이고 Conservative 유형이자 증가 유형이기 때문이다. --enable-redirect-malloc으로 이를 구현하여 (API 대신 malloc/free 사용하는)시스템 할당자 대용으로 사용할 수 있다. 사실 이렇게 하면 같은 LD_PRELOAD트릭을 트릭을 사용할 수 있다. 프로그램이 메모리를 유출한다는 의심이 들면 이 가비지 컬렉터를 사용하여 프로세스 사이즈를 줄일 수 있다. 메모리 유출이 심했을 때 Mozilla 초기에는 많은 사람들이 이 기술을 사용했다. 이 가비지 컬렉터는 Windows®와 UNIX 모두 사용할 수 있다.

다음은 가비지 컬렉션의 장점이다:

  • 메모리의 이중 유휴화(double-freeing)나 객체 수명을 걱정할 필요가 없다.
  • 어떤 컬렉터의 경우 일반 할당에 사용되는 같은 API를 사용할 수 있다.

다음은 가비지 컬렉션의 단점이다:

  • 대부분의 컬렉터를 사용할 때, 메모리가 비워져가고 있을 때 기회가 없다.
  • 많은 경우, 가비지 컬렉션은 다른 형태의 메모리 관리 보다 느리다.
  • 가비지 컬렉션 에러로 인한 버그는 디버그가 어렵다.
  • 사용되지 않는 포인터를 null로 설정하지 않는다면 메모리 유출이 있다.




위로



결론

퍼포먼스, 용이성, 구현가능성, 쓰레딩 기능 등 비교할 것이 많다. 프로젝트 요구사항에 맞는 다양한 메모리 관리 패턴이 있다. 각 패턴마다 광범위한 구현을 갖추고 있고, 이들 각각 장단점이 있다. 프로그래밍 환경을 위해 디폴트 기술을 사용하는 것은 좋은 일이지만 사용할 수 있는 옵션을 아는 것 또한 중요한 일이다. 다음 표에서는 이 글에서 다루어진 메모리 관리 전략들을 비교했다.


표 1. 메모리 할당 전략 비교

전략할당 속도할당 해제 속도캐시 지역성용이성보편성실시간 사용SMP 및 쓰레드 친화력
커스텀 할당자구현에 의존구현에 의존구현에 의존매우 어려움없음구현에 의존구현에 의존
일반 할당자적은 메모리 사용에 빠름매우 빠름거의 없음쉬움매우 보편적NoNo
GNU malloc중간빠름중간쉬움VeryNo중간
Hoard중간중간중간쉬움VeryNoYes
Reference countingN/AN/A우수함중간중간Yes (malloc구현에 의존)구현에 의존
Pooling중간매우 빠름우수함중간중간Yes (malloc 구현에 의존)구현에 의존
가비지 컬렉션중간 (slow when collection occurs)중간거의 없음중간중간No거의 없음
증가 가비지 컬렉션중간중간중간중간중간No거의 없음
중도 증가 가비지 컬렉션중간중간중간쉬움매우 보편적No거의 없음






출처: http://elechole.tistory.com/268 [다연수연아빠의 임베디드 세상....]

'ENCRYPTION' 카테고리의 다른 글

machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
C Program to Implement Sieve of eratosthenes to Generate Prime Numbers Between Given Range  (0) 2018.12.03
메르센 소수  (0) 2018.12.03
블로그 이미지

remoted

Remoted's IT LAB & POST DATABASE

댓글을 달아 주세요

Sieve of Eratosthenes

ENCRYPTION 2018. 12. 3. 01:03

소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89

주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데,

그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ

이것보다 더 좋은 방법은 아마도 없을 것이라 자신함 !! 

만약 있다면 댓글 달아주시기 바람.


요번에는 c++로 구현해보았음.



1. 알고리즘


에라토스테네스의 체 (Sieve of Eratosthenes)라는 알고리즘이다.

아래 그림을 보면 무엇인지 알 수 있다.





120까지의 모든 소수를 구한다고 해보자.

 

2부터 120까지 배열에 모두 넣은 후

소수가 아닌 것들을 모두 체크해버리는 것이다.


2를 제외한 모든 2의 배수를 체크한다.

3을 제외한 모든 3의 배수를 체크한다.

4는 아까 체크당했으므로 소수 아님.

5를 제외한 모든 5의 배수를 체크한다.

......


체크가 안된 수들이 소수이다.



이 알고리즘을 이용하면, 최악과 최선의 프로그램을 만들어낼 수 있다.



2. 예제


에라토스테네스의 체를 이용해서 구현을 해보겠다.(에라토스테네스...이름 겁나 안외워지는군ㅋㅋㅋㅋㅋㅋ


void getChe1(int num) {

    int *arr;

    arr = (int *) malloc(sizeof(int) * num);

    

    // 입력받은  만큼 배열에 모두 초기화 해둔다

    for (int i = 2; i <= num; i++) {

        arr[i] = i;

    }

    

    for (int i = 2; i <= num; i++) {  // 나누는 값 : i

        for (int j = 2; j <= num; j++) {

            if (arr[j] != i && arr[j] % i == 0) {  // 자신과 같지않고 0으로 떨어지면 소수아님

                arr[j] = 0// 소수가 아닌 경우 0을 넣어둔다

            }

        }

    }

    

    // 출력

    for (int i = 2; i<= num; i++) {

        if (arr[i] != 0)   

            cout << arr[i] << " ";

    }

}


int main(void{

    clock_t start, end;

    

    start = clock();

    getChe1(50000);

    end = clock();

    

    double time = (double)(end - start) / CLOCKS_PER_SEC; 

    cout << "수행시간 : " << time;

}


결과 및 수행시간 >>



어마어마하다. 18초나 걸렸다... ㅋㅋㅋ


1편에서 구현했던 최악의 알고리즘의 3배정도의 시간이 걸렸다.

1편의 최악의 알고리즘의 시간은 아래와 같았다. 6.07415초..




하지만, 에라토스테네스의 체를 잘 이용하면 최상의 소수 구하기 프로그램을 만들 수 있다.



최적의 방법을 생각해내보자..



그것은 바로!


체크할 때, 모든 수를 다 돌면서 체크할 필요 없이

체크 할 배수만큼만 반복문을 돌게하는 것이다.


그리고, 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다.

(왜냐면, 체크된 수의 배수들도 이미 다 체크가 되어있기 때문이다)




예제 >>


void getChe(int num) {

    int *arr;

    arr = (int *)malloc(sizeof(int) * num);

    int i = 2;


    // 입력받은  만큼 배열에 모두 초기화 해둔다

    for (i = 2; i <= num; i++) {

        arr[i] = i;

    }

    

    for (i = 2; i <= num; i++) { 

        if (arr[i] == 0// 이미 체크된 수의 배수는 확인하지 않는다

            continue;

        for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크

            arr[j] = 0;

        }

    }


    // print

    for (i = 2; i <= num; i++) {

        if (arr[i] != 0)

            cout << arr[i] << " ";

    }

}



결과 및 수행시간 >>



확 줄었다!! 심지어 1초도 안걸린다.



1편에서 최적의 알고리즘이라고 했던, 특정 수보다 작은 소수들로 나누어보는 알고리즘의 속도는

아래와 같았었다.




이것도 1초는 안걸리지만 에라토스테네스의 체를 이용한 것보단 느린편이다.




그리고 추가적으로..

조금 더 좋게 해보기위해 수학의 공식도 이용을 해보았다 ㅋㅋ

수학자들에 의해 이미 증명된 공식. 좀 간단히 설명하자면,


소수는 n의 배수가 아니어야 한다.

입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.

그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.



이 이론을 위의 예제와 접목해보면 아래같이 할 수 있다.

나눌 수를 루트 num까지만 돌리는 것~!


 for (i = 2; i <= sqrt(num); i++) { 

        if (arr[i] == 0// 이미 체크된 수의 배수는 확인하지 않는다

            continue;

        for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크

            arr[j] = 0;

        }

    }


수행 시간은 아래와 같다.



루트 씌우기 전엔 0.0006489초 였으니 아주 미세한 차이지만 조~~금 더 줄었다 : )




출처: http://marobiana.tistory.com/91 [Take Action]


'ENCRYPTION' 카테고리의 다른 글

machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
C Program to Implement Sieve of eratosthenes to Generate Prime Numbers Between Given Range  (0) 2018.12.03
메르센 소수  (0) 2018.12.03
블로그 이미지

remoted

Remoted's IT LAB & POST DATABASE

댓글을 달아 주세요

This C program is used to implement Sieve of Eratosthenes to generate prime numbers between given range. The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer. Implement this algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn’t optimize by using pre-computed wheels, i.e. don’t assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.

Here is the source code of the C program to generate prime numbers. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define limit 100 /*size of integers array*/
  5.  
  6. int main(){
  7.     unsigned long long int i,j;
  8.     int *primes;
  9.     int z = 1;
  10.  
  11.     primes = malloc(sizeof(int) * limit);
  12.  
  13.     for (i = 2;i < limit; i++)
  14.         primes[i] = 1;
  15.  
  16.     for (i = 2;i < limit; i++)
  17.         if (primes[i])
  18.             for (j = i;i * j < limit; j++)
  19.                 primes[i * j] = 0;
  20.  
  21.     printf("\nPrime numbers in range 1 to 100 are: \n");
  22.     for (i = 2;i < limit; i++)
  23.         if (primes[i])
  24.             printf("%d\n", i);
  25.  
  26. return 0;
  27. }

$ gcc prime.c -o prime
$ ./prime
 
Prime numbers in range 1 to 100 are: 
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97


'ENCRYPTION' 카테고리의 다른 글

machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
C Program to Implement Sieve of eratosthenes to Generate Prime Numbers Between Given Range  (0) 2018.12.03
메르센 소수  (0) 2018.12.03
블로그 이미지

remoted

Remoted's IT LAB & POST DATABASE

댓글을 달아 주세요

메르센 소수

ENCRYPTION 2018. 12. 3. 01:01

메르센 소수

위키백과, 우리 모두의 백과사전.
둘러보기로 가기검색하러 가기

메르센 수(Mersenne number)는 2의 거듭제곱에서 1이 모자란 숫자를 가리킨다. 지수 에 대한 메르센 수는 로 나타내고 목록은 아래와 같다.

13715316312725551110232047409581911638332767... (OEIS의 수열 A000225)

메르센 소수(Mersenne prime)는 메르센 수 중에서 소수인 수이다. 예를 들면 3과 7은 둘 다 소수이고 이므로 3과 7은 둘 다 메르센 소수이다. 반대로 은 소수가 아니다. 현대에 알려진 매우 큰 소수들 중에는 메르센 소수가 상당히 많다.

3731127819113107152428721474836472305843009213693951... (OEIS의 수열 A000668)

메르센 소수가 무한히 많이 존재하는지 아니면 그 개수가 정해져 있는지는 아직 알려져 있지 않다.

메르센 수의 속성[편집]

메르센 수는 다음의 몇 가지 속성을 지닌다. :

은 이항계수의 에서 1을 뺀 값이다.

메르센 수의 속성 2[편집]

메르센 수의 지수가 홀수소수 이면 소인수의 형태는 다음과 같음을 페르마가 증명하였다.

 (는 음이 아닌 정수)

이것은 메르센 수가 소수, 즉 메르센 소수일때도 성립한다.

메르센 소수에 관한 정리[편집]

  • 1) 만일 이 하나의 양의 정수이면, 이항정리에 의해 다음과 같이 쓸 수 있다:

또는

이다( =  = 로,  = 로 놓았을 때).

증명

역사[편집]

1644년 마랭 메르센은  형태가 소수가 되는 것은,  일 때  뿐이라고 발표하였다. 그러나 그 주장의 일부는 잘못임이 밝혀졌다. 목록에 포함되지 않은 는 소수이며, 목록에 포함되어 있는 는 합성수이다.

리젤 수의 발견자이기도 한 스웨덴의 수학자인 한스 리젤이 1957년에 컴퓨터를 이용하여 18번째의 메르센 소수를 발견한 이래, 이후 컴퓨터를 활용하여 새로운 메르센 소수를 찾고 있다.

메르센 소수 찾기[편집]

 다음 등식은 이 메르센 소수가 되기 위해서는  자신이 소수여야 한다는 것을 알려준다.

따라서, 메르센 소수를 찾기 위해서는 지수가 소수인 경우만 조사하면 되지만, 일반적으로 그 역은 참이 아니다. 즉 이 소수라고 하여  또한 소수인 것은 아니다. 예를 들어, 11은 소수지만 로 소인수분해된다.

메르센 소수 목록[편집]

현재까지 발견한 메르센 소수 표 (OEIS의 수열 A000668):

#의 자리수발견일발견자
1231기원전 430년 경고대 그리스 수학자
2371기원전 430년 경고대 그리스 수학자
35312기원전 300년 경고대 그리스 수학자
471273기원전 300년 경고대 그리스 수학자
513819141456년아무개
61713107161588년피에트로 카탈디
71952428761588년피에트로 카탈디
8312147483647101772년레온하르트 오일러
9612305843009213693951191883년이반 미흐비치 페르부쉰
1089618970019…449562111271911년R. E. Powers
11107162259276…010288127331914년R. E. Powers
12127170141183…884105727391876년에두아르 뤼카
13521686479766…1150571511571952년 1월 30일라파헬 로빈슨
14607531137992…0317281271831952년 1월 30일라파헬 로빈슨
151,279104079321…1687290873861952년 6월 25일라파헬 로빈슨
162,203147597991…6977710076641952년 10월 7일라파헬 로빈슨
172,281446087557…1328363516871952년 10월 9일라파헬 로빈슨
183,217259117086…9093150719691957년 9월 8일한스 리젤
194,253190797007…3504849911,2811961년 11월 3일알렉산더 허비츠
204,423285542542…6085806071,3321961년 11월 3일알렉산더 허비츠
219,689478220278…2257541112,9171963년 5월 11일도널드 길리스
229,941346088282…7894635512,9931963년 5월 16일도널드 길리스
2311,213281411201…6963921913,3761963년 6월 2일도널드 길리스
2419,937431542479…9680414716,0021971년 3월 4일브리언트 터커맨
2521,701448679166…5118827516,5331978년 10월 30일랜돈 커트 놀과 로라 니켈
2623,209402874115…7792645116,9871979년 2월 9일랜돈 커트 놀
2744,497854509824…01122867113,3951979년 4월 8일해리 넬슨과 데이빗 슬로빈스키
2886,243536927995…43343820725,9621982년 9월 25일데이빗 슬로빈스키
29110,503521928313…46551500733,2651988년 1월 28일월크 콜킷과 루크 웰시
30132,049512740276…73006131139,7511983년 9월 19일[1]데이빗 슬로빈스키
31216,091746093103…81552844765,0501985년 9월 1일[1]데이빗 슬로빈스키
32756,839174135906…544677887227,8321992년 2월 19일데이빗 슬로빈스키와 폴 게이지
33859,433129498125…500142591258,7161994년 1월 4일데이빗 슬로빈스키와 폴 게이지
341,257,787412245773…089366527378,6321996년 9월 3일데이빗 슬로빈스키와 폴 게이지 [1]
351,398,269814717564…451315711420,9211996년 11월 13일GIMPS / 조엘 아르멩고 [2][깨진 링크(과거 내용 찾기)]
362,976,221623340076…729201151895,9321997년 8월 24일GIMPS / 고든 스펜스 [3][깨진 링크(과거 내용 찾기)]
373,021,377127411683…024694271909,5261998년 1월 27일GIMPS / 롤랜드 클락슨 [4][깨진 링크(과거 내용 찾기)]
386,972,593437075744…9241937912,098,9601999년 6월 11일GIMPS / 난야 하이라트왈라 [5]
3913,466,917924947738…2562590714,053,9462001년 11월 14일GIMPS / 마이클 카메론 [6]
4020,996,011125976895…8556820476,320,4302003년 11월 17일GIMPS / 마이클 셰이퍼 [7]
4124,036,583299410429…7339694077,235,7332004년 5월 15일GIMPS / 조지 핀들리 [8]
4225,964,951122164630…5770772477,816,2302005년 2월 18일GIMPS / 마르틴 노바크 [9]
43*30,402,457315416475…6529438719,152,0522005년 9월 15일GIMPS / 커티스 쿠퍼와 스티븐 분 [10]
44*32,582,657124575026…0539678719,808,3582006년 9월 4일GIMPS / 커티스 쿠퍼와 스티븐 분 [11]
45*37,156,667202254406…30822092711,185,2722008년 9월 6일GIMPS / Hans-Michael Elvenich [12]
46*42,643,801169873516…56231475112,837,0642009년 4월 12일**GIMPS / Odd Magnar Strindmo
47*43,112,609316470269…69715251112,978,1892008년 8월 23일GIMPS / Edson Smith [13]
48*57,885,161581887266…72428595117,425,1702013년 1월 25일GIMPS / Curtis Cooper [14]
49*74,207,281300376418…08643635122,338,6182015년 9월 17일***GIMPS / Curtis Cooper [15]
5077,232,917467333183…76217907123,249,4252017년 12월 26일GIMPS / Jon Pace

44번째 알려진 메르센 소수를 시각적으로 보여 주기 위해서는 1페이지 당, 10진수 75개 자리수의 숫자를 50줄씩 쓴 2,616페이지가 필요하다.

*표의 43번째 수인 과 49번째 수인  사이에 아직 발견되지 않은 다른 메르센 소수가 있는지는 아직 알려져 있지 않다. 따라서 이 번호들은 바뀔 수도 있다. 소수가 작은 소수부터 순차적으로 발견되는 것은 아니다. 예를 들어, 29번째 메르센 소수는 30번째와 31번째 소수의 발견 이후에 발견되었다.

**M42,643,801는 2009년 4월 12일 컴퓨터에 의해 처음 발견되었다. 그러나 6월 4일까지 이 사실을 인지한 사람은 아무도 없었다. 그래서, 발견일을 4월 12일 또는 6월 4일로 간주한다. 발견자 스트린드모(Strindmo)는 alias Stig M. Valstad를 사용한 것으로 보인다.

***M74,207,281는 2015년 9월 17일 컴퓨터에 의해 처음 발견되었다. 그러나 2016년 1월 7일까지 이 사실을 인지한 사람은 아무도 없었다. 그래서, 발견일을 2015년 9월 17일 또는 2016년 1월 7일로 간주한다.

완전수[편집]

메르센 소수는 완전수와 여러 관련성이 있어 흥미롭다. 기원전 4세기에 유클리드는 이 메르센 소수이면 다음과 같이 짝수 완전수임을 보였다.

18세기에 오일러는 모든 짝수 완전수는 이와 같은 형태를 갖는다는 것을 증명했다. 홀수 완전수는 아직 발견되지 않았으며 존재하지 않는 것으로 추측된다.

일반화[편집]

의 2진법 표현은 숫자 1이 번 반복된다. 예를 들면, 25 - 1 = 111112와 같이 표기된다. 그러므로 메르센 소수는 2를 밑으로 하는 단위 반복 소수이다.

관련 항목[편집]

각주[편집]

외부 링크[편집]


'ENCRYPTION' 카테고리의 다른 글

machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
C Program to Implement Sieve of eratosthenes to Generate Prime Numbers Between Given Range  (0) 2018.12.03
메르센 소수  (0) 2018.12.03
블로그 이미지

remoted

Remoted's IT LAB & POST DATABASE

댓글을 달아 주세요