Patent ID: 7930337

Claim:
A computer program, disposed on a computer readable storage medium, comprising instructions for causing circuitry to multiply two numbers, the program to: segment A into multiple segments, a x , and an additional set, a h , wherein A is a binary representation of one of the two numbers and A comprises n bits corresponding to the multiple segments a x and at least one most significant bit corresponding to the additional set a h , and wherein a h comprises the at least one most significant bit of A; segment B into multiple segments, b x , and an additional set, b h , wherein B is a binary representation of the other of the two numbers and B comprises n bits corresponding to the multiple segments b x and at least one most significant bit corresponding to the additional set b h , and wherein b h comprises the at least one most significant bit of B, wherein x represents an ordinal of each segment, h represents a most significant bit position of each additional set and n is greater than a native word size of the computer; perform Karatsuba multiplication of the segments, a x , A and, the segments, b x , of B to generate a result; and adjust the result of the Karatsuba multiplication if a value of at least one of a h and b h is not zero to obtain a multiplication result of the two numbers.