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 cctech
mailing list