Store it as $$$2^k \cdot m$$$, $$$m$$$ is odd and you store $$$m$$$ modulo $$$10^{9}$$$.

Addition (wlog $$$k_1 \le k_2$$$): $$$2^{k_1} \cdot m_1 + 2^{k_2} \cdot m_2 = 2^{k_1} \cdot (m_1 + 2^{k_2 - k_1} \cdot m_2)$$$

Knowing the modulo $$$10^9$$$ is the same as know the modulo $$$2^9$$$ and modulo $$$5^9$$$, and vice versa (Chinese Remainder Theorem).

Modulo $$$5^9$$$ is easy in this case, since the only division is division by $$$2$$$ and because $$$\gcd(5^9, 2) = 1$$$, $$$2^{-1} \pmod 5^9$$$ exists and we can just multiply with that number.

Modulo $$$2^9$$$ on the other hand is harder, since division by $$$2$$$ can result in different values, depending on the actual values of the actual number. I don't think this can be solved faster than bignum in general due to the following use case:

• Imagine that we already have some number type that does this. We will also store a floating point estimation of the result.
• We know the modulo $$$2^9$$$ of the result, so we know whether the result is even or odd.
• If it is even, we divide by $$$2$$$
• If it is odd, we minus by $$$1$$$ then divide by $$$2$$$.
• Repeat this until we have $$$0$$$ or close enough (check with the floating point estimation).
• This whole process effectively means we have extracted the bits of the actual value or at least most of it, assume the floating point estimation is reasonably correct

So the number type must store at least as much information as (roughly) the actual result, so it can't really be faster than bignum. Note that any type of number that can find modulo $$$10^9$$$ will also find modulo $$$2^9$$$, so they also run into the same problem.

tl;dr: My conclusion is that this isn't possible to do faster than storing / knowing every bits. Maybe for the problem you were trying to solve, it's possible to change the formula around to avoid the division, or maybe the amount of division is small enough that it's feasible to just store all the bits.