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<N>() 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

#include "bignum.hpp"
#include <print>

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:

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:

  5   100
+   65500
---------
  ?     ?

First, 100+65500=65600 but that is too high, we thus compute:

65600 % 65536 = 64 65600 / 65536 = 1

and get:

  5   100
+ 0 65500
+ 1     0
---------
  ?    64

Adding 5+1 does not overflow, we can thus finish:

  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:

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

      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.