base is typically 2 for microelectronic applications, 28 for 8-bit firmware, or 232 or 264 for software applications. The REDC algorithm requires products modulo , and typically so that REDC can be used to compute products. However, when is a power of , there is a variant of REDC which requires products only of machine word sized integers. Suppose that positive multi-precision integers are stored little endian, that is, is stored as an array such that for all and . The algorithm begins with a multiprecision integer and reduces it one word at a time. First an appropriate multiple of is added to make divisible by . Then a multiple of is added to make divisible by , and so on. Eventually is divisible by , and after division by the algorithm is in the same place as REDC was after the computation of . function MultiPrecisionREDC is Input: Integer N with , stored as an array of p words, Integer , --thus, r = logB R Integer N′ in such that , Integer T in the range , stored as an array of words. Output: Integer S in such that , stored as an array of p words. Set (extra carry word) for do --loop1- Make T divisible by c ← 0 m ← for do --loop2- Add the low word of and the carry from earlier, and find the new carry x ← T[i + j] ← c ← end for for do --loop3- Continue carrying x ← T[i + j] ← c ← end for end for for do S[i] ← T[i + r] end for if then return else return end if end function The final comparison and subtraction is done by the standard algorithms. The above algorithm is correct for essentially the same reasons that REDC is correct. Each time through the loop, is chosen so that is divisible by . Then is added to . Because this quantity is zero mod , adding it does not affect the value of . If denotes the value of computed in the th iteration of the loop, then the algorithm sets to . Because MultiPrecisionREDC and REDC produce the same output, this sum is the same as the choice of that the REDC algorithm would make. The last word of , (and consequently ), is used only to hold a carry, as the initial reduction result is