I ran into this question when writing a program. I need to generate two matrices, and calculate their product.

However, I must ensure all entries are within 8-bit signed integer range, i.e. $[-128, 128)$. Is there a way to algorithmically achieve this?

Furthermore, what if I need every intermediate result during calculation is also within such range?

Besides, I think the algorithm needs not to be deterministic, but with high probability is enough. For example, is there a way to randomly generate the initial $A$ and $B$, so that the entries of product $AB$ are highly likely to within $[-128, 127)$? If so, I can run the program several times to be lucky.


The dimensions of $A$ and $B$ are inputs of the program, which are typically 1K ~ 5K.

  • $\begingroup$ That depends on what the dimension of the matrices is. $\endgroup$ Jul 28, 2016 at 13:37
  • $\begingroup$ @GregoryGrant, the dimensions are inputs of the program, which are typically 1K ~ 5K. But as a math problem, I think we should treat them as variables? $\endgroup$
    – hxhxhx88
    Jul 28, 2016 at 14:03
  • $\begingroup$ So you're saying your matrices might have up to $5,000$ dimensions? There's no way to do arithmetic on matrices with $5,000$ rows and columns in only the $8$-bit range. You might want to completely reconsider what you are doing. $\endgroup$ Jul 28, 2016 at 14:30
  • $\begingroup$ @GregoryGrant why no way? Yes the matrix is of , e.g. 5000x5000, dims. I am writing GPU code, and need data for testing. I am not sure what kind of arithmetic do are referring to? I think I can obviously do matrix calculation. $\endgroup$
    – hxhxhx88
    Jul 28, 2016 at 14:54
  • 1
    $\begingroup$ matrix multiplication is arithmetic. Those are big matrices, each entry of the product is a sum of $5,000$ numbers so if they add up to something less than $128$ in every one of the $25,000,000$ entries of the product matrix, then they must be very sparse and be mostly all zeros. $\endgroup$ Jul 28, 2016 at 14:57

2 Answers 2


Let $D$ be the dimension of the matrices. For each row of $A$, simply choose $127$ of them at random to equal $1$ and set the rest to $0$. Do the same for each column of $B$. You are then guaranteed that the entries of $AB$ are nonnegative and at most $127$.

For a more random approach, choose each entry of $A$ and $B$ independently, taking the value $-1$ with probability $p$, $1$ with probability $p$, and $0$ with probability $1-2p$. The variance of each entry of $AB$ is $4p^2D$, which will be quite small if $p$ is sufficiently small as a function of $D$. Thus with high probability, the entries of $AB$ will all be less than $128$ in absolute value.


With Python...

import numpy as np

low = -128
high = 128
size = (5,5)
dt = np.dtype('i1')
A = np.random.randint(low, high,size, dtype= dt)
B = np.random.randint(low, high, size, dtype=dt)

C = np.dot(A,B)

The entries can't be outside your range because the representation doesn't exist.

array([[-124,  -95,   93,  -61,   40],
       [ -54, -117,   -7,   35,   68],
       [  79,   68,  -82,   83,  -68],
       [  91,  -14,   28,  102,   92],
       [ -40,   30, -122,  -30,  -40]], dtype=int8)

If you change the dtype you'd see that it will go outside the range..

dt = np.dtype('i2')

array([[ -7161,   3352,  13377, -12262,  -2379],
       [ -7873,   8113,  -5097,  -7848,   3062],
       [ -8811,   9435,   9431, -11306,   1616],
       [ 12141, -24141,  24527,   5043,   -622],
       [  4488,  -6618,  -5862,  15442,   1308]], dtype=int16)

For a large matrix you can generate a sparse matrix. The library is scipy sparse. Then determine the level of sparsity so you can fit it in memory.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .