Discrete structure

MAC281 Discrete Structures Project (Integrative learning, written) Goal: The main goal of the project is to let students use their prior knowledge, try to use the skills they have learnt to solve real world problems. Using this assignment students are required to learn to use the skills they have learned in their previous classes, solve the problems given and reflect on how they can apply it to solve real world issues. Deliverables: The students are required to submit a written report along with the programs they have written. The report has to address all the prompts mentioned. The report should be properly presented by using appropriate font (Time new roman, preferably font size 12). Please keep the report ANONYMOUS without adding any name or course information. Tasks: 1. Write an iterative C++ function that inputs a nonnegative integer n and returns the nth Fibonacci number. 2. Write a recursive C++ function that inputs a nonnegative integer n and returns the nth Fibonacci number. 3. Compare the number of operations and time taken to compute Fibonacci numbers recursively versus that needed to compute them iteratively. 4. Use the above functions to write a C++ program for solving each of the following computational problems. I. Find the exact value of f100, f500, and f1000, where fn is the nth Fibonacci number. What are times taken to find out the exact values? II. Find the smallest Fibonacci number (1) greater than 1,000,000, and (2) greater than 1,000,000,000. III. Find as many prime Fibonacci numbers as you can. It is unknown whether there are infinitely many of these. Find out the times taken to find first 10, 20, 30, 40up to 200 and draw a graph and see the pattern. Initial report submission to Discussions, due on Sunday April 16: 1. Prepare a project report in WORD document to describe how you implement above tasks, including (1) problem analysis and solution plan, (2) source code, (3) discussion on experimental results in tables or graphs, (4) reflection and conclusion. 2. Your reflection should address all of the below mentioned questions a) Describe the Fibonacci series and write briefly what you have done in the assignment. b) What are the different skills, programming techniques have you used in order to run the experiments? c) What did you observe when you did the comparisons in Task 3 and Task 4? Explain the graph that you have drawn from Task 4.III? d) List at least three different applications of the Fibonacci numbers to sciences and describe one of them in details. Think of situation or a real world problem where you can apply concept of Fibonacci numbers to solve it. Explain? e) Write a paragraph, explaining what you have done in this assignment. What were the challenges you have faced when solving these problems. How can you improve the programs you have written to solve these problems? Peer review at Discussions, due on Wednesday April 19: 3. Check at least two other students reflection, and post your comments to others work, by Monday April 17. 4. Read other students comments, and provide feedback to the comments. Final report revision and resubmission based on feedback, due on April 24: 5. Prepare a WORD document including the revised project report, remove all information related to the names, or class information, and submit the final version to Assessment. // i need this part 3. Check at least two other students reflection, and post your comments to others work, by Monday April 17. here are few students works......... one student

Fibonacci Project Report

Problems:

(1) Integer variables can only calculate up to Fibonacci(46).

(2) Unsigned integer, long integer, and unsigned long integer variables can only calculate up to Fibonacci(47).

(3) Long long integer, and unsigned long long integer variables can only calculate up to Fibonacci(93).

(4) When using the library, the most prime numbers we can find is 10 numbers, and the computer gets stuck.

(5) Without using the library, the most prime number we can find is 11 numbers, and the computer gets stuck.

(6) When using array, every digit is a separate number which is hard to find the prime numbers.

Solution:

(1) We found a library that can declare an InfInt which can store almost unlimited range of integer numbers.

(2) Theres also a suggestion to use array.

(3) Try to use long long integer variables to find more than 10 prime numbers.

(4) Try to use array to find more prime numbers.

(5) Convert array to string and convert string to long long integer to find the prime numbers.

Source Code:

Iterative #include

#include

#include

using namespace std;

InfInt result, first = 0, second = 1;

int counter = 0;

InfInt Fibonacci(int a);

bool IsPrime(InfInt num);

int main() {

clock_t begin = clock();

int n;

cout << "Please enter the position of Fibonacci: " << endl;

cin >> n;

int n2 = n;

cout << "Prime numbers in Fibonacci(" << n2 << ") are: ";

cout << ". The Fibonacci number is: " << Fibonacci(n) << endl;

cout << "The total prime numbers are: " << counter << "numbers." << endl;

clock_t end = clock();

double time_period = double(end - begin) / 1000;

cout << "Time period is: " << time_period << endl;

system("pause");

return 0;

}

InfInt Fibonacci(int a) {

int a2 = a;

for (int i = 1; i <= a; i++) {

result = first + second;

second = first;

first = result;

IsPrime(result);

}

return result;

}

bool IsPrime(InfInt num) {

int r = num.toInt();

if (r <= 1) return false;

else if (r == 2) {

counter++;

cout << r;

}

else if (r == 3 || r == 5) {

counter++;

cout << "," << r;

}

else {

for (int i = 2; i <= sqrt(r); i++) {

if (result % i == 0) return false;

}

counter++;

cout << "," << r;

}

}

Recursive

#include

#include

#include

using namespace std;

InfInt result, first = 0, second = 1;

int counter = 0;

InfInt Fibonacci(int &a);

bool IsPrime(InfInt r);

int main() {

clock_t begin = clock();

int n;

cout << "Please enter the position of Fibonacci: " << endl;

cin >> n;

int n2 = n;

cout << "Prime numbers in Fibonacci(" << n2 << ") are: ";

cout << ". The Fibonacci number is: " << Fibonacci(n) << endl;

cout << "Total prime numbers are: " << counter << endl;

clock_t end = clock();

double time_period = double(end-begin)/1000;

cout << "Time period is: " << time_period << endl;

system("pause");

return 0;

}

InfInt Fibonacci(int &a){

int a2 = a;

result = first + second;

second = first;

first = result;

IsPrime(result);

if(a == 1) return result;

if(a > 0){

a -= 1;

Fibonacci(a);

}

return result;

}

bool IsPrime(InfInt r) {

int num = r.toInt();

if (num <= 1) return false;

else if (num == 2) {

counter++;

cout << r;

}

else if (num == 3 || num == 5) {

counter++;

cout << "," << r;

}

else {

for (int i = 2; i <= sqrt(num); i++) {

if (result % i == 0) return false;

}

counter++;

cout << "," << r;

}

}

Array-Iterative

#include

#include

#include

using namespace std;

unsigned short int result[256],first[256], second[256];

string s_result;

int counter = 0;

int Fibonacci(int a);

bool IsPrime(string r);

int main(int argc, const char * argv[]) {

clock_t begin = clock();

result[0] = 0, first[0] = 0, second[0] = 1;

int n;

cout << "Please enter the position of Fibonacci: " << endl;

cin >> n;

cout << "Prime number: ";

int a = Fibonacci(n);

cout << " Total prime numbers are: " << counter << " numbers." << endl;

cout << "The Fibonacci number is: ";

for(int i = 0; a >= i; a--){

cout << result[a];

}

cout << endl;

clock_t end = clock();

double elapsed_secs = double(end - begin) / 1000;

cout << "Time period: " << elapsed_secs << " sec." << endl;

system("pause");

return 0;

}

int Fibonacci(int a){

for(int j = 1; j <= a; j++){

for (int i = 0; i < 256; i++) {

if (first[i] >= 10) {

first[i + 1] += (first[i] / 10);

first[i] %= 10;

}

if (second[i] >= 10) {

second[i + 1] += (second[i] / 10);

second[i] %= 10;

}

if (result[i] >= 10) {

result[(i + 1)] += (result[i] / 10);

result[i] %= 10;

}

result[i] = (first[i] + second[i]);

second[i] = first[i];

first[i] = result[i];

}

for (int i = 0; i < 256; i++) {

if (first[i] >= 10) {

first[i + 1] += (first[i] / 10);

first[i] %= 10;

}

if (second[i] >= 10) {

second[i + 1] += (second[i] / 10);

second[i] %= 10;

}

if (result[i] >= 10) {

result[(i + 1)] += (result[i] / 10);

result[i] %= 10;

}

}

for (int i = 2; i < 256; i++) {

if (result[i] == 0 && result[i - 1] == 0 && result[i - 2] == 0) {

int b = (i - 3);

for (int j = 0; b >= j; b--) {

s_result += to_string(result[b]);

}

IsPrime(s_result);

s_result = "";

break;

}

}

}

for(int i = 2; i < 256; i++){

if (result[i] == 0 && result[i - 1] == 0 && result[i - 2] == 0) return (i - 3);

}

return 4;

}

bool IsPrime(string r) {

long long int x = stoll(r);

if (x <= 1) return false;

else if (x == 2) {

counter++;

cout << r;

}

else if (x == 3 || x == 5) {

counter++;

cout << "," << r;

}

else {

for (int i = 2; i <= sqrt(x); i++) {

if (x % i == 0) return false;

}

counter++;

cout << "," << r;

}

}

Array-Recursive

#include

#include

#include

using namespace std;

unsigned short int result[256], first[256], second[256];

string s_result;

int counter = 0;

int Fibonacci(int &a);

bool IsPrime(string r);

int main(int argc, const char * argv[]) {

clock_t begin = clock();

result[0] = 0, first[0] = 0, second[0] = 1;

int n;

cout << "Please enter the position of Fibonacci: " << endl;

cin >> n;

cout << "Prime number: ";

int a = Fibonacci(n);

cout << " Total prime numbers are: " << counter << " numbers." << endl;

cout << "The Fibonacci number is: ";

for (int i = 0; a >= i; a--) {

cout << result[a];

}

cout << endl;

clock_t end = clock();

double elapsed_secs = double(end - begin) / 1000;

cout << "Time period: " << elapsed_secs << " sec." << endl;

system("pause");

return 0;

}

int Fibonacci(int &a) {

a--;

for (int i = 0; i < 256; i++) {

if (first[i] >= 10) {

first[i + 1] += (first[i] / 10);

first[i] %= 10;

}

if (second[i] >= 10) {

second[i + 1] += (second[i] / 10);

second[i] %= 10;

}

if (result[i] >= 10) {

result[(i + 1)] += (result[i] / 10);

result[i] %= 10;

}

result[i] = (first[i] + second[i]);

second[i] = first[i];

first[i] = result[i];

}

for (int i = 0; i < 256; i++) {

if (first[i] >= 10) {

first[i + 1] += (first[i] / 10);

first[i] %= 10;

}

if (second[i] >= 10) {

second[i + 1] += (second[i] / 10);

second[i] %= 10;

}

if (result[i] >= 10) {

result[(i + 1)] += (result[i] / 10);

result[i] %= 10;

}

}

for (int i = 2; i < 256; i++) {

if (result[i] == 0 && result[i - 1] == 0 && result[i - 2] == 0) {

int b = (i - 3);

for (int j = 0; b >= j; b--) {

s_result += to_string(result[b]);

}

IsPrime(s_result);

s_result = "";

break;

}

}

if (a > 0) Fibonacci(a);

else for (int i = 2; i < 256; i++) if (result[i] == 0 && result[i - 1] == 0 && result[i - 2] == 0) return (i - 3);

}

bool IsPrime(string r) {

long long int x = stoll(r);

if (x <= 1) return false;

else if (x == 2) {

counter++;

cout << r;

}

else if (x == 3 || x == 5) {

counter++;

cout << "," << r;

}

else {

for (int i = 2; i <= sqrt(x); i++) {

if (x % i == 0) return false;

}

counter++;

cout << "," << r;

}

}

Reflection

a) Describe the Fibonacci series and write briefly what you have done in the assignment.

Fibonacci series is F(n) = F(n-1)+F(n-2), and I have written 4 different programs to find Fibonacci numbers in C++ and also calculated the time period of running 4 programs finding positions of Fibonacci numbers and Fibonacci primes.

b) What are the different skills, programming techniques have you used in order to run the experiments?

I have inserted a new library in order to show a big number of Fibonacci, and have used array to represent the big number in another way.

c) What did you observe when you did the comparisons in Task 3 and Task 4? Explain the graph that you have drawn from Task 4.III?

In Task 3: Recursive function is always taking longer than Iterative one.

In Task 4: I. When Im using the Library with InfInt, the result: Iterative: F(100) 0.004 sec / F(500) 0.023 sec / F(1000) 0.059 sec Recursive: F(100) 0.006 sec / F(500) 0.025 sec / F(1000) 0.067 sec Using array, the result: Iterative: F(100) 0.003 sec / F(500) 0.005 sec / F(1000) 0.009 sec Recursive: F(100) 0.005 sec / F(500) 0.011 sec / F(1000) 0.01 sec

II. Find the smallest Fibonacci number greater than 1,000,000: Fibonacci(31): 1346269. No matter in which function: 0.002 sec The smallest Fibonacci number greater than 1,000,000,000: Fibonacci(45): 1134903170. No matter in which function: 0.003 sec

III. Find as many prime Fibonacci numbers as you can. I can only find 12 prime Fibonacci numbers which are:

d) List at least three different applications of the Fibonacci numbers to sciences and describe one of them in details. Think of situation or a real world problem where you can apply concept of Fibonacci numbers to solve it. Explain?

Branching trees show Fibonacci sequence: Lately, theres a 13-Year-Old student makes solar power breakthrough by harnessing the Fibonacci Sequence. After studying how trees branch in a very specific way, Aidan Dwyer created a solar cell tree that produces 20-50% more power than a uniform array of photovoltaic panels. (Inhabitat news)

Sunflower seeds grow in Fibonacci spirals: A Fibonacci spiral is a series of connected quarter-circles drawn inside an array of squares with Fibonacci numbers for dimensions.

Humans body also follows Fibonacci Sequence: We have one mouth, one nose, two eyes, three segments to each limb and five fingers on each hand.

e) Write a paragraph, explaining what you have done in this assignment. What were the challenges you have faced when solving these problems. How can you improve the programs you have written to solve these problems?

I have tried so many ways to represent the number greater than a value since I found out that the biggest type of variables long long int can only counted up to Fibonacci(93): 12200160415121876738, and finally found a library on internet that could store almost unlimited range of integer numbers and a hint for writing it in array. And I also tried to find the prime Fibonacci numbers by using different type of variables in the program, the fastest way is to use int yet which can only counted up to Fibonacci(46): 1836311903, more than that it shows negative numbers. And long long int is also faster than using array or the library yet which can counted up to Fibonacci(93), more than that it also shows negative numbers. But when I use the library, I cant find more than 12 prime Fibonacci numbers, and I have no solution so far.

here is another student ,,

Fibonacci Number, Recursive vs Iterative

The problem is to calculate Fibonacci number recursively and iteratively, and to compare them with the time it need to complete the calculation. First, I use formula for finding Fibonacci numbers F_n = F_n-1 + F_n-2. So now we know it, and I start implementing this into the C++ program. The first problem I encounter when the basic are implemented is that it does not hold a big integer. So I use a library call ttmath to hold the big number as the Fibonacci series got bigger. The time it takes to find f(100), f(1000), f(10000) in the iterative way is below 0 second. It is really fast to calculate.

As I implement recursion, I found something really odd, there is a lot less code when writing a recursive function to find the Fibonacci number. But as I watch, calculating f(10)- f(40), it have the same speed as the iterative way. However, as the number go bigger and bigger, the time taken is started to pile up. It takes really long to find f(100) and beyond. Because it started to take its precious time at f(50). In most case the more the code the longer the execution time and this is backward.

To compute recursively for f(20) and iteratively at f(20) the time I got is the same. It ranges from 0.0012 to 0.0025 second, but as the number get bigger for recursive the timing grew to the extreme. It takes hours to compute value in the 100000. Which is not efficient, and in iterative still use way less time then recursive, the timing is still below 0 second when calculating f(100), 0.018 second. One of the reason to this is that it compares more frequently then the iterative one. So this took most of the time on the calculation.

Reflection

After doing the project and coming up with a solution to the problems. I think that there are much more to coding, some code it might long and it is hard coded and the result can be better, however the only problem with long code is when there are a error is harder to find and to fix. Recursive and iterative way in finding the Fibonacci number are different in timing. Iterative way to find the numbers; it uses a lot more codes than recursive way. However, it takes less time to figure out the answer. Sometime some solution is better off to use recursive as the way to implement the code. Sometime it isnt the best solution in time wise. So it all depends on the problems given to figure out what is the best way to implementing the solution to it.

So at the end the best solution for finding the Fibonacci numbers is using iterative implementation. It is the most efficient in time and operations use to find the result to the problems given.

This is the source code for finding Fibonacci number. I used ttmath library to be in charge of the big numbers. And this could be the reason to why it can be calculating below the 0 second. However that is not the case, I check the program and run without including the ttmath library to handle big numbers it still works, the run time is still below 0 second, it is in the millisecond.

---------------------------------------------------

#include "ttmath/ttmath.h"

#include

#include

#include

using namespace std;

int main()

{

ttmath::UInt<1000> x,y,z;

//using the ttmath here to establize that the variable (x, y, z ) can store big intergers.

int i;

int b;

cin>> b; //entering integer to be calculate

cout<< "Enter the number to the find the fibonacci at that number"<

x = 1;

y = 1;

float clicks = clock();//clock function, to count the time

for (i = 1; i < b; ++i) {// loop to calculate the Fibonacci number.

z = y;

y = y + x;

x = z;

}

clicks = clock() - clicks;

cout << setw(8) << i << setw(1100) << x << endl; // the preision is calculated to hold that much places.

cout << "seconds: " << float(clicks)/CLOCKS_PER_SEC << endl; // to put the time into seconds

return 0;

}

Below is the recursive version of finding Fibonacci number. In this program I did not include the ttmath library is due to the fact that when calculating big numbers, in recursive it become really slow. So I did not implement the library to store big numbers.

---------------------------------------------------

#include

using namespace std;

long fibonacci(long);

int main(void)

{

int n;

n = 50;

cout<< n << "th: " << fibonacci(n) <<" ";

return 0;

}

long fibonacci(long number)

{

if(number == 0 || number == 1)

return number;

else

return (fibonacci(number-1) + fibonacci(number-2));

}

Below contains code for recursive with clock

#include

#include

#include

using namespace std;

long fibonacci(long);

int main(void)

{

float clicks = clock();

int n;

cin>> n;

cout<< n << "th: " << fibonacci(n) <<" ";

clicks = clock() - clicks;

cout << setw(8)<< "seconds: " << float(clicks)/CLOCKS_PER_SEC << endl; // to put the time into seconds

return 0;

}

long fibonacci(long number)

{

if(number == 0 || number == 1)

return number;

else

return (fibonacci(number-1) + fibonacci(number-2));

}

Find as many prime Fibonacci numbers as you can. It is unknown whether there are infinitely many of these. Find out the times taken to find first 10, 20, 30, 40...up to 200 and draw a graph and see the pattern.

below code is to calculate prime number

#include

#include

#include

void rePrime ();

using namespace std;

int main()

{

ttmath::UInt<1000> x,y,z;

//using the ttmath here to establize that the variable (x, y, z ) can store big intergers.

int i;

int b;

cin>> b; //entering integer to be calculate

cout<< "Enter the number to the find the fibonacci at that number"<

x = 1;

y = 1;

float clicks = clock();//clock function, to count the time

for (i = 1; i < b; ++i) {// loop to calculate the Fibonacci number.

z = y;

y = y + x;

x = z;

for(i = 1; i < b; ++i){

rePrime(x);

}

}

clicks = clock() - clicks;

cout << setw(8) << i << setw(1100) << x << endl; // the preision is calculated to hold that much places.

cout << "seconds: " << float(clicks)/CLOCKS_PER_SEC << endl; // to put the time into seconds

return 0; }

void rePrime (){

int n, i;

for(i = 2; i <= n / 2; ++i)

{

if(n % i == 0)

{

if (n<2)

cout<< is prime: << x<

break;

}

}

please can u do the the comment , and peer review one please....