# Zkouška C++ 11. 9. 2026 ## Arbitrarily long integers...in templates! The goal of this exercise is to make a helpful compile-time library to work with long integers that do not fit into the usual long integer types such as `uint256_t`. These are also called "bigints" or "bignums", and allow you to run marvelous computation such as finding that `23452374523452138762298572983 * 94385729384572938457239485723948 = 2213569475196206297972399098969681433605799933670361068896884`. The main use of such integers at compile-time might be e.g. pre-determining complicated constants for cryptographic libraries. Your task is to make a single templated type bignum that carries a long integer separated into several smaller integers, saved as variadic template parameters. Examples follow: - We could represent a "short" value `123` just as `bignum<123>()`, because it fits in a single integer. - Longer values that exceed the size of the integer in the template are stored by splitting the integers to multiple ones, each storing several bits of the whole value: - In a simplified binary case (for demonstration only), we might easily represent the `123` (which is `0b1111011`) as `bignum_binary<1,1,0,1,1,1,1>()` (the bits are written in little endian for convenience). - Alternatively (again only for demonstration), we can imagine the `123` in a hexadecimal base (`0x7b`) and represent it as `bignum_hex<0xb, 0x7>()`. - To prevent the templates from growing too much, we can use a much wider "base" for the number storage; for example, with 16-bit base one can store number `65536` (which is `2^16`) as `bignum<0,1>()`, and `8589934593` (which is `2^33+1`) as `bignum<1,0,2>()`. ## The task Implement `bignum` that saves long integers in variadic template parameters in base-`65536` (i.e., base-`2^16`). The template arguments are saved in "little endian" order, as shown above. Implement several functions that work with such integers: - It must be possible and safe to construct "small" integers (less than 16-bits in size) by writing just `bignum()` with a given desired `N`. - function `shrink` should be a helper function that "canonicalizes" the numbers by removing possible unnecessary zeroes; e.g., `shrink(bignum<1,2,3,0,0>())` should produce `bignum<1,2,3>()`. - `operator+` should add long integers via the usual overflow&carry algorithm. For example: - `bignum<1>() + bignum<2,4>()` produces `bignum<3,4>()` - `bignum<65535>() + bignum<65535>()` should produce `bignum<65534, 1>()` - `operator*` should multiply long integers via the usual shift-and-add algorithm. For example: - `bignum<1,0,2>() * bignum<1,2,3>()` should produce `bignum<1,2,5,4,6>()` - `bignum<65535>() * bignum<65535>()` should produce `bignum<1, 65534>()` - function `bignum_to_hex` produces a `std::string` with a hexadecimal representation of the long number: - `bignum<>()` should format as `0x0` - `bignum<1, 65534>()` should format as `0xfffe0001` - `bignum<10,1>()` should format as `0x1000a`. ## Simplifications and constraints - The users will only construct your bignum representation via the `bignum<...>()` constructor, and will always use the correct representation. In turn, you don't have to "validate" the input data, neither break large input integers to smaller - Negative integers are not considered; the behavior of your implementation with e.g. `bignum<-1>()` may be undefined. - All functions must be `constexpr`, and evaluable at compile time, except for `bignum_to_hex` which may produce results at run-time (i.e., there's no need for compile-time strings). - You can assume that all integers going into bignum_to_hex have been shrinked for you. The code should work with at least 2000-bit integers. ## Hints You are advised to prepare several helper functions: - `shift1` shifts the lowest 16 bits into an existing bignum (this simplifies iterative construction of longer numbers without unnecessary pattern-matching of the template arguments) - `mult1` multiplies an existing bignum with a given small 16-bit constant, handling the overflows (this is helpful as a building block for multiplication) ## Recommendations about the test suite: It is useful to start with implementation of `operator+`; it is the technically simplest part of the exercise. The expected implementation of shrink uses a different recursion pattern than the other operations, so it is useful to postpone it. shrink is used in all tests, but in most cases there are no zeroes to remove, thus a simple no-op implementation might do. ## Test case ```cpp #include "bignum.hpp" #include int main() { constexpr bignum<1, 2, 3> a; constexpr bignum<4, 5, 0> b; constexpr bignum<6, 0, 0, 0> c; std::println("{}", bignum_to_hex(shrink(a * b + c * c * c * c * c * c))); return 0; } ``` The above code should print out `0xf0016000db644`. ## Algorithms explained To maintain some similarity to the usual elementary-school numerical methods, we will write the numbers in the more common "big endian" here, e.g., `bignum<2,1>()` will be written as `1,2`. The decimal interpretation of such number is: ```text 1 * 65536 ^ 2 + 2 * 65536 ^ 0 ``` ...which is `65536 + 2 = 65538`. ## Addition Let's add `bignum<100,5>()` and `bignum<65500>()`: We write the numbers as: ```text 5 100 + 65500 --------- ? ? ``` First, `100+65500=65600` but that is too high, we thus compute: `65600 % 65536 = 64` `65600 / 65536 = 1` and get: ```text 5 100 + 0 65500 + 1 0 --------- ? 64 ``` Adding `5+1` does not overflow, we can thus finish: ```text 5 100 + 0 65500 + 1 0 --------- 6 64 ``` ## Multiplication by a single digit First, `mult1` is able to multiply a number by a "short" constant, using the same carry-over algorithm as the addition (except the carry can be higher than 1). For example, let's multiply `bignum<11,2,1>()` by `32768` (which is exactly `2^15`, i.e., half of 65536) `11 * 32768 = 98304` which is (after division with remainder) `5 * 65536 + 32768` we remember intermediate result `32768` and carry `5` `2 * 32768 = 65536`, giving `1 * 65536 + 0` we remember intermediate result 0 and carry `1` `1 * 32768 = 32768`, giving `0 * 65536 + 32768` we remember result `32768` with no carry The result of this is an addition that looks like this: ```text 5 32768 + 1 0 + 32768 0 0 ---------------- 32769 5 32768 ``` ...corresponding to `bignum<32768, 5, 32769>()`. ## Full multiplication The algorithm for full multiplication decomposes one of the numbers to single digits, multiplies the other one by each of the single digits, and adds the results together (with proper shifting). The following example illustrates the situation when multiplying `bignum<5,0,0,1>()` with `bignum<4,0,3>()`, giving (the example is selected such that it does not trigger any carry, for clarity): ```text 1 0 0 5 * 3 0 4 --------------- 4 0 0 20 ( = 4 * 1 0 0 5 ) + 0 0 0 0 ( = 0 * 1 0 0 5 ) + 3 0 0 15 ( = 3 * 1 0 0 5 ) --------------- 3 0 4 15 0 20 ``` ## Submission Submit a single file `bignum.hpp` that implements the template for bignum and associated functions in the global namespace.