Multiplying Large Numbers
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
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.
from math import floorMod proc mult(prod : var openArray[int], lhs, rhs : openArray[int]) = var tmp_prod : int var sum : int var carry : int var lower_digit : int for l_index, l_digit in lhs: for r_index, r_digit in rhs: tmp_prod = l_digit*r_digit lower_digit = floorMod(tmp_prod, 10) carry = tmp_prod div 10 # form sum sum = prod[l_index + r_index] + lower_digit if sum > 9: carry += sum div 10 sum = floorMod(sum, 10) if (l_index + r_index) <= prod.high: prod[l_index + r_index] = sum if (l_index + r_index + 1) <= prod.high: prod[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
a = 12345 b = 56789 prod = 0701060205