Efficient multiplication sequence for large integer operands wider than the multiplier hardware

Abstract

A method of operating a multiplication circuit to perform multiply-accumulate operations on multi-word operands is characterized by an operations sequencer that is programmed to direct the transfer of operand segments between RAM and internal data registers in a specified sequence. The sequence processes groups of two adjacent result word-weights (columns), with the multiply cycles within a group proceeding in a zigzag fashion by alternating columns with steadily increasing or decreasing operand segment weights. In multiplier embodiments having additional internal cache registers, these store frequently used operand segments so they aren't reloaded from memory multiple times. In this case, the sequence within a group need not proceed in a strict zigzag fashion, but can jump to a multiply operation involve at least one operand segment stored in a cache.