Unsigned Integers without Software Limits
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Unsigned Integers without Software Limits
This lab's project is called UnsignedBigInt_CPP;
Once again, we will ignore negative integers, creating an unsigned bignum.
Deliverables
● README-resources.md file, list lab partner and references used.
● Test suites for the class UBigIn t, function BigFib, template power, and your solo code.
● A C++ class UBigInt to represent a double-precision unsigned integer, with
○ UBigInt(n) converts an unsigned long integer value n into a UBigInt
○ Definitions for +, -, *, +=, -=, *=, <, <=, ==, >, >=, !=
○ The output operation <<
○ Overflow during any arithmetic operation will throw an exception
○ (Note that you are not required to have input or division, or to make multiplication efficient; you may optionally, provide an input operation >> and/or constructor from a string, so that UBigInt i("1234") creates 1234).
Your class should be declared in UBigInt.h, with function/method bodies in UBigIn t.cpp.
You should be able to run with valgrind to demonstrate efficient memory management.
● A function bigFib that returns a UBigInt value that gives the nth element of the Fibonacci sequence, in bigFib.h and bigFib.cpp.
Details
The code to be written
● For your README file, remember to both list your lab partner's name and email
address, and also list any resources you consult other than the course textbooks. It's also appropriate to cite any web sources (in particular, any from which you copy-paste!) in comments in your code.
● Your test suites for the class UBigIn t, function bigFib, template power, and your solo code, should each provide a test suite demonstrating the interesting cases of all required features.
As usual, we strongly recommend writing all tests for each class/function first, to understand the big picture and possible usage case, and then writing/testing/debugging code in increments that are as small as you can make them.
● A C++ class UBigInt that represents a double-precision unsigned integer, so that
○ UBigInt(n) converts an unsigned long integer value n into a UBigInt. This should also allow implicit casting of unsigned integers into UBigInt values, as is the default when you create a one-parameter constructor without the keyword explicit.
○ The binary arithmetic operations +, -, *, +=, -=, and *=, and the comparison
operations <, <=, ==, >, >=, and != should all work.1 Note that some operations may need more memory than contained in an unsigned long integer; your UBigInt should handle this situation.
○ The output operation << works and can be used to provide output. Once again, you are allowed to use either base ten or hexadecimal or, if you really want to dig into C++ details, respect the current default base of the stream you're printing to.
○ Overflow during any arithmetic operation will throw an exception, but now the
only exception will be if you get a number that's below zero (since we're working with unsigned values).
Your class should be declared in UBigIn t.h, with function/method bodies in UBigIn t.cpp.
● A function bigFib that returns a UBigInt value that gives the nth element of the
Fibonacci sequence, for any integer n for which the result will fit in a UBigInt variable.
As in previous labs, bigFib(1) = bigFib(2) = 1. You may choose to define Fib(0) as 0, or
not, as you wish. Either way, the sequence should produce bigFib(5)==5 and bigFib(12)==144.
Your function should be declared in bigFib.h, with function/method bodies in bigFib.cpp.
Strategies for success when writing challenging code, e.g., code using the free-store heap
Novice C/C++ programmers typically approach code that uses new/malloc with a workflow that goes something like this:
1. (painful approach): write all the functions you think you'll need, as well as you can (i.e., all but "fib")
2. (painful approach): write the application that uses those functions (i.e. "fib")
3. (painful approach): run the application with an interesting example (e.g., "fib(429)" or "fib(200000)")
4. (painful approach): try to fix any bugs, if it crashes; declare victory, if it doesn't
We recommend this alternative:
1. (pain-minimizing approach): identify the minimum functionality that would let you check if anything works at all in your core functionality, e.g., a way to build a simple "big int"
value, and the printing function
2. (pain-minimizing approach): write code for that test, and maybe one or two other very simple tests, e.g. just creating and printing the number 7, and write that C++ code to make it work
3. (pain-minimizing approach): run the stuff you've got so far, including with valgrind, and keep debugging until you get this to run o.k., e.g., you might realize that your minimum functionality to get past valgrind includes a C++ destructor.
4. (pain-minimizing approach): identify a minimum increment of functionality, e.g., consider addition, so you could write, e.g., x = x+1 or x=x+x.
5. (pain-minimizing approach): write some basic tests of that functionality, including cases where you test important functionality like increasing the number of digits, and some
more-ambitious tests like running x = x+x to keep doubling 2, 4, 8, 16, 32 … 2150 , and printing each one
6. (pain-minimizing approach) now write, test (including with valgrind), and thoroughly
debug the code for your incremental functionality, e.g. "+". But, be alert as you do …
maybe your addition operator uses call-by-value, which means you'll need to initialize a big int from another big int, so you'd better make that initialization the first increment of functionality, and do Steps 4, 5, and 6 for that, and then come back to writing and testing addition. Or, you could use call-by-reference in your addition operator, and debug that first, and then handle initialization later.
7. (pain-minimizing approach): keep identifying small increments of functionality, and repeat steps 4-6 for each, and keep going until your last step is the interesting use of the application itself e.g., fib(429); in each repetition, re-run the whole set of tests, and make sure valgrind doesn't complain.
There are more steps there, and you have to go around a loop of Steps 4-6, but each step is designed to be achievable, and it avoids the ultimate dismay of having all the parts of your code break at once.
Running valgrind (copy of stuff from Piazza, with lots of additional details and more tests!)
To execute the "Strategies for success" above, you'll need to run "valgrind" a lot. Here are the steps, in the context of your project (there is also more discussion of this in Dive into Systems).
Remember to start with the simplest step beyond what you've succeeded with before … .
"succeeded with" doesn 't just mean getting the right answer, it means getting the right answer without any complaints from valgrind. If you come to us and ask about a problem when you're
trying to compute fib(6543) or something, when you could get fib(6542), our first question will be "does the run that gets fib(6542) get past valgrind without errors?". We're going to start help with one tiny step past the most interesting case that passes valgrind.
So, if you've not run valgrind, comment out your entire "main", and use "Test #1" from above, or the equivalent C code, which could be several lines longer, but will only do the things the above C++ code does. If you're doing C, remember that both languages do some things automatically, e.g., getting rid of the local variable "one" when the function finishes … in C++, the class
designer has the option of assisting in the process by writing a destructor, and C++ will
automatically call it, but the C program would need an explicit call to prepare for the fact that "one" is about to disappear.
Then, to run valgrind:
1. Build your program (in C-Lion, hit the "build hammer" (it's almost the furthest-left thing in the set of icons in the upper right of your C-Lion window). There's also a command line tool, ask if you need it.
a. If this prints errors or warnings, deal with them
b. if not, you should be able to run your program on the command line by using the command
./cmake-build-debug/BigIn t
in the project directory (if you start the "Terminal" inside C-Lion, it starts in that directory).
2. Run valgrind, with the command
valgrind ./cmake-build-debug/BigIn t
3. Look at the results. There should be five lines starting with a number within "=", e.g.
==1398953==, giving valgrind output, then the output of your program (in this example, just "1"), then nine lines with that same ==number== identification, including exactly the following (except the "number") among other lines with other details:
==number== in use at exit: 0 bytes in 0 blocks
and, later, exactly
==number== All heap blocks were freed -- no leaks are possible
and, at the end, exactly
==number== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0
from 0)
2024-01-27