4096_t
Due Thu, 01 Oct
Review Show
Goal: Implement 4096 bit integers
- My responsibility
- I will provide 1 week of instruction on rings, number theory, and programming languages.
- I will provide an autograder Containerfile
- Your responsibility
- You will implement a 4096 bit unsigned integer in C89 as:
- “4096_t.c” implementation file, and
- “4096_t.h” header file.
- You will store your “4096_t” files in the “4096_t” folder on your “sysinc” GitHub repository.
- You will implement a 4096 bit unsigned integer in C89 as:
Topic Areas
| Review: | Newish: |
|---|---|
| - Rings | - \(\varnothing\) |
Resources
- The BigAdd lab
- The “Header” entry formed my starter code.
- My Finite Slides
- Contextual background
- My BigNum Slides
- I used this, and its references. Try scroll mode (press ‘r’)
- I think my slides are suitable for multiplication.
- Division is something of a challenge problem.
- I would begin with the following:
- Wikipedia Division Algorithms
- I used this and Stack Overflow to implement division.
- I used a variety of bitshifts.
BigMul Show
- I find the following bulletin summary the most helpful to making a bigmul implementation:
- I Made a pointer to a
uint32_t uint32_t *alias;- Set it equal to the location of some array of
uint64_t uint32_t *alias = &array;- Copied elements of the “alias” into 64 bit values.
uint64_t tmp = alias[5];- Multiplied, tracking significance.
- I Made a pointer to a
- Versus in class, I will note I made
uint32_taliases for all operands. - Additional, I made a uint64_t twice as large as the input arrays, to hold intermediate results.
NoteAdvanced Students
Advanced Students should implement multiplication using only addition (possibly using the existing “BigAdd” from prior work) and bitshifts.
BigDiv Show
While I hope all students complete BigDiv, it is a de facto challenge problem - I found no “easy” solution, and understand it is a comparatively complex system.
- I implemented division as recursive long division with considerable error handling.
- I began by aligning the most significant non-zero bit, which was non-trivial but simple enough.
- You should write the following functions:
uint64_t bigdiv(uint64_t *num, uint64_t *den, uint64_t *quo, uint64_t *rem) {
/* Your code here */
return 0;
}
uint64_t bigquo(uint64_t *num, uint64_t *den, uint64_t *quo) {
uint64_t rem[S];
bigdiv(num,den,quo,rem);
return 0;
}
uint64_t bigrem(uint64_t *num, uint64_t *den, uint64_t *rem) {
uint64_t quo[S];
bigdiv(num,den,quo,rem);
return 0;
}- I additionally wrote the following helper functions.
- These are not all required, or even recommended, simply what I used.
- They are not debugged - some errors are likely handled within my
bigdiv- I expect many off-by-one errors from the comments, which I added just for this document.
/* Detemine the log of a 4096bit in base 2^64 */
uint64_t biglog(uint64_t *in) {
uint64_t log = S;
while (log && !in[--log]) { }
return log;
}
/* Detemine the log of a 64bit in base 2 */
uint64_t lillog(uint64_t in) {
uint64_t log = 0;
while ((in >> log++) && log < 64) {}
return log;
}
/* Find the address of the most significant bit of a 4096bit integer */
uint64_t getmsb(uint64_t *n) {
uint64_t b, l;
b = biglog(n);
l = lillog(n[b]);
return b * 64 + l;
}
/* Return 64 bits from a 4096 bit integer, begging at bit `ind` */
uint64_t get_64(uint64_t *n, uint64_t ind) {
uint64_t b = ind / 64, l = ind % 64;
return (n[b] << (64 - l)) + (b ? (n[b - 1] >> l) : 0);
}Tester Show
- I am providing the following Containerfile, which will serve as a minimal autograder
- I pivoted back to Alpine because Ubuntu was slow.
Containerfile
FROM alpine
RUN apk add build-base gcc curl python3
RUN curl https://raw.githubusercontent.com/cd-c89/sysinc/refs/heads/main/4096_t/4096_t.h -o 4096_t.h
RUN curl https://raw.githubusercontent.com/cd-c89/sysinc/refs/heads/main/4096_t/tester.c -o tester.c
RUN curl https://raw.githubusercontent.com/cd-c89/sysinc/refs/heads/main/4096_t/tester.py -o tester.py
COPY 4096_t.c .- All three of the these files were previous introduced in the BigAdd lab.
Usage
- I built my container via:
- I tested my code via:
- If the above script returns the following you are done:
- Upload your code to your GitHub on which I am a collaborator.
- I will review the most recent version prior to the due date.
- A satisfying solution need only pass “MUL”, though ambitious students should pursue the division operations as well.
Testing
- When the container is built, it copies in
4096_t.c - Within the container,
tester.py:- Compiles
tester.cas C89 with appropriategccflags.tester.cis dependent on both your4096_t.cand my4096_t.h
- Creates two values of size less than 2048 bits.
- Performs all relevant operations over these values, check the results.
- Compiles