I am curious how to construct the cheapest addition for d digits.
Intuitively, “cheapest” refers to using as few gates as possible, exploting some mathematical properties of binary addition, and perhaps reusing some intermediate results. Though I am not sure how exactly to compare “costs” of gates of different dimensions. (This probably requires some insight into how the hardware of actual computers is built. The mathematical “cost” of gates should approximate the actual costs of producing and operating the hardware. I mean, the ultimate benefit of this exercise would be to design an actual computer that is cheaper or faster or more energy efficient.)
Even very simply stated problems in boolean circuit optimization turn out to be deeply connected with extremely hard mathematical and computational problems, and in some cases even provably undecidable problems.
I don’t hold out very much hope of ever being able to find and prove solutions to most of these questions, even assuming superintelligence.
On the other hand, there are no doubt lots of practical improvements, even very substantial ones, to be made.
I am curious how to construct the cheapest addition for d digits.
Intuitively, “cheapest” refers to using as few gates as possible, exploting some mathematical properties of binary addition, and perhaps reusing some intermediate results. Though I am not sure how exactly to compare “costs” of gates of different dimensions. (This probably requires some insight into how the hardware of actual computers is built. The mathematical “cost” of gates should approximate the actual costs of producing and operating the hardware. I mean, the ultimate benefit of this exercise would be to design an actual computer that is cheaper or faster or more energy efficient.)
Then the same question for multiplication. Then, for building the entire computer.
Even very simply stated problems in boolean circuit optimization turn out to be deeply connected with extremely hard mathematical and computational problems, and in some cases even provably undecidable problems.
I don’t hold out very much hope of ever being able to find and prove solutions to most of these questions, even assuming superintelligence.
On the other hand, there are no doubt lots of practical improvements, even very substantial ones, to be made.