NATIONAL BUREAU OF STANDARDS REPORT

1278

CALCULATION OF CONTINUED FRACTIONS

BY USE OF AN IBM 60lj. MULTIPLIER

By

D. Teichroew

Institute of Statistics

University of North Carolina

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U.. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. As tin, Acting Director

THE NATIONAL BUREAU OF STANDARDS

The scope of activities of the National Bureau of Standards is suggested in the following listing of the divisions and sections engaged in technical work. In general, each section is en- gaged in specialised research, development, and engineering in the field indicated by its

title. A brief description of the activities, and of the resultant reports and publications,

appears on the inside of the back cover of this report.

1. ELECTRICITY. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Electrochemistry.

2. OPTICS AND METROLOGY. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

3. HEAT AND POWER. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fuels.

4. ATOMIC AND RADIATION PHYSICS. Spectroscopy. Radiometry. Mass Spectrometry. Physical Electronics. Electron Physics. Atomic Physics. Neutron Measurements. Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

5. CHEMISTRY. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical Chemistry. Inorgpnic Chemistry. Eluctrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

6. MECHANICS. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. 'Capacity, Density, and Fluid Meters.

7. ORGANIC AND FIBROUS MATERIALS. Rubber. Textiles. Paper. Leather. Testing and

Specifications. Organic Plastics. Dental Research.

8. METALLURGY. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy. Corrosion.

9. MINERAL PRODUCTS. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Building Stone. Concreting Materials. Constitution and Microstructure. Chemistry' of Mineral

Products.

10. BUILDING TECHNOLOGY. Structural Engineering. Fire Protection. Heating and Air Conditioning. Exterior and Interior Coverings. Codes and Specifications.

11. APPLIED MATHEMATICS. Numerical Analysis. Computation. Statistical Engineering. Ma- chine Development.

12. ELECTRONICS. Engineering Electronics. Electron TVibes. Electronic Computers. Electremic Instrumentation.

13. ORDNANCE DEVELOPMENT. Mechanical Research and Development. Electromechanical

Fuzes. Technical Services. Missile Fuzing Research. Missile Fuzing Development. Projectile Fuses. Ordnance Components. Ordnance Tests. Ordnance Research.

14. RADIO PROPAGATION. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

15. MISSILE DEVELOPMENT. Missile Engineering. Missile Dynamics. Missile Intelligence.

Missile Instrumentation. Technical Services. Combustion.
NBS PROJECT NBS REPORT

3011-60-0002 1278

CALCULATION OP CONTINUED FRACTIONS

BY USE OP AN IBM 60l+ MULTIPLIER

By

D. Teichroew

Institute of Statistics

University of North Carolina

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

This report is issued f in any form, either in w

frosi the Office of the D

n, reprinting, or reproduction

mission in writing is obtained

shington 25, D- C.
II

*
FOREWORD

The introduction of high-speed automatic computing

machines has made it feasible to consider empirical sampling

as a general method in statistical research 0 One of the

problems encountered is the transformation of variates distributed uniformly over (0,1) to variates having other distri

butionSo Continued fraction expans ions such as the one given

in this report should make it possible to carry out the trans

formations in cases where power series converge too slowly

or do not converge at all c Mr* Teichroew prepared this report as a guest worker at

the National Bureau of Standards during the summer of 1951

His work was performed under Contract C3T-525 between the

National Bureau of Standards and the University of North

Carolina,,

Jo Ho Curtiss

Chief, National Applied

Mathematics Laboratories

A p V Q As tin

Acting Director

National 3ureau of Standards

CALCULATION OF CONTINUED FRACTIONS

BY USE OF AN IBM 6OI4. MULTIPLIER

Do Tsiehroew

Institute of Statistics

University of North Carolina

ABSTRACT '

This paper gives an example of the us© of continned fraction expansions in calculating values of

functions by high-speed automatic machines « This,

method * applied here to the doubly®exponential distribution F(x) s e«e^x

f should prove useful in a

wide variety of empirical sampling problem©

lo INTRODUCTION

In mathematical and statistical calculations values of

various functions are frequently required e If only low speed

relay multipliers are available* the values can usually be ob«

tained most efficiently from punch®card or punch-tape tables©

However* if high speed electronic calculators are uged* the

time required to look up values in a table becomes prohibitive

and the values of th© function can be obtained more rapidly

by direct calculations Q It ha® been usual to use power series

expansions for this© In this paper an example is given of the

use ©f continued fraction expansions©

In th® us© of power series expansions two difficulties

are encountered 1 (a) th© range for which the aeries converges is limited;
'
= 2 «=*

(b) the numbers entering into the calculations become

very large or very small*

Th© latter difficulty is usually surmounted by a floating d©ci«

raal point | and the first, by multiplying the argument by a suit«

ably chosen constant arid later making the necessary adjustment * In both cases extensive programming and a detailed knowledge

of numbers which will arise in the calculation are required®

On th© other hand, the advantages of power series expansions

ar© that programming for an iterative method of calculation is

fairly simple and that only a few numbers have to be stored®

Such general statements cannot be mad© about continued

fraction expansions* However, for some th© following state*

ments hold: the expansion converges for a large range of values

of th© argument? th© numbers entering into th© calculations

remain reasonably close to unityj and th© successive approxima®

tions can be calculated by an iterative method* However, more

storage space is required than is needed for power series*

Ho THEORY

A continued fraction expansion of a function f(x) takes

th© form

Y(x) * bc

4* ax

FT * •••

where the a^ and b± may be functions of x* For convenience

th© expansion is often written in th© form
'
& f(x) * b0 + ax a2 Ej

Fj F2 Fj + . 6 . • The ii**-'1 approximant to f(x) is given by

fn

(x) » b0 + a, a2

an

SI + 5i K

It is shown in [1] that this approxim&nt may b© calculated as

follows s ,%(x) - bo 4' A * ^

1^2 + ©*® 41 (AA ® a ® ^n)

whore

1 + * “ m^rrri^j

r» -

n

~ °n~l un

with Initial values

A *i

si

1 h - rv r2

III. METHOD OP CALCULATION

Th© value of tn@ function can therefore bo obtained by

calculating successive approximations until the product

^1^2®*® /n ^ to g©ro to as many digits as required©

This can he don® by carrying out th© steps in the calculation

given in Column 1 of Table I© Column 2 gives the values required from storage; and Column 3# the initial values required©
Ki ft
TABLE I

( 1 ) Calculation( 2 ) ( 3 ) Required from Storage Initial Values

1

1

3 ° (A1 n«l aiAi

b0 + »iAl

In general an extensile memory will b© required if many

and b^ are needed* i e @ e if many iterations will be required

before /f s>© becomes z®ro Q However, if an and bn ar©

functions of n and x only* and this function can be calculated

in an iterative method, machines with relatively small memories

can b© used© In the following section an example is given in

which the 60l^, with only thirty-*two memory positions* was used©

In the study of extreme values the distribution function

appears© In sampling experiments it is necessary to calculate

th© inverse function

for given values of y e Sine© 0 Hr y % 1 , the power series ex®

IV© EXAMPLE

y

* F(x) * e®6 K

log@ C«l©g@(*y)]

pans ion could be used to calculate

s “loga(fy)

- 5

®

Since z can take any value between zero and infinity

,

the powen series is not sufficient to calculate 9 efficiently

x = -lcge s

However, the continued fraction expansion

ioge s - IsrSJL ±s£l kMl toil

i 2 3 4 g; converges for all 0 < Furthermore, the an and bn are

such that

r .« |§|*<«-U

n(n-T)

where

|^J

denotes the greatest integer in e

The storage assignment in th© 604 was as follows

s

Storage

FS-1

FS -2

I

s

' s'=>3 PS4j,

MQ

Counter

GS^Il s GS*’!

G3 -2

GS^ij.

Factor

n

z®l

Temporary

y#

1 * /njl A rn

Decimal

xxx 9 XXoXXX

xx®xxxx

X C XXXX

£ 0 XXXX

In this cas© s was less than 10 » Even with this restriction the calculations can be carried out to only four decimal

places because of the lack pf storage positions Therefor© on©

can not expect th© results to be accurate to four decimals®

Table II gives th© intermediate calculations for s * 10® Th©

only value punched on the card is the final on©, i c ©« 2

©

30214.

* Th© expansion for log@x and numerous others are given in

[2] and [J]®

o
f
• 6 «=»

Table III gives some results for the range ,1 ^ z ® 10© The

aeeur&cy decreases as z **poo because 1 + /^ and there are

fewer than I4. significant figures. In order to get greater

accuracy a larger memory would be needed.

This work was dons on a 60l|» with 60 program steps. Each

iteration was obtained by Impulsing the program repeat s sup®

pression of th© program repeat being based on a balance test

of GS=4, The machine completed approximately 1100 cards per

hour.
V

*
v>

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

cs <=s

TABLE II

CALCULATION OF logglO

r

nM „

3- + 4

&

/ n /f S' * 1*2.<. . / n

9*0000 1.0000 <3,0000 9o0000

4.5ooo 0.1818 -0.8182 -7.3636

1.5000 0.7857 -0.2143 1.5781

3.0000 0.2979 “0 o ?021 . =1.1080

1 .8000 0.6510 <=0.3490 0.3867

2.7000 0.3626 =0 G 6374 -0.2465

1.9286 0.5885 -0 .4115 0.1014

2.5n4 0*3979 -0.6021 020 0O6II

2.C000 0.5569 -Oo443i 0.0271

2,,5000 0.4l80 -0.5820 -o.oi58

2.0455 0.5391 ©4&09 0.0073

'2.4545 0.4304 0696 -P.0042

2.0769 0.5280 -0.4720 0.0020

2.4231 0 .4387 -0.5613 -0.0011

2*1000 0.5205 <=0 .4795 0.0005

2 .4000 o©4446 “0 <>5554 -0,0003

2.1176 0.5134 =>0 0L1866 OoOOOI

fn

9«0000

1*6362

3o2143

2.1063

2.4930

2.2465

2.3479

2.2868

2.3139

2.2981

2.3054

2.3012

2.3032

2.3021

2.3026

2.3023

2.3024

8

TABLE III

ACCURACY OP VALUES CALCULATED BY THE 6OI1. MULTIPLIER

X B calculated log@x

cl -2 <,30259 <=2.3024

c 2 <=1 0 6094l4. -1.6091

.3 -1.20397 -1 .2045

»o .91629 -0 .9164

.5 06932.5 -0.6931

06 -0.51083 -0.5110 . .7 •0» 35667 -0.356?

0 8 •=*0 ©22314 -0.22J1

o9 »0, 10536 -0.1054

loO OoO OoO

2o0 0 069315 0.6932

3o0 1.09861 1.0985

4.0 1.38629 1.3863

5.o

6„o

1 0609I4

1.79176

1 06095

1.7914

TpO 1.94591 1.9460

8.0 2.07944 2.0794 ' 9.0 2 ©19722 2ol971

10 oO 2.30258 2.3024
I

-

.
9

REFERENCES

[1] Ralph Eg Lan© P

86 Interpolation by Means of Continued

Fractions 9 n Proceedings of the Fraternal Actuarial

Ag sogiat ion B TfoTTTTi951t-°UM

.

12 ] 0© Perron® Die Lehr© ~/©n der Keitonbruchen* L@ipil& s 1913 o “~~“

[3] H e S© Wall, The Analytic Theory of Continued Fractions * Van Hostran^TelT^oFFg i9i$iS«

’ ’
- • , . I ' .
THE NATIONAL BUREAU OF STANDARDS

Functions and Activities

The National Bureau of Standards is the principal agency of

the Federal Government for fundamental and applied research in physics, mathematics, chemistry, and engineering. Its activities range

from the determination of physical constants and properties of materials, the development and maintenance of the national standards

of measurement in the physical sciences, and the development of

methods and instruments of measurement, to the development of special

devices for the military and civilian agencies of the Government.

The work includes basic and applied research, development, engineering, instrumentation, testing, evaluation, calibration services,

and various scientific and technical advisory services. A major

portion of the NBS work is performed for other government agencies,

particularly the Department of Defense and the Atomic Energy Commission. The functions of the National Bureau of Standards are set

forth in the Act of Congress, March 3, 1901, as amended by Congress

in Public Law 619, 1950. The scope of activities is suggested in

the listing of divisions and sections on the inside of the front

cover.

Reports and Publications

The results of the Bureau’s work take the form of either actual

equipment and devices or published papers and reports. Reports are

issued to the sponsoring agency of a particular project or program.

Published papers appear either in the Bureau’s own series of publications or in the journals of professional and scientific societies.

The Bureau itself publishes three monthly periodicals, available

from the Government Printing Office : the Journal of Research, which

presents complete papers reporting technical investigations; the

Technical News Bulletin, which presents summary and preliminary re- ports on work in progress; and Basic Radio Propagation Predictions,

which provides data for determining the best frequencies to use for

radio communications throughout the world. There are also five

series of i nonperiodical publications: the Applied Mathematics Series, Circulars, Handbooks, Building Materials and Structures Reports, and Miscellaneous Publications.

Information on the Bureau’s publications can be found in

NBS Circular 460, Publications of the National Bureau of Standards

( $1.00). Information on calibration services and- fees can be found

in NBS Circular 483, Testing by the National Bureau of Standards

(25 cents). Both are available from the Government Printing Of fice

Inquiries regarding the Bureau’s reports and publications should be

addressed to the Office of Scientific Publications r National Bureau

of Standards, Washington 25, D. C.