It's generally considered to be the case that there are sixteen possible logical operations between two N-bit numbers and four possible logical operations on one N-bit number. I'd like to know how many possible arithmetic operations there are between two N-bit numbers. I'm asking in the context of ALU design, so I think in order to answer, it might first be helpful to clarify what precisely "arithmetic" means in this context. I suppose it is something to do with operations that can be expressed in algorithms that use a carry bit and maybe it means that they operate on numbers in two's compliment (or not) but this is all quite vague and insufficient to answer the question.
5
-
1$\begingroup$ (Compliments for seeing an advantage in defining terms.) (In the case of logical operations, there are quite a number of functions not depending on all arguments.) I guess I'd prefer arithmetic operations to be understandable from a base case (a # 0 = 0 # a = a) and one reduction (a # successor(b) = successor(a) # b = successor(a # b)) with possible additions like a # b = b # a. $\endgroup$– greybeardCommented Nov 10, 2021 at 7:35
-
$\begingroup$ Thank you, that's an inspiring good start. I don't know why the base case should be commutative though since subtraction isn't and we'd want to include subtraction: a - 0 = a, S(a) - 1 = a, etc. $\endgroup$– AnthonyCommented Nov 10, 2021 at 7:58
-
1$\begingroup$ If I'm understanding you correctly as to what you mean by "arithmetic", consider any invertible function $f$ which maps words to words. Then for any arithmetic operator $\oplus$, $f(f^{-1}(x) \oplus f^{-1}(y))$ is also an arithmetic operator, correct? $\endgroup$– Pseudonym ♦Commented Nov 10, 2021 at 8:25
-
$\begingroup$ @Pseudonym So you mean like 2*(x/2 ⊕ y/2) should be counted? Why? Isn't that more of a difference of algorithm than operation? Could you give a concrete example that doesn't produce the same result? $\endgroup$– AnthonyCommented Nov 11, 2021 at 5:31
-
$\begingroup$ If x is an integer, x/2 isn't necessarily an integer, so not a good example. But the circular rotation of the bits would work as an example. What I mean is, pick $f$ to be any permutation of the numbers $0 \ldots 2^{N}-1$. $\endgroup$– Pseudonym ♦Commented Nov 11, 2021 at 6:00
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Due to the imprecise nature of the question, it is hard to give a precise answer. Since my "post" mostly shares links to my own thoughts and answers to related questions, I won't even try to pretend that this would be an appropriate answer to the question (-> community wiki).
I'm asking in the context of ALU design, ...
I also pondered questions related to arithmetic and CPU primitives in the past, but more from the perspective of the "user" of the CPU, not the "designer".
The answer to my question Which associative and commutative operations are defined for any commutative ring? hints at how to answer this type of question from a category theory perspective where "natural operation" has a precise meaning. The discussion also provides examples of operations that are not "natural" in that sense, but are still defined generically for any commutative ring.
My motivation for pondering questions of which CPU primitives would be needed for "good support of parallelization" of the type that "would be available to hardware itself on the circuit level" can be seen in my question Is scalable hardware support for LogCFL (= sAC^1) possible? and in my unfocused review of related work and "opinions" in ALogTime, LogCFL, and threshold circuits: dreams of fast solutions. Uzi Vishkin seems to have made a much more serious effort than I ever will, and even argued his case from an economic perspective:
Alas, the software spiral is now broken: (a) nobody is building hardware that provides improved performance on the old serial software base; (b) there is no broad parallel computing application software base for which hardware vendors are committed to improve performance; and (c) no agreed-upon architecture currently allows application programmers to build such software base for the future
My own CPU "user" perspective (and actual relevant work and an appropriate short survey of existing work) can be seen in Theory and practice of signed-digit representations and in my answer to the question What number representation is this? This material might be interesting in that it shows that there is both relevant existing work that is not widely known, as well as useful representation systems not yet properly explored and worked out.
I recently revisited that kind of questions from the perspective to focus less on numbers and arithmetic: Useful primitives CPUs could provide, from TC0 (or NC1)
I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational primitives could exist, that are sometimes more useful than numbers.
Interestingly enough, I learned this Monday about concrete actually missing CPU primitives from this perspective: "shuffle" operations between the individual bytes and bits of CPU registers. AES seems to use those, and the non-availability of those "shuffle" operations currently seems to make hardware implementation much faster than software implementation than really necessary. But that still raises the basic question again whether it would have been possible for CPUs to provide a sufficiently comprehensive set of primitives.
$\begingroup$
$\endgroup$
There are 2n input bits, and if you assume a carry bit, it's 2n+1 input bits. There are n output bits plus a carry bit, so n+1 output bits.
For each output bit we can divide the set of input bits into those that produce an output of 0, and those that produce an output of 1. There are $2^{2n+1}$ possible ways to choose a subset of 2n+1 input bits.
Since there are n+1 output bits, we raise this to the power n+1, for a total of $2^{(n+1)(2n+1)}$ possible arithmetic functions processing 2n input bits and a carry bit, and producing n output bits and a carry bit. Without the carry bit, it is just $2^{2n^2}$ possible arithmetic functions.
$\begingroup$
$\endgroup$
Let us define the logic for all arithmetic as: XOR3(A,B,C)
Only difference between arithmetic functions would be how carry or borrow passes between slices. I support at least seven useful carry chain configurations in my own ALU.
Carry, Borrow, Worrob (B-A's carry for reverse subtraction) Borrow-like magnitude comparisons A=B, A<=B, A=>B, A<>B. I count seven meaningful ways to pass carry.
Not counting options that lock the chain for logic. Not counting rotate left, which also gives A plus A.
https://hackaday.io/project/174243/gallery#2b97119f08463dbe2b61c01254eea4ba
