컴퓨터가 실수를 연분수 표현(continued fraction)으로 나타내는 방법

1. 유리수의 continued fraction continued fraction은 실수를 수렴하는 유리수의 수열로 표현하는 것이다. 이는 problem solving에서 유용할 수 있는데, 쉽게 계산될 수 있으며, 실수의 최적 유리수 근사를 찾는데 효과적으로 사용될 수 있어서 그렇다. 게다가 정수론에서 유용하게 사용되는 유클리드 알고리즘과 연관되어있다. 어떤 정수 $a_{0}, a_{1}, ..., a_{k}$에 대하여, $a_{1}, a_{2}, ... , a_{k}$가 1이상의 자연수일때, $$r = a_{0} + \frac{1}{a_{1} + \frac{1}{... + \frac{1}{a_{k}}}}$$ 를 유리수 r의 연분수 표현(continued fraction)이라고 부른다. 이를 r을 간단하..

• format_list_bulleted 대수학
• · 2023. 9. 20.
• textsms

Fast Fourier Transform을 이용한 빠른 다항식 곱셈 공부하기

1. 두 다항식의 곱셈 다항식 $f(x) = a_{0}x^{0} + a_{1}x^{1} + ... + a_{n-1}x^{n-1}$과 $g(x) = b_{0}x^{0} + b_{1}x^{1} + ... + b_{n-1}x^{n-1}$의 곱셈은.. $f(x)g(x) = a_{0}b_{0}x^{0} + (b_{0}a_{1} + a_{1}b_{0})x^{1} + ... + a_{n-1}b_{n-1}x^{2n-2}$로 나타날 것이다. 다항식을 각각 계수만을 가진 길이가 n인 벡터 A = [a0,a1,...,an-1], B = [b0, b1, ... , bn-1]로 나타낸다고 할때, 두 다항식의 곱셈은 길이가 2n-1인 벡터 C = [c0,c1,...,c(2n-2)]로 나타나며, $$c_{i} = \sum_{j=0..

• format_list_bulleted 대수학
• · 2023. 8. 29.
• textsms

키타마사 법(kitamasa method, きたまさ法)에 대한 공부

1. 키타마사 법(kitamasa method) 수열 $a_{n}$의 점화식을 이전의 몇개 항으로 정의한다면, 귀납적 정의, 재귀적 수열 등으로 부른다. $$a_{n} = \sum_{i = 1}^{k} w_{i}a_{n-i}$$ 이런 형태로 정의되는 대표적인 수열은 피보나치 수열이다. $$a_{n} = a_{n-1} + a_{n-2}, w_{1} = w_{2} = 1, k = 2$$ 이 피보나치 수열의 가장 빠른? 해법중 하나는 행렬을 이용하는 방법이다. https://deepdata.tistory.com/760 행렬을 이용한 피보나치 수열 문제의 해법 1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + ..

• format_list_bulleted 대수학
• · 2023. 8. 27.
• textsms

다항식의 곱셈과 나눗셈 기본 컴퓨터 구현 방법 배우기

1. 다항식의 곱셈 두 다항식의 곱셈은 구현하는 방법이 많이 있지만... 당장은 어려우니 일단 $O(k^{2})$으로 naive하게 구현 해보자. 다항식은 각 항의 계수를 배열에 저장하면 되는데 $f(x) = 2x^{2} + x + 1$이라고 한다면, a = [1,1,2]로 저장하면 된다. 곱셈하고자 하는 다항식이 $g(x) = x + 5$라고 한다면 b = [5,1]이고 두 다항식의 곱셈은 $f(x)g(x) = 2x^{3} + 11x^{2} + 6x + 5$로 [5,6,11,2]가 나와야한다. f(x)가 len(a)-1차수 다항식이고 g(x)가 len(b)-1차수 다항식이면, f(x)g(x)는 len(a)+len(b)-2차수 다항식이다. 위에서 len(a) = 3, len(b) = 2이고 각각 2차 1..

• format_list_bulleted 대수학
• · 2023. 8. 26.
• textsms