I need help writing this fibonacci sequence program in C, the part that gets me
ID: 3858388 • Letter: I
Question
I need help writing this fibonacci sequence program in C, the part that gets me is the hexadecimal part in the parse function. These are the function requirements. It has to include a header file for big40.h and can't have a main function. Header file is:
.............................
#ifndef __BIG40_H
#define __BIG40_H
#define MAX40 40
//const int MAX40=40;
typedef struct Integer40
{
// a dynamically allocated array to hold a 40
// digit integer, stored in reverse order
int *digits;
} Integer40;
typedef struct big40RatingStruct{
char *NID; //pointer to a malloc'ed buffer for the NID
float degreeOfDifficulty; //1.0 for super easy to 5.0 for insanity++
float duration; // Hours spent writing, reading,
// designing & building the code
} big40RatingStruct;
char *cryptoVariableFilename; // for the filename
int seed;//to seed the RNG or not
int nFib; //control the number of Fibonacci numbers to calculate
Integer40 *cryptoVariable; // 40 digits of used to start the F[x]
Integer40 *hwConfigVariable; // 40 digits of psuedo or real
// randomness to start the F[x]
// Functional Prototypes
Integer40 *big40Add(Integer40 *p, Integer40 *q);
Integer40 *big40Destroyer(Integer40 *p);
Integer40 *fibBig40(int n, Integer40 *first, Integer40 *second);
void big40Rating(void);
Integer40 *parseString(char *str);
Integer40 *loadHWConfigVariable(int doSeed);
Integer40 *loadCryptoVariable(char *inputString);
.................................................................................
function rquirements:
..............................................
In the source file you submit, big40.c, you must implement the following functions. You may implement
any auxiliary functions you need to make these work, as well. Notice that none of your
functions should print anything to the screen or STDOUT.
Integer40 *big40Add(Integer40 *p, Integer40 *q);
Description: Return a pointer to a new, dynamically allocated Integer40 struct that contains the
result of adding the 40 digit integers represented by p and q.
Special Notes: If a NULL pointer is passed to this function, simply return NULL. If any dynamic
memory allocation functions fail within this function, also return NULL, but be careful
to avoid memory leaks when you do so.
Hint: Before adding two huge integers, you will want to create an array to store the result. Remember
that all integers in this problem are 40 digits long. In the event that the most significant
digits (MSD) result in a carry, the carry will be ignored. For example, if the MSD of
the two inputs are 9 and 7, the resultant MSD will be 6 with a carry of 1 for the MSD + 1
digit. (916 + 716 = 1016, therefore 6 is the MSD and the 1 is ignored.)1
Returns: A pointer to the newly allocated Integer40 struct, or NULL in the special cases mentioned
above.
Integer40 *i40Destroyer(Integer40 *p);
Description: Destroy any and all dynamically allocated memory associated with p. Avoid segmentation
faults and memory leaks.
Returns: NULL
Integer40 *parseString(char *str);
Description: Convert a number from string format to Integer40 format. (For example function
calls, see big40-main01.c.)
Special Notes: If the empty string (“”) is passed to this function, treat it as a zero (“0”). If
any dynamic memory allocation functions fail within this function, or if str is NULL, return
NULL, be careful to avoid memory leaks when you do so. You may assume the string
will only contain ASCII digits ‘0’ through ‘9’ and the letters ’A’ thru ’F’ in either upper
or lower case, for a minimum of 40 digits. In the event that 40 digits are not in the input
string, print an error message to STDERR and fill with leading zeroes. Also, if there are
more than 40 digits in the input string use the first 40 digits in the string.
Returns: A pointer to the newly allocated Integer40 struct, or NULL if dynamic memory allocation
fails or if the input str is NULL.
1The subscript of 16 indicate base 16. However the two expressions 1016 and 10x are equivalent and used
equally often.
Integer40 *fibBig40(int n, Integer40 *first, Integer40 *second);
Description: This is your Fibonacci function. Pay careful attention the F(0) is initialized with
the hwConfigVariable and F(1) is initialized with the cryptoVariable. Implement an iterative
solution that runs in O(n) time and returns a pointer to a Integer40 struct that contains
F(n). Be sure to prevent memory leaks before returning from this function.
Space Consideration: When computing F(n) for large n, it’s important to keep as few Fibonacci
numbers in memory as necessary at any given time. For example, in building up to F(10000),
you won’t want to hold Fibonacci numbers F(0) through F(9999) in memory all at once.
Find a way to have only a few Fibonacci numbers in memory at any given time over the
course of a single call to fibBig40(...).
Special Notes: Remember that n is the second parameter passed as an input argument to the
program. You may assume that n is a non-negative integer. If any dynamic memory allocation
functions fail within this function, return NULL, but be careful to avoid memory leaks
when you do so.
Returns: A pointer to an Integer40 representing F(n), or NULL if dynamic memory allocation
fails.
void big40Rating();
STDERR output: Outputs the following items to STDERR, delimited by a semicolon “;”:
1. NID
2. A difficulty rating of how difficult you found this assignment on a scale of 1.0 (ridiculously
easy) through 5.0 (insanely difficult).
3. Duration, in hours, of the time you spent on this assignment.
The first argument to this function is the pointer to the big40RatingStruct which is defined
in the big40.h include file. Make sure to output those items to STDERR. Each element should
be terminated or delimited by a “;”.
Integer40* loadHwConfigVariable(int seed);
Returns: A pointer to an Integer40 array of 40 random digits. If the input variable seed is set,
the random number generator will be seeded, otherwise not. Regardless, the 40 digits will be
initialized in 10 unique groups of 4 random digits. Returns NULL if there is an error during
creation or initialization of the hwConfigVariable.
Integer40* loadCryptoVariable(char *cryptoVariableFilename);
Returns: A pointer to an Integer40 array of 40 random digits read in from the cryptoVariable-
Filename. Returns NULL if there is an error during initialization of the cryptoVariable or in
the file I/O.
Explanation / Answer
public class Fibonnaci {
// Output = 0 1 1 2 3 5 8 13
static int fibMemo[];
public static void main(String args[]) {
int num = 20;
System.out.println("By For Loop");
Long startTimeForLoop = System.nanoTime();
// returns the fib series
int fibSeries[] = fib(num);
for (int i = 0; i < fibSeries.length; i++) {
System.out.print(" " + fibSeries[i] + " ");
}
Long stopTimeForLoop = System.nanoTime();
System.out.println("");
System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));
System.out.println("By Using Recursion");
Long startTimeRecursion = System.nanoTime();
// uses recursion
int fibSeriesRec[] = fibByRec(num);
for (int i = 0; i < fibSeriesRec.length; i++) {
System.out.print(" " + fibSeriesRec[i] + " ");
}
Long stopTimeRecursion = System.nanoTime();
System.out.println("");
System.out.println("For Loop Time:" + (stopTimeRecursion -startTimeRecursion));
System.out.println("By Using Memoization Technique");
Long startTimeMemo = System.nanoTime();
// uses memoization
fibMemo = new int[num];
fibByRecMemo(num-1);
for (int i = 0; i < fibMemo.length; i++) {
System.out.print(" " + fibMemo[i] + " ");
}
Long stopTimeMemo = System.nanoTime();
System.out.println("");
System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
}
//fib by memoization
public static int fibByRecMemo(int num){
if(num == 0){
fibMemo[0] = 0;
return 0;
}
if(num ==1 || num ==2){
fibMemo[num] = 1;
return 1;
}
if(fibMemo[num] == 0){
fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
return fibMemo[num];
}else{
return fibMemo[num];
}
}
public static int[] fibByRec(int num) {
int fib[] = new int[num];
for (int i = 0; i < num; i++) {
fib[i] = fibRec(i);
}
return fib;
}
public static int fibRec(int num) {
if (num == 0) {
return 0;
} else if (num == 1 || num == 2) {
return 1;
} else {
return fibRec(num - 1) + fibRec(num - 2);
}
}
public static int[] fib(int num) {
int fibSum[] = new int[num];
for (int i = 0; i < num; i++) {
if (i == 0) {
fibSum[i] = i;
continue;
}
if (i == 1 || i == 2) {
fibSum[i] = 1;
continue;
}
fibSum[i] = fibSum[i - 1] + fibSum[i - 2];
}
return fibSum;
}
}