Browse Prior Art Database

Logarithm by Sequential Squaring

IP.com Disclosure Number: IPCOM000051233D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 16K

Publishing Venue

IBM

Related People

Karp, AH: AUTHOR

Abstract

Currently implemented algorithms for the logarithm use polynomial fits over a reduced range. This approach is difficult to implement in hardware and makes it difficult to change the precision of the result. A novel algorithm is described herein which resolves this problem. To understand the algorithm, consider the following: z=log(b)(b/c/)=Chi)=clog(b) b-1 + log(b)(bChi), where b is the machine base, c is the characteristic, and b/-1/ less than or equal to Chi is greater than 1. If we let y=log(b)(bChi)=b/y/, expressing y in binary y = Sigma/p/i-1/ y(i) 2/-i/, where p is the precision desired for the logarithm, allows us to write f=(bChi)=Pi/p/i-1/ b y(i)2/-i/. The proposed algorithm consists of the following steps: 1. f approaches f/2/ 2.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 97% of the total text.

Page 1 of 2

Logarithm by Sequential Squaring

Currently implemented algorithms for the logarithm use polynomial fits over a reduced range. This approach is difficult to implement in hardware and makes it difficult to change the precision of the result. A novel algorithm is described herein which resolves this problem. To understand the algorithm, consider the following:

z=log(b)(b/c/)=Chi)=clog(b) b-1 + log(b)(bChi), where b is the machine base, c is the characteristic, and b/-1/ less than or equal to Chi is greater than 1. If we let y=log(b)(bChi)=b/y/, expressing y in binary y = Sigma/p/i-1/ y(i) 2/-i/, where p is the precision desired for the logarithm, allows us to write f=(bChi)=Pi/p/i-1/ b y(i)2/-i/.

The proposed algorithm consists of the following steps: 1. f approaches f/2/

2. If f is greater than b, then y(i)=1 and f

approaches (1/b) f else y(i)=0

3. Repeat steps 1 and 2 p times.

If b is a power of 2, then the multiplication in step 2 can be replaced by a shift. If the results are rounded, only p-bit arithmetic is needed.

The proposed algorithm has the following advantages over the onQ implemented in the IBM System/370. 1. The logarithm is computed directly in the desired base. No

bits will be lost in the base conversion.

2. The algorithm can be vectorized even on machines that do

not have rich vector instruction sets.

3. A hardware implementation is straightforward because of

the simplicity of the algorithm.

4. Any desired precision can be obtained.

1

Page 2 of 2

2

...