Digital System Research

Computational Complexity

Can the known order of arithmetic operations be smashed?

Does an underlying number system affect the computational complexity of basic arithmetic operations? Indeed, this is true. Researchers at DSR are studying and analyzing newly discovered relationships.

There are significant tradeoffs between performing calculations in the binary number system versus performing calculations in the residue number system. The research and development at DSR has helped shed light on in this now expanded set of tradeoffs. Completing the comparison picture is the invention of new fractional residue formats which allow general purpose computation. For example, new fractional formats developed by DSR enjoy many of the same speed advantage as residue integer operations. Adding a fractional value to another fractional value requires only one clock, and multiplying a fractional value by an integer requires one clock, regardless of data width.

Additionally, multiplying a fractional value with another fractional value is linear with respect to digits, and is comparable with the multiply time of binary circuits having similar digit based architecture. The result is fast residue multiply combined with even faster operations of addition, subtraction and integer multiplication; when operated together this yields a significant improvement to the time complexity order of binary arithmetic operations.

Sorry, the comment form is closed at this time.

Delivering the next leap in computation™