Lines Matching refs:digits
171 reason that $7$ times $6$ is $42$. However, $42$ has two digits of precision as opposed to one digit we started with.
285 A multiple precision integer of $n$-digits shall be denoted as $x = (x_{n-1}, \ldots, x_1, x_0)_{ \beta }$ and represent
286 the integer $x \equiv \sum_{i=0}^{n-1} x_i\beta^i$. The elements of the array $x$ are said to be the radix $\beta$ digits
291 The term ``mp\_int'' shall refer to a composite structure which contains the digits of the integer it represents, as well
344 The norm of a multiple precision integer, for example $\vert \vert x \vert \vert$, will be used to represent the number of digits in the representation
567 As a well known analogy, school children are taught how to form numbers larger than nine by prepending more radix ten digits. In the decimal system
568 the largest single digit value is $9$. However, by concatenating digits together larger numbers may be represented. Newly prepended digits
576 that is the sign of this particular integer is positive as opposed to negative. Second, the integer has three digits in
578 arithmetic. The third property is how many digits placeholders are available to hold the integer.
582 Similarly, computer algorithms must maintain strict control over memory usage to ensure that the digits of an integer
615 \item The \textbf{used} parameter denotes how many digits of the array \textbf{dp} contain the digits used to represent
619 many digits are available in the array to use by functions before it has to increase in size. When the \textbf{used} count
623 \item The pointer \textbf{dp} points to a dynamically allocated array of digits that represent the given multiple
624 precision integer. It is padded with $(\textbf{alloc} - \textbf{used})$ zero digits. The array is maintained in a least
625 significant digit order. As a pencil and paper analogy the array is organized such that the right most digits are stored
640 array of digits.
643 leading zero digits in the most significant positions must be trimmed.
723 Given the basic mp\_int structure an initialization routine must first allocate memory to hold the digits of
724 the integer. Often it is optimal to allocate a sufficiently large pre-set number of digits even though
726 would occur when operations are performed on the integers. There is a tradeoff between how many default digits to allocate
727 and how many re-allocations are tolerable. Obviously allocating an excessive amount of digits initially will waste
730 If the memory for the digits has been successfully allocated then the rest of the members of the structure must
731 be initialized. Since the initial state of an mp\_int is to represent the zero integer, the allocated digits must be set
746 1. Allocate memory for \textbf{MP\_PREC} digits. \\
766 the digits is allocated. If this fails the function returns before setting any of the other members. The \textbf{MP\_PREC}
771 Allocating a block of digits at first instead of a single digit has the benefit of lowering the number of usually slow
775 Once the allocation has been made the digits have to be set to zero as well as the \textbf{used}, \textbf{sign} and
804 In order to assure the mp\_int is in a known state the digits must be set to zero. On most platforms this could have been
815 When an mp\_int is no longer required by the application, the memory that has been allocated for its digits must be
828 3. Free the memory allocated for the digits of $a$. \\
840 This algorithm accomplishes two goals. First, it clears the digits and the other mp\_int members. This ensures that
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()
863 the digits are assigned zero instead of using block memory operations (such as memset()) since this is more portable.
865 The digits are deallocated off the heap via the XFREE macro. Similar to XMALLOC the XFREE macro actually evaluates to
869 Now that the digits have been cleared and deallocated the other members are set to their final values (lines 36 and 37).
882 When storing a value in an mp\_int structure, a sufficient number of digits must be available to accomodate the entire
892 \textbf{Output}. $a$ is expanded to accomodate $b$ digits. \\
897 4. Re-allocate the array of digits $a$ to size $v$ \\
916 It is assumed that the reallocation (step four) leaves the lower $a.alloc$ digits of the mp\_int intact. This is much
917 akin to how the \textit{realloc} function from the standard C library works. Since the newly allocated digits are
934 function leaves the base of the allocation intact which means the first \textbf{alloc} digits of the mp\_int are the same as before
935 the re-allocation. All that is left is to clear the newly allocated digits and return.
942 Occasionally the number of digits required will be known in advance of an initialization, based on, for example, the size
944 will allocate \textit{at least} a specified number of digits.
951 \textbf{Input}. An mp\_int $a$ and the requested number of digits $b$. \\
952 \textbf{Output}. $a$ is initialized to hold at least $b$ digits. \\
956 3. Allocate $v$ digits. \\
972 digits allocated can be controlled by the second input argument $b$. The input size is padded upwards so it is a
973 multiple of \textbf{MP\_PREC} plus an additional \textbf{MP\_PREC} digits. This padding is used to prevent trivial
987 The number of digits $b$ requested is padded (line 24) by first augmenting it to the next multiple of
992 The digits are allocated and set to zero at the same time with the calloc() function (line @25,XCALLOC@). The
1046 When a function anticipates a result will be $n$ digits it is simpler to assume this is true within the body of
1048 $j$ digit produces a result of at most $i + j$ digits. It is entirely possible that the result is $i + j - 1$
1050 (\textit{via mp\_grow}) to accomodate $i + j - 1$ digits than further expanded to accomodate the final carry.
1058 will not contribute to the precision of the result. In fact, through subsequent operations more leading zero digits would
1072 \textbf{Output}. Any excess leading zero digits of $a$ are removed \\
1087 when all of the digits are zero to ensure that the mp\_int is valid at all times.
1147 1. If $b.alloc < a.used$ then grow $b$ to $a.used$ digits. (\textit{mp\_grow}) \\
1166 If $b$ does not have enough room for the digits of $a$ it must first have its precision augmented via the mp\_grow
1167 algorithm. The digits of $a$ are copied over the digits of $b$ and any excess digits of $b$ are set to zero (step two
1187 copying digits (line 25).
1189 The mp\_int $b$ must have enough digits to accomodate the used digits of the mp\_int $a$. If $b.alloc$ is less than
1191 simplify the inner loop that copies the digits from $a$ to $b$, two aliases $tmpa$ and $tmpb$ point directly at the digits
1192 of the mp\_ints $a$ and $b$ respectively. These aliases (lines 43 and 46) allow the compiler to access the digits without first dereferencing the
1193 mp\_int pointers and then subsequently the pointer to the digits.
1195 After the aliases are established the digits from $a$ are copied into $b$ (lines 49 to 51) and then the excess
1196 digits of $b$ are set to zero (lines 54 to 56). Both ``for'' loops make use of the pointer aliases and in
1197 fact the alias for $b$ is carried through into the second ``for'' loop to clear the excess digits. This optimization
1221 array of digits within an mp\_int structure directly. It may seem that a pointer alias is strictly not required
1234 /* copy all the digits */
1322 After the function is completed, all of the digits are zeroed, the \textbf{used} count is zeroed and the
1389 This algorithm computes the negation of an input. First it copies $a$ over $b$. If $a$ has no used digits then
1391 $a$ had no digits then it must be positive by definition. Had step three been omitted then the algorithm would return
1468 3. Clamp excess used digits (\textit{mp\_clamp}) \\
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
1480 zero digits used and the newly added four bits would be ignored.
1482 Excess zero digits are trimmed in steps 2.1 and 3 by using higher level algorithms mp\_mul2d and mp\_clamp.
1492 addition on line 39 ensures that the newly added in bits are added to the number of digits. While it may not
1494 as well as the call to mp\_clamp() on line 41. Both functions will clamp excess leading digits which keeps
1495 the number of used digits low.
1500 to compare $1,234$ to $1,264$ the digits are extracted by their positions. That is we compare $1 \cdot 10^3 + 2 \cdot 10^2 + 3 \cdot 10^1 + 4 \cdot 10^0$
1501 to $1 \cdot 10^3 + 2 \cdot 10^2 + 6 \cdot 10^1 + 4 \cdot 10^0$ by comparing single digits at a time starting with the highest magnitude
1504 The first comparision routine that will be developed is the unsigned magnitude compare which will perform a comparison based on the digits of two
1544 \textbf{MP\_GT} and similar with respect to when $a = b$ and $a < b$. The first two steps compare the number of digits used in both $a$ and $b$.
1546 If both have the same number of digits than the actual digits themselves must be compared starting at the leading digit.
1548 By step three both inputs must have the same number of digits so its safe to start from either $a.used - 1$ or $b.used - 1$ and count down to
1549 the zero'th digit. If after all of the digits have been compared, no difference is found, the algorithm returns \textbf{MP\_EQ}.
1558 The two if statements (lines 25 and 29) compare the number of digits in the two inputs. These two are
1559 performed before all of the digits are compared since it is a very cheap test to perform and can potentially save
1561 smaller than $a.used$, meaning that undefined values will be read from $b$ past the end of the array of digits.
1590 comparison code. When the signs are equal the digits of the inputs must be compared to determine the correct result. In step
1610 $\left [ 3 \right ]$ & Give the probability that algorithm mp\_cmp\_mag will have to compare $k$ digits \\
1611 & of two random digits (of equal magnitude) before a difference is found. \\
1632 One significant difference between a logical shift and the way decimals are shifted is that digits below the zero'th position are removed
1650 trailing digits first and propagate the resulting carry upwards. Since this is a lower level algorithm the name will have a ``s\_'' prefix.
1670 3. If $c.alloc < max + 1$ then grow $c$ to hold at least $max + 1$ digits (\textit{mp\_grow}) \\
1687 11. Clamp excess digits in $c$. (\textit{mp\_clamp}) \\
1703 destination. Then it will apply a simpler addition loop to excess digits of the larger input.
1707 same number of digits. After the inputs are sorted the destination $c$ is grown as required to accomodate the sum
1713 two digits from $a$ and $b$ are added together along with the carry $\mu$. The carry of this step is extracted and stored
1717 for one of the inputs that has more digits. A simplified addition loop is then used to essentially copy the remaining digits
1720 The final carry is stored in $c_{max}$ and digits above $max$ upto $oldused$ are zeroed which completes the addition.
1736 compiler does not have to dereference $a$, $b$ or $c$ (respectively) to access the digits of the respective mp\_int.
1739 compatibility within the implementation. The initial addition (line 66 to 75) adds digits from
1740 both inputs until the smallest input runs out of digits. Similarly the conditional addition loop
1741 (line 81 to 90) adds the remaining digits from the larger of the two inputs. The addition is finished
1744 for the next loop (line 97 to 99) which set any old upper digits to zero.
1771 3. If $c.alloc < max$ then grow $c$ to hold at least $max$ digits. (\textit{mp\_grow}) \\
1787 10. Clamp excess digits of $c$. (\textit{mp\_clamp}). \\
1804 most $max$ digits in length as opposed to $max + 1$. Similar to the addition algorithm the \textbf{used} count of $c$ is copied locally and
1822 10 will ensure that any leading digits of $c$ above the $max$'th position are zeroed.
1837 The first subtraction loop (lines 47 through 61) subtract digits from both inputs until the smaller of
1854 Recall from section 5.2 that an mp\_int represents an integer with an unsigned mantissa (\textit{the array of digits}) and a \textbf{sign}
1919 s\_mp\_add and s\_mp\_sub that the mp\_clamp function is used at the end to trim excess digits. The mp\_clamp algorithm will set the \textbf{sign}
2015 the digits left or right as well to shift individual bits of the digits left and right. It is important to note that not all ``shift'' operations
2016 are on radix-$\beta$ digits.
2031 1. If $b.alloc < a.used + 1$ then grow $b$ to hold $a.used + 1$ digits. (\textit{mp\_grow}) \\
2059 Step 1 and 2 grow the input as required to accomodate the maximum number of \textbf{used} digits in the result. The initial \textbf{used} count
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
2069 Step 8 clears any leading digits of $b$ in case it originally had a larger magnitude than $a$.
2092 1. If $b.alloc < a.used$ then grow $b$ to hold $a.used$ digits. (\textit{mp\_grow}) \\
2105 9. Clamp excess digits of $b$. (\textit{mp\_clamp}) \\
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
2118 reading past the end of the array of digits.
2132 the polynomial basis \cite[pp. 48]{ROSE}. Given such a notation a multiplication or division by $x$ amounts to shifting whole digits a single
2136 Converting from an array of digits to polynomial basis is very simple. Consider the integer $y \equiv (a_2, a_1, a_0)_{\beta}$ and recall that
2155 2. If $a.alloc < a.used + b$ then grow $a$ to at least $a.used + b$ digits. (\textit{mp\_grow}). \\
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}).
2185 step 8 sets the lower $b$ digits to zero.
2207 window of exactly $b$ digits over the input.
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.
2251 Also the digits are copied from the leading to the trailing edge.
2253 Once the window copy is complete the upper digits must be zeroed and the \textbf{used} count decremented.
2264 the upper digits of the input to make sure the result is correct.
2268 Now that algorithms for moving single bits as well as whole digits exist algorithms for moving the ``in between'' distances are required. For
2315 After the digits have been shifted appropriately at most $lg(\beta) - 1$ shifts are left to perform. Step 5 calculates the number of remaining shifts
2320 This algorithm is loosely measured as a $O(2n)$ algorithm which means that if the input is $n$-digits that it takes $2n$ ``time'' to
2366 7. Clamp excess digits of $c$. (\textit{mp\_clamp}) \\
2420 8. Clamp excess digits of $c$. (\textit{mp\_clamp}) \\
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
2504 simplify most discussions, it will be assumed that the inputs have comparable number of digits.
2508 facet of this algorithm, is that it has been modified to only produce a certain amount of output digits as resolution. The importance of this
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.
2544 6. Clamp excess digits of $t$. \\
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
2567 All of step 5 is the infamous $O(n^2)$ multiplication loop slightly modified to only produce upto $digs$ digits of output. The $pb$ variable
2568 is given the count of digits to read from $b$ inside the nested loop. If $pb \le 1$ then no more output digits can be produced and the algorithm
2611 sing the Comba routine are that min$(a.used, b.used) < \delta$ and the number of digits of output is less than
2620 digits as output. In each iteration of the outer loop the $pb$ variable is set (line 49) to the maximum
2705 three single precision multiplications. If the precision of the accumulator for the output digits is less then $3 \cdot (\beta - 1)^2$ then
2731 the smaller input may not have more than $256$ digits if the Comba method is to be used. This is quite satisfactory for most applications since
2732 $256$ digits would allow for numbers in the range of $0 \le x < 2^{7168}$ which, is much larger than most public key cryptographic algorithms require.
2742 Place an array of \textbf{MP\_WARRAY} single precision digits named $W$ on the stack. \\
2743 1. If $c.alloc < digs$ then grow $c$ to $digs$ digits. (\textit{mp\_grow}) \\
2776 This algorithm performs the unsigned multiplication of $a$ and $b$ using the Comba method limited to $digs$ digits of precision.
2782 The $ty$ variable is set to the minimum count of $ix$ or the number of digits in $b$. That way if $a$ has more digits than
2786 The variable $iy$ is the minimum digits we can read from either $a$ or $b$ before running out. Computing one column at a time
2808 As per the pseudo--code we first calculate $pa$ (line 48) as the number of digits to output. Next we begin the outer loop
2863 multiplicands that have $n$ times fewer digits than the inputs. The asymptotic running time of this algorithm is
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}
2895 Let $m$ represent the number of digits in the multiplicands (\textit{assume both multiplicands have the same number of digits}). There exists a
2942 of this system of equations has made Karatsuba fairly popular. In fact the cutoff point is often fairly low\footnote{With LibTomMath 0.18 it is 70 and 109 digits for the Intel P4 and AMD Athlon respectively.}
3019 number of digits for the next section of code.
3264 1. Init a temporary mp\_int of at least $2 \cdot a.used +1$ digits. (\textit{mp\_init\_size}) \\
3283 5. Clamp excess digits of $t$. (\textit{mp\_clamp}) \\
3349 1. If $b.alloc < 2a.used + 1$ then grow $b$ to $2a.used + 1$ digits. (\textit{mp\_grow}). \\
3374 10. Clamp excess digits from $b$. (\textit{mp\_clamp}) \\
3385 s\_mp\_sqr when the number of input digits is less than \textbf{MP\_WARRAY} and less than $\delta \over 2$.
3390 addition MIN condition on $iy$ (step 5.5) to prevent overlapping digits. For example, $a_3 \cdot a_5$ is equal
3429 point is fairly high. For example, on an AMD Athlon XP processor with $\beta = 2^{28}$, the cutoff point is around 127 digits.
3478 The radix point for squaring is simply placed exactly in the middle of the digits when the input has an odd number of digits, otherwise it is
3483 Now if $5n$ single precision additions and a squaring of $n$-digits is faster than multiplying two $n$-digit numbers and doubling then
3520 is exactly at the point where Comba squaring can no longer be used (\textit{128 digits}). On slower processors such as the Intel P4
3521 it is actually below the Comba limit (\textit{at 110 digits}).
3562 \textbf{TOOM\_SQR\_CUTOFF} or \textbf{KARATSUBA\_SQR\_CUTOFF} digits then either the Toom-Cook or the Karatsuba Squaring algorithm is used. If
3575 & that have different number of digits in Karatsuba multiplication. \\
3677 Let $n$ represent the number of digits in $b$. This algorithm requires approximately $2n^2$ single precision multiplications to produce the quotient and
3692 the number of digits in $b$. For the purposes of this discussion we will assume that the number of digits in $a$ is $2m$, which is generally true if
3699 Since the digits of $a'$ do not contribute much to the quotient the observation is that they might as well be zero. However, if the digits
3701 with the irrelevant digits trimmed. Now the modular reduction is trimmed to the almost equivalent equation
3711 by as much as one (\textit{provided the radix point is chosen suitably}) and now that the lower irrelevent digits have been trimmed the quotient
3720 For example, let $\beta = 10$ represent the radix of the digits. Let $b = 9999$ represent the modulus which implies $m = 4$. Let $a = 99929878$
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.
3737 multiplications would be required. Using a multiplier that will only produce digits at and above the $m - 1$'th digit reduces the number
3742 multiple of the modulus, that is $0 \le a - b \cdot \lfloor (q_0 \cdot \mu) / \beta^{m+1} \rfloor < 3b$. If $b$ is $m$ digits than the
3743 result of reduction equation is a value of at most $m + 1$ digits (\textit{provided $3 < \beta$}) implying that the upper $m - 1$ digits are
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
3749 only the lower $m+1$ digits requires ${m^2 + 3m - 2} \over 2$ single precision multiplications.
3763 Let $m$ represent the number of digits in $b$. \\
3768 3. $q \leftarrow q \cdot \mu$ (\textit{note: only produce digits at or above $m-1$}) \\
3805 Recall that the multiplication for the quotient on step 3 must only produce digits at or above the $m-1$'th position. An algorithm called
3808 of digits in $b$ is very much smaller than $\beta$.
3811 $a \ge b \cdot \lfloor (q_0 \cdot \mu) / \beta^{m+1} \rfloor$ only the lower $m+1$ digits are being used to compute the residue, so an implied
3812 ``borrow'' from the higher digits might leave a negative result. After the multiple of the modulus has been subtracted from $a$ the residue must be
3825 The first multiplication that determines the quotient can be performed by only producing the digits from $m - 1$ and up. This essentially halves
3826 the number of single precision multiplications required. However, the optimization is only safe if $\beta$ is much larger than the number of digits
4068 3. If $x.alloc < digs$ then grow $x$ to $digs$ digits. \\
4071 Eliminate the lower $k$ digits. \\
4108 calculates $x + \mu n \beta^{ix}$ by multiplying $\mu n$ and adding the result to $x$ shifted by $ix$ digits. Both the addition and
4152 1. if $x.alloc < n.used + 1$ then grow $x$ to $n.used + 1$ digits. \\
4153 Copy the digits of $x$ into the array $\hat W$ \\
4158 Elimiate the lower $k$ digits. \\
4170 Zero excess digits and fixup $x$. \\
4175 9. Clamp excessive digits of $x$. \\
4189 on the input as the baseline reduction algorithm. An additional two restrictions are imposed on this algorithm. The number of digits $k$ in the
4194 contents of $x$ with the excess digits zeroed. The reduction loop is very similar the to the baseline loop at heart. The multiplication on step
4214 The $\hat W$ array is first filled with digits of $x$ on line 48 then the rest of the digits are zeroed on line 55. Both loops share
4383 performed by moving whole digits to the right $p$ places. In practice division by $\beta^p$ is much faster than division by $2^p$ for any $p$.
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$.
4412 2. If $x.alloc < 2m$ then grow $x$ to $2m$ digits. \\
4421 7. Clamp excess digits of $x$. \\
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
4453 The first step is to grow $x$ as required to $2m$ digits since the reduction is performed in place on $x$. The label on line 52 is where
4457 The aliases $tmpx1$ and $tmpx2$ refer to the digits of $x$ where the latter is offset by $m$ digits. By reading digits from $x$ offset by $m$ digits
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.
4520 This algorithm determines if a value is in Diminished Radix form. Step 1 rejects obvious cases where fewer than two digits are
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.
5168 All of step 12 is the window processing loop. It will iterate while there are digits available form the exponent to read. The first step
5170 read and if there are no digits left than the loop terminates.
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
5188 By step 13 there are no more digits left in the exponent. However, there may be partial bits in the window left. If $mode = 2$ then
5290 used to find the maximum is to ``eyeball'' the two numbers, typically only the leading digits and quickly estimate a quotient. By only using leading
5291 digits a much simpler division may be used to form an educated guess at what the value must be. In this case $k = \lfloor 54/23\rfloor = 2$ quickly
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
5304 speaking the estimation is based on assuming the lower $\vert \vert y \vert \vert - p$ and $\vert \vert x \vert \vert - p$ lower digits of the
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.
5371 Setup the quotient to receive the digits. \\
5372 3. Grow $q$ to $a.used + 2$ digits. \\
5408 Now find the remainder fo the digits. \\
5437 14. Clamp excess digits of $q$ \\
5455 After the first two trivial cases of inputs are handled the variable $q$ is setup to receive the digits of the quotient. Two unsigned copies of the
5460 At this point the division algorithm can begin producing digits of the quotient. Recall that maximum value of the estimation used is
5462 to the left (\textit{step ten}) so that it has the same number of digits as $x$. The loop on step eleven will subtract multiples of the
5466 Now the remainder of the digits can be produced. The equation $\hat q = \lfloor {{x_i \beta + x_{i-1}}\over y_t} \rfloor$ is used to fairly
5480 is that when the estimations are being made (\textit{inside the loop on step 13.5}) that the digits $y_{t-1}$, $x_{i-2}$ and $x_{i-1}$ may lie
5481 outside their respective boundaries. For example, if $t = 0$ or $i \le 1$ then the digits would be undefined. In those cases the digits should
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
5509 leading digit of the quotient. The loop beginning on line 184 will produce the remainder of the quotient digits.
5512 algorithm eliminates multiple non-zero digits in a single iteration. This ensures that $x_i$ is always non-zero since by definition the digits
5515 Lines 214, 216 and 223 through 225 manually construct the high accuracy estimations by setting the digits of the two mp\_int
5575 2. Grow $c$ to at least $pa + 1$ digits. \\
5587 10. Clamp excess digits of $c$. \\
5607 read from the source. This function uses pointer aliases $tmpa$ and $tmpc$ for the digits of $a$ and $c$ respectively.
5623 3. Init $q$ to $a.used$ digits. \\
5636 9. Clamp excess digits of $q$. \\
5747 \textbf{Output}. A pseudo-random number of $b$ digits \\
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
5766 final result has at least $b$ digits. It relies heavily on a third-part random number generator which should ideally generate uniformly all of
5882 \hspace{3mm}7.1 Reverse the digits $str_1, str_2, \ldots str_n$. \\
5884 \hspace{3mm}8.1 Reverse the digits $str_0, str_1, \ldots str_n$. \\
5893 This algorithm computes the radix-$r$ representation of an mp\_int $a$. The ``digits'' of the representation are extracted by reducing
5896 are required instead of a series of $n \times k$ divisions. One design flaw of this approach is that the digits are produced in the reverse order
5897 (see~\ref{fig:mpradix}). To remedy this flaw the digits must be swapped or simply ``reversed''.