REVUE D'ANALYSE NUMÉRIQUE
ET DE LA
THÉORIBDE
L'APPROXIMATION, Tome3,
No2,
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.
IntroductionWalther [1]
proposed.a unified algorithm for
elementary functions 'dueto
coordinatetransformation. In a
previouspaper l2), the
authorhas discussed
mainly the circular
case(* : + 1)
andits
application to ,complex arithmetic.In the
present paper,the
author wouldlike to
discussthe
hyperbolic case (m- -
1),in
orderto
give a modified alogrithmfor
the computation,of
squareroot,
exponentialand logarithmic
functions.$ 2. Thc principlc of
CORDICin the
hyperbolie caseIn
orderto
makethe
paper self-contained,we
shal1 beginwith
theprinciple of con¡rc in the hyperbolic
case.I-tet x,
y
bethe
real numbers satisfyingfi> ly l.
The hyþerbolic coor- d,ittøtes(R,A) of a point P:
(x,y) is
tlefined byR: (x'- y')tt', A: arctanh(ylx); x:
Rcosh-¡4.,!:
RsínhA.It is
well-knownthat
RzA 12 isthe
areaof the
domain surrounded.by
the s-axis, radiusvector OP
anclthe
hyperbola x2- y' : c
passing throughP
(seeFig. t).
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¡lnYh+L:ln*ìexo
which yields in the hyperbolic
coordi- natesTherefore,
we may
compute squarefoot, exponential
and. logarithmicat the final
steP,it is
easYto
areof
order e, Provided-that
k that for x, in
(6),the trun-
of. higher ovd,er
than
e.$ 3.
Practiceand
convergenceol
CORIIICIn the binary arithmetic, the transformation
?.(8u)is most
easily performed,if
wetake
8¡: *
2- A, where (1) is computed onlyby
addition, åubtraction andshiftinþ 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
caseI,
and.,,i1 zo
{ 0 then
8o:: -
EÈ else8o::
e¿;"in the
caseIL
Unfortunately, the
constantspis
c1onot
salisfythe
convergence cf1-terion of w¡LtuEn [l]
:(9) 9r--f,,p¡3þ*-t (h:r'2....'n-2).
t-!In fact,
Bo'ssatisfy an inequality-of
_oÞþositedirection in.(9);
Ilow.ever, as mentiòäedin lil and pioved in l2f, the
inequalitv-(9)is
!ry'tei!;13 adtl the
correctiomierm I P,
t,<
3h* I in .the.1eft
hand sideof
(9)'Therefore
it is
enoughto
atid. somemodification in
ord'erto
guaranteethe
convergence. Probablythe
simplest way,is to
reþeøt th.e. þroc.ess onceirore
wit:¡îh" ru*"
valuesof
eo añd. puat the
Þ¿-thstep (i > l),
whereho: 1, h¡:3h¿: + l (i 2 l), i.e.,
h: 4, l3' 40'
721, ."
For the usual
accuracy lessthan
11 decirnals,it is
enoughto repeat
ath
= 4 and
13only.
Piecisely speaking, we should write2-h for 7<h<
42-w-t\ ¡ot 5<h<14
2-tn-zt for
15s
k,<
42 and, soon, but we
continue usethe notation
(8) ' Í-(2)
Ro+,:
Rox Ko, Ku:0 -
|f¡rrzAnrt :
AnI
nn, c(r¿:
afctanh$É.lVe introduce a
third
variablez
and trans- form is simultaneouslywith
(1) asFig. I
Zh+t:
2¡-
&nWe 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 byx, : 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
selectone of the following two
goals:f. y or / is
forced.to be
0.II. z is
forced.to be
0.If the
goal was reachedat the
stepsy, in the
casef,
we have(6) x,,: K(x! - !?)ttr, zn:
ztf
arctanh tt,, - ,, ¡ !1¡,g!J-L.
2 -tt-ytsimiarly, if the
goal was reachedat the
step znin the
caserr,
we have(7) x":
K(x1coshe,I
Yrsinhzr)'y, : K(xt
sinhz,* yr
coshzr).(3)
at
I
176 SIN HITOTUMATU 4 5 THE COMPUTATION OF SQUARE ROOT L77
An
alternate modificationwill be to insert
"' :2 e.
andthe
corres- pondingvalue e'n:
arctanh e'7,at all or
necessafysteps. 4* We prefer
theformer
one becauseof the
simplicity.The
convergence regionin the
caseII
is(10) lzrl SB:Ð90*9n*
æ9r,+... :1.117...
and
that in the
caseI
is(11) 'lylxrl stanhB:0.806...,
The
valuesof
po's should.be
preassigned.. Remarkthat
pomay
be replaced.by et if
efis
negligeable, anð,by
.p+ + "i if
efis
negligeable, sothat
we needrather few
constantsin the
algorithm.$ 4.
Applicationto
square rootIt is
easyto
seethat xr: t +
c,!r: I - c
givesx, : K(x| - y?)'t' :
(2K4¿)^,lt
in
(6).Ilence
taking^fî: t¡ZX,
¡ne havex*:1fÌ in (6). Remark that
if we
needno logarithmic function
simultaneously,the variable z
andthe
constants po's are unnecessøry.F:nther, by the remark at the
end.of
$ 2, we have only to repeat the processwith
repetetion at h:
4, 13, ..., until, h: nl2,
providedthat
accuracy of.n bits is
necessary.The
processis
asin the flow chart
shownin Fig.
2.The
constants areRepeat 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 betterto
determinetlthe
constant cin
sucha
mannerthat the
residue becomes smallestfor
variousvatiõ
of I in the interval {ll4 S, S 1} or {1/16 S,
= 1}. For rossac'=3m in our Institute which
lnas 37bits in
mantissa,the optimal
valueof
¿ is 0.36451229226,In the
practice,it will be better to
normalizet in {U8
= , < Uzt
in
ord.erto
avoid overflowin
thefix point
arithmetic. Forthat
case, there is amod,ified proced.ure.Start fuomh:2(ez:
U4)withc
:0'27233292991 (approxima,cely 314 of the previous c), anð.repeat twicewith
same e at' h:1 (:2 x 3 + 1)
instead.of 4
and-13. The
convergence regionis
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 Stlc s
ezB:9.348. ..
which is surely
impliesthe 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.
I7B
sINHlroruNlAru
6According
to the
resultsof 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
algorithmfor
exponential lunctionSince ¿o
:
sinhøf coshø, it will be natual to try to
compute ø*by conorc
caseII, starting ltom
x1: lt : llk,
z¡:
gives xn
:
eo, provid.ed'that zr:
d'lies within
theItO). Hówever,-in the
above,discussion,we have
a1*r> lyo l, which
doesnot imply the limiting
casegiïe an'alternate proof to
guaranteethe
result'Il xr: y,
formation
(1),is
replaced byxh+|.: xnÍ * tanhao):
#¡ s€chøÈ expc{¿: xh(l - 8l)t"
expo(À,which
givesn, -- nLfi tt -
8fl)r/2"exP (oo):
Kxreo.Þ:1
Indeed,
we
canpfove that the final result (4) under coÌDlc
caseII is true withoirt the^iestriction q<lyrl,
whilein the
caseI, the
restriction(11)
is iídispensable. i' ,
,The actual algorithm
to
compute etlor
reaT argumentI is
as follows :1'. Put
t'7og2Q:
ry* s; m: integer, -
1<s
S 02o.Pttt
21:s7ogr2, h:llK
whe¡e
log"2:0.69314718056
and'l/K is
givenin
(12).3o.
Repeatthe
Procedure,,if. z
10 then
begin øi: x(l - e); z::
zi 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
theinitial
step, we have always%þ:
yo underthe
trans- sothat the
variabley is
unnecessary.The
transformationtc"n+r
1 xoÍ I
8o). Since we haveput
8otanh
ao,we
seeTHE COMPUTATION OP SQUARE ROOT 179
Remark
that in the
above scaling 1o, sis
always negative, sothat at the first
step, we have alwaysz < 0.
Ifenceit will
bebetter to
startwith
zz:
s'1og2f arctanh(ll2), xr: llzK, e:2-', þ':2,3, ...
In the
computationof
complex exponeÍrtial function fexp (ø+ iy) :
e*(cosy I i
sin y),we combine
with
coRDrcin
circular casefor the trigonometric
functions.rn
that
caseit will
be better to start witjnx, :
TlKK+ :
0'36662806930 ' '"
where
K+: Ëtt *
h:o 2-2h)1t2.$ 6.
Computationof
logarithmie lunetionI,ogarithmic function
1ogI will be
computedby the
inwerse pfocess asin tlie
previous paragraph. Ilowever,to
avoid actual division, we preferthe following
algorithms :Assume
first that the
argumentI is
sufficiently near 1 (precise boundwill
givenlater in
(15)).1'.
Put)íz: tlKt: J\¡zx :
7.045723138,y : t, zz:0.
Ilere K, : Kl(l -2-2¡trz.
2o.
Repeatthe
following process:,,if.
x > y
then beginø: :
(1- e)fri 2i :a f p
end-else
begin x:: (l -f
")x, z::
z-
Pend;"
where
" : 2-h, I -
arctanhe,lor h.:2,3, ..., and at h:4
anð' 13 repeatingtwice with
same e'-The repetition is
completelysimilar to the
onein
$5
except ojrlVthe branching condition -is
replaced by
x> y
instead o1 z< 0'
The processbrings ø
as close asy. Finally iÎ x : y, then
we havex --
(KrlR1) ed:
t,which
gives z:
d":7og
t.180 SIN HITOTUMATU B
Ilere we start from
k:2, since (l - 2-Ð : ll2 is too
sma11to
recover later by other prod.ucts. Hence the convergence region is ¡estrictedin
I zt
I S B - þt: B' *0.568..., (15) 0.57... :
e- B/<
ltl <
ea': L.76...
For other
valuesof
ú, we make scalingt :2^
.y
(m being integer), and. set22:
77¡ .log"2 in
(14) insteadof 0.
Herewe
cannottake
112 <Sy S I or 1 3y
5_2,bttt we must
choosethe
mantissay in
(16)
314=y =312 or tlJt:t
But this restriction is not
seriousin the
actraT programming.=JÌ.
Finally
remarkthat this
algorithmis not
suitablefor the
computation of 1ogI
whenthe
argumentI is
quite cl,oseto l. In
sucha
casewe
should replacethe function by
1og (1* r)
computed.by the Taylor
serieslog
(l *s) :5 - "' 2t s + "' - ....
'or by other
approximation formulas, Added.in
Proof :After I
køuefinisked 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,
Tome3,
No2,
1924,pp. tBl-Z0B
CN BEST ONE-SIDED APPROXIMATION WITH INTERPOLATORY FAMILIES*
by
II]JA, LAZARDVIC (Beogracl)
0.
IntroductionI,etX beasetformedwithn f l pointsof the real axis
andf :X
-> Rbe the restriction, at X, of a polynomial of
degreeø. Evidently,
there are polynomialsP
anð,Q of
degreen,
sttc\tthat-
(0.1) P(x) > 0,
Q@)z
0forxeX,and,
(0.2) .f:P-QonX.
Professor
r.
popovrcru has proposed the followingproblem: to
studythe
existenceand the
uniquenessãf a pair (P*,Q\-of
polynomials oi d.egreeS ø 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 hasa
solution,let
this-minimal pair be
determined.Further, let a similar
problem besolved.
in the
case whenX
containsn + 2
points.+ Communicatecl at the Colloque on Functional Bquations, I.açi lgTB