|
In this assignment you will get started with programming in the Go
language. To solve this assignment you will need to install Go, figure
out how to compile, run, and debug a Go program, and implement a few
key pieces in a partial BigUInt codebase that we will give to you.
Overview
Go (or golang, as it helps to search for it) is an imperative programming language generally aimed at the development of distributed systems.
In some ways, it is related to systems languages like C and Rust, in that programs are built using structs and functions (and like Rust, while it supports "methods", they are basically just special functions).
In other ways it is more similar to managed languages like C# and Java, in that, while it does not have a VM, it has a lot of "managed" features:
it has a garbage collector, full runtime type information, and the design strives to have essentially no undefined behaviour.
This assignment's objective in particular is to help you get to grips with Go's basic features. You will learn:
A BigUInt is a simplified version of a BigInt, just like the one that ships in Go's standard library, or the default int implementation in Python, or the equivalent data structure available in most programming languages.
At a high level, the goal of a Big(U)Int is to store unbounded-precision integers.
In many programming languages, like C, C++, Java, and Go, the built-in integer types can only hold number represented by their bit width, which will often be 32 or 64.
While this may be good enough for many situations, sometimes a truly unbounded number is needed, or, in Python's case, an unbounded number is provided by default for usability's sake.
This is the BigInt: it represents a number a variable-length sequence of machine ints, requiring any int-supported operations to be implemented as array manipulations.
BigUInt is, like the uint type in Go or unsigned int in C, an unsigned variant of BigInt that does not need to support negative numbers, making implementation a little simpler.
BigUInt
This assignment's specific variant of BigUInt is already pre-defined for you by us: it is a struct containing a reference to a slice of unsigned bytes.
This means that your task is to implement a pair of unsigned integer operations on slices of unsigned bytes: addition, subtraction, and deep copying.
In addition to Go's extensive documentation, of which we recommend the tour for language features, and How to Write Go Code for the package and testing concepts, the provided assignment code aims to be an example of how to lay out a Go project.
We provide you with three files:
(1) biguint.go,
(2) biguint_test.go,
(3) go.mod.
The file biguint.go has some code that helps to figure
things out. This file includes the bytesFromUInt64
method, which unpacks a 64-bit unsigned integer into a slice of
bytes, and (*BigUInt).String(), which is a standard
stringification method for BigUInt instances.
We also provide some testing infrastructure
in biguint_test.go to help guide you in testing this
first assignment, and to give you a base to work from when building your
own tests in subsequent assignments.
The go.mod file is a module definition, whose full implications are discussed
in Using Go Modules.
Generally speaking, the file defines the root directory of a collection of Go packages, a canonical name by which one
can import those packages, and any dependency information.
In this case, the canonical name is example.org/cpsc416/a2, rooted at example.org
due to this being a course assignment.
There is no additional dependency information, except go 1.14, which indicates the version of the Go toolchain
that initialized the module, and defines the provided code's Go language compatibility.
You should only modify the code in biguint.go.
As a starting point, make sure you can run the provided tests, which should fail.
BigUInt API
The following API calls below are defined and we also provide their implementations:
type BigUInt struct {
data []uint8
}
Our BigUInt type definition, containing a slice of unsigned bytes.
Unsigned ints should be split up into 2 digit base 16 chunks,
indexed from least to most significant, e.g., []uint8{ 0x00,
0xFF } represents 0xFF00. This is also an example of
a slice type.
var ErrUnderflow = errors.New("arithmetic underflow")
This is the underflow error for subtraction.
Go's error handling is minimalistic by design, and can be confusing when coming from languages that have more heavyweight error
handling support.
Some general guidance is available on the basic idioms of Go error handling.
Additionally, Go 1.13 and above adds the ability to standard-ly nest one error inside another,
which may be useful in larger projects, where one kind of error might cause another.
In this assignment, you just have to return this error in the correct situation.
func NewBigUInt(i uint64) *BigUInt
The constructor for a BigUInt, based on a uint64. This function
relies on bytesFromUInt64, which takes an unsigned
64-bit integer and converts it into an array of bytes, following the
scheme for this assignment (least to most significant bytes). Note
that the resulting slice and therefore the underlying bytes of
the BigUInt do not include any leading zeroes,
stopping at the most significant non-zero byte.
func (x *BigUInt) Bytes() []uint8
Provides access to the raw bytes underlying a given BigUInt.
func (x *BigUInt) String() string
This function demonstrates some more slice-based code. It generates a
string representing x, under the following scheme:
- digits should be printed in base 16, with lowercase letters
- groups of 8 digits should be separated by underscores
- no leading zeroes should be printed
- the string should be prefixed with "0x"
See the golang's printf-style string formatting manual.
The three API calls below are defined for you, but you have to provide the implementation:
func (x *BigUInt) Copy() *BigUInt
Generates an exact and fully independent (deep) copy of a given
BigUInt. Note that the copy should not share any memory
with x.
func (x *BigUInt) Add(y *BigUInt) *BigUInt
The Add method increases x by the number represented
by y, and should return a pointer
to x. Note that x's slice's size may
increase as a result of this operation. More
specifically, x's slice should have the minimum
length necessary to represent the resulting sum.
func (x *BigUInt) Subtract(y *BigUInt) (*BigUInt, error)
The Subtract method decreases x by the number represented by
y, and returns a pointer to x. Note that x's
slice's size may decrease as a result of this
operation. If y > x, then Subtract
should return (nil, ErrUnderflow), and x
should be left unchanged (this may take some care). As
with Add above, x's slice should have the
minimum length necessary to represent the resulting number.
Testing
A large amount of testing code is provided
in biguint_test.go. You do not need to modify this file
for this assignment, but keep in mind that you will need to make your
own tests in future assignments.
Assumptions you can make
- For this assignment, no assumptions, other than basic Go functionality and any stated API semantics, are allowed.
- You can assume that inputs to the
BigUInt API will never be nil.
Assumptions you cannot make
- Any bounds, aside from free memory (do not worry about memory allocation failure), on the size a BigUInt can reach.
- We will run only the provided tests against your code. (We have more tests)
Implementation requirements
- The client code must be runnable
on CS
ugrad server machines and be compatible with Go version
1.15.6.
- Your code must be compatible with the given API, and run successfully against the provided test cases.
- Your solution can only
use standard library Go
packages.
- Your solution code must be Gofmt'd
using gofmt.
Starter code
You can download the zipped starter code here.
Note that you cannot change the API. Our marking scripts will
rely on this API to automatically grade your solution.
Handin instructions
Keep the provided file layout at the top-level in your solution. You
may include additional files, but we do not expect this will be
necessary. Do not reference any additional libraries in your solution.
More instructions about submitting using a git repository via
https://github.students.cs.ubc.ca/ will be posted here and on
Piazza.
Rough grading scheme
Your code must not change the API above. Your
code must work on ugrad servers (e.g.,
remote.students.cs.ubc.ca).
If any of these are violated,
your mark for this assignment is 0. This is true regardless of how
many characters had to be changed to make your solution compile, and
regardless of how well your solution works with a different API or on
a different machine.
For a list of server machines you can use, please
see this
page. Note that the right version of Go (version 1.15.6) is
installed in /cs/local/bin/go.
The high-level A1 mark breakdown looks like this:
- 5% : Copy works
- 35% : Add works
- 60% : Subtract works
Advice
-
Start simple, and don't worry about edge cases until the main control flow works.
If you're stuck on how to implement addition and subtraction, review long-form addition and subtraction and implement them as literally as you can.
It's easy to forget the specifics and edge cases of the method, since it's so much easier to take shortcuts or rely on calculators most of the time.
- Compile and run your code on the ugrad servers.
Make sure to follow the
course collaboration policy and refer
to the submission instructions
that detail how to submit your solution.
|