nna — NNA (Natural Number Array)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.
For this crate:
crate::Addercrate::Subercrate::add!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);
}
Compared to other big integer representations, NNA has the following outstanding advantages:
[0, 100), the average time is about 2 microseconds.Limb of NNA is specified using generics, so you can adjust it according to your use case.size_hint is implemented, making NNA more efficient when placed into dynamic containers.Like traditional big integers, the main body is a dynamic array.
Limb: the element type of the array ${a_n}$.$$
N=\sum_{i=0}^{l-1}n_iL^i
$$
$$
N=\sum_{i=0}^{l-1}(n_i+1)L^i
$$
This representation gives NNA a very nice property.
The so-called compact bijection property means that NNA covers every natural number exactly once, without gaps, starting from 0.
Take extremes, use mathematical induction.
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.
When $l=0$, $N_{min}=0$, $N_{max}=0$.
When $l=1$, $N_{min}=1$, $N_{max}=L$.
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.
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.
We have proved three statements:
From these we can prove the compact bijection property.
Conclusion: The range of NNA is the entire set of natural numbers $\mathbb{N}$.
Recursion, boundary case analysis, case analysis.
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$.
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?
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.
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.
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.
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.
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!
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。