Dynamic algorithm selection

Patent metadata

Field	Value
Publication number	US-12578925-B2
Application number	US-202217680436-A
Country	US
Kind code	B2
Filing date	Feb 25, 2022
Priority date	Feb 25, 2022
Publication date	Mar 17, 2026
Grant date	Mar 17, 2026

Abstract

Dynamic selection of a multiplication algorithm by receiving operands A and B, determining a difference between A and B, selecting a first multiplication algorithm if the difference falls below a threshold, selecting a second multiplication algorithm if the difference equals or exceeds the threshold, pre-scaling the operands, calculating a quotient for the scaled operands, back multiplying the quotient using the selected algorithm, yielding a product, subtracting the product from operand A, yielding a remainder, and providing the remainder as an output.

First claim

What is claimed is:

1 . A computer implemented method for dynamic selection of a multiplication algorithm comprising:
receiving, by one or more computer processors, operands A and B; determining, by the one or more computer processors, a difference between A and B; selecting, by the one or more computer processors, a digit wise multiplication algorithm if the difference falls below a threshold; selecting, by the one or more computer processors, a multi-digit multiplication algorithm if the difference equals or exceeds the threshold; determining a product, by the one or more computer processors using the selected algorithm, of B and a quotient of A divided by B; determining, by the one or more computer processors, a second difference between the product from A; and providing, by the one or more computer processors, the second difference as an output.

2 . The computer implemented method according to claim 1 , wherein determining the difference between A and B comprises:
determining, by the one or more computer processors, a difference between a number of leading zeros for B minus a number of leading zeros for A.

3 . The computer implemented method according to claim 1 , wherein the threshold is four.

4 . The computer implemented method according to claim 1 , wherein the digit wise multiplication algorithm comprises digit wise multiplication and continuous summing of partial products.

5 . A computer program product for dynamic selection of a multiplication algorithm, the computer program product comprising one or more computer readable storage devices and collectively stored program instructions on the one or more computer readable storage devices, that when executed cause a processor to:
receive operands A and B; determine a difference between A and B; estimate a number of quotient digits according to the difference between A and B; select a digit wise multiplication algorithm if the difference falls below a threshold; select a multi-digit multiplication algorithm if the difference equals or exceeds the threshold; determine a product using the selected algorithm, of B and a quotient of A divided by B; determine a second difference between A and the product; and providing the second difference as an output.

6 . The computer program product according to claim 5 , wherein determining the difference between A and B comprises:
determining a difference between a number of leading zeros for B minus a number of leading zeros for A.

7 . The computer program product according to claim 5 , wherein the threshold is four.

8 . The computer program product according to claim 5 , wherein the digit wise multiplication algorithm comprises digit wise multiplication and continuous summing of partial products.

9 . A computer system for dynamic selection of a multiplication algorithm, the computer system comprising:
one or more computer processors; one or more computer readable storage devices; and stored program instructions on the one or more computer readable storage devices, which when executed cause the one or more computer processors to:
receive operands A and B;
determine a difference between A and B;
estimate a number of quotient digits according to the difference between A and B;
select a digit wise multiplication algorithm if the difference falls below a threshold;
select a multi-digit multiplication algorithm if the difference equals or exceeds the threshold;
determine a product using the selected algorithm, of B and a quotient of A divided by B;
determine a second difference between A and the product; and
providing the second difference as an output.

10 . The computer system according to claim 9 , wherein determining the difference between A and B comprises:
determining a difference between a number of leading zeros for B minus a number of leading zeros for A.

11 . The computer system according to claim 9 , wherein the threshold is four.

12 . The computer system according to claim 9 , wherein the digit wise multiplication algorithm comprises digit wise multiplication and continuous summing of partial products.

13 . A computer implemented method for dynamic selection of a multiplication algorithm comprising:
receiving operands A and B; determining a difference between A and B; estimating a number of quotient digits according to the difference between A and B; selecting a digit wise multiplication algorithm if the estimated number of quotient digits falls below a threshold; selecting a multi-digit multiplication algorithm if the estimated number of quotient digits equals or exceeds the threshold; determining a product, by the one or more computer processors using the selected algorithm, of B and a quotient of A divided by B; determining, by the one or more computer processors, a second difference between the product from A; and providing, by the one or more computer processors, the second difference as an output.

14 . The computer implemented method according to claim 13 , wherein determining the difference between A and B comprises:
determining a difference between a number of leading zeros for B minus a number of leading zeros for A.

15 . The computer implemented method according to claim 13 , wherein the digit wise multiplication algorithm comprises digit wise multiplication and continuous summing of partial products.

16 . A computer implemented method for dynamic selection of a multiplication algorithm comprising:
receiving operands A and B; determining a difference between A and B; selecting a digit wise multiplication algorithm if the difference falls below a threshold; selecting a multi-digit multiplication algorithm if the difference equals or exceeds the threshold;. pre-scaling the operands; calculating a quotient for the operands; back multiplying the quotient and operand B, using the selected algorithm, yielding a product; subtracting the product from operand A, yielding a remainder; and providing the remainder as an output.

17 . The computer implemented method according to claim 16 , wherein determining the difference between A and B comprises:
determining a difference between a number of leading zeros for B minus a number of leading zeros for A.

18 . The computer implemented method according to claim 16 , wherein the threshold is four.

Assignees

• IBM

Inventors

• Schelm Kerstin Claudia
• Lichtenau Cedric
• Klein Michael
• Payer Stefan
• Leber Petra

Classifications

• G06F7/4915

  Multiplying; Dividing (G06F7/492, G06F7/498 take precedence) · CPC title

• G06F7/52

  Multiplying; Dividing (G06F7/483 - G06F7/491, G06F7/544 take precedence) · CPC title

• G06F7/5443

  Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00) · CPC title

• G06F7/462

  Multiplying; dividing · CPC title

• G06F7/72

  using residue arithmetic · CPC title