# Better Algorithm to determine the number of all TRUE rows in a logical matrix

I have a matrix of logicals (TRUE, FALSE) and I need to count the number of rows that contain only TRUE values.

My current algorithm:

For every row:

1. initialize counter
2. reduce each col by + (take the sum of all the values in that row)
3. if the result from 1. == the number of total columns, increment counter.

Is there a different (hopefully more efficient) routine I could apply?

• Any way to do this must examine all entries in each row in the worst case, i.e. $n \cdot m$ entries for an $n \times m$ matrix. You can get a better algorithm by stopping as soon as you see a FALSE in a row, which makes the best case better (and presumably the average too) but has the same worst case. – vonbrand Sep 27 '15 at 17:29
• @vonbrand thanks, I have tried this and in practice actually checking for a FALSE is much slower than just summing over the whole row then checking the sum :( – hannah heres Sep 27 '15 at 17:31
• That very much depends on an optimized "reduce sum over row" implementation in your language (and if it is "reduce and", they might internally do short circuiting). – vonbrand Sep 27 '15 at 17:34
• @vonbrand yea in c++ or c or R this seems to be the case, sorry if I didn't set it up clearly; thanks for the input though :) – hannah heres Sep 27 '15 at 17:42
• If the matrix is stored as column bit vectors, you can reduce the column vectors with logical AND, stopping if you get all zeroes, then do a bit count. – Davislor Sep 28 '15 at 11:23