# 密码学 | math代写 | c代写 | c++代写 – Assignment 1 Bignum Package

### 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, 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.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.

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_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)