5 ms·

A 'Binary' System for Complex Numbers (1965) [pdf]

36 points by espeed 11y ago

poizan42 11y ago
This was published in JACM Volume 12, 1965: http://dl.acm.org/citation.cfm?doid=321264.321274 http://dl.acm.org/citation.cfm?doid=321264.321274. So for it to be unclassified it would have to somehow have been classified after being publicy published.
- dang 11y ago
  Thanks, I was hoping someone would find the actual date, which we've now added to the title. (Originally it said "Unclassified 2011".)
- jamessb 11y ago
  I think you are confusing 'unclassified' and 'declassified': declassified means that it was previously (but no longer) classified; unclassified means that it is not classified. If this had been classified then declassified it would have the original marker (but crossed out), and the text at the bottom would be "Declassified and Approved for Release", rather than just "Approved for Release". For an example of this, see https://www.nsa.gov/public_info/_files/cryptologs/cryptolog_01.pdf https://www.nsa.gov/public_info/_files/cryptologs/cryptolog_...
  - poizan42 11y ago
    Yeah, I think I (as well as other users) got confused by it being "unclassified in 2011" as the title said previously.
daveloyall 11y ago
If scalar numbers could be called "1D", then could these `a + bi` numbers be called "2D"? ie, an ordered pair? ie, a vector? IFF I'm understanding the above correctly, I have a question: does encoding scheme described in this system let you add/subtract vectors using the fast integer hardware in CPUs?
- jsprogrammer 11y ago
  Perhaps the theoretical idea of an `a + bi` number could be called 2D. However, this particular implementation, anyway, only represents scalar values (every number is just a binary string).
- eximius 11y ago
  Traditionally, complex numbers are on a 2D plane, yes. However, this method uses a subset of complex numbers strung out linearly. Conceptually, the visualization of Cantor's diagonalization argument is similar.
- yoklov 11y ago
  Vector operations are already possible in hardware using the fast, well, vector hardware in the cpu. And ime the speed up from using integers is minor and often not the cost from conversion (to e.g 28.4 fixed or similar), since you often need floats in the end.
mrcactu5 11y ago
why was this classified?? in any case this is really clever. the norm-squared of 1+i in the Gaussian integers is (1+i)(1-i) = 1 + 1 = 2. the norm is sqrt(2). another way to think of this is we can color a checkerboard like this: xoxoxoxo oxoxoxox xoxoxoxo oxoxoxox The o's are "even" in this binary system and the x's are "odd" So in a sense this is the "square-root" of the binary numbers in the complex intgers Z[i] I wonder then how "carries" work in this binary system?
- poizan42 11y ago
  > why was this classified?? It wasn't, it isn't clear to me what it even has to do with NSA. It was published in Journal of the ACM, Volume 12, 1965: http://dl.acm.org/citation.cfm?doid=321264.321274 http://dl.acm.org/citation.cfm?doid=321264.321274. Actually the -1+i base was proposed by S. Khmelnik a year earlier (at least according to Wikipedia, I can't read Russian...)
DanBC 11y ago
Walter Penney also invented a binary game: https://en.wikipedia.org/wiki/Penney%27s_game https://en.wikipedia.org/wiki/Penney%27s_game > Penney's game, named after its inventor Walter Penney, is a binary (head/tail) sequence generating game between two players. At the start of the game, the two players agree on the length of the sequences to be generated. > This length is usually taken to be three, but can be any larger number. > Player A then selects a sequence of heads and tails of the required length, and shows this sequence to player B. Player B then selects another sequence of heads and tails of the same length. Subsequently, a fair coin is tossed until either player A's or player B's sequence appears as a consecutive subsequence of the coin toss outcomes. The player whose sequence appears first wins. > Provided sequences of at least length three are used, the second player (B) has an edge over the starting player (A). This is because the game is nontransitive such that for any given sequence of length three or longer one can find another sequence that has higher probability of occurring first.
deleted 11y ago
[deleted]
s-phi-nl 11y ago
Essentially, this defines a homomorphic pairing function[1] for the integers. A Gaussian integer can be seen as the pair (a, b) where a and b are integers. This assigns a unique natural number to each one. One can use this to show that pairs of integers have the same cardinality as natural numbers. Further, since one can sum the binary representations of two numbers and get the representation of the result, this is homomorphic under addition. I have never before seen a pairing function with that property (not that I have seen many). [1] https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairin...
jacobolus 11y ago
It’s too bad there’s no analysis here of the comparative cost (in terms of logic gates or whatever) between this system and a conventional pair-of-numbers representation, for various operations (e.g. addition, multiplication, negation, multiplicative inversion, trigonometric functions, ...). My suspicion is that this kind of thing wouldn’t have enough savings to be worthwhile except for very specialized problems, but it’s hard to guess without seeing someone try. It would be a fun thing to play with for a high school student with a bit of free time.

36 points by espeed 11y ago

This was published in JACM Volume 12, 1965: http://dl.acm.org/citation.cfm?doid=321264.321274 http://dl.acm.org/citation.cfm?doid=321264.321274. So for it to be unclassified it would have to somehow have been classified after being publicy published.

dang 11y ago
Thanks, I was hoping someone would find the actual date, which we've now added to the title. (Originally it said "Unclassified 2011".)
jamessb 11y ago
I think you are confusing 'unclassified' and 'declassified': declassified means that it was previously (but no longer) classified; unclassified means that it is not classified. If this had been classified then declassified it would have the original marker (but crossed out), and the text at the bottom would be "Declassified and Approved for Release", rather than just "Approved for Release". For an example of this, see https://www.nsa.gov/public_info/_files/cryptologs/cryptolog_01.pdf https://www.nsa.gov/public_info/_files/cryptologs/cryptolog_...
- poizan42 11y ago
  Yeah, I think I (as well as other users) got confused by it being "unclassified in 2011" as the title said previously.

daveloyall 11y ago

If scalar numbers could be called "1D", then could these `a + bi` numbers be called "2D"? ie, an ordered pair? ie, a vector? IFF I'm understanding the above correctly, I have a question: does encoding scheme described in this system let you add/subtract vectors using the fast integer hardware in CPUs?

jsprogrammer 11y ago
Perhaps the theoretical idea of an `a + bi` number could be called 2D. However, this particular implementation, anyway, only represents scalar values (every number is just a binary string).
eximius 11y ago
Traditionally, complex numbers are on a 2D plane, yes. However, this method uses a subset of complex numbers strung out linearly. Conceptually, the visualization of Cantor's diagonalization argument is similar.
yoklov 11y ago
Vector operations are already possible in hardware using the fast, well, vector hardware in the cpu. And ime the speed up from using integers is minor and often not the cost from conversion (to e.g 28.4 fixed or similar), since you often need floats in the end.

mrcactu5 11y ago

why was this classified?? in any case this is really clever. the norm-squared of 1+i in the Gaussian integers is (1+i)(1-i) = 1 + 1 = 2. the norm is sqrt(2). another way to think of this is we can color a checkerboard like this: xoxoxoxo oxoxoxox xoxoxoxo oxoxoxox The o's are "even" in this binary system and the x's are "odd" So in a sense this is the "square-root" of the binary numbers in the complex intgers Z[i] I wonder then how "carries" work in this binary system?

poizan42 11y ago
> why was this classified?? It wasn't, it isn't clear to me what it even has to do with NSA. It was published in Journal of the ACM, Volume 12, 1965: http://dl.acm.org/citation.cfm?doid=321264.321274 http://dl.acm.org/citation.cfm?doid=321264.321274. Actually the -1+i base was proposed by S. Khmelnik a year earlier (at least according to Wikipedia, I can't read Russian...)

DanBC 11y ago

Walter Penney also invented a binary game: https://en.wikipedia.org/wiki/Penney%27s_game https://en.wikipedia.org/wiki/Penney%27s_game > Penney's game, named after its inventor Walter Penney, is a binary (head/tail) sequence generating game between two players. At the start of the game, the two players agree on the length of the sequences to be generated. > This length is usually taken to be three, but can be any larger number. > Player A then selects a sequence of heads and tails of the required length, and shows this sequence to player B. Player B then selects another sequence of heads and tails of the same length. Subsequently, a fair coin is tossed until either player A's or player B's sequence appears as a consecutive subsequence of the coin toss outcomes. The player whose sequence appears first wins. > Provided sequences of at least length three are used, the second player (B) has an edge over the starting player (A). This is because the game is nontransitive such that for any given sequence of length three or longer one can find another sequence that has higher probability of occurring first.

deleted 11y ago

[deleted]

s-phi-nl 11y ago

Essentially, this defines a homomorphic pairing function[1] for the integers. A Gaussian integer can be seen as the pair (a, b) where a and b are integers. This assigns a unique natural number to each one. One can use this to show that pairs of integers have the same cardinality as natural numbers. Further, since one can sum the binary representations of two numbers and get the representation of the result, this is homomorphic under addition. I have never before seen a pairing function with that property (not that I have seen many). [1] https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairin...

jacobolus 11y ago

It’s too bad there’s no analysis here of the comparative cost (in terms of logic gates or whatever) between this system and a conventional pair-of-numbers representation, for various operations (e.g. addition, multiplication, negation, multiplicative inversion, trigonometric functions, ...). My suspicion is that this kind of thing wouldn’t have enough savings to be worthwhile except for very specialized problems, but it’s hard to guess without seeing someone try. It would be a fun thing to play with for a high school student with a bit of free time.