PDP-8: count number of set bits in a word

Guy Dunphy guykd at optusnet.com.au
Fri Apr 5 17:05:51 CDT 2019


At 08:49 PM 5/04/2019 +0000, you wrote:
>Hi Kyle,
>
>hat's a really interesting problem, and the government (NSA) wanted this badly and done FAST.
>
>they asked Seymour Cray to create a specific instruction for this and they called it 'population count'
>
>Anybody know the why and how it is useful?
>
>I am deep in matrix math books and 'classification algorithms' in statistics math, looking into electronics reliability WCCA, so this is an interesting topic.
>
>Randy

If we're considering hardware solutions, then the best way is to build a simple I/O device, with a writeable latch for the data word, fed as address into some nonvolatile memory like a big EPROM or flash, the output of which can be read via a port. Fill the NV memory with the required lookup table (derived by some code written in anything. BASIC for lols.)
So the required code is just one write and one read.

See the size chart: https://en.wikipedia.org/wiki/EPROM
The biggest EPROM made was ST M27C322, 32 Mbit, 2Mx16.  21 Address bits, 16 data bits, 80nS access time.
http://pdf.datasheetcatalog.com/datasheet/stmicroelectronics/6184.pdf
Wasteful though, since the result only needs 5 bits.

For an 8 bit result, 27C4001, 512K x 8 bit, 19 Address bits. 
http://www-inst.eecs.berkeley.edu/~cs150/fa02/docs/M27C4001.pdf

If the argument is only a 16bit word, then use a 27512.  64K x 8 bit

Guy


More information about the cctalk mailing list