# US 2017/0255449 A1 · Fast divider and fast division method thereof

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255449 A1
- Document ID: US20170255449A1
- Status: Published application
- Kind: A1
- Application number: 15/442,879
- Filed: 2017-02-27
- Published: 2017-09-07
- Earliest claimed: 2016-03-02
- Assignees: Realtek Semiconductor Corp.
- Applicants: Realtek Semiconductor Corp.
- Inventors: TSUNG-HSUAN LI; HAO-TIEN CHIANG; SHIH-TSE CHEN
- Web page: https://patentgrep.com/patent/US20170255449A1

## CPC

- G06F 7/535: Dividing only
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 2207/5355: Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Provided is a fast divider including an initial parameter setting unit and an arithmetic unit. The arithmetic unit is coupled to the initial parameter setting unit that receives a divisor and a dividend, and sets a plurality of initial parameters of a sequence according to the divisor and the dividend. The plurality of initial parameters includes an initial term, a first term and a common ratio having an absolute value smaller than 1. The arithmetic unit stores a recurrence relation of the sequence and iteratively computes a quotient using the recurrence relation according to the plurality of initial parameters. The recurrence relation indicates that a (k+1)th term is equal to a product of a kth term multiplied by a sum of the common ratio and 1 subtracted by a product of a (k−1)th term multiplied by the common ratio. k is an integer larger than or equal to 1.

## Claims

### Claim 1

A fast divider, comprising:
an initial parameter setting unit being configured to receive a divisor and a dividend and set a plurality of initial parameters of a sequence according to said divisor and said dividend, wherein said plurality of initial parameters comprise an initial term, a first term and a common ratio, and said common ratio has an absolute value smaller than 1; and
an arithmetic unit being coupled to said initial parameter setting unit and configured to store a recurrence relation of said sequence and iteratively compute a quotient using said recurrence relation according to said plurality of initial parameters, wherein said recurrence relation indicates that a (k+1)th term is equal to a product of a kth term multiplied by a sum of said common ratio and 1 subtracted by a product of a (k−1)th term multiplied by said common ratio, and k is an integer larger than or equal to 1.

### Claim 2 (depends on 1)

The fast divider of claim 1, wherein said initial term is equal to 0, said first term is equal to a first function divided by 2 to the power of a second function, and said common ratio is equal to 1 subtracted by a product of said first term multiplied by said divisor, wherein said first function and said second function exist as said common ratio has an absolute value smaller than 1

### Claim 3 (depends on 2)

The fast divider of claim 2, wherein said divisor is within a range between 2 to the power of s and 2 to the power of s+1 with s being an integer, said first function is equal to 2 to the power of s+1 subtracted by said divisor and said second function is equal to a product of s multiplied by 2 when a product of said divisor multiplied by 3 is smaller than or equal to 2 to the power of s+2, and said first function is equal to 2 to the power of s+2 subtracted by said divisor and said second function is equal to a product of s multiplied by 2 plus 2 when a product of said divisor multiplied by 3 is larger than 2 to the power of s+2.

### Claim 4 (depends on 1)

The fast divider of claim 1, wherein said first term estimated by said initial parameter setting unit corresponds to a convergence speed of said sequence, and said common ratio approaches 0 and said convergence speed of said sequence becomes faster when said first term approaches a reciprocal of said divisor.

### Claim 5 (depends on 1)

The fast divider of claim 1, wherein said arithmetic unit converts said recurrence relation into a matrix product of a parameter matrix multiplied by a column matrix having said first term and said initial term as elements, wherein a plurality of elements in said parameter matrix depend on said common ratio, and said parameter matrix changes as the number of iteration computations increases, wherein said parameter matrix is equal to the square of a previous parameter matrix obtained after a (t−1)th iteration computation is executed when a tth iteration computation is being executed, so that the power of said parameter matrix increases exponentially as the number of said iteration computations increases, and wherein t is an integer larger than 1

### Claim 6 (depends on 5)

The fast divider of claim 5, wherein said arithmetic unit diagonalizes and rewrites said parameter matrix and selects an element in said parameter matrix rewritten as an iteration coefficient so as to rewrite said recurrence relation according to said iteration coefficient, wherein said recurrence relation rewritten indicates that an iteration result after said tth iteration computation is equal to a sum of a product of said first term multiplied by said iteration coefficient and a product of said initial term multiplied by a difference of 1 and said iteration coefficient and said arithmetic unit iteratively computes according to said recurrence relation rewritten so that said iteration result approaches said quotient as the number of said iteration computations increases.

### Claim 7

A fast division method, comprising:
Step A: receiving a divisor and a dividend;
Step B: estimating a plurality of initial parameters of a sequence according to said divisor and said dividend, wherein said plurality of initial parameters comprise an initial term, a first term and a common ratio and said common ratio has an absolute value smaller than 1; and
Step C: iteratively computing a quotient using a recurrence relation of said sequence according to said plurality of initial parameters, wherein said recurrence relation indicates that a (k+1)th term is equal to a product of a kth term multiplied by a sum of said common ratio and 1 subtracted by a product of a (k−1)th term multiplied by said common ratio, and k is an integer larger than or equal to 1.

### Claim 8 (depends on 7)

The fast division method of claim 7, wherein said initial term is equal to 0, said first term is equal to a first function divided by 2 to the power of a second function, and said common ratio is equal to 1 subtracted by a product of said first term multiplied by said divisor, wherein said first function and said second function exist as said common ratio has an absolute value smaller than 1

### Claim 9 (depends on 8)

The fast division method of claim 8, wherein said divisor is within a range between 2 to the power of s and 2 to the power of s+1 with s being an integer, said first function is equal to 2 to the power of s+1 subtracted by said divisor and said second function is equal to a product of s multiplied by 2 when a product of said divisor multiplied by 3 is smaller than or equal to 2 to the power of s+2, and said first function is equal to 2 to the power of s+2 subtracted by said divisor and said second function is equal to a product of s multiplied by 2, plus 2, when a product of said divisor multiplied by 3 is larger than 2 to the power of s+2.

### Claim 10 (depends on 7)

The fast division method of claim 7, wherein said first term corresponds to a convergence speed of said sequence, and said common ratio approaches 0 and said convergence speed of said sequence becomes faster when said first term approaches a reciprocal of said divisor.

### Claim 11 (depends on 7)

The fast division method of claim 7, wherein Step C further comprises a step of:
Step C1: converting said recurrence relation into a matrix product of a parameter matrix multiplied by a column matrix having said first term and said initial term as elements, wherein a plurality of elements in said parameter matrix depend on said common ratio, and said parameter matrix changes as the number of iteration computations increases, wherein said parameter matrix is equal to the square of a previous parameter matrix obtained after a (t−1)th iteration computation is executed when a tth iteration computation is being executed, so that the power of said parameter matrix increases exponentially as the number of said iteration computations increases, and wherein t is an integer larger than 1

### Claim 12 (depends on 11)

The fast division method of claim 11, wherein Step C further comprises steps of:
Step C-2: diagonalizing and rewriting said parameter matrix;
Step C-3: selecting an element in said parameter matrix rewritten as an iteration coefficient so as to rewrite said recurrence relation according to said iteration coefficient, wherein said recurrence relation rewritten indicates that an iteration result after said tth iteration computation is equal to a sum of a product of said first term multiplied by said iteration coefficient and a product of said initial term multiplied by a difference of 1 and said iteration coefficient; and
Step C-4: iteratively computing according to said recurrence relation rewritten so that said iteration result approaches said quotient as the number of said iteration computations increases.
