Sunday, August 28, 2016

[lrrnlvbb] Square popcount

Type a long number digit by digit.  After each digit, the computer calculates and displays the the number of 1s in the binary representation of the square of the number entered so far.

Merely demonstrates that computers are extremely fast at arithmetic: the binary population count seems to be displayed instantly after typing each digit.  Consider a human trying to replicate the calculation by hand.

(10*a + b)^2 = 100*a^2 + 20*a*b + b^2.  Parallel, e.g., GPU, implementations of small*big multiplication, addition, and popcnt could make this very fast.

No comments :