Algorithm 2.5 Sine Function Computation

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives

• Explain the main ideas and vocabulary in Algorithm 2.5 Sine Function Computation.
• Work through the source examples for Algorithm 2.5 Sine Function Computation without depending on raw chunk order.
• Use Algorithm 2.5 Sine Function Computation as selective reference when learner modules point back to How To Solve It By Computers.

Prerequisites

• None curated yet.

Module targets

• module-05-problem-solving

AI companion modes

• Explain simply
• Socratic tutor
• Quiz me
• Challenge my understanding
• Diagnose my confusion
• Generate extra practice
• Revision mode
• Connect forward / backward

Source-of-truth note

This unit is anchored to How To Solve It By Computers and the source chapter "Algorithm 2.5 Sine Function Computation". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance

• Primary source: How To Solve It By Computers
• Source chapter: Algorithm 2.5 Sine Function Computation
• Raw source file: 023-algorithm-2-5-sine-function-computation.md

Merged source

Algorithm 2.5 Sine Function Computation

---

id: '023-algorithm-2-5-sine-function-computation' book: "How to Solve It by Computer" source_file: "../how-to-solve-it-by-computer-r-g-dromey-for-unit-1.pdf" ocr_source: "../ocr-extracted.txt" chunk_index: 23 chunk_total: 138 title: "Algorithm 2.5 SINE FUNCTION COMPUTATION" part: "" chapter: "" pages: start: 81 end: 85 words: 992

Algorithm 2.5 SINE FUNCTION COMPUTATION

Algorithm 2.5 SINE FUNCTION COMPUTATION

Design an algorithm to evaluate the function sin(x) as defined by the infinite

series expansion

5! 7!

Algorithm development

This problem embodies some of the techniques we have seen in earlier

algorithms. Studying the expression for sin (x) we see that powers and

fnotnrinl« follnwino the

are required. We can easily generate this odd sequence by starting with 1 and successively adding 2. Our other problem is to compute the general term

xi/i! which can be expressed as

it

The function we need to compute this will involve the following steps:

1;

O;

while j<i do

begin

fp fp*x/j

end

The algorithm can be completed by implementing the additions and subtrac-

anu applupl VV appu (i.e. Y/ i!) is computed by starting at the smallest j value and working

upwards. In calculating n! we used the efficient approach of calculating each

term from its predecessor. The question this raises is can we do the same with

the present problem? To explore this possibility we can examine the overlap

for some snecific terms of the series- For examnle

Q Y ovi

xxxxxxxxx

3!

xxx><x

5!

Each of the terms x2/(3><2), x2/(5x4), x2/(7x6),... can be described by the

general term:

2 x for i(i--l)

to genelate consecutive terms of the sine series we can use nereiore

x (previous term) current lth term = i(i--l)

To get the terms to alternate in sign we can use the device employed in

problem 2.3.8. Repeatedly executing

qiøn Rion

will generate alternating positive and negative terms. This can be incorpo-

rated directly into our term expression. The initial conditions are therefore

tsin = x;

term.

The ith term and summation which can be generated iteratively from their

predecessors are:

i: -- 1+2

term.

-- term); tsin = tsin + term

We now have an effective iterative mechanism for generating successive

terms of the sine function. The only other consideration is how to terminate

the algorithm.

Clearlv we can onlv evaluate sin (x) to a finite number of terms. An

important consideration here is the desired accuracy we require for sin (x).

Because x is in the range we can see that the contribution from

higher terms quickly becomes very small. For example the 4th term (i.e.

x7/7!) makes a contribution of less than 0.0002. In circumstances like this a

useful way to bring about termination is to fix an acceptable error level (e.g.

lx 10-6) and generate successive terms until the contribution of the current

'CDD a 1 na1YDID

Droblem confirms that this is an acceotable termination condition. Because

VVV UDV v a 1 uV for the termination test.

The overall strategy for our sine function algorithm can be summarized

as follows.

Set up initial conditions for the first term that cannot be computed 1.

iteratively.

2. While the absolute value of current term is greater than the acceptable

error do (a) identify the current ith term,

(b) generate current term from its predecessor,

"'1 rrpnt t Art" 'Mith t hp onnrnnrlntø tn t hp

sum for the sine function.

Since the sine expression involves the calculation of a single value it is best

implemented as a function.

Pascal implementation

function sin (x: reai): real;

const error = 1

var i {variable to generate sequence 1 3 5 7}: integer;

Xz squareuj, term {current sum of terms -- eventua//y approximates sin}: reai;

begin {function returns sin (x) with an accuracy of=<error} {assert:--l.O = < x = < 1.0}

tsin

anel uwauvn, I Atsin is sum of first (j,+ 1) terms} white abs (term)>error do

begin {generate and accumulate successive terms of sine expression}

--term *x2 / (i * (i--l)); tgin: = tgin + tarm

sin:= tsin {assert: sin --sine (x)Aabs (term)=<error}

end

Notes on desian

The number of loop iterations for this algorithm is a function of the 1.

error requirements. For an error of less than 10-6 only 5 terms need to be evaluated. This accuracy will suffice for most practical applications.

The cost of generating successive terms of the series is constant. This is

successive terms was proportional to the position of the terms in the

series (i.e. later terms required more computation).

2. Before, and throughout the iterative process, at the jth pass (j is not

explicitly defined) term represents the jth term in the sine series expan-

Sion and tsin contains the appropriately signed summation of the first j

terms in the series expansion. The invariant restrictions on the vari-

ables tsin and term hold for all j > 1. We can be confident that the

algorithm will terminate because for the chosen x range (i.e. 1)

t hp Af tDYh1 f" It u vv therefore eventually become less than the set error level. In this

discussion we have not considered contributions from round-off

e rrnrc 3. The number of multiplications is reduced by precomputing the x*x

term.

This algorithm embodies the same basic mechanism that is applied in 4.

the factorial and summation algorithms. The only differences involve

choice of initial conditions, choice of iterative terms, and choice of

termination conditions.

5. w nere it is appropriate, generation of each term from its predecessor usually leads to the simplest and most efficient implementation for a

nrnhlem It therefore worth nnttino in the evtrn Pffnrt tn if

terms can be generated from their predecessors. Specific examples are

good for this purpose.

6. Take particular note of the way the alternating sign effect is achieved

and also of the way termination is brought about.

mppucauuuus

Mathematical and statistical computations.

-uppueuuue:uary pruuuems

2.5.1 Design an algorithm to find the sum of the first n terms of the series

The exoonential growth constant e is characterized bv the exores- 2.5.2

1 1

Devise an algorithm to compute e to n terms.