# US 2006/0136542 A1 · Division algorithm

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

- Number: US 2006/0136542 A1
- Document ID: US20060136542A1
- Status: Published application
- Kind: A1
- Application number: 11/020,983
- Filed: 2004-12-22
- Published: 2006-06-22
- Earliest claimed: 2004-12-22
- Assignees: Intel Corporation
- Inventors: Venkataraman Natarajan; Prasad Ghatigar
- Web page: https://patentgrep.com/patent/US20060136542A1

## CPC

- G06F 7/535: Dividing only
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

According to an aspect of the present invention, a quotient of a dividend divided by a divisor may be determined after reducing the dividend, divisor, and the remainder by using operations such as add, subtract, multiply, shift, AND which may result in reduced processor cycles (time).

## Claims

### Claim 1

A method comprising
shifting a dividend and a divisor based upon a power-of-two to obtain a shifted dividend and a shifted divisor,
generating a shifted quotient and an intermediate remainder that are indicative of the shifted dividend divided by the divisor,
shifting the intermediate remainder based upon the power-of-two to obtain a shifted remainder,
generating a remainder quotient indicative of the shifted remainder divided by the shifted divisor, and
generating, based upon the shifted quotient, the remainder quotient, and the power-of-two, a quotient that is indicative of the dividend divided by the divisor.

### Claim 2 (depends on 1)

The method of claim 1 wherein generating the remainder quotient comprises repeatedly subtracting the shifted divisor from the shifted remainder until the shifted remainder has a predetermined relationship to the shifted divisor, and updating the remainder quotient based upon the repeated subtracting of the shifted divisor from the shifted remainder.

### Claim 3 (depends on 1)

The method of claim 1 wherein generating the remainder quotient comprises repeatedly subtracting an increased shifted divisor that is larger than the shifted divisor from the shifted remainder until the shifted remainder has a predetermined relationship to the increased shifted divisor, and updating the remainder quotient based upon the repeated subtracting of the increased shifted divisor from the shifted remainder.

### Claim 4 (depends on 1)

The method of claim 1 wherein generating the remainder quotient comprises generating an increased shifted divisor based upon a reduced power-of-two that is smaller than the power-of-two of the shifted divisor, and
repeatedly subtracting the increased shifted divisor from the shifted remainder until the shifted remainder has a predetermined relationship to the increased shifted divisor,
incrementing the remainder quotient by the reduced power-of-two for each time the increased shifted divisor is subtracted from the shifted remainder,
in response to the shifted remainder having the predetermined relationship to the increased shifted divisor, repeatedly subtracting the shifted divisor from the shifted remainder until the shifted remainder has a predetermined relationship to the shifted divisor, and
incrementing the remainder quotient by one each time the shifted divisor is subtracted from the shifted remainder.

### Claim 5 (depends on 1)

The method of claim 1 wherein generating the shifted quotient comprises repeatedly subtracting the divisor from the shifted dividend until the shifted dividend has a predetermined relationship to the divisor, and
updating the shifted quotient based upon the repeated subtracting of the divisor from the shifted dividend.

### Claim 6 (depends on 1)

The method of claim 1 wherein generating the intermediate remainder comprises subtracting a product of the shifted quotient, the power-of-two, and the divisor from the dividend.

### Claim 7 (depends on 1)

The method of claim 1 further comprising incrementing the quotient by one in response to determining that dividing the dividend by the divisor results in a remainder.

### Claim 8

An apparatus comprising
a network interface to receive a packet of a packet size and to send fragments of a fragment size, and
a processor to fragment the packet into a number of fragments determined by a quotient of the packet size divided by the fragment size, wherein the processor computes the quotient by
assigning the packet size to a dividend and the fragment size to a divisor, bit-shifting the dividend and the divisor to the right by a first integer to obtain a shifted dividend and a shifted divisor,
generating a shifted quotient and an intermediate remainder that are indicative of the shifted dividend divided by the divisor,
bit-shifting the intermediate remainder to the right by the first integer to obtain a shifted remainder,
generating a remainder quotient indicative of the shifted remainder divided by the shifted divisor, and
generating the quotient based upon the shifted quotient, the remainder quotient, and the first integer.

### Claim 9 (depends on 8)

The apparatus of claim 8 wherein the processor generates the remainder quotient by
repeatedly subtracting the shifted divisor from the shifted remainder until the shifted remainder has a predetermined relationship to the shifted divisor, and
updating the remainder quotient based upon the repeated subtracting of the shifted divisor from the shifted remainder.

### Claim 10 (depends on 8)

The apparatus of claim 8 wherein the processor generates the remainder quotient by
repeatedly subtracting an increased shifted divisor that is larger than the shifted divisor from the shifted remainder until the shifted remainder has a predetermined relationship to the increased shifted divisor, and
updating the remainder quotient based upon the repeated subtracting of the increased shifted divisor from the shifted remainder.

### Claim 11 (depends on 8)

The apparatus of claim 8 wherein the processor generates the remainder quotient by
generating an increased shifted divisor based upon a second integer that is smaller than the first integer, and
repeatedly subtracting the increased shifted divisor from the shifted remainder until the shifted remainder has a predetermined relationship to the increased shifted divisor,
incrementing the remainder quotient by the second integer for each time the increased shifted divisor is subtracted from the shifted remainder,
in response to the shifted remainder having the predetermined relationship to the increased shifted divisor, repeatedly subtracting the shifted divisor from the
shifted remainder until the shifted remainder has a predetermined relationship to the shifted divisor, and
incrementing the remainder quotient by one each time the shifted divisor is subtracted from the shifted remainder.

### Claim 12 (depends on 8)

The apparatus of claim 8 wherein the processor generates the shifted quotient by
repeatedly subtracting the divisor from the shifted dividend until the shifted dividend has a predetermined relationship to the divisor, and
updating the shifted quotient based upon the repeated subtracting of the divisor from the shifted dividend.

### Claim 13 (depends on 8)

The apparatus of claim 8 wherein the processor generates the intermediate remainder by
generating a power-of-two based upon the first integer, and
subtracting a product of the shifted quotient, the power-of-two, and the divisor from the dividend.

### Claim 14 (depends on 8)

The apparatus of claim 8 wherein the processor further increments the quotient by one in response to determining that dividing the dividend by the divisor results in a remainder.

### Claim 15

A machine-readable medium comprising a plurality of instructions that in response to being executed result in a processor
bit-shifting a dividend and a divisor to the right by a first integer to obtain a shifted dividend and a shifted divisor,
generating a shifted quotient and an intermediate remainder that are indicative of the shifted dividend divided by the divisor,
bit-shifting the intermediate remainder to the right by the first integer to obtain a shifted remainder,
generating a remainder quotient indicative of the shifted remainder divided by the shifted divisor, and
generating, based upon the shifted quotient, the remainder quotient, and the first integer, a quotient that is indicative of the dividend divided by the divisor.

### Claim 16 (depends on 15)

The machine-readable medium of claim 15 wherein the plurality of instructions further result in the processor generating the remainder quotient by generating an increased shifted divisor that is larger than the shifted divisor by a power-of-two,
reducing the shifted remainder by the increased shifted divisor until the shifted remainder has a predetermined relationship to the increased shifted divisor, and incrementing the remainder quotient by the power-of-two each time the shifted remainder is reduced by the increased shifted divisor.

### Claim 17 (depends on 16)

The machine-readable medium of claim 16 wherein the plurality of instructions further result in the processor generating the remainder quotient by in response to the shifted remainder having the predetermined relationship to the increased shifted divisor, reducing the shifted remainder by the shifted divisor until the shifted remainder has a predetermined relationship to the shifted divisor, and
incrementing the remainder quotient by one each time the shifted remainder is reduced by the shifted divisor.

### Claim 18 (depends on 15)

The machine-readable medium of claim 15 wherein the plurality of instructions further result in the processor generating the shifted quotient by reducing the shifted dividend by the divisor until the shifted dividend has a predetermined relationship to the divisor, and
incrementing the shifted quotient each time the shifted dividend is reduced by the divisor.

### Claim 19 (depends on 15)

The machine-readable medium of claim 15 wherein the plurality of instructions further result in the processor generating the intermediate remainder by
generating a power-of-two based upon the first integer, and
subtracting a product of the shifted quotient, the power-of-two, and the divisor from the dividend.

### Claim 20 (depends on 15)

The machine-readable medium of claim 15 wherein the plurality of instructions further result in the processor further increments the quotient by one in response to determining that dividing the dividend by the divisor results in a remainder.
