Script Programming(스크립트 프로그래밍)

정수의 곱셈을 빨리하기 위한 방법 중의 하나로 기수법으로 표현된 정수를 여러 조각으로 분할하여 덧셈이나 뺄셈 회수는 몇회 증가하는 대신, 곱셈 횟수를 몇회 감소하는 방법입니다. 곱셈이 덧셈이나 뺄셈 보다는 시간이 많이 걸린다는 전제 하에 카라츄바 곱셈(Karatsuba multiplication)을 적용하면 시간복잡도 O(N**2) 의 계산 과정을 을 약 시간복잡도 O(N*&1.5)의 계산 과정으로 줄일 수 있습니다. (여기서 N은 기수법으로 표현된 정수의 분할 개수입니다.) 예를 들어 두 자리 십진법 수 23과 45의 곱셈 23*45을 생각해 봅니다. (이 경우 N = 2 입니다.) 2 3 x ) 4 5 ----------- 1 5 1 0 1 2 8 ----------- 1 0 3 5 위의 곱셈표에서 ..

피보나치 수열이 0 이상의 정수 n에 대하여 선형점화공식(linear recurency): f(n) = f(n - 1) + f(n - 2) 과 과 초기조건(initial condition): f(0) = 0, f(1) = 1 로 정의된 수열인데 이를 음의 정수 n에 대하여도 위의 점화공식을 f(n) = f(n + 2) - f(n + 1) (∀ n = -1, -2, -3, -4, -5, ...) 로 고쳐 축차 적용하여 얻어지는 수열 f(-1), f(-2), f(-3), f(-4), f(-5), .... 을 네가보나치 수열(negabonacci sequence)이라고 한다. 즉, f(-1) = f(1) - f(0) = 1 - 0 = 1 f(-2) = f(0) - f(-1) = 0 - 1 = -1 f(-3) ..

피보나치 수열는 피보나치가 토끼의 성장과 번식을 관찰하다가 발견한 수열이라고 합니다. 피보나치 수(Fibonacci number)의 정의는 간단합니다. 0과 1로 시작해서 덧셈을 계속 이어가면 얻어지는 수들입니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...... 초항을 제 0항으로 하고 제 0항, 제 1항, 제 2항, ...... 순으로 나열하면 F(0), F(1), F(2), F(3), F(4), F(5), F(6), F(7), F(8), F(9), F(10), ...... 이 되고, 번호를 괄호 속에 넣지 않고 우측 첨자로 붙여 나열하면, F0, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, ...... 이 됩니다. 즉, F0 = F(0) = ..

Algorithm STRASSEN(A,B) 1. n ←number of rows of A 2. if n = 1 then return (a11b11) 3. else 4. Determine Aij and Bij for i, j = 1, 2 (blocks as before) 5. Compute M1, . . . , M7 (as below) 6. Compute C11, C12, C21, C22 (as below) 7. return C11 C12 C21 C22 M1 = (A11 + A22)*(B11 + B22) M2 = (A21 + A22)*B11 M3 = A11*(B12 − B22) M4 = A22*(B21− B11) M5 = (A11 + A12)*B22 M6 = (A21 − A11)*(B11 + B12) M7..

십의 자리수가 같고 1의 자리수를 합하면 10이 되는 두 자연수위 솝셈을 쉽고 빨리 계산하는 방법을 소개 한다. 25 75 81 63 19 x) 25 x) 75 x) 89 x) 67 x) 11 625 5625 7209 4221 209 1의 자리수를 곱하여 그 아래에 자리를 맞추어 적어둔다. 그 왼 쪽에는 10의 자리수 둘 중 하나만 플러스 1 하여 서로 곱한다. 예를 들어 25*25의 경우에는 10의 자리수가 2와 2인데 둘 중 하나만 플러스 1 하면 3과 2가 된다. 이 둘을 곱하면 6이다. 이를 또 그 밑에 1의 자리수 곱하여 적어둔 그 좌측에 자리를 맞추어 붙여주면 계산이 끝난다. 이 과정을 좀 더 상세하게 설명하면 25 x) 25 25

중학교 수학만 공부한 사람이면 누구나 아는 계산식 ab = ((a + b)^2 - (a - b)^2)/4 를 이용하는 곱셈 계산법에 대해서 알아 보자. n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 G(n) 0 0 1 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81 (위의 표에서 G(n) = n*n/4 = (n^2)/4 이다, ) G(n) = k^2 if n = 2k (짝수), G(n) = k(k+1) = k^2 + k if n = 2k + 1 (홀수) 임을 이용해도 된다. 이 때는 제곱수만 기억하고 있으면 된다. 예를 들어 8*7 의 값을 구한다고 하자. 먼저 8과 7의 합과 차를 구한다. 8 + 7 = 15 8 - 7 = 1 이다..