 | This article does not cite any sources .(June 2019) (Learn how and when to remove this template message) |
Reduction of summands is an algorithm for fast binary multiplication of non-signed binary integers. It is performed in three steps: production of summands, reduction of summands, and summation.
In binary multiplication, each row of the summands will be either zero or one of the numbers to be multiplied. Consider the following:
1001 x1010 ----- 0000 1001 0000 1001
The second and fourth row of the summands are equivalent to the first term. Production of the summands requires a simple AND gate for each summand. Given enough AND gates, the time to produce the summands will be one cycle of the arithmetic logic unit.
The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If none or not all inputs to the AND gate are HIGH, a LOW output results. The function can be extended to any number of inputs.
An arithmetic logic unit (ALU) is a combinational digital electronic circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on floating point numbers. An ALU is a fundamental building block of many types of computing circuits, including the central processing unit (CPU) of computers, FPUs, and graphics processing units (GPUs). A single CPU, FPU or GPU may contain multiple ALUs.
The summands are reduced using a common 1-bit full adder that accepts two 1-bit terms and a carry-in bit. It produces a sum and a carry-out. The full adders are arranged such that the sum remains in the same column of summands, but the carry-out is shifted left. In each round of reduction, three bits in a single column are used as the two terms and carry-in for the full adder, producing a single sum bit for the column. This reduces the bits in the column by a factor of 3. However, the column to the right will shift over carry-out bits, increasing the bits in the column by a third of the number of rows of summands. At worst, the reduction will be 2/3 the number of rows per round of reduction.
An adder is a digital circuit that performs addition of numbers. In many computers and other kinds of processors adders are used in the arithmetic logic units or ALU. They are also used in other parts of the processor, where they are used to calculate addresses, table indices, increment and decrement operators, and similar operations.
The following shows how the first round of reduction is performed. Note that all "empty" positions of the summands are considered to be zero (a . is used here as indicator of the "assumed zero values"). In each row, the top three bits are the three inputs to the full adder (two terms and carry-in). The sum is placed in the top bit of the column. The carry-out is placed in the second row of the column to the left. The bottom bit is a single feed into an adder. The sum of this adder is placed in the third row of the column. Carry-out is ignored as it will always be zero, but by design it would be placed in the fourth row of the column to the left. For design, it is important to note that rows 1, 3, 5, ... (counting from the top) are filled with sums from the column itself. Rows 2, 4, 6, ... are filled with carry-out values from the column to the right.
1011 x0110 ----- ...0000 ..1011. .1011.. 0000... ------- 0111010 000100. 00000..
Reduction is performed again in exactly the same way. This time, only the top three rows of summands are of interest because all other summands must be zero.
0111010 000100. 00000.. ------- 0110010 001000.
When there are only two significant rows of summands, the reduction cycles end. A basic full adder normally requires three cycles of the arithmetic logic unit. Therefore, each cycle of reduction is commonly 3 cycles long.
When there are only two rows of summands remaining, they are added using a fast adder. There are many designs of fast adders, any of which may be used to complete this algorithm.
The calculation time for the reduction of summands algorithm is: T = 1Δt + r3Δt + FA (where r is the number of reduction cycles and FA is the time for the fast adder at the end of the algorithm).
In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each decimal digit is represented by a fixed number of bits, usually four or eight. Special bit patterns are sometimes used for a sign or for other indications.
A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.
Golden ratio base is a non-integer positional numeral system that uses the golden ratio as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary. Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ + 1 = φ2. For instance, 11φ = 100φ.
In mathematics and digital electronics, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: typically "0" (zero) and "1" (one).
Two's complement is a mathematical operation on binary numbers, and is an example of a radix complement. It is used in computing as a method of signed number representation.
In CPU design, the use of a sum-addressed decoder (SAD) or sum-addressed memory (SAM) decoder is a method of reducing the latency of the CPU cache access and address calculation. This is achieved by fusing the address generation sum operation with the decode operation in the cache SRAM.
In mathematics, finite field arithmetic is arithmetic in a finite field as opposed to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
Elementary arithmetic is the simplified portion of arithmetic that includes the operations of addition, subtraction, multiplication, and division. It should not be confused with elementary function arithmetic.
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture.
In electronics, a carry-select adder is a particular way to implement an adder, which is a logic element that computes the -bit sum of two -bit numbers. The carry-select adder is simple but rather fast, having a gate level depth of .
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0,1) matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets.
The Dadda multiplier is a hardware multiplier design invented by computer scientist Luigi Dadda in 1965. It is similar to the Wallace multiplier, but it is slightly faster and requires fewer gates.
A carry-save adder is a type of digital adder, used in computer microarchitecture to compute the sum of three or more n-bit numbers in binary. It differs from other digital adders in that it outputs two numbers of the same dimensions as the inputs, one which is a sequence of partial sum bits and another which is a sequence of carry bits.
A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. It is built using binary adders.
In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation. It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardware, but at the expense of high latency.
The serial binary adder or bit-serial adder is a digital circuit that performs binary addition bit by bit. The serial full adder has three single-bit inputs for the numbers to be added and the carry in. There are two single-bit outputs for the sum and carry out. The carry-in signal is the previously calculated carry-out signal. The addition is performed by adding each bit, lowest to highest, one per clock cycle.
Kochanski multiplication is an algorithm that allows modular arithmetic to be performed efficiently when the modulus is large. This has particular application in number theory and in cryptography: for example, in the RSA cryptosystem and Diffie–Hellman key exchange.
The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number. The ones' complement of the number then behaves like the negative of the original number in some arithmetic operations. To within a constant, the ones' complement behaves like the negative of the original number with binary addition. However, unlike two's complement, these numbers have not seen widespread use because of issues such as the offset of −1, that negating zero results in a distinct negative zero bit pattern, less simplicity with arithmetic borrowing, etc.