Method and apparatus for division employing associative memory

Claim 3

using adding means to add the first entry from the table of multiples to the numerator or intermediate result; 2. storing the result of said subtraction; 3. decrementing by 1 the value of the detected multiplier; 4. and storing the value of the decremented, detected multiplier as the intermediate quotient value; I. detecting if no underflow condition results from said subtraction and if the detected multiplier does not correspond to the last entry in the table of multiples, then: 1. storing the result of said subtraction; 2. and storing the value of the detected multiplier as the intermediate quotient value; J. detecting if no underflow condition results from said subtraction and if the detected multiplier corresponds to the last entry in the table of multiples, then:

Claim 4

using adding means to add the first entry from the table of multiples to the numerator or intermediate result; 2. storing the result of said subtraction; 3. decrementing by 1 the value of the detected multiplier; 4. and storing the value of the decremented, detected multiplier as the intermediate quotient value; I. detecting if no underflow condition results from said subtraction and if the detected multiplier does not correspond to the last entry in the table of multiples, then: 1. storing the result of said subtraction; 2. and storing the value of the detected multiplier as the intermediate quotient value; J. detecting if no underflow condition results from said subtraction and if the detected multiplier corresponds to the last entry in the table of multiples, then:

Claim 5

setting a pass indicator equal to the detected multiplier; 2. performing a second pass by repeating steps D through I using the result of said subtraction as the intermediate result; 3. using summing means to sum the pass indicator to the detected multiplier resulting from the second pass; 4. storing the sum as the intermediate quotient; K. and, left-shifting the numerator or intermediate result.

Claim 6

setting a pass indicator equal to the detected multiplier; 2. performing a second pass by repeating steps D through I using the result of said subtraction as the intermediate result; 3. using summing means to sum the pass indicator to the detected multiplier resulting from the second pass; 4. storing the sum as the intermediate quotient; K. and, left-shifting the numerator or intermediate result.

Claim 7

The method as claimed in claim 1 wherein the base or index is hexadecimal.

Claim 8

The method as claimed in claim 1 wherein the base or index is binary coded decimal.

Claim 9

The method as claimed in claim 1 wherein the steps D through K are repeated until all quotient digits have been determined.

Claim 10

Apparatus for performing division wherein a digit value multiplied by a denominator value is less than or equal to a numerator or intermediate result, comprising: generating means for generating a table of multiples by multiplying the denominator value by successive integer multipliers starting with unity; means for storing the multiples generated by said generating means; an associative memory array; means, connected to said generating means, for storing the most significant byte of the multiples in the associative array; means, connected to said associative array, for sequentially comparing the most significant byte of the numerator or intermediate result with each entry in the associative array to find a selected entry which is less than or equal to the most significant byte of the numerator or intermediate result; means, connected to said comparing means, for detecting the multiplier corresponding to the largest most significant byte satisfying the comparison; means responsive to said detected multiplier for selectively addressing said table of multiples for the corresponding multiple; subtracting means for subtracting the selected multiple from the numerator or intermediate result; means for storing the result of said subtraction; first means, connected to said subtracting means, for detecting underflow; second means, responsive to said detected multiplier, for determining if said detected multiplier corresponds to the largest multiple in the table of multiples; means, responsive to said first and second means, for storing the detected multiplier as an intermediate quotient if said first means detects no underflow and if said second means detects no correspondence; means, responsive to said first means, for decrementing said detected multiplier and for storing said decremented detected multiplier as an intermediate quotient if said first means detects underflow; means, responsive to said first and second means, for storing said multiplier and for forcing a second pass if said first means detects no underflow and if said second means detects correspondence; and means, for summing said stored multiplier with the multiplier resulting from the second pass, and for storing the sum as an intermediate quotient.

Claim 11

Apparatus for performing division wherein a digit value multiplied by a denominator value is less than or equal to a numerator or intermediate result, comprising: generating means for generating a table of multiples by multiplying the denominator value by successive integer multipliers starting with unity; means for storing the multiples generated by said generating means; an associative memory array; means, connected to said generating means, for storing the most significant byte of the multiples in the associative array; means, connected to said associative array, for sequentially comparing the most significant byte of the numerator or intermediate result with each entry in the associative array to find a selected entry which is less than or equal to the most significant byte of the numerator or intermediate result; means, connected to said comparing means, for detecting the multiplier corresponding to the largest most significant byte satisfying the comparison; means responsive to said detected multiplier for selectively addressing said table of multiples for the corresponding multiple; subtracting means for subtracting the selected multiple from the numerator or intermediate result; means for storing the result of said subtraction; first means, connected to said subtracting means, for detecting underflow; second means, responsive to said detected multiplier, for determining if said detected multiplier corresponds to the largest multiple in the table of multiples; means, responsive to said first and second means, for storing the detected multiplier as an intermediate quotient if said first means detects no underflow and if said second means detects no correspondence; means, responsive to said first means, for decrementing said detected multiplier and for storing said decremented detected multiplier as an intermediate quotient if said first means detects underflow; means, responsive to said first and second means, for storing said multiplier and for forcing a second pass if said first means detects no underflow and if said second means detects correspondence; and means, for summing said stored multiplier with the multiplier resulting from the second pass, and for storing the sum as an intermediate quotient.

Claim 12

Apparatus as claimed in claim 5 wherein the means for storing said multiples is a read/write storage array.

Claim 13

Apparatus as claimed in claim 6 wherein the read/write array and the associative array are loaded simultaneously.

Claim 14

Apparatus as claimed in claim 6 wherein the most significant byte of the numerator or intermediate result is stored in a register connected to the associative array for comparison with the entries of the associative array.

Claim 15

Apparatus for performing hexadecimal division wherein a digit value multiplied by a denominator value is less than or equal to a numerator or intermediate result, comprising: generating means for generating a table of the first eight multiples for the denominator value; means, connected to said generating means, for storing the multiples generated by said generating means; an associative memory array; means, connected to said generating means, for storing the most significant byte of the multiples in the associative array; means, connected to said associative array, for sequentially comparing the most significant byte of the numerator with each entry in the associative array to find a selected entry which is less than or equal to the most significant byte of the numerator; means, connected to said comparing means, for detecting the multiplier corresponding to the largest most significant byte satisfying the comparison; means responsive to said detected multiplier for selectively addressing said table of multiples for the corresponding multiple; subtracting means for subtracting the selected multiple from the numerator or intermediate result; means for storing the result of said subtraction; first means, connected to said subtracting means, for detecting underflow; second means, responsive to said detected multiplier, for determining if said detected multiplier equals eight; means, responsive to said first and second means, for storing the detected multiplier as an intermediate quotient if said first means detects underflow and if said second means detects inequality; means, responsive to said first means, for decrementing said detected multiplier and for storing said decremented multiplier as an intermediate quotient if said first means detects underflow; means, responsive to said first and second means, for storing said multiplier, and for forcing a second pass if said first means detects no underflow and if said second means detects equality; and means, for summing said stored multiplier with the multiplier resulting from the second pass, and for storing the sum as an intermediate quotient.

Claim 16

Apparatus for performing hexadecimal division wherein a digit value multiplied by a denominator value is less than or equal to a numerator or intermediate result, comprising: generating means for generating a table of the first eight multiples for the denominator value; means, connected to said generating means, for storing the multiples generated by said generating means; an associative memory array; means, connected to said generating means, for storing the most significant byte of the multiples in the associative array; means, connected to said associative array, for sequentially comparing the most significant byte of the numerator with each entry in the associative array to find a selected entry which is less than or equal to the most significant byte of the numerator; means, connected to said comparing means, for detecting the multiplier corresponding to the largest most significant byte satisfying the comparison; means responsive to said detected multiplier for selectively addressing said table of multiples for the corresponding multiple; subtracting means for subtracting the selected multiple from the numerator or intermediate result; means for storing the result of said subtraction; first means, connected to said subtracting means, for detecting underflow; second means, responsive to said detected multiplier, for determining if said detected multiplier equals eight; means, responsive to said first and second means, for storing the detected multiplier as an intermediate quotient if said first means detects underflow and if said second means detects inequality; means, responsive to said first means, for decrementing said detected multiplier and for storing said decremented multiplier as an intermediate quotient if said first means detects underflow; means, responsive to said first and second means, for storing said multiplier, and for forcing a second pass if said first means detects no underflow and if said second means detects equality; and means, for summing said stored multiplier with the multiplier resulting from the second pass, and for storing the sum as an intermediate quotient.