Assignment 1 Bignum Package
密码学 | math代写 | c代写 | c++代写 – 这是math大数分解代写的题目
In this part of the assignment, you are asked to implement a service that performs basic algebra on integers of arbitrary lengths, calledbignums. 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 structurebnt, which is a pointer to the (externally abstract)struct bn. The functions operating on this structure are described below. This interface is defined in the filebn.h, which is available from MyUni.
1.1.1 bnt bnalloc(void)
Allocates a new bignum and initialises it to (positive) 0. ReturnsNULLif not enough resources are available. We provide a sample implementation of this function, which you can use.
1.1.2 void bnfree(bnt bn)
Frees all the resources associated with the bignumbn.
1.1.3 int bnadd(bnt result, bnt a, bnt b)
Adds the bignumsaandband places the sum inresult. Returns 0 if completed successfully and 1 otherwise.
1.1.4 int bnsub(bnt result, bnt a, bnt b)
Subtracts the bignumbfromaand places the difference inresult. Returns 0 if completed successfully and1 otherwise. Undergraduate students: ifais smaller thanb, the result is set to 0.
1.1.5 int bnmul(bnt result, bnt a, bnt b)
Multiplies the bignumsaandband places the product inresult. Returns 0 if completed successfully and 1 otherwise.
1.1.6 *int bnfromString(bnt bn, const char str)
Read the decimal number in the stringstrand stores its value inbn. Returns 0 if completed successfully and1 otherwise.
Undergraduate students need only handle non-negative numbers. Postgraduate students need to handle both positive and negative numbers.
1.1.7 *int bntoString(bnt bn, char buf, int buflen)
Converts a bignumbnto a string. including the terminatingNULcharacter. Ifbuflenis large enough to store the converted string, the function stores the string inbufand returns 0. Otherwise,bufis 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 bnIAmAnUndergrad()
Returns 1 if youre an undergraduate student, 0 if youre 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 structurestruct bn(Figure 1), and implementations of thebnallocand bntoStringfunctions. 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 fields of the structure are:
bnlenThe length (number of digits) of the number represented by the structure.
bndataAn array that stores the values of the digits of the number.
bnsignThe sign of the number. The value of the sign is 1 for positive numbers and1 for negative
numbers. Undergraduate students should set the field to 1 when allocating numbers and may assume
it does not change after that.
bnsizeThe number of digits allocated inbndata.
The number is reprsented as a sequence ofdigitsin base 2^16 = 65536. That is, ifsis the value ofbnsign, lthe value ofbnlen, anddithe value of theithelement inbndata(i.e.bndata[i]), then the value represented by the structure is given by:s
l 1
i=0(
(^16) )idi.
1.3 An Example
Figure 2 shows a program that uses the library to calculate the first 1000 elements of the Fibonacci sequence.
#include <stdio.h> #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: %s\n", i, buf);
bn_add(a, a, b);
bn_t t = a;
a = b;
b = t;
}
Figure 2: Calculating the first 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, difference, 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 modified.
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 ofwordsseparated by one or more white spaces. (Technically, a white space character is a character for whichisspace()returnsTRUE.) 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 tostderr 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 ataror atgzfile. When the contents of the file is extracted, it creates a single folder whose name is your a number. The folder should contain aMakefileand all of the sources required for building your library and calculator. Runningmakein the folder should create the librarylibbn.aand the binarycalc. It may also create other intermediate files, e.g. object files. 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 sampleMakefilethat assumes that the library code is in the filebn.cand the calculator code is incalc.c. The assignment is designed for Linux systems. The providedMakefileand code may fail to work on other systems. They should work in the Windows Environment for Linux and in virtual machines. The defaultgccversion on the University computers isveryold, and lacks many useful features. To enable a reasonably recent version ofgcc, use scl enable devtoolset-8 bash. This will open a new shell, with the correct environment variables for usinggcc 8. Any software you submit should be compatible with thenewerversion ofgcc.