---
library_name: kernels
license: apache-2.0
---

# bignum

Batched arbitrary-precision integer arithmetic on the GPU, loadable through
`kernels`: addition, subtraction, multiplication, signed comparison, and
modular reduction over a batch of wide integers, exact at every width. The
reference baseline is Python's native integer arithmetic, compared digit for
digit, with GMP as the throughput yardstick.

Exact algorithms over the integers, Hermite and Smith normal forms, lattice
basis reduction, integer relation detection, carry coefficients that grow past
64 bits and are not decomposable by CRT the way determinants are. They need
wide arithmetic on the device itself, and GPUs have no such type. This kernel
supplies it as a batch primitive: thousands of 8192-bit values computed at
once, so the wide-integer inner loops of exact linear algebra run where the
rest of the computation lives.

![A 64 by 64 lane wall pulses as batches of 2048-bit modular multiplies sweep through, with completion counters running against GMP](https://huggingface.co/kernels/phanerozoic/bignum/resolve/main/media/hero.gif)

*4,096 lanes of 2048-bit `a*b mod M` in flight: 2.5 million exact modular
multiplies per second, 2.6x one GMP core, every lane digit-for-digit equal to
GMP.*

## Usage

```python
import torch
from kernels import get_kernel

bn = get_kernel("phanerozoic/bignum", version=1, trust_remote_code=True)

a = bn.to_device([3**400, -(5**300), 2**1000])
b = bn.to_device([7**200, 11**150, 1], limbs=a.size(0))

bn.from_device(bn.add(a, b))
bn.from_device(bn.mul(a, b))
bn.compare(a, b)                       # -1, 0 or 1 per lane
bn.from_device(bn.mod(a, (1 << 127) - 1))
```

`version` selects the release branch; `trust_remote_code` is required by
`kernels` for publishers without the trusted-publisher mark.

## API

| Symbol | Purpose |
|---|---|
| `to_device(values, limbs=None)` | pack Python ints into an `[L, N]` limb tensor |
| `from_device(tensor)` | unpack a limb tensor into Python ints |
| `limbs_for(bits)` | limb count holding a signed value of that magnitude |
| `add(a, b)`, `sub(a, b)` | elementwise sum and difference, wrapping at the operand width |
| `mul(a, b)` | elementwise product, widened to `La + Lb` limbs |
| `compare(a, b)` | elementwise signed comparison, `-1`, `0` or `1` per lane |
| `mod(a, M)` | every lane reduced modulo one modulus, into `[0, M)` |
| `mulmod(a, b, M)` | elementwise `a * b mod M` |
| `barrett_mu(M, operand_limbs)` | reusable Barrett constant for a fixed modulus and operand width |

## Method

A batch of N integers, each L limbs of 64 bits, is an `[L, N]` int64 tensor:
limb `i` of value `t` sits at `i * N + t`, so consecutive threads touch
consecutive addresses on every limb access and the carry chains that are
sequential within one value amortize across the batch. Values are
little-endian two's complement at a fixed width, up to 128 limbs (8192 bits).

Addition, subtraction, and comparison run directly on the two's-complement
representation, one thread per value. Multiplication converts to sign and
magnitude, accumulates schoolbook partial products through `__umul64hi`, and
reapplies the sign. Modular reduction is Barrett:
`q = floor(a * mu / 2^(64 * La))` with `mu` precomputed on the host, then
`a - q * M` corrected by at most a few subtractions. Sizing `mu` to the
operand width rather than the modulus width keeps the quotient estimate valid
for any dividend below `2^(64 * La)`, so wide values reduce against a small
modulus without a narrowing step. Working buffers live in a host-allocated
global scratch region indexed by thread.

## Measured

Batched `a*b mod M` at 2048 bits, 4,096 lanes, against GMP via gmpy2 on one
CPU core of the same host, results compared digit for digit:

| | ops/s |
|---|---|
| bignum, one GPU | 2,543,000 |
| GMP, one CPU core | 971,000 |

The batch is the regime: per-op latency favors GMP, aggregate throughput and
residency next to tensors favor the device.

## Verification

Every operation is compared against Python's native integer arithmetic, digit
for digit: round-trip packing at the signed word boundaries, addition and
subtraction at 8 to 700 bits, multiplication across all four sign
combinations, comparison at the boundaries, and reduction against moduli of
61 to 256 bits with dividends far exceeding the modulus squared.

## Requirements and limits

- NVIDIA GPU with compute capability 8.0+.
- Fixed width per batch, up to 128 limbs (8192 bits); `mod`/`mulmod` take one
  shared modulus per call.
- Single-value latency is not the target; batch width is what fills the
  device.

## References

Barrett, "Implementing the Rivest Shamir and Adleman public key encryption
algorithm on a standard digital signal processor" (1986); GMP as the CPU
reference implementation.

## License

Apache-2.0.