1 2 3 4 5 6 7 8 9 10 11 12 | void multiply(long long M[2][2], long long N[2][2]) { long long a = M[0][0]*N[0][0] + M[0][1]*N[1][0]; long long b = M[0][0]*N[0][1] + M[0][1]*N[1][1]; long long c = M[1][0]*N[0][0] + M[1][1]*N[1][0]; long long d = M[1][0]*N[0][1] + M[1][1]*N[1][1]; M[0][0] = a; M[0][1] = b; M[1][0] = c; M[1][1] = d; } |
1 2 3 4 5 6 7 8 9 10 11 | void power(long long M[2][2], int n) { if( n == 0 || n == 1) return; //no operation needed for base case long long A[2][2] = {{1,1},{1,0}}; power(M, n/2); //recursively call power on n/2 multiply(M, M); //a constant time multiplication if (n%2 != 0) //To handle odd n multiply(M, A); } |
1 2 3 4 5 6 7 8 | long long fib_m(int n) { long long A[2][2] = {{1,1},{1,0}}; //matrix A if (n == 0) return 0; //base case F0 = 0 power(A, n-1); //raise A to power (n-1) return A[0][0]; //Fn is element (0,0) } |
1 2 3 4 5 6 7 8 9 | Fib(n): load F0 to register 0 //smaller term in register 0 load F1 to register 1 //greater term in register 1 for k in range [2,3,…,n] swap the values in two registers //register 1 holds smaller term sum up the values in two register //sum up 2 terms store the sum to register 1 //register 1 holds the sum end for return register 1 //return the sum |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | long long fib_asm(int upto) { if ( upto < 2 ) return upto; //F0 = 0, F1 = 1 int mycount = upto - 1; long long f0 = 0L, f1 = 1L; asm ( "0: \n" //back to this when mycount > 0 "XGR %0, %1 \n" //1st XOR "XGR %1, %0 \n" //2nd XOR "XGR %0, %1 \n" //3rd XOR "AGR %1, %0 \n" //Add 2 terms, store to f1 "BRCT %2, 0b \n" //back to 0 if mycount > 0 :"+r"(f0), "+r"(f1), "+r"(mycount) ); return f1; //return f1 } |
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) | Powered by Discuz! 7.0.0 |