• Nu S-Au Găsit Rezultate

View of A new method for the computation of square root, exponential and logarithmic functions through hyperbolic CORDIC

N/A
N/A
Protected

Academic year: 2022

Share "View of A new method for the computation of square root, exponential and logarithmic functions through hyperbolic CORDIC"

Copied!
5
0
0

Text complet

(1)

REVUE D'ANALYSE NUMÉRIQUE

ET DE LA

THÉORIB

DE

L'APPROXIMATION, Tome

3,

No

2,

1974,

pp. 173-180

A NEW METHOD FOR THE COMPUTATION

OF SQUARE ROOT, EXPONENTIAL AND LOGARITHMIC FUNCTIONS THROUGH HYPERBOLIC CORDIC

by

SIN HITOTUMATU

'

(Kyoto)

$ 1.

Introduction

Walther [1]

proposed.

a unified algorithm for

elementary functions 'due

to

coordinate

transformation. In a

previous

paper l2), the

author

has discussed

mainly the circular

case

(* : + 1)

and

its

application to ,complex arithmetic.

In the

present paper,

the

author would

like to

discuss

the

hyperbolic case (m

- -

1),

in

order

to

give a modified alogrithm

for

the computation

,of

square

root,

exponential

and logarithmic

functions.

$ 2. Thc principlc of

CORDIC

in the

hyperbolie case

In

order

to

make

the

paper self-contained,

we

shal1 begin

with

the

principle of con¡rc in the hyperbolic

case.

I-tet x,

y

be

the

real numbers satisfying

fi> ly l.

The hyþerbolic coor- d,ittøtes

(R,A) of a point P:

(x,

y) is

tlefined by

R: (x'- y')tt', A: arctanh(ylx); x:

Rcosh-¡4.,

!:

RsínhA.

It is

well-known

that

RzA 12 is

the

area

of the

domain surrounded.

by

the s-axis, radius

vector OP

ancl

the

hyperbola x2

- y' : c

passing through

P

(see

Fig. t).

(2)

774 SIN HITOTUMATU 2 J THE COMPUTATION OF SQUARE ROOf 175

v Now taking a constant

So(l Ðu I

< l),

we

shall apply the linear

trairsfoimation 1(8u) : @0, yo)

+

(xn+t

!a+ì

by

(1)

?(so)

%p+t: xal

S¡ln

Yh+L:ln*ìexo

which yields in the hyperbolic

coordi- nates

Therefore,

we may

compute square

foot, exponential

and. logarithmic

at the final

steP,

it is

easY

to

are

of

order e, Provided-

that

k that for x, in

(6),

the trun-

of. higher ovd,er

than

e.

$ 3.

Practice

and

convergence

ol

CORIIIC

In the binary arithmetic, the transformation

?.(8u)

is most

easily performed,

if

we

take

: *

2- A, where (1) is computed only

by

addition, åubtraction and

shiftinþ without actual

multiplication'

For

convenience,

we

Put

(B) En:2-þ,

9¿

:

afctanh e¿

and select suitably the signatufe 8¿

: f

eo. Precisely we take the algorithm

,,if lu à 0 then

8o:

: -

eo else 8u

: :

ep;"

in the

case

I,

and.

,,i1 zo

{ 0 then

8o

:: -

else

8o::

e¿;"

in the

case

IL

Unfortunately, the

constants

pis

c1o

not

salisfy

the

convergence cf1-

terion of w¡LtuEn [l]

:

(9) 9r--f,,p¡3þ*-t (h:r'2....'n-2).

t-!

In fact,

Bo's

satisfy an inequality-of

_oÞþosite

direction in.(9);

Ilow.ever, as mentiòäed

in lil and pioved in l2f, the

inequalitv-(9)

is

!ry'te

i!;13 adtl the

correctiom

ierm I P,

t,

<

3h

* I in .the.1eft

hand side

of

(9)'

Therefore

it is

enough

to

atid. some

modification in

ord'er

to

guarantee

the

convergence. Probably

the

simplest way

,is to

reþeøt th.e. þroc.ess once

irore

wit:¡

îh" ru*"

values

of

eo añd. pu

at the

Þ¿-th

step (i > l),

where

ho: 1, h¡:3h¿: + l (i 2 l), i.e.,

h

: 4, l3' 40'

721, .

"

For the usual

accuracy less

than

11 decirnals,

it is

enough

to repeat

at

h

= 4 and

13

only.

Piecisely speaking, we should write

2-h for 7<h<

4

2-w-t\ ¡ot 5<h<14

2-tn-zt for

15

s

k,

<

42 and, so

on, but we

continue use

the notation

(8) ' Í-

(2)

Ro+,:

Ro

x Ko, Ku:0 -

|f¡rrz

Anrt :

An

I

nn, c(r¿

:

afctanh$É.

lVe introduce a

third

variable

z

and trans- form is simultaneously

with

(1) as

Fig. I

Zh+t:

-

&n

We take a seouence Ð0, and repeat the transformation Z-(àr),

T(tr,

.

7'(8,-') with. (3)--sta*in{'riãm-itÀ

"'i.'";

a;,,

i;:;;l-""tiì *" jrrirr"

(x,,

!,, z,). Tl.e final

values are given by

x, : K(x,

coshø

f

31, sinhø)

(4) lu : K(thsinhø f

y1 cosho()

Zn: Zt- d'

where

(5) K :'ñ(t - ¡;¡rtz.

o

:'1]

arctanhø,.

h:t h-r

rn the practical application, we

select

one of the following two

goals:

f. y or / is

forced.

to be

0.

II. z is

forced.

to be

0.

If the

goal was reached

at the

steps

y, in the

case

f,

we have

(6) x,,: K(x! - !?)ttr, zn:

zt

f

arctanh tt

,, - ,, ¡ !1¡,g!J-L.

2 -tt-yt

simiarly, if the

goal was reached

at the

step zn

in the

case

rr,

we have

(7) x":

K(x1coshe,

I

Yrsinhzr)'

y, : K(xt

sinhz,

* yr

coshzr).

(3)

at

I

(3)

176 SIN HITOTUMATU 4 5 THE COMPUTATION OF SQUARE ROOT L77

An

alternate modification

will be to insert

"' :2 e.

and

the

corres- ponding

value e'n:

arctanh e'7,

at all or

necessafy

steps. 4* We prefer

the

former

one because

of the

simplicity.

The

convergence region

in the

case

II

is

(10) lzrl SB:Ð90*9n*

æ

9r,+... :1.117...

and

that in the

case

I

is

(11) 'lylxrl stanhB:0.806...,

The

values

of

po's should.

be

preassigned.. Remark

that

po

may

be replaced.

by et if

ef

is

negligeable, anð,

by

.p

+ + "i if

ef

is

negligeable, so

that

we need

rather few

constants

in the

algorithm.

$ 4.

Application

to

square root

It is

easy

to

see

that xr: t +

c,

!r: I - c

gives

x, : K(x| - y?)'t' :

(2K4¿)

^,lt

in

(6).

Ilence

taking

^fî: t¡ZX,

¡ne have

x*:1fÌ in (6). Remark that

if we

need

no logarithmic function

simultaneously,

the variable z

and

the

constants po's are unnecessøry.

F:nther, by the remark at the

end.

of

$ 2, we have only to repeat the process

with

repetetion at h

:

4, 13, ..., until, h

: nl2,

provided

that

accuracy of.

n bits is

necessary.

The

process

is

as

in the flow chart

shown

in Fig.

2.

The

constants are

Repeat the process for k=!,2,.,., rt/z, and- at k=+ and lJ repeat tr,rice l¡ith sane ¿ The assigneDer)t foi r and y must be performed si'mqltaneously

Fig. 2

æ

fn the practical

pïograllr.,

it will

be better

to

determinetl

the

constant c

in

such

a

manner

that the

residue becomes smallest

for

various

vatiõ

of I in the interval {ll4 S, S 1} or {1/16 S,

= 1}. For rossac'=3m in our Institute which

lnas 37

bits in

mantissa,

the optimal

value

of

¿ is 0.36451229226,

In the

practice,

it will be better to

normalize

t in {U8

= , < Uzt

in

ord.er

to

avoid overflow

in

the

fix point

arithmetic. For

that

case, there is amod,ified proced.ure.

Start fuomh:2(ez:

U4)

withc

:0'27233292991 (approxima,cely 314 of the previous c), anð.repeat twice

with

same e at' h

:1 (:2 x 3 + 1)

instead.

of 4

and-

13. The

convergence region

is

0.33

*

e-B'

< ltlcl = eB'+3, B' : B - þt which surely covers the interval

{li8<t<il2).

(12) and,

K : l7(l -

2-2þ¡lz

* n (l -

2-2k¡rt2,

llK :1.2074970806

h:r h:4,13,

c

: ll4K2

:0.36451229219. . .

The convergence region is

(13)

0.1068.

.. -

e-28 S

tlc s

ezB

:9.348. ..

which is surely

implies

the interval {ll4 < t < 1} or

{1/16

< t S l}

x--/l

Y<Y*¿x x € x + ey

e ¿x05

Ly

€x x+x- y.y

YES No

(=z-

k ¡

5 -. Revue d'¿nalyse numórique et de la théorie de I'approximation, tome 3, 1974.

(4)

I7B

sIN

HlroruNlAru

6

According

to the

results

of the

numerical experiments,

it

seems inte-

festing

that the repetition up to the final bit

(until. å

:

38) gives worse resultã

than to stop at

h

:20; the maxirrial relative effor in the first

case

is nearly 3 tlmes bigger t}ran that' in the leatter

case.

S 5. A new

algorithm

for

exponential lunction

Since ¿o

:

sinhø

f coshø, it will be natual to try to

compute ø*

by conorc

case

II, starting ltom

x1

: lt : llk,

:

gives xn

:

eo, provid.ed'

that zr:

d'

lies within

the

ItO). Hówever,-in the

above,discussion,

we have

a1

*r> lyo l, which

does

not imply the limiting

case

giïe an'alternate proof to

guarantee

the

result'

Il xr: y,

formation

(1),

is

replaced by

xh+|.: xnÍ * tanhao):

s€chøÈ expc{¿

: xh(l - 8l)t"

expo(À,

which

gives

n, -- nLfi tt -

8fl)r/2"exP (oo)

:

Kxreo.

Þ:1

Indeed,

we

can

pfove that the final result (4) under coÌDlc

case

II is true withoirt the^iestriction q<lyrl,

while

in the

case

I, the

restriction

(11)

is iídispensable. i' ,

,

The actual algorithm

to

compute et

lor

reaT argument

I is

as follows :

1'. Put

t'7og2Q

:

ry

* s; m: integer, -

1

<s

S 0

2o.Pttt

21

:s7ogr2, h:llK

whe¡e

log"2:0.69314718056

and'

l/K is

given

in

(12).

3o.

Repeat

the

Procedure

,,if. z

10 then

begin ø

i: x(l - e); z::

z

i p

end.

else

begin xi:

rç(l

*.); zt:2-

P end;

where

e:2-þ, e:

atctanh2-þ,

for

h

: 1,2,3, .. . with repetition at

h

: 4

anð. 13.

at

the

initial

step, we have always

%þ:

yo under

the

trans- so

that the

variable

y is

unnecessary.

The

transformation

tc"n+r

1 xoÍ I

8o). Since we have

put

8o

tanh

ao,

we

see

THE COMPUTATION OP SQUARE ROOT 179

Remark

that in the

above scaling 1o, s

is

always negative, so

that at the first

step, we have always

z < 0.

Ifence

it will

be

better to

start

with

zz:

s'1og2

f arctanh(ll2), xr: llzK, e:2-', þ':2,3, ...

In the

computation

of

complex exponeÍrtial function fexp (ø

+ iy) :

e*(cos

y I i

sin y),

we combine

with

coRDrc

in

circular case

for the trigonometric

functions.

rn

that

case

it will

be better to start witjn

x, :

T

lKK+ :

0'36662806930 ' '

"

where

K+: Ëtt *

h:o 2-2h)1t2.

$ 6.

Computation

of

logarithmie lunetion

I,ogarithmic function

1og

I will be

computed

by the

inwerse pfocess as

in tlie

previous paragraph. Ilowever,

to

avoid actual division, we prefer

the following

algorithms :

Assume

first that the

argument

I is

sufficiently near 1 (precise bound

will

given

later in

(15)).

1'.

Put

)íz: tlKt: J\¡zx :

7.045723138,

y : t, zz:0.

Ilere K, : Kl(l -2-2¡trz.

2o.

Repeat

the

following process:

,,if.

x > y

then begin

ø: :

(1

- e)fri 2i :a f p

end-

else

begin x:: (l -f

")x, z::

z

-

P

end;"

where

" : 2-h, I -

arctanhe,

lor h.:2,3, ..., and at h:4

anð' 13 repeating

twice with

same e'-

The repetition is

completely

similar to the

one

in

$

5

except ojrlV

the branching condition -is

replaced by

x

> y

instead o1 z

< 0'

The process

brings ø

as close as

y. Finally iÎ x : y, then

we have

x --

(KrlR1) ed

:

t,

which

gives z

:

d"

:7og

t.

(5)

180 SIN HITOTUMATU B

Ilere we start from

k

:2, since (l - 2-Ð : ll2 is too

sma11

to

recover later by other prod.ucts. Hence the convergence region is ¡estricted

in

I zt

I S B - þt: B' *0.568..., (15) 0.57... :

e- B/

<

l

tl <

ea'

: L.76...

For other

values

of

ú, we make scaling

t :2^

.

y

(m being integer), and. set

22:

77¡ .

log"2 in

(14) instead

of 0.

Here

we

cannot

take

112 <

Sy S I or 1 3y

5_2,

bttt we must

choose

the

mantissa

y in

(16)

314

=y =312 or tlJt:t

But this restriction is not

serious

in the

actraT programming.

=JÌ.

Finally

remark

that this

algorithm

is not

suitable

for the

computation of 1og

I

when

the

argument

I is

quite cl,ose

to l. In

such

a

case

we

should replace

the function by

1og (1

* r)

computed.

by the Taylor

series

log

(l *s) :5 - "' 2t s + "' - ....

'

or by other

approximation formulas, Added.

in

Proof :

After I

køue

finisked to þreþør ent I

the

þøþers [3], t4l

ønd.

l5l &re c

d.

u rn

sed,

here. Tlt'e øuthor woul,d.

lihe to d,i ons eir in ø

seþørøte þaþer.

REFERENCÉS

[1 ] W alther, J. 5., A unified, algorithm for elementary Junotions, Spring Joint Com- puter Confetence 379-385, 1971.

[2] Hitotumatu S., Cowþlex øri.thmetiothroøgh CORDIC, R.I.M.S. Preprint 138 (1973) ;

will appeat in l{odai Math. Sem. Report.

[3] M e g g i t t, J. 8., Psewd,o-diui,sion ønd, þseud,o-multi,þlicalion þlocesses, IBM J. Res.

Dev. G, 210-226, (19621.

[ ] Specker, W. I{., A class of algoritkrnus for \t x, exp ø, sin x, cos Í, t{t x and ct{t x, IEEÐ Trans. Þ.C. 11r, 85-86, (1965).

l5l Koyùf,.ãgi, S., W atanabe, I(. ancl IIagiwâta, H., Aþþroxi'mation of ele-

' mentary functions by micro-þrogramming (in Japanes), Ptoc. 14th Annual Meeting of the Inlormation Processing Society of Japan, l7l-172, (1573).

Received 1. IlL 1974.

Reseørch Institute Jor M athetnatical Sciences

I{ltoto Uniuersil,jt, Kyoto, Jaþart

REVUE D'ANALYSE NUMÉRIQUE

ET DE LA TIIÉORIE DE L'APPROXIMATION,

Tome

3,

No

2,

1924,

pp. tBl-Z0B

CN BEST ONE-SIDED APPROXIMATION WITH INTERPOLATORY FAMILIES*

by

II]JA, LAZARDVIC (Beogracl)

0.

Introduction

I,etX beasetformedwithn f l pointsof the real axis

andf :

X

-> R

be the restriction, at X, of a polynomial of

degree

ø. Evidently,

there are polynomials

P

anð,

Q of

degree

n,

sttc\t

that-

(0.1) P(x) > 0,

Q@)

z

0

forxeX,and,

(0.2) .f:P-QonX.

Professor

r.

popovrcru has proposed the following

problem: to

study

the

existence

and the

uniqueness

ãf a pair (P*,Q\-of

polynomials oi d.egree

S ø which is minimal,

i.e.,

(0.3) P>P*>0,QZQ*20 onX

for every pair

(P, Q)

which

verifies (0.2)

; if the

problem has

a

solution,

let

this-

minimal pair be

determined.

Further, let a similar

problem be

solved.

in the

case when

X

contains

n + 2

points.

+ Communicatecl at the Colloque on Functional Bquations, I.açi lgTB

Referințe

DOCUMENTE SIMILARE

The Constitution of the Republic of Albania regulates three situations that require extraordinary measures: war situation, state of emergency and state of natural

3 (a &amp; b) shows the specific wear rate of the composites with varying the parameters such as load and sliding velocity. Similarly, the sliding velocity was taken as 10 m/s and

, Convergence of the family of the deformed Euler-Halley iterations under the H¨ older condition of the second derivative, Journal of Computational and Applied Mathematics,

The comparison of the properties of WO 3 with respect to the used substrate material (FTO glass, quartz glass and graphite substrates) shows that there is a dependency on

HCT which was developed in the early 1960s by Gary Becker, asserts the following (Becker, 1994): (i) By attending university, graduates will be provided with knowledge and skills as

The evolution to globalization has been facilitated and amplified by a series of factors: capitals movements arising from the need of covering the external

Using a case study designed for forecasting the educational process in the Petroleum-Gas University, the paper presents the steps that must be followed to realise a Delphi

Then if the first experiment can result in any one of m possible outcomes and if, for each outcome of the first experiment, there are n possible outcomes of the second experiment,