Patent ID: 6748590
Filing Date: 2004-06-08
Classification: G06F

Abstract:
A computer-implemented method for multiplication by an integer comprising the steps of:(a) recursively finding the factors of the integer using a power of 2, a power of 2 plus 1 and a power of 2 minus 1; (b) recursively finding one of the factors of the integer (or the factors found in (a)) plus and minus 1; using a power of 2, a power of 2 plus 1; and a power of 2 minus 1; (c) adding to and subtracting from the integer all powers of 2 less than the integer; (d) finding the factors of each resulting sum and difference of (c) using the power of 2 used in calculating the sum and difference of (c) plus and minus 1; (e) constructing one or more instruction sequences based upon the factors found in (a) and (b), and upon the factors found in (d) if a resulting sum or difference factored evenly in (d) and the resulting factor is a power of 2; (f) finding the lowest cost instruction sequence from the one or more instruction sequences; and (g) executing the lowest cost instruction sequence to effect the multiplication by the integer.