Computing floating-point polynomials in an integrated circuit device

• US 8,949,298 B1
• Filed: 09/16/2011
• Issued: 02/03/2015
• Est. Priority Date: 09/16/2011
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Yaary, Michael D
• Application Number:
  US13/234,419
• Time in Patent Office: 1,236 Days
• Field of Search: None
• US Class Current: 708/204
• CPC Class Codes: G06F 2207/5523 Calculates a power, e.g. the square, of a number or a function, e.g. polynomials
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/548 Trigonometric functions; Co-ordinate transformations
• CPC Class Codes: G06F 7/552 Powers or roots , e.g. Pythagorean sums

Abstract

Polynomial circuitry for calculating a polynomial having terms including powers of an input variable, where the input variable has a mantissa and an exponent, and the circuitry has a number of bits of precision, includes multiplier circuitry that calculates a common power of the input variable factored out of terms of the polynomial having powers of the variable greater than 1. The polynomial circuitry further includes, for each respective remaining term of the polynomial that contributes to the number of bits of precision: (1) a coefficient memory loaded with a plurality of instances of a coefficient for the respective term, each instance being shifted by a different number of bits, (2) address circuitry for selecting one of the instances of the coefficient based on the exponent, and (3) circuitry for combining the selected instance of the coefficient with a corresponding power of the input variable to compute the respective term.

Claims

1. Polynomial circuitry for calculating a polynomial having terms including powers of an input variable, said input variable represented by a mantissa and an exponent, said circuitry having a number of bits of precision and comprising:

a plurality of coefficient memories, each respective one of said coefficient memories corresponding to a respective one of said terms of said polynomial, wherein;

for each respective one of said terms of said polynomial, said respective one of said coefficient memories that corresponds to said respective one of said terms of said polynomial is loaded with a plurality of instances of a respective coefficient for said respective one of said terms of said polynomial, and

said instances of said respective coefficient for said respective one of said terms of said polynomial are multiple versions of said respective coefficient for said respective one of said terms of said polynomial, each version being shifted by a different number of bits; and

respective address circuitry associated with each respective one of said coefficient memories, said respective address circuitry selecting one of said instances of said respective coefficient for said respective one of said terms of said polynomial based on said exponent.

2. The polynomial circuitry of claim 1 further comprising:

multiplier circuitry that calculates a common power of said input variable factored out of terms of said polynomial having powers of said variable greater than 1; and

for each remaining respective one of said terms of said polynomial, from which said common power has been factored out, that contributes to said number of bits of precision, circuitry for combining said selected one of said instances of said respective coefficient for said respective one of said terms of said polynomial with a corresponding power of said input variable to compute said respective term of said polynomial.

3. The polynomial circuitry of claim 2 further comprising circuitry for combining said respective ones of said terms of said polynomial.

4. The polynomial circuitry of claim 3 wherein said multiplier circuitry comprises at least one fixed-point multiplier.

5. The polynomial circuitry of claim 3 wherein said circuitry for combining said selected one of said instances of said respective coefficient with a corresponding power of said input variable to compute said respective term of said polynomial comprises, for at least each of said respective terms for which said corresponding power is greater than 1, a multiplier circuit.

6. The polynomial circuitry of claim 5 wherein said multiplier circuit comprises a fixed-point multiplier.

7. The circuitry of claim 3 wherein said circuitry for combining said respective ones of said terms of said polynomial comprises adder circuitry.

8. The circuitry of claim 7 wherein said adder circuitry comprises fixed-point adder circuitry.

9. A method of configuring a programmable device as circuitry for calculating a polynomial having terms including powers of an input variable, said input variable represented by a mantissa and an exponent, said circuitry having a number of bits of precision, said method comprising:

configuring, on said programmable device;

a plurality of coefficient memories, each respective one of said coefficient memories corresponding to a respective one of said terms of said polynomial, wherein;

for each respective one of said terms of said polynomial, said respective one of said coefficient memories that corresponds to said respective one of said terms of said polynomial is loaded with a plurality of instances of a respective coefficient for said respective one of said terms of said polynomial, and

said instances of said respective coefficient corresponding to said respective one of said terms of said polynomial are multiple versions of said respective coefficient for said respective one of said terms of said polynomial, each version being shifted by a different number of bits; and

respective address circuitry associated with each respective one of said coefficient memories, said respective address circuitry selecting one of said instances of said respective coefficient corresponding to said respective one of said terms of said polynomial based on said exponent.

10. The method of claim 9 further comprising:

configuring circuitry on said programmable device as multiplier circuitry that calculates a common power of said input variable factored out of terms of said polynomial having powers of said variable greater than 1; and

for each remaining respective one of said terms of said polynomial, from which said common power has been factored out, that contributes to said number of bits of precision, configuring circuitry for combining said selected one of said instances of said respective coefficient for said respective one of said terms of said polynomial with a corresponding power of said input variable to compute said respective term of said polynomial.

11. The method of claim 10 further comprising configuring circuitry on said programmable device as circuitry for combining said respective ones of said terms of said polynomial.

12. The method of claim 11 wherein said configuring circuitry of said programmable device as multiplier circuitry comprises configuring at least one fixed-point multiplier.

13. The method of claim 11 wherein said configuring circuitry for combining said selected one of said instances of said respective coefficient with a corresponding power of said input variable to compute said respective term of said polynomial comprises configuring a multiplier circuit for at least each of said respective terms for which said corresponding power is greater than 1.

14. The method of claim 13 wherein said configuring a multiplier circuit comprises configuring a fixed-point multiplier.

15. The method of claim 11 wherein said configuring circuitry for combining said respective ones of said terms of said polynomial comprises configuring adder circuitry.

16. The method of claim 15 wherein said configuring adder circuitry comprises configuring fixed-point adder circuitry.

17. A non-transitory machine-readable data storage medium encoded with non-transitory machine-executable instructions for configuring a programmable device as circuitry for calculating a polynomial having terms including powers of an input variable, said input variable represented by a mantissa and an exponent, said circuitry having a number of bits of precision, said instructions comprising:

instructions to configure circuitry of said programmable device as;

a plurality of coefficient memories, each respective one of said coefficient memories corresponding to a respective one of said terms of said polynomial, and being wherein;

for each respective one of said terms of said polynomial, said respective one of said coefficient memories that corresponds to said respective one of said terms of said polynomial is loaded with a plurality of respective instances of a respective coefficient for said respective one of said terms of said polynomial, and

said instances of said respective coefficient corresponding to said respective one of said terms of said polynomial are multiple versions of said coefficient for said respective one of said terms of said polynomial, each version being shifted by a different number of bits; and

address circuitry for selecting one of said instances of said respective coefficient based on said exponent.

18. The non-transitory machine-readable data storage medium of claim 17 wherein said instructions further comprise:

instructions to configure circuitry on said programmable device as multiplier circuitry that calculates a common power of said input variable factored out of terms of said polynomial having powers of said variable greater than 1; and

instructions to configure, for each remaining respective one of said terms of said polynomial, from which said common power has been factored out, that contributes to said number of bits of precision, circuitry on said programmable device as circuitry for combining said selected one of said instances of said respective coefficient for said respective one of said terms of said polynomial with a corresponding power of said input variable to compute said respective term of said polynomial.

19. The non-transitory machine-readable data storage medium of claim 18 wherein said instructions further comprise instructions to configure circuitry on said programmable device as circuitry for combining said respective ones of said terms of said polynomial.

20. The non-transitory machine-readable data storage medium of claim 19 wherein said instructions to configure circuitry of said programmable device as multiplier circuitry comprise instructions to configure at least one fixed-point multiplier.

21. The non-transitory machine-readable data storage medium of claim 19 wherein said instructions to configure circuitry for combining said selected one of said instances of said respective coefficient with a corresponding power of said input variable to compute said respective term of said polynomial comprise instructions to configure a multiplier circuit for at least each of said respective terms for which said corresponding power is greater than 1.

22. The non-transitory machine-readable data storage medium of claim 21 wherein said instructions to configure a multiplier circuit comprise instructions to configure a fixed-point multiplier.

23. The non-transitory machine-readable data storage medium of claim 19 wherein said instructions to configure circuitry for combining said respective ones of said terms of said polynomial comprise instructions to configure adder circuitry.

24. The non-transitory machine-readable data storage medium of claim 23 wherein said instructions to configure adder circuitry comprise instructions to configure fixed-point adder circuitry.

25. A method of using circuitry to calculate a polynomial having terms including powers of an input variable, said input variable represented by a mantissa and an exponent, said circuitry having a number of bits of precision, said method comprising:

for each respective one of said terms of said polynomial, shifting, by a different number of bits, a plurality of instances of a respective coefficient corresponding to said respective one of said terms of said polynomial,

for each respective one of said terms of said polynomial, loading a respective one of a plurality of coefficient memories with said plurality of instances of said respective coefficient corresponding to said respective one of said terms of said polynomial, and

for each respective one of said terms of said polynomial, selecting one of said instances of said respective coefficient corresponding to said respective one of said terms of said polynomial by using said exponent as an address into said respective one of a plurality of coefficient memories.

26. The method of claim 25 further comprising:

calculating a common power of said input variable factored out of terms of said polynomial having powers of said variable greater than 1; and

for each remaining respective one of said terms of said polynomial, from which said common power has been factored out, that contributes to said number of bits of precision, combining said selected instance of said respective coefficient corresponding to said remaining respective one of said terms of said polynomial with a corresponding power of said input variable to compute said remaining respective one of said terms of said polynomial.