Assignment 1 — Bignum Package

联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

Assignment 1 — Bignum Package

In this part of the assignment, you are asked to implement a service that performs basic algebra on integers of arbitrary lengths, called bignums. The service includes two main components: a library that provides an API for managing and operating on bignums, and a calculator program that performs basic calculations with arbitrary length integers. Postgraduate students need to implement the complete library. Undergraduates only need to handle positive integers.

1 Library

1.1 Interface

The library provides one abstract data structure bn t, which is a pointer to the (externally abstract) struct bn. The functions operating on this structure are described below. This interface is de ned in the le bn .h, which is available from MyUni.

1.1.1 bn t bn alloc(void)

Allocates a new bignum and initialises it to (positive) 0. Returns NULL if not enough resources are available. We provide a sample implementation of this function, which you can use.

1.1.2 void bn free(bn t bn)

Frees all the resources associated with the bignum bn.

1.1.3 int bn add(bn t result, bn t a, bn t b)

Adds the bignums a and b and places the sum in result. Returns 0 if completed successfully and _1 otherwise.

1.1.4 int bn sub(bn t result, bn t a, bn t b)

Subtracts the bignum b from a and places the di erence in result. Returns 0 if completed successfully and _1 otherwise.

Undergraduate students: if a is smaller than b, the result is set to 0.

1.1.5 int bn mul(bn t result, bn t a, bn t b)

Multiplies the bignums a and b and places the product in result. Returns 0 if completed successfully and _1 otherwise.

1.1.6 int bn fromString(bn t bn, const char *str)

Read the decimal number in the string str and stores its value in bn. Returns 0 if completed successfully and _1 otherwise.

Undergraduate students need only handle non-negative numbers. Postgraduate students need to handle both positive and negative numbers.

1.1.7 int bn toString(bn t bn, char *buf, int buflen)

Converts a bignum bn to a string. including the terminating NUL character. If buflen is large enough to store the converted string, the function stores the string in buf and returns 0. Otherwise, buf is not changed and the return value is the number of characters required to store the string representation, The function returns a negative number in case of error.

We provide a sample implementation of this function, which you can use.

1.1.8 int bn IAmAnUndergrad()

Returns 1 if you’re an undergraduate student, 0 if you’re a postgraduate student. It is highly recommended not to return the wrong value. Implementations that return 0 will be marked on handling both positive and negative numbers.. Implementations that return 1 will only be marked on handling non-negative numbers only, with a penalty of 20% for postgraduate students that use this option.

1.2 Sample Implementation

We provide a very partial implementation of the library. (Available from MyUni.) This includes a sample declaration of the bignum structure struct bn (Figure 1), and implementations of the bn alloc and bn toString functions. If you wish, you may use your own implementation of the structure or the functions, but you need to make sure you provide the full functionality. Past experience shows that students who use their own implementation tend to do worse than average.

struct bn {

int bn_len;

int bn_size;

int bn_sign;

uint16_t *bn_data;

};

Figure 1: Bignum abstraction.

The elds of the structure are:

bn len The length (number of digits) of the number represented by the structure.

bn data An array that stores the values of the digits of the number.

bn sign The sign of the number. The value of the sign is 1 for positive numbers and _1 for negative numbers. Undergraduate students should set the eld to 1 when allocating numbers and may assume it does not change after that.

bn size The number of digits allocated in bn data.

The number is reprsented as a sequence of digits in base 216 = 65536. That is, if s is the value of bn sign, l the value of bn len, and di the value of the ith element in bn data (i.e. bn data[i]), then the value represented by the structure is given by: s (216 )i di .

1.3 An Example

Figure 2shows a program that uses the library to calculate the rst 1000 elements of the Fibonacci sequence.

#include

#include “bn .h”

int main() {

char buf[1000];

bn_t a = bn_alloc();

bn_t b = bn_alloc();

bn_fromString(a, “0”);

bn_fromString(b, “1”);

for (int i = 0; i < 1000; i++) { bn_toString(a, buf, sizeof(buf)); printf("%2d: %sn", i, buf); bn_add(a, a, b); bn_t t = a; a = b; b = t; } Figure 2: Calculating the rst 1000 Fibonacci numbers. 2 Calculator Word Description Decimal number Decimal numbers consist of a sequence of one or more decimal digits ('0'– '9'). For postgraduate students, the number may be preceded by a sign ( '- ' or '+'). When processed, the input number is converted into a bignum which is pushed to the stack. +, -, or * Pops two values from the stack and pushes their sum, di erence, or product back to the stack. in the case of subtraction, the bignum at the stack top is subtracted from the value below it. For example, the sequence __5 3 -__ leaves the number 2 at the top of the stack. dup Copies the value of the bignum at the top of the stack and pushes the duplicate value into the stack. pop Pops a bignum from the top of the stack. print Prints the value of the bignum at the top of the stack followed by a newline ('/n'). swap Swaps the order of the two bignums at the top of the stack. dump Prints the contents of the stack, one bignum per line, starting from the stack top. The stack is not modi ed. clear Clears the stack. Table 1: Calculator syntax. The calculator uses the library you developed to evaluate arithmetic expressions and display the results. The input consists of a sequence of words separated by one or more white spaces. (Technically, a white space character is a character for which isspace() returns TRUE.) Table 1 summarises the words that the calculator recognises. 2.1 Error Handling In case of error, your calculator should issue an error message. The message should be printed to stderr and should start with the word ‘Error’ . 2.2 Examples Input Output 3 5 + print 8 3 5 + print 8 3 dup * print dup * print dup * print 9 81 6561 3 5 - print 0 (undergraduates) -2 (postgraduates) 3 Submission Guideline You should submit a tar or a tgz le. When the contents of the le is extracted, it creates a single folder whose name is your a number. The folder should contain a Makefile and all of the sources required for building your library and calculator. Running make in the folder should create the library libbn .a and the binary calc. It may also create other intermediate les, e.g. object les. Make should compile all the sources with -Wall, and the compilation should issue no warnings. (Note that you may only use C for the assignment). We provide a sample Makefile that assumes that the library code is in the le bn .c and the calculator code is in calc .c. The assignment is designed for Linux systems. The provided Makefile and code may fail to work on other systems. They should work in the Windows Environment for Linux and in virtual machines. The default gcc version on the University computers is very old, and lacks many useful features. To enable a reasonably recent version of gcc, use scl enable devtoolset- 8 bash . This will open a new shell, with the correct environment variables for using gcc 8. Any software you submit should be compatible with the newer version of gcc.