I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor switches that will be required per multiply, in terms of $N$?

  • $\begingroup$ Is a "switch" just a transistor? Or is it the act of a transistor output "changing state"? Because the latter is something that only makes sense to me when the transistor is part of a memory circuit, and a multiplier can be implemented without memory. Next: What multiplication algorithm is being used? $\endgroup$ – j_random_hacker Jan 12 at 20:31
  • 1
    $\begingroup$ Wikipedia has a thorough page on the bit complexity of integer multiplication. I am not aware of any work which tries to take advantage of many different multiplications being done at once. $\endgroup$ – Yuval Filmus Jan 12 at 20:43
  • $\begingroup$ A 'switch' is the transistor changing state. I think all transistors have this property, not just memory-- if you're e.g. using a transistor to compute a NOT, if the transistor is in a 1 state and you give it a 1 as input, it will have to switch to the 0 (NOT 1) state. $\endgroup$ – abergal Jan 12 at 20:54
  • $\begingroup$ There is an unfortunate ambiguity in the meaning of switch here. Neither toggle nor flip, inversion, (signal) edge, or (state) change seem any better. Transition is used for change in stored state more often than for signal state change, e.g, change in the state of an automaton. (The other meaning being device steered between *passing/conducting and blocking/isolating - electrical charges, photons, molecules - you name it.) $\endgroup$ – greybeard Jan 12 at 23:50
  • 2
    $\begingroup$ Please edit the question to incorporate relevant information into your post, including defining what you mean by "switch", so it is self-contained and reads well for someone who encounters it for the first time, and so people don't have to read the comments to understand what you're asking. Then you can flag the comments as 'no longer needed' once all of that information has been incorporated into the question. $\endgroup$ – D.W. Jan 13 at 8:47

I haven't edited my question, but in case others are here: this thesis addresses the question I was intending (https://core.ac.uk/download/pdf/52104064.pdf), finding e.g. 1189 average transitions required for a certain architecture for a 16-bit by 16-bit multiply that's completely random bits. \


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.