Lines Matching refs:divisor
3652 The precision of the division is proportional to the value of $q$. If the divisor $b$ is used frequently as is the case with
3707 Note that the original divisor $2^q$ has been replaced with $\beta^{m+1}$ where in this case $q$ is a multiple of $lg(\beta)$. Also note that the
3708 exponent on the divisor when added to the amount $q_0$ was shifted by equals $2m$. If the optimization had not been performed the divisor
5258 will be used. Let $x$ represent the divisor and $y$ represent the dividend. Let $q$ represent the integer quotient $\lfloor y / x \rfloor$ and
5286 their reason of existing are never explained. For this example let $y = 5471$ represent the dividend and $x = 23$ represent the divisor.
5302 As alluded to earlier the quotient digit $k$ can be estimated from only the leading digits of both the divisor and dividend. When $p$ leading
5303 digits are used from both the divisor and dividend to form an estimation the accuracy of the estimation rises as $p$ grows. Technically
5305 dividend and divisor are zero.
5308 of the estimation technique is to use $t + 1$ digits of the dividend and $t$ digits of the divisor, in particularly when $t = 1$. The estimate
5310 represent the most significant digits of the dividend and divisor respectively.
5347 remainder. The purpose of normalization is to ensure the leading digit of the divisor is sufficiently large such that the estimated quotient will
5348 lie in the domain of a single digit. Consider the maximum dividend $(\beta - 1) \cdot \beta + (\beta - 1)$ and the minimum divisor $\beta / 2$.
5449 This algorithm will calculate quotient and remainder from an integer division given a dividend and divisor. The algorithm is a signed
5452 First the divisor $b$ must be non-zero which is enforced in step one. If the divisor is larger than the dividend than the quotient is implicitly
5456 divisor $y$ and dividend $x$ are made as well. The core of the division algorithm is an unsigned division and will only work if the values are
5475 by optimizing Barrett reduction.}. Steps 13.6 and 13.7 subtract the multiple of the divisor from the dividend (\textit{Similar to step 3.3 of
5476 algorithm~\ref{fig:raddiv}} and then subsequently add a multiple of the divisor if the quotient was too large.
5499 Lines 109 and 113 handle the two trivial cases of inputs which are division by zero and dividend smaller than the divisor
5611 divisor is only a single digit a specialized variant of the division algorithm can be used to compute the quotient.
5650 If the divisor $b$ is equal to three a variant of this algorithm is used which is called mp\_div\_3. It replaces the division by three with
5923 This chapter discusses several fundamental number theoretic algorithms such as the greatest common divisor, least common multiple and Jacobi
5928 The greatest common divisor of two integers $a$ and $b$, often denoted as $(a, b)$ is the largest integer $k$ that is a proper divisor of
5941 \textbf{Output}. The greatest common divisor $(a, b)$. \\
5956 This algorithm will quickly converge on the greatest common divisor since the residue $r$ tends diminish rapidly. However, divisions are
5967 \textbf{Output}. The greatest common divisor $(a, b)$. \\
5981 \textbf{Proof} \textit{Algorithm~\ref{fig:gcd2} will return the greatest common divisor of $a$ and $b$.}
5984 divisible by the greatest common divisor (\textit{until the last iteration}) and in the last iteration of the algorithm $b = 0$, therefore, in the
5989 not divide the greatest common divisor but will divide $b - a$. In this case ${b - a} \over p$ is also an integer and still divisible by
5990 the greatest common divisor.
6001 \textbf{Output}. The greatest common divisor $(a, b)$. \\
6028 divisor of $p^k$. After step two the remaining common divisor of $a$ and $b$ cannot be divisible by $p$. This means that $p$ can be safely
6038 and will produce the greatest common divisor.
6046 \textbf{Output}. The greatest common divisor $c = (a, b)$. \\
6079 This algorithm will produce the greatest common divisor of two mp\_ints $a$ and $b$. The algorithm was originally based on Algorithm B of
6083 The first two steps handle the cases where either one of or both inputs are zero. If either input is zero the greatest common divisor is the
6088 factor of the remaining greatest common divisor between $u$ and $v$ and can be safely evenly divided out of either whenever they are even. Step
6096 After $v = 0$ occurs the variable $u$ has the greatest common divisor of the pair $\left < u, v \right >$ just after step six. The result
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
6129 Linear Feedback Shift Registers (LFSR) tend to use registers with periods which are co-prime (\textit{e.g. the greatest common divisor is one.}).
6152 dividing the product of the two inputs by their greatest common divisor.
6366 binary approach is very similar to the binary greatest common divisor algorithm except it will produce a full solution to the Diophantine
6426 The astute reader will observe that steps seven through nine are very similar to the binary greatest common divisor algorithm mp\_gcd. In this case
6433 If $v$, the greatest common divisor of $a$ and $b$ is not equal to one then the algorithm will report an error as no inverse exists. Otherwise, $C$