nna — NNA (Natural Number Array)

Features

The main function is to provide big integer arithmetic on natural numbers. However, unlike traditional implementations, we have optimized the representation of big integers, called NNA.

API

For this crate:

• Addition iterator: crate::Adder
• Subtraction iterator: crate::Suber
• Macro for simplified addition: crate::add!
• Macro for simplified subtraction: crate::sub!

Example of addition:

use crate::add;

#[test]
fn main () {
    let a = vec![7u32, 7, 7];
    let b = vec![4u32, 5, 6, 7];
    let r: Vec<u32> = add!(a, b, u8);
    dbg!(r);
}

Advantages of NNA

Compared to other big integer representations, NNA has the following outstanding advantages:

• Compact representation – greatly reduces redundancy and the number of loop iterations in arithmetic operations.
• Uniqueness – avoids leading-zero redundancy.
• Lightweight – for 1,000,000 additions of NNA with lengths in the range [0, 100), the average time is about 2 microseconds.

Technical optimizations

• The Limb of NNA is specified using generics, so you can adjust it according to your use case.
• NNA has no fixed container; the entire representation is built around iterators as the carrier of NNA. Every operation that outputs a new NNA is implemented as an iterator. This not only makes NNA adaptable to different containers, but more importantly supports streaming and lazy evaluation.
• size_hint is implemented, making NNA more efficient when placed into dynamic containers.

Possible drawbacks of NNA

• The representation is slightly more complex than traditional big integer formats, which may slow down per-element traversal. However, the more compact representation may compensate for this – specific performance needs further benchmarking.
• Using iterators as the carrier may cause repeated computation of certain values inside loops. However, Rust’s compiler optimizations (e.g., loop fusion) can mitigate this – the degree of fusion depends on the optimization level and capability of the compiler.

The NNA representation

Core structure

Like traditional big integers, the main body is a dynamic array.

Concepts

Parameters

• $N$: the natural number represented.
• $l$: length of the array.
• $L$: base.
• $n$: the array. Subscripts indicate indices (starting from 0 as the first element, not 1).
• $n_i$: the value of the element at index $i$.

Types

• Limb: the element type of the array ${a_n}$.

Representation

Traditional big integer representation

$$
N=\sum_{i=0}^{l-1}n_iL^i
$$

NNA representation

$$
N=\sum_{i=0}^{l-1}(n_i+1)L^i
$$

This representation gives NNA a very nice property.

Proof of the compact bijection property of NNA

Goal

The so-called compact bijection property means that NNA covers every natural number exactly once, without gaps, starting from 0.

Method

Take extremes, use mathematical induction.

Proof

Minimum and maximum

For a fixed length $l$,
Minimum $N_{min}=\frac{L^l-1}{L-1}$,
Maximum $N_{max}=\frac{L^{l+1}-1}{L-1}-1$.

If we treat each digit’s contribution as an independent function $(n_i+1)L^i$, then because $L$ and $i$ are positive integer constants, $L^i$ is constant. Hence as $n_i$ increases, $(n_i+1)$ increases, and so does the whole term – it is a linear function with positive slope, monotonically increasing over its domain. Considering the range of $n_i$, i.e., all natural numbers in $[0, L)$, the minimum of this digit is $L^i$, and the maximum is $L^{i+1}$.

What about the overall minimum and maximum of the whole NNA? Since each digit’s contribution is independent, the overall maximum is the sum of each digit’s maximum, and the overall minimum is the sum of each digit’s minimum. This becomes a geometric series, and applying the summation formula yields the results above.

Continuity across different lengths

$l=0$

When $l=0$, $N_{min}=0$, $N_{max}=0$.

$l=1$

When $l=1$, $N_{min}=1$, $N_{max}=L$.

$l=2$

When $l=2$, $N_{min}=L+1$, $N_{max}=L^2+L$.

It is easy to see that the minimum of length $l+1$ equals the maximum of length $l$ plus one. Substituting the formulas and subtracting proves this:
$$
\frac{L^{l+1}-1}{L-1}-\left(\frac{L^{l+1}-1}{L-1}-1\right)=1
$$
This shows that the value ranges of adjacent lengths are consecutive in the natural numbers.

Continuity within the same length

All values of NNA with fixed length $l$ are consecutive natural numbers – the proof is identical to that for traditional big integer representations, so it is omitted here.

Mathematical induction

We have proved three statements:

• The minimum value of NNA is 0.
• For a fixed length, the values are consecutive in $\mathbb{N}$.
• The ranges of adjacent lengths are consecutive in $\mathbb{N}$.

From these we can prove the compact bijection property.
Conclusion: The range of NNA is the entire set of natural numbers $\mathbb{N}$.

Addition theory for NNA

Notations

• $a$: first NNA array.
• $b$: second NNA array.
• $r$: resulting NNA array.
• $c$: carry.
• $t$: the value contributed by a digit.

Method

Recursion, boundary case analysis, case analysis.

Proof

When there is no incoming carry

We obtain $a_i$ and $b_i$. Simply adding them does not give the correct result, because the in‑memory value is not the actual contribution of the digit. The contribution of a digit is $t_i = (n_i+1)L^i$, not $t_i = n_iL^i$. For the result digit $r_i$, we must satisfy $t_{ai}+t_{bi}=t_{ri}$, i.e. $(a_i+1)L^i+(b_i+1)L^i=(r_i+1)L^i$. Simplifying gives $a_i+b_i+1=r_i$. Thus the required $r_i$ is $a_i+b_i+1$, not $a_i+b_i$.

When there is a carry out

But $r_i$ may become $\ge L$, violating the per‑digit range. The range of $r_i$ is $[1,2L)$, which clearly exceeds the limit – this is overflow. Therefore we must handle a carry to the next digit. Mathematically, this is dividing $r_i$ by $L$ to obtain quotient and remainder. In computer science, we only need to capture the overflow (high byte) or test for overflow, because the overflow has a limited range. Here the maximum carry is 1, so can we store it as a bool?

Carry crisis

Not at all! Because we may need to add a carry from the previous digit.

Suppose we have $a_i$, $b_i$ and $c_{i-1}$ (the carry from the previous digit; before the first digit, $c_{-1}=0$). To satisfy $t_{ai}+t_{bi}+c_{i-1}L^i = t_{ri}$, we need $a_i+b_i+c_{i-1}+1 = r_i$. Now $c_{i-1}$ is in the range $[0,2)$, so $r_i$ can be in $[1,2L+1)$. As before, the carry is the quotient of division by $L$, and now the carry may be 2. So we must also handle the case where the carry can be 2.

Any further crisis?

Consider the case where $c_{i-1}$ could be 2. Again with $a_i$, $b_i$ and $c_{i-1}$, but this time $c_{i-1}\in[0,3)$. Then $r_i\in[1,2L+2)$, and the maximum carry is still 2. So it stabilises at 2 – no further recursion needed. Since $c$ can be in $[0,3)$, we cannot use a bool for the carry; a wider type like u8 is required.

When only one operand has a digit

What if the two NNA operands have different lengths? When we reach a position where only one operand has a digit, how do we compute the sum and the new carry? Assume that the existing digit is $n_i$, so its contribution is $t_{ni}=(n_i+1)L^i$. To satisfy $t_{ni}+c_{i-1}L^i = t_{ri}$, we need $n_i+c_{i-1}+1 = r_i+1$, which simplifies to $n_i+c_{i-1}=r_i$. Hence the result digit $r_i$ is simply the input digit plus the incoming carry. Because $c_{i-1}\in[0,3)$, we get $r_i\in[0, L+2)$, and the carry out from this digit is either 0 or 1. So no need to change the carry range.

When neither operand has a digit

If neither operand has a digit, then we have exhausted the arrays. However, we must still handle any leftover carry. Suppose the incoming carry is $c_{i-1}$. To satisfy $c_{i-1}L^i = t_{ri}$, we need $c_{i-1}-1 = r_i$. That is, we subtract 1 from the carry and output that as the digit. What if $c_{i-1}=0$? Then $r_i = -1$. Interestingly, a digit value of -1 has the contribution $t_{-1}=(-1+1)L^i=0$, which means these trailing -1s are effectively absent – we can simply stop iterating.

Acknowledgements

Finally, thank you all for your support. I have implemented addition and subtraction, though the documentation and comments for subtraction are not yet complete. More operations (multiplication, division, comparison, base conversion) and special‑case fast algorithms may come later. Stay tuned!