The succ
function can be called prod(max)
times. The function can also be
written with a carry or overflow “bit”. Then when i == len(counter)
the return
value should be counter, True
. The return value of the last line,
counter, False
.
def succ(counter, max):
i = 0
counter[i] += 1
while counter[i] == max[i]:
counter[i] = 0
i += 1
if i == len(counter): return counter, i
counter[i] += 1
return counter, i
This function can be used to simulate multiple for-loops, where every element of
max
notes the number of loops. The i
return value, shows which for-loop just
overflowed. This can be used to simulate a step in that loop.
This code is a version of Algorithm M (TAOCP 7.2.1.1), but with the least
significant number in position 0. Here we always increase position 0, and deal
with overflow after that with the while
-loop. By incrementing position 0
first, we can use equality to check for overflow, instead of checking
max[i]-1
.
An example of the output of the code.
c = [0,0,0]
m = [2,2,2]
# c = [0,0,0]
c, i = succ(c, m)
# c = [1,0,0]
c, i = succ(c, m)
# c = [0,1,0]
c, i = succ(c, m)
# c = [1,1,0]
c, i = succ(c, m)
# c = [0,0,1]
c, i = succ(c, m)
# c = [1,0,1]
c, i = succ(c, m)
# c = [0,1,1]
c, i = succ(c, m)
# c = [1,1,1]
The counter can be used to show the elements of a tensor where each column is
separated by a space, and rows by one or more newlines. The counter helps when
there are multiple dimensions and you don’t know how many. The len(shape)
is
the number of dimensions, and each element of shape is the max value for that
dimension in the counter.
# Very much simplified piece of code
class Tensor:
def __init__(self, data, shape) -> None:
self.data = data
self.shape = shape
def show(self):
s = self.shape
t = [0] * len(self.shape)
for x in self.data:
n, j = succ(t, s)
print(x, end=" " if j == 0 else ("\n"*j))
t = n
print()
As View
class can be used to do some transformations on the data. The index
function return the index into data
based on the strides
of the tensor.
Instead of looping through the elements we loop through the number of elements
of noted by the shape
of the view. This shape can be different from the
shape
of the Tensor
t
.
def index(counter, strides):
return sum([c*s for c, s in zip(counter, strides)])
class View:
shape: Tuple[int, ...]
strides: Tuple[int, ...]
def __init__(self, shape, strides) -> None:
self.shape = shape
self.strides = strides
def view(self, t: Tensor):
counter = [0] * len(self.shape)
for i in range(int(prod(self.shape))):
idx = index(counter, self.strides)
counter, j = succ(counter, self.shape)
print(t.data[idx], end=" " if j == 0 else ("\n"*j))
print()