Browse Prior Art Database

Method for efficient approximation of integer and floating-point square root, inverse square root, and division

IP.com Disclosure Number: IPCOM000007515D
Publication Date: 2002-Apr-02
Document File: 5 page(s) / 83K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for efficient approximation of integer and floating-point square root, inverse square root, and division. Benefits include improved accuracy, improved performance, and reduced code size.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 43% of the total text.

Method for efficient approximation of integer and floating-point square root, inverse square root, and division

Disclosed is a method for efficient approximation of integer and floating-point square root, inverse square root, and division. Benefits include improved accuracy, improved performance, and reduced code size.

Background

      Conventionally, games on PDAs are minimal because the floating-point emulation is extremely slow and consumes lot of power. Integer and floating-point square root computation is an important routine in 3-D graphics and game development. Precision and dynamic ranges are the two conflicting aspects in approximation functions. This issue can be efficiently resolved by dynamically developing the most optimized variant using leading-bit computation.

              ARM4-based architecture is targeted for mobile and handheld devices with low power consumption and high-performance requirements. Integer and floating-point computation is highly desirable for 3-D graphics and game development. Conventionally, ARM4 embedded devices support integer and floating-point computation through emulation.

              Arithmetic operations using floating-point emulation are CPU intensive. Therefore, an efficient computation of integer and floating-point square root that consumes less CPU cycles is highly desirable. Any performance enhancement in terms of MIPS and power consumption is crucial to the OEMs and ISVs for their product development.

Description

              The disclosed method computes integer and floating-point square roots (see Figure 1), inverse square roots (see Figure 2), and division (see Figure 3) with almost full precision and yet with only a fraction of CPU cycles consumed by the emulation counterpart. Several techniques are utilized, including:

§       Rational chaining approximation

§       Serial expansion

§       Normalization

§       Leading-bit computation

§       Fixed-point arithmetic

§                Numerical adjustment techniques

              Comparative analyses are conducted of the results and cycle counts for the following cases of test data:

§         Floating-point square root (see Figure 4)

§         Floating-point inverse square root (see Figure 5)

§         Floating-point division (see Figure 6)

§         Integer square root (see Figure 7)

§         Integer inverse square root (see Figure 8)

§         Integer division (see Figure 9)

Advantages

              The disclosed method presents advantages over the conventional solution, including:

§         Very high precision because of a highly accurate approximation technique, using rational chaining approximation, normalization, and numerical adjustments with fixed-point arithmetic

§         Maximum precision and optimal performance because no lookup tables are used for leading-bit computation, maintaining a balance between precision and dynamic ranges

§         Greatly improved performance because leading-bit computation is performed without any memory access

§         Improved performance because of code-size reduction that increases the likelihood of the code remaining in the instruction cache (IC) under a multi-tasking environment

§         25 to...