Multiplying Large Numbers

Posted on Jul 9, 2021

Recently, I mentioned that I’m working on a new RTL called Polished. Polished will have a built in simulator backend that aims to be very fast.

Since wires in a netlist can have any length, the backend must be able to handle any arithmetic operation between two wires.

The final implementation that will end up going into Polished will be different from the toy example present below in the following ways:

  • will sign extend lhs and rhs to match the width of value being assigned to
  • the above results in the iteration length of the nested 2-deep loop being asgn.len*asgn.len instead of lhs.len*rhs.len
  • digits of base 4294967296(2^32) A.K.A uint32 instead of base 10

The Nim snippet at the end is primarily a functional toy example of how one might multiply two large numbers. The implementation optimizes for space, instead of creating as many intermediate products as there are digits in lhs or rhs, and then summing those intermediate products(such and implementation would be easy fodder for SIMD units by the way), the following implementation accumulates the product onto the prod var itself.

Lastly, while I can rewrite the following implementation such that it is possible to do var product = a prod b or even better, overload the assignment operator such that we can do var product = a * b, the issue with this is that nim may compile those statements to the following semi-nim pseudocode:

var product = [0,0,0,0]
var i1 = a*b
product = i1
collect_garbage()

I’d like to generate as little garbage as possible so that my simulator backend can be fast on large designs, perhaps even approaching millions of cycles per second on a single thread (multithreaded simulations will eventually be supported).

I know Nim can be smart sometimes and avoid the above using NVRO, but I’d rather not take any chances.

toy_mult.nim

from math import floorMod
proc mult(dest : var openArray[int], lhs, rhs : openArray[int]) = 
  var prod           : int
  var sum            : int
  var carry          : int

  for l_index, l_digit in lhs:
    for r_index, r_digit in rhs:
      if (l_index + r_index) <= dest.high:

        prod           = l_digit*r_digit

        # form sum
        sum   = dest[l_index + r_index] + floorMod(prod, 10)
        carry = (prod div 10) + (sum div 10)
        dest[l_index + r_index] = floorMod(sum, 10)

        if (l_index + r_index + 1) <= dest.high:
          dest[l_index + r_index + 1] += carry

proc string(number : var openArray[int]) : string = 
  for digit in number:
    result = $digit & result

# now we do 12345 * 56789
# note that we have to insert the numbers in backwards
var a    = [5,4,3,2,1]
var b    = [9,8,7,6,5]
var prod = [0,0,0,0,0,0,0,0,0,0]

prod.mult(a,b)
echo "a = ", a.string
echo "b = ", b.string
echo "prod = ", prod.string

Results

a = 12345
b = 56789
prod = 0701060205

Notable References I’ve Used: