Lines Matching refs:product
215 major companies such as RSA Security, Certicom and Entrust have built entire product lines on the implementation and
234 the product of two $n$-bit integers requires at least $2n$ bits of precision to be represented faithfully. A multiple
326 $a = 23$ and $b = 49$ represent two single precision variables. The single precision product shall be written
327 as $c \leftarrow a \cdot b$ while the double precision product shall be written as $\hat c \leftarrow a \cdot b$.
328 In this particular case, $\hat c = 1127$ and $c = 127$. The most significant digit of the product would not fit
534 highly modular. Being highly modular is a desirable property of any project as it often means the resulting product
1057 For example, suppose the product of two integers was $x_n = (0x_{n-1}x_{n-2}...x_0)_{\beta}$. The leading zero digit
2309 quickly compute the product.
2316 required. If it is non-zero a modified shift loop is used to calculate the remaining product.
2501 Computing the product of two integers in software can be achieved using a trivial adaptation of the standard $O(n^2)$ long-hand multiplication
2509 modification will become evident during the discussion of Barrett modular reduction. Recall that for a $n$ and $m$ digit input the product
2510 will be at most $n + m$ digits. Therefore, this algorithm can be reduced to a full multiplier by having it produce $n + m$ digits of the product.
2514 constant $\delta = 2^{\alpha - 2lg(\beta)}$ will represent the maximal weight of any column in a product (\textit{see sub-section 5.2.2 for more information}).
2533 Compute the product. \\
2556 This algorithm computes the unsigned product of two inputs $a$ and $b$, limited to an output precision of $digs$ digits. While it may seem
2564 temporary mp\_int variable $t$ is used to hold the intermediate result of the product. This allows the algorithm to be used to
2590 Each row of the product is added to the result after being shifted to the left (\textit{multiplied by a power of the radix}) by the appropriate
2591 count. That is in pass $ix$ of the inner loop the product is added starting at the $ix$'th digit of the reult.
2623 Inside the inner loop we calculate $\hat r$ as the mp\_word product of the two mp\_digits and the addition of the
2626 is required for the product. In x86 terms for example, this means using the MUL instruction.
2628 Each digit of the product is stored in turn (line 69) and the carry propagated (line 72) to the
2648 the product vector $\vec x$ as follows.
2702 At the nested $O(n^2)$ level the Comba method adds the product of two single precision variables to each column of the output
2709 The maximum number of terms in any column of a product is known as the ``column weight'' and strictly governs when the algorithm can be used. Recall
2809 to produce the individual columns of the product. We use the two aliases $tmpx$ and $tmpy$ (lines 62, 63) to point
2821 a carry for the next pass. After the outer loop we use the final carry (line 77) as the last digit of the product.
2828 The product $a \cdot b \equiv f(x)g(x)$ is the polynomial $W(x) = \sum_{i=0}^{2n} w_i x^i$. The coefficients $w_i$ will
2829 directly yield the desired product when $\beta$ is substituted for $x$. The direct solution to solve for the $2n + 1$ coefficients
2843 is simply the product $W(0) = w_0 = a_0 \cdot b_0$. The $\zeta_1$ term is the product
2928 Using the observation that $ac$ and $bd$ could be re-used only three half sized multiplications would be required to produce the product. Applying
2974 Calculate the final product. \\
2989 This algorithm computes the unsigned product of two inputs using the Karatsuba multiplication algorithm. It is loosely based on the description
3123 This algorithm computes the product of two mp\_int variables $a$ and $b$ using the Toom-Cook approach. Compared to the Karatsuba multiplication, this
3242 represent the number being squared. The first observation is that in row $k$ the $2k$'th column of the product has a $\left (x_k \right)^2$ term in it.
3244 The second observation is that every column $j$ in row $k$ where $j \ne 2k$ is part of a double product. Every non-square term of a column will
3245 appear twice hence the name ``double product''. Every odd column is made up entirely of double products. In fact every column is made up of double
3249 occurs at column $2k + 1$. For example, on row $1$ of the previous squaring, column one is part of the double product with column one from row zero.
3304 very algorithm. The product $a_{ix}a_{iy}$ will lie in the range $0 \le x \le \beta^2 - 2\beta + 1$ which is obviously less than $\beta^2$ meaning that
3328 drawback that it must double the product inside the inner loop as well. As for multiplication, the Comba technique can be used to eliminate these
3332 propagation operations from the inner loop. However, the inner product must still be doubled $O(n^2)$ times. The solution stems from the simple fact
3461 Compute final product. \\
3641 fixed point representation of $5$. The product $ab$ is equal to $45(2^{2q})$ which when normalized by dividing by $2^q$ produces $45(2^q)$.
3657 leads to a product of $19$ which when divided by $2^q$ produces $2$. However, with $q = 4$ the reciprocal is $\lfloor 2^q/5 \rfloor = 3$ and
3732 half of the product. It would be nice to be able to remove those digits from the product to effectively cut down the number of single precision
3733 multiplications. If the number of digits in the modulus $m$ is far less than $\beta$ a full product is not required for the algorithm to work properly.
3734 In fact the lower $m - 2$ digits will not affect the upper half of the product at all and do not need to be computed.
3747 $O(m^2)$ multiplication algorithm only the lower $m+1$ digits of the product have to be computed. Similarly the value of $a$ can
3801 for the quotient to have enough precision. If $a$ is the product of two numbers that were already reduced modulo $b$, this will not be a problem.
4133 a $k \times 1$ product $k$ times.
4193 As in the other Comba reduction algorithms there is a $\hat W$ array which stores the columns of the product. It is initially filled with the
4273 then a x86 multiplier could produce the 62-bit product and use the ``shrd'' instruction to perform a double-precision right shift. The proof
4274 of the above equation is very simple. First write $x$ in the product form.
4758 multiplied against the current product. In each iteration the product is squared which doubles the exponent of the individual terms of the
4759 product.
4780 When the product $a^{32} \cdot a^8 \cdot a^4$ is simplified it is equal $a^{44}$ which is the desired exponentiation. This particular algorithm is
5008 which uses Barrett reduction to reduce the product modulo $p$. The second algorithm mp\_exptmod\_fast performs the same operation
5138 algorithm to keep the product small throughout the algorithm.
6123 The least common multiple of a pair of integers is their product divided by their greatest common divisor. For two integers $a$ and $b$ the
6152 dividing the product of the two inputs by their greatest common divisor.
6307 the $(-1)^{(p-1)(a'-1)/4}$ is computed and multiplied against the current product $s$. The latter term evaluates to one if both $p$ and $a'$
6311 $\left ( {p' \over a'} \right )$ which is multiplied against the current Jacobi product.
6324 has to proceed compute the Jacobi. The variable $s$ is used to hold the current Jacobi product. Note that $s$ is merely a C ``int'' data type since