assign1.h File Reference

Functions that you need to implement for SUSTech CS205 (s22) assignment 1. More...

Go to the source code of this file.

Functions
int	quick_power (int x, int n)
int	matrix_addition (matrix mat_a, matrix mat_b, matrix mat_res)
int	matrix_multiplication (matrix mat_a, matrix mat_b, matrix mat_res)
int	naive_matrix_exp (matrix mat_a, int exp, matrix mat_res)
int	fast_matrix_exp (matrix mat_a, long long exp, matrix mat_res)
int	fast_cal_fib (long long n)

Variables
const int	MODULO
	Instead of using the magic number 1e9 + 7 everywhere in your program, you should use this constant when you need to take a module.

Detailed Description

Functions that you need to implement for SUSTech CS205 (s22) assignment 1.

EVERY functions should be defined in your source file, even if you could not implement it (in this case, leave a blank function body is okay). You NEED NOT modify this file, and DON'T submit this to Blackboard

Author

gdjs2

chris

Date

2022-03-01

Function Documentation

fast_cal_fib()

int fast_cal_fib

(

long long

n

)

Calculate the nth number in Fibonacci Sequence using Fast Matrix Exponentiation

Todo:

task 5, 20 pts

Parameters

n	the index of the result in Fibonacci Sequence

Returns

the number with index
in Fibonacci Sequence

fast_matrix_exp()

int fast_matrix_exp	(	matrix	mat_a,
		long long	exp,
		matrix	mat_res
	)

Calculate the result the of matrix exponentiation in a fast way

Todo:

task 4, 15 pts

Parameters

mat_res

the matrix used to store the result of mat_a ^ exp

Returns

1 if the size of mat_res does not match required size or mat_a is not square; 0 otherwise

Attention

it is guaranteed that mat_res is different from mat_a

matrix_addition()

int matrix_addition	(	matrix	mat_a,
		matrix	mat_b,
		matrix	mat_res
	)

Calculate the result the of matrix addition When returning 1, do not modify the entities in mat_res

Todo:

task 2-1, 20 pts

Parameters

mat_res

the matrix used to store the result of A + B

Returns

1 if the size of mat_res does not match required size or mat_a and mat_b cannot do the addition; 0 otherwise

Attention

it is guaranteed that mat_res is different from mat_a or mat_b

matrix_multiplication()

int matrix_multiplication	(	matrix	mat_a,
		matrix	mat_b,
		matrix	mat_res
	)

Calculate the result the of matrix multiplication

Todo:

task 2-2, 30 pts

Parameters

mat_res

the matrix used to store the result of A * B

Returns

1 if the size of mat_res does not match required size or mat_a and mat_b cannot do the multiplication; 0 otherwise

Attention

it is guaranteed that mat_res is different from mat_a or mat_b

naive_matrix_exp()

int naive_matrix_exp	(	matrix	mat_a,
		int	exp,
		matrix	mat_res
	)

Calculate the result the of matrix exponentiation in a naive way

Todo:

task 3, 15 pts

Parameters

mat_res

the matrix used to store the result of mat_a ^ exp

Returns

1 if the size of mat_res does not match required size or mat_a is not square; 0 otherwise

Attention

it is guaranteed that mat_res is different from mat_a

quick_power()

int quick_power	(	int	x,
		int	n
	)

Calculate power of x^n in O(log n)

Todo:

task 1, 20 pts

Parameters

x	the base number
n	the exponent number

Returns

the power, an integer