Lines Matching defs:digit
171 reason that $7$ times $6$ is $42$. However, $42$ has two digits of precision as opposed to one digit we started with.
308 The variable $\beta$ represents the radix of a single digit of a multiple precision integer and
318 For the purposes of this text $x_j$ will refer to the $j$'th digit of a single precision array and $\hat x_j$ will refer to
319 the $j$'th digit of a double precision array. Whenever an expression is to be assigned to a double precision
328 In this particular case, $\hat c = 1127$ and $c = 127$. The most significant digit of the product would not fit
568 the largest single digit value is $9$. However, by concatenating digits together larger numbers may be represented. Newly prepended digits
625 significant digit order. As a pencil and paper analogy the array is organized such that the right most digits are stored
642 \item The value of \textbf{used} implies the digit at index $(used - 1)$ of the \textbf{dp} array is non-zero. That is,
725 the initial integer will represent zero. If only a single digit were allocated quite a few subsequent re-allocations
771 Allocating a block of digits at first instead of a single digit has the benefit of lowering the number of usually slow
846 digit pointer \textbf{dp} setting.
862 The digits of the mp\_int are cleared by the for loop (line 27) which assigns a zero to every digit. Similar to mp\_init()
884 is large enough to simply increase the \textbf{used} digit count. However, when the size of the array is too small it
913 The requested digit count is padded up to next multiple of \textbf{MP\_PREC} plus an additional \textbf{MP\_PREC} (steps two and three).
928 if the \textbf{alloc} member of the mp\_int is smaller than the requested digit count. If the count is not larger than \textbf{alloc}
931 When a re-allocation is performed it is turned into an optimal request to save time in the future. The requested digit count is
993 \textbf{used} count is set to zero, the \textbf{alloc} count set to the padded digit count and the \textbf{sign} flag set
1047 the function instead of checking during the computation. For example, a multiplication of a $i$ digit number by a
1048 $j$ digit produces a result of at most $i + j$ digits. It is entirely possible that the result is $i + j - 1$
1055 there would be an excess high order zero digit.
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
1063 \textbf{used} count until a non-zero most significant digit is found. Also in this system, zero is considered to be a
1413 \textbf{Input}. An mp\_int $a$ and a digit $b$ \\
1429 This algorithm sets a mp\_int to a small single digit value. Step number 1 ensures that the integer is reset to the default state. The
1430 single digit is set (\textit{modulo $\beta$}) and the \textbf{used} count is adjusted accordingly.
1441 is zero. Next we set the digit and reduce it modulo $\beta$ (line 22). After this step we have to
1442 check if the resulting digit is zero or not. If it is not then we set the \textbf{used} count to one, otherwise
1448 One important limitation of this function is that it will only set one digit. The size of a digit is not fixed, meaning source that uses
1478 next four bits from the source are extracted and are added to the mp\_int. The \textbf{used} digit count is
1479 incremented to reflect the addition. The \textbf{used} digit counter is incremented since if any of the leading digits were zero the mp\_int would have
1493 seem obvious as to why the digit counter does not grow exceedingly large it is because of the shift on line 28
1502 positions. If any leading digit of one integer is greater than a digit in the same position of another integer then obviously it must be greater.
1545 Obviously if the digit counts differ there would be an imaginary zero digit in the smaller number where the leading digit of the larger number is.
1546 If both have the same number of digits than the actual digits themselves must be compared starting at the leading digit.
1549 the zero'th digit. If after all of the digits have been compared, no difference is found, the algorithm returns \textbf{MP\_EQ}.
1621 established. The next logical set of algorithms to develop are addition, subtraction and digit shifting algorithms. These
1705 The first two steps will handle sorting the inputs such that $min$ and $max$ hold the digit counts of the two
1710 At this point the first addition loop will go through as many digit positions that both inputs have. The carry
1712 one digit of the summand. First
1714 in $\mu$ and finally the digit of the result $c_n$ is truncated within the range $0 \le c_n < \beta$.
1716 Now all of the digit positions that both inputs have in common have been exhausted. If $min \ne max$ then $x$ is an alias
1743 After line 94, $tmpc$ will point to the $c.used$'th digit of the mp\_int $c$. This is useful
1817 significant bit. Thus, the high order bits of the mp\_digit that are not part of the actual digit will either be all zero, or all one. All that
1920 to \textbf{MP\_ZPOS} when the \textbf{used} digit count reaches zero.
2014 In order to facilitate operations on polynomials in $x$ as above a series of simple ``digit'' algorithms have to be established. That is to shift
2021 operation to perform. A single precision logical shift left is sufficient to multiply a single digit by two.
2063 are the same there is no need to perform two reads from the digits of $a$. Step 6.1 performs a single precision shift on the current digit $a_n$ to
2064 obtain what will be the carry for the next iteration. Step 6.2 calculates the $n$'th digit of the result as single precision shift of $a_n$ plus
2068 Step 7 takes care of any final carry by setting the $a.used$'th digit of the result to the carry and augmenting the \textbf{used} count of $b$.
2116 core as the basis of the algorithm. Unlike mp\_mul\_2 the shift operations work from the leading digit to the trailing digit. The algorithm
2117 could be written to work from the trailing digit to the leading digit however, it would have to stop one short of $a.used - 1$ digits to prevent
2183 the digits of $a$ of length $b$. The head of the sliding window is at $i$ (\textit{the leading digit}) and the tail at $j$ (\textit{the trailing digit}).
2184 The loop on step 7 copies the digit from the tail to the head. In each iteration the window is moved down one digit. The last loop on
2206 for the leading digit while $bottom$ (line 45) is an alias for the trailing edge. The aliases form a
2211 Division by powers of $x$ is easily achieved by shifting the digits right and removing any that will end up to the right of the zero'th digit.
2250 is $b$ digits wide is used to copy the digits. Unlike mp\_lshd the window slides in the opposite direction from the trailing to the leading digit.
2270 shifts $k$ times to achieve a multiplication by $2^{\pm k}$ a mixture of whole digit shifting and partial digit shifting is employed.
2377 mp\_mul\_2d by first using whole digit shifts then single precision shifts. This algorithm will also produce the remainder of the division
2432 is copied to $b$, leading digits are removed and the remaining leading digit is trimed to the exact bit count.
2446 the number. First we zero any digits above the last digit in $2^b$ (line 42). Next we reduce the
2447 leading digit of both (line 46) and then mp\_clamp().
2491 For centuries general purpose multiplication has required a lengthly $O(n^2)$ process, whereby each digit of one multiplicand has to be multiplied
2492 against every digit of the other multiplicand. Traditional long-hand multiplication is based on this process; while the techniques can differ the
2502 algorithm that school children are taught. The algorithm is considered an $O(n^2)$ algorithm since for two $n$-digit inputs $n^2$ single precision
2503 multiplications are required. More specifically for a $m$ and $n$ digit input $m \cdot n$ single precision multiplications are required. To
2509 modification will become evident during the discussion of Barrett modular reduction. Recall that for a $n$ and $m$ digit input the product
2562 The first thing this algorithm checks for is whether a Comba multiplier can be used instead. If the minimum digit count of either
2591 count. That is in pass $ix$ of the inner loop the product is added starting at the $ix$'th digit of the reult.
2596 5.4.1 is propagated through the nested loop. If the carry was not propagated immediately it would overflow the single precision digit
2600 digit since that digit is assumed to be zero at this point. However, if $ix + pb \ge digs$ the carry is not set as it would make the result
2628 Each digit of the product is stored in turn (line 69) and the carry propagated (line 72) to the
2676 congruent to adding a leading zero digit.
2704 the carries. For example, in the multiplication of two three-digit numbers the third column of output will be the sum of
2706 an overflow can occur and the carry information will be lost. For any $m$ and $n$ digit inputs the maximum weight of any column is
2710 from earlier that a double precision type has $\alpha$ bits of resolution and a single precision digit has $lg(\beta)$ bits of precision. Given these
2723 Let $\rho = lg(\beta)$ represent the number of bits in a single precision digit. By further re-arrangement of the equation the final solution is
2797 $O \left ((p + q)n^2 \right )$ time to multiply two $n$-digit numbers. The Comba method requires only $O(pn^2 + qn)$ time, however in practice,
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.
2864 $O \left ( k^{lg_n(2n - 1)} \right )$ for $k$ digit inputs (\textit{assuming they have the same number of digits}). Figure~\ref{fig:exponent}
3002 The remaining steps 13 through 18 compute the Karatsuba polynomial through a variety of digit shifting and addition operations.
3128 The two inputs $a$ and $b$ are first split into three $k$-digit integers $a_0, a_1, a_2$ and $b_0, b_1, b_2$ respectively. From these smaller
3151 large numbers. For example, a 10,000 digit multiplication takes approximaly 99,282,205 fewer single precision multiplications with
3225 For any $n$-digit input, there are ${{\left (n^2 + n \right)}\over 2}$ possible unique single precision multiplications required compared to the $n^2$
3431 Consider squaring a 200 digit number with this technique. It will be split into two 100 digit halves which are subsequently squared.
3432 The 100 digit halves will not be squared using Karatsuba, but instead using the faster Comba based squaring algorithm. If Karatsuba multiplication
3433 were used instead, the 100 digit numbers would be squared with a slower Comba based multiplication.
3483 Now if $5n$ single precision additions and a squaring of $n$-digits is faster than multiplying two $n$-digit numbers and doubling then
3693 two $m$-digit numbers have been multiplied. Dividing $a$ by $b$ is the same as dividing a $2m$ digit integer by a $m$ digit integer. Digits below the
3694 $m - 1$'th digit of $a$ will contribute at most a value of $1$ to the quotient because $\beta^k < b$ for any $0 \le k \le m - 1$. Another way to
3736 The value of $\mu$ is a $m$-digit number and $q_0$ is a $m + 1$ digit number. Using a full multiplier $(m + 1)(m) = m^2 + m$ single precision
3737 multiplications would be required. Using a multiplier that will only produce digits at and above the $m - 1$'th digit reduces the number
3993 Instead of computing the reduction on a bit-by-bit basis it is actually much faster to compute it on digit-by-digit basis. Consider the
4014 The value $\mu n \beta^t$ is a multiple of the modulus $n$ meaning that it will not change the residue. If the first digit of
4015 the value $\mu n \beta^t$ equals the negative (modulo $\beta$) of the $t$'th digit of $x$ then the addition will result in a zero digit. This
4059 \textbf{Input}. mp\_int $x$, mp\_int $n$ and a digit $\rho \equiv -1/n_0 \mbox{ (mod }n\mbox{)}$. \\
4125 The multiplication $\mu n \beta^{ix}$ is performed in one step in the inner loop. The alias $tmpx$ refers to the $ix$'th digit of $x$ and
4136 carries from $0$ to $ix - 1$ must have been propagated upwards to form a valid $ix$'th digit. The solution as it turns out is very simple.
4137 Perform a Comba like multiplier and inside the outer loop just after the inner loop fix up the $ix + 1$'th digit by forwarding the carry.
4147 \textbf{Input}. mp\_int $x$, mp\_int $n$ and a digit $\rho \equiv -1/n_0 \mbox{ (mod }n\mbox{)}$. \\
4199 Also note that digit $\hat W_{ix}$ must have the carry from the $ix - 1$'th digit propagated upwards in order for this to work. That is what step
4223 digit, that is $\_ \hat W_{t} = \hat W_{n.used + t}$.
4384 Also with the choice of $n = \beta^p$ reducing $x$ modulo $n$ merely requires zeroing the digits above the $p-1$'th digit of $x$.
4391 Now that division and reduction (\textit{step 1 and 3 of figure~\ref{fig:DR}}) have been optimized to simple digit operations the multiplication by $k$
4393 as well be a single digit. The smaller the value of $k$ is the faster the algorithm will be.
4440 digit is set to the carry and the upper digits are zeroed. Steps 5 and 6 emulate the reduction modulo $\beta^m$ that should have happend to
4461 By line 67 the pointer $tmpx1$ points to the $m$'th digit of $x$ which is where the final carry will be placed. Similarly by line 74 the
4462 same pointer will point to the $m+1$'th digit where the zeroes will be placed.
4498 of restricted Diminished Radix form if all of the digits are equal to $\beta - 1$ except the trailing digit which may be any value.
4521 in the mp\_int. Step 2 tests all but the first digit to see if they are equal to $\beta - 1$. If the algorithm manages to get to
4607 is sufficient to solve for $k$. Alternatively if $n$ has more than one digit the value of $k$ is simply $\beta - n_0$.
4620 \item The number has only one digit.
4621 \item The number has more than one digit and every bit from the $\beta$'th to the most significant is one.
4625 one digit than it will always be of the correct form. Otherwise all of the bits above the first digit must be one. This arises from the fact
4626 that there will be value of $k$ that when added to the modulus causes a carry in the first digit which propagates all the way to the most
4784 The first algorithm in the series of exponentiation algorithms will be an unbounded algorithm where the exponent is a single digit. It is intended
4813 This algorithm computes the value of $a$ raised to the power of a single digit $b$. It uses the left to right exponentiation algorithm to
4840 the $i$'th $k$-bit digit of the exponent of $b$. For $k = 1$ the definitions are synonymous and for $k > 1$ algorithm~\ref{fig:KARY}
4962 exponent as $b \equiv \left ( 111, 101, 0, 110, 0, 100, 0 \right )_{2}$. The single digit $0$ in the second representation are where
5159 \item The variable $bitcnt$ indicates how many bits are left in the current digit of the exponent left to be read. When it reaches zero a new digit
5161 \item The variable $buf$ holds the currently read digit of the exponent.
5162 \item The variable $digidx$ is an index into the exponents digits. It starts at the leading digit $x.used - 1$ and moves towards the trailing digit.
5169 inside this loop is to extract a new digit if no more bits are available in the current digit. If there are no bits left a new digit is
5172 After a digit is made available step 12.3 will extract the most significant bit of the current digit and move all other bits in the digit
5173 upwards. In effect the digit is read from most significant bit to least significant bit and since the digits are read from leading to
5249 for the package. The subsequent section discusses a set of algorithms which allow a single digit to be the 2nd operand for a variety of operations.
5288 To find the first digit of the quotient the value of $k$ must be maximized such that $kx\beta^t$ is less than or equal to $y$ and
5289 simultaneously $(k + 1)x\beta^t$ is greater than $y$. Implicitly $k$ is the maximum value the $t$'th digit of the quotient may have. The habitual method
5295 Again this process is repeated to produce the quotient digit $k = 3$ which makes the quotient $q = 200 + 3\beta = 230$ and the remainder
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
5345 For the purposes of division a normalized input is when the divisors leading digit $x_n$ is greater than or equal to $\beta / 2$. By multiplying both
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$.
5354 At most the quotient approaches $2\beta$, however, in practice this will not occur since that would imply the previous quotient digit was too small.
5380 Normalize the inputs such that the leading digit of $y$ is greater than or equal to $\beta / 2$. \\
5384 Find the leading digit of the quotient. \\
5457 positive. Now the two values $x$ and $y$ must be normalized such that the leading digit of $y$ is greater than or equal to $\beta / 2$.
5461 $2\beta - {2 \over \beta}$ which means that a digit of the quotient must be first produced by another means. In this case $y$ is shifted
5463 shifted copy of $y$ until $x$ is smaller. Since the leading digit of $y$ is greater than or equal to $\beta/2$ this loop will iterate at most two
5464 times to produce the desired leading digit of the quotient.
5467 accurately approximate the true quotient digit. The estimation can in theory produce an estimation as high as $2\beta - {2 \over \beta}$ but by
5468 induction the upper quotient digit is correct (\textit{as established on step eleven}) and the estimate must be less than $\beta$.
5472 order approximation to adjust the quotient digit.
5474 After both phases of estimation the quotient digit may still be off by a value of one\footnote{This is similar to the error introduced
5503 The number of bits in the leading digit is calculated on line 151. Implictly an mp\_int with $r$ digits will require $lg(\beta)(r-1) + k$ bits
5504 of precision which when reduced modulo $lg(\beta)$ produces the value of $k$. In this case $k$ is the number of bits in the leading digit which is
5508 Throughout the variables $n$ and $t$ will represent the highest digit of $x$ and $y$ respectively. These are first used to produce the
5509 leading digit of the quotient. The loop beginning on line 184 will produce the remainder of the quotient digits.
5520 This section briefly describes a series of single digit helper algorithms which come in handy when working with small constants. All of
5521 the helper functions assume the single digit input is positive and will treat them as such.
5547 This algorithm initiates a temporary mp\_int with the value of the single digit and uses algorithm mp\_add to add the two values together.
5559 The single digit subtraction algorithm mp\_sub\_d is essentially the same except it uses mp\_sub to subtract the digit from the mp\_int.
5562 Single digit multiplication arises enough in division and radix conversion that it ought to be implement as a special case of the baseline
5564 only has one digit.
5596 This algorithm quickly multiplies an mp\_int by a small single digit value. It is specially tailored to the job and has a minimal of overhead.
5606 In this implementation the destination $c$ may point to the same mp\_int as the source $a$ since the result is written after the digit is
5610 Like the single digit multiplication algorithm, single digit division is also a fairly common algorithm used in radix conversion. Since the
5611 divisor is only a single digit a specialized variant of the division algorithm can be used to compute the quotient.
5647 algorithm another digit of the dividend is reduced and another digit of quotient produced. Provided $b < \beta$ the value of $\hat w$
5662 indicate the respective value is not required. This allows a trivial single digit modular reduction algorithm, mp\_mod\_d to be created.
5751 3. Pick a non-zero random digit $d$. \\
5755 \hspace{3mm}5.2 Pick a random digit $d$. \\
5765 This algorithm produces a pseudo-random integer of $b$ digits. By ensuring that the first digit is non-zero the algorithm also guarantees that the