Pure BigInts for Nim

This library provides a pure implementation for arbitrary precision integers in Nim.

It can be installed through nimble with:

nimble install bigints

bigints provides a BigInt type and related operations with standard Nim syntax:

• creation of BigInt from all standard integer types (initBigInt)
• comparisons (<, <=, ==)
• addition, negation and subtraction (+, -, += -=)
• multiplication (*, *=)
• bit shifts (shr, shl)
• integer division and modulo operation (div, mod)
• exponentiation (^, pow)
• conversion of BigInt from/to strings supporting bases from 2 to 36 (initBigInt, $)
• iteration utilities (inc, dec, countdown, countup, .., ..<)

Most of the operations above (all those for which it makes sense) are also available between a BigInt and a int32.

For examples of usage see the examples folder.

Current limitations and possible enhancements

• not expected to work on 32 bit
• some common bitwise operations (and, or, xor, not) are not implemented
• operations between BigInt and standard integer types besides int32 are not implemented
• api for BigInt type is probably unstable (currently it is a tuple, it might become an object or ref object in the future)
• arithmetical operations such as addition, multiplication and division are not optimized for performance (e.g. karatsuba multiplication is not implemented)

Full API documentation

The following api documentation is generated with mddoc. To regenerate install mddoc with nimble and run

mddoc .\src\bigints.nim

API: bigints

import bigints

type Flags

Flags = enum
 Negative

type BigInt

BigInt = tuple[limbs: seq[uint32], flags: set[Flags]]

proc initBigInt

proc initBigInt(vals: seq[uint32]; flags: set[Flags] = {}): BigInt

proc initBigInt

proc initBigInt[T: int8 | int16 | int32](val: T): BigInt

proc initBigInt

proc initBigInt[T: uint8 | uint16 | uint32](val: T): BigInt

proc initBigInt

proc initBigInt(val: int64): BigInt

proc initBigInt

proc initBigInt(val: uint64): BigInt

template initBigInt

template initBigInt(val: int): BigInt

template initBigInt

template initBigInt(val: uint): BigInt

proc initBigInt

proc initBigInt(val: BigInt): BigInt

const zero

zero = ([0'u], {})

const one

one = ([1'u], {})

proc cmp

Returns:

• a value less than zero, if a < b
• a value greater than zero, if a > b
• zero, if a == b

proc cmp(a, b: BigInt): int64

proc cmp

Returns:

• a value less than zero, if a < b
• a value greater than zero, if a > b
• zero, if a == b

proc cmp(a: BigInt; b: int32): int64

proc cmp

proc cmp(a: int32; b: BigInt): int64

proc <

proc `<`(a, b: BigInt): bool

proc <

proc `<`(a: BigInt; b: int32): bool

proc <

proc `<`(a: int32; b: BigInt): bool

proc <=

proc `<=`(a, b: BigInt): bool

proc <=

proc `<=`(a: BigInt; b: int32): bool

proc <=

proc `<=`(a: int32; b: BigInt): bool

proc ==

proc `==`(a, b: BigInt): bool

proc ==

proc `==`(a: BigInt; b: int32): bool

proc ==

proc `==`(a: int32; b: BigInt): bool

proc -

proc `-`(a: BigInt): BigInt

proc +

proc `+`(a: BigInt; b: int32): BigInt

proc +

proc `+`(a, b: BigInt): BigInt

template +=

template `+=`(a: var BigInt; b: BigInt)

template +=

template `+=`(a: var BigInt; b: int32)

template optAddInt

template optAddInt{
 x = y + z
}(x, y: BigInt; z: int32)

template optAdd

template optAdd{
 x = y + z
}(x, y, z: BigInt)

proc -

proc `-`(a: BigInt; b: int32): BigInt

template -=

template `-=`(a: var BigInt; b: int32)

proc -

proc `-`(a, b: BigInt): BigInt

template -=

template `-=`(a: var BigInt; b: BigInt)

template optSub

template optSub{
 x = y - z
}(x, y, z: BigInt)

proc *

proc `*`(a: BigInt; b: int32): BigInt

template *=

template `*=`(a: var BigInt; b: int32)

proc *

proc `*`(a, b: BigInt): BigInt

template *=

template `*=`(a: var BigInt; b: BigInt)

template optMulInt

template optMulInt{
 x = `*`(y, z)
}(x: BigInt{noalias}; y: BigInt; z: int32)

template optMulSameInt

template optMulSameInt{
 x = `*`(x, z)
}(x: BigInt; z: int32)

template optMul

template optMul{
 x = `*`(y, z)
}(x: BigInt{noalias}; y, z: BigInt)

template optMulSame

template optMulSame{
 x = `*`(x, z)
}(x, z: BigInt)

proc shr

proc `shr`(x: BigInt; y: int): BigInt

template optShr

template optShr{
 x = y shr z
}(x, y: BigInt; z)

proc shl

proc `shl`(x: BigInt; y: int): BigInt

template optShl

template optShl{
 x = y shl z
}(x, y: BigInt; z)

proc reset

proc reset(a: var BigInt)

proc div

proc `div`(a: BigInt; b: int32): BigInt

proc div

proc `div`(a, b: BigInt): BigInt

proc mod

proc `mod`(a: BigInt; b: int32): BigInt

proc mod

proc `mod`(a, b: BigInt): BigInt

proc divmod

proc divmod(a: BigInt; b: int32): tuple[q, r: BigInt]

proc divmod

proc divmod(a, b: BigInt): tuple[q, r: BigInt]

template optDivMod

template optDivMod{
 w = y div z
 x = y mod z}(w, x, y, z: BigInt)

template optDivMod2

template optDivMod2{
 w = x div z
 x = x mod z}(w, x, z: BigInt)

template optDivMod3

template optDivMod3{
 w = w div z
 x = w mod z}(w, x, z: BigInt)

template optDivMod4

template optDivMod4{
 w = y mod z
 x = y div z}(w, x, y, z: BigInt)

template optDivMod5

template optDivMod5{
 w = x mod z
 x = x div z}(w, x, z: BigInt)

template optDivMod6

template optDivMod6{
 w = w mod z
 x = w div z}(w, x, z: BigInt)

proc ^

proc `^`[T](base, exp: T): T

proc pow

proc pow(base: int32 | BigInt; exp: int32 | BigInt): BigInt

proc toString

proc toString(a: BigInt; base: range[2 .. 36] = 10): string

proc $

proc `$`(a: BigInt): string

proc initBigInt

proc initBigInt(str: string; base: range[2 .. 36] = 10): BigInt {.raises: [ValueError], tags: [].}

proc inc

proc inc(a: var BigInt; b: BigInt)

proc inc

proc inc(a: var BigInt; b: int32 = 1)

proc dec

proc dec(a: var BigInt; b: BigInt)

proc dec

proc dec(a: var BigInt; b: int32 = 1)

iterator countdown

iterator countdown(a, b: BigInt; step: int32 = 1): BigInt {.inline.}

iterator countup

iterator countup(a, b: BigInt; step: int32 = 1): BigInt {.inline.}

iterator ..

iterator `..`(a, b: BigInt): BigInt {.inline.}

iterator ..<

iterator `..<`(a, b: BigInt): BigInt {.inline.}