그저께 퇴근하다가 갑자기 작은 게임이 하나 만들고 싶어졌다 ㅇㅇ

그래서 구현을 하려다가 어차피 개좆대로 짤건데 좆같은 c++ 말고 평소에 배우고 싶었던 러스트로 짜보자는 생각이 났다

그런 이유로 어제부터 러스트 공부를 시작했다

그렇기 때문에 러스트로 피보나치 수열 짜왔다


환경은 아래와 같다

OS: Ubuntu 20.04

Processor: Intel i7

RAM: 16Gb


목표 : get_fibo 함수 만들기

어떤 븅신처럼 재귀로는 안 짤거다 그 지랄하다 회사 짤린다


일단 간단한 모델링부터 생각하자

a_1 = 1, a_2 =1, a_n = a_(n-1) + a_(n-2) (for n >= 3)이다.

이를 행렬로 다시 나타내면 아래와 같다.

[a_(n+2); a_(n+1)] = [1 1; 1 0] [a_(n+1); a_n]

이를 쭉 전개한 후 정리하면 다음과 같다.

[a_(n+2); a_(n+1)] = [1 1; 1 0]^n [1; 1]


실제로 되는지 확인해보자

[a_4; a_3] = [1 1; 1 0]^2[1; 1] = [2 1; 1 1][1; 1] = [3; 2]

익히 알다시피 a_4 = 3, a_3 = 2다

물론 니가 의심이 든다면 증명해도 된다 여기선 귀찮으니 생략한다


그럼 여기서 심플한 아이디어를 적용하자

예를 들어 a_34를 구한다고 하면 위 공식에 따라 이렇게 될 것이다.

[1 1; 1 0]^32 [1; 1]

그런데 행렬의 곱셈은 결합법칙이 성립하므로 다음과 같이 다시 쓸 수 있다.

[1 1; 1 0]^32 = [1 1; 1 0]^16 * [1 1; 1 0]^16

[1 1; 1 0]^16도 마찬가지로 [1 1; 1 0]^16 = [1 1; 1 0]^8 * [1 1; 1 0]^8

[1 1; 1 0]^8도 마찬가지로...

즉 n을 이진법으로 변환한 후 거듭제곱들을 구해서 걔네끼리 곱하면 훨씬 빨리 구할 수 있다


정수론 시간에 배운 테크닉이다 이거보다 더 빠른거 있으면 추천 좀


어쨌든 이러면 구현할 것이 구체적으로 나왔다

1. 행렬

2. 행렬간의 곱셈

3. 행렬의 거듭제곱을 빠르게 계산


터미널을 열고 cargo new {project_name} --bin을 입력하면 새로운 폴더가 생성되며 cargo가 베이스 라인을 잡아준다

러스트 배우면서 이게 제일 편했음 맨날 CMakeLists 쳐만들기 좆같았는데 알아서 해줌 개쩜


1ebec223e0dc2bae61ab96b304de297d388452685727799b9d8fe2abf31c3cc05cfe2a63a7cb7c4e852708911dab38ab47fc3e


하지만 난 씹하남자기 때문에 vim으로 코딩하지 않는다

멀쩡한 에디터 냅두고 그딴걸 왜 씀

이미 작성이 끝난 상태라 옆에 뭐가 많은데 일단 lib.rs를 보자

pub mod fibo;

달랑 이 한 줄 있다 fibo라는 모듈을 외부에서 쓸 수 있게 하겠다는 선언이다.

러스트는 컴파일 시 lib.rs를 보고 라이브러리를 컴파일한다

그럼 fibo는 어떻게 컴파일 하냐고?

그래서 해당 모듈과 같은 이름을 가진 러스트 스크립트를 만들어서 거기서 fibo 모듈을 작성하면 된다.


그게 위 사진에 나온 fibo.rs의 정체다

14~19line struct Mat을 보자

128바이트짜리 정수 네 개를 갖는단 소리다 끝


아니 시발 아까 행렬 곱셈 짠다며? ㅇㅇ 짤거임

바로 아래 impl Mat {...} 구문이 바로 그거다


fn mat_prod(&self, other: &Mat) -> Mat 을 보자

나 자신과 다른 Mat를 빌려서 Mat을 새로 만들어 준다는 뜻이다

그리고 안의 Mat은 익숙히 아는 그 공식이다 행 * 열


이제 fn new(i: i32) -> Mat을 보자

32바이트 정수를 입력받아서 Mat를 새로 만들어 준다는 뜻이다

let mut powers: Vec<i32> = Vec::new(); 여기에 이진법의 변환 결과를 담아둘 것이다

let mut divisor = i; 입력받은 i를 복사한다

while divisor > 0 { ... }

2로 나눈 나머지를 powers에 저장하고 divisor는 2로 나눈 몫을 취한다 언제까지? divisor가 0보다 큰 경우

예를 들어 i = 5라면, powers = [1,0,1]이 된다.

여기서 러스트의 한 가지 특이한 점이자 좋은 점은 위 코드에서 mut을 빼면 정상작동하지 않는다

왜냐면 mut이 없는 모든 변수는 다 불변성이거든 ㅇㅇ 변수가 변할 필요가 없으면 무조건 변하지 않음을 명시하는 건 매우 좋은 습관이다

러스트는 여기서 더 나아가서 변할 필요가 있을 때만 변함을 명시하라고 강제한다


let mat1 = Mat { ... }

[1 1; 1 0]을 선언하는 과정이다.


여기가 [1 1; 1 0]^n을 구하기 위한 핵심파트다

let mut matrices ...

matrices.push(mat);

}


for i in 0..powers.len() {...}

powers의 길이만큼 반복을 할 거다

이 때 i는 0부터 시작해서 하나씩 늘어난다


let cur_val = powers[i];

powers의 i번째 원소를 가져온다

수열은 항상 1부터 쓰지만 코딩할 땐 0부터 쓰는게 근본이다 matlab 근본없는 새끼야 좆까

cur_val은 논리적으로 0 또는 1밖에 들어갈 수가 없다 2로 나눈 나머지가 들어 있는 거에서 가져왔으니 당연한거다

어쨌든 이게 0이면 구하지 않는다

let mut mat = mat1.clone();

띠용? 이상한게 나왔다 뭔가하니 러스트의 규칙상 mat1은 자동으로 복사할 수 없다

즉 위에서 정수 받듯이 받을 수 없는 것이다

그러므로 Mat을 복사하는 함수가 필요하다 이런 문제는 Clone 트레이트를 구현함으로써 해결한다

그럼 그건 어떻게 구현하냐고? 아래와 같다

impl Clone for Mat {

    fn clone(&self) -> Self {

        Mat {

            one_one: self.one_one,

            one_two: self.one_two,

            two_one: self.two_one,

            two_two: self.two_two,

        }

    }

}

이제 원래 보던 곳으로 돌아가서 다음 구문 for _ in 0..i { ... }을 보자

행렬을 거듭제곱하는 파트다 이를 통해서 [1 1; 0 1]^1 [1 1; 0 1]^2 [1 1; 0 1]^4 [1 1; 0 1]^8 ... 이런 행렬을 빠르게 얻어내게 된다

그리고 이걸 matrices에 저장한다


let mut mat = mat1.clone();

for matrix in matrices {

mat = mat.mat_prod(&matrix);

}

mat

마지막으로 위에서 얻어낸 거듭제곱 행렬들을 모조리 곱해주고 그걸 반환한다


이로써 위에서 말한 1, 2, 3을 다했다 나머지는 조립만 하면 끝이다

조립 과정은 귀찮으니 생략한다

1ebec223e0dc2bae61ab96b304de297d388452685727799b9d8fe2abf21c3fc2b3bb3514a5ff210789142e800c58256dd08949

피보나치 수열을 1항부터 130항까지 찍어보라고 시켰다

0.00s가 걸리는 모습이다

값도 멀쩡하게 잘 나오니까 성공이다 끝