Skip to main content

Algorithm 3.7 Raising A Number To A Large Power Part 1

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 3.7 Raising A Number To A Large Power Part 1.
  • Work through the source examples for Algorithm 3.7 Raising A Number To A Large Power Part 1 without depending on raw chunk order.
  • Use Algorithm 3.7 Raising A Number To A Large Power Part 1 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 3.7 Raising A Number To A Large Power Part 1". 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 3.7 Raising A Number To A Large Power Part 1
  • Raw source file: 042-algorithm-3-7-raising-a-number-to-a-large-power-part-1.md

Merged source​

Algorithm 3.7 Raising A Number To A Large Power Part 1​

id: '042-algorithm-3-7-raising-a-number-to-a-large-power-part-1' 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: 42 chunk_total: 138 title: "Algorithm 3.7 RAISING A NUMBER TO A LARGE POWER (Part 1)" part: "" chapter: "" pages: start: 145 end: 148 words: 1046​

Algorithm 3.7 RAISING A NUMBER TO A LARGE POWER (Part 1)

Algorithm 3.7 RAISING A NUMBER TO A LARGE POWER​

Problem

Given some integer x. compute the value of xn where n is a positive integer

considerably greater than 1.

Algorithm development

where x and n are given is a straightforward task. A simple method of

evaluation is to repeatedly multiply an accumulating product p by x for n

iterations, for example,

1 to n dop: = p*x for i.

In most cases, evaluating xn in this way is satisfactory. There are, however,

occasions (e.g. as in a recently published encryption algorithm) where it is

necessary to strive for higher efficiencies in evaluating the power of some integer. Let us therefore concern ourselves with trying to discover a more

ernclent algorithm for power evaluation.

It is not obvious where to start in designing a more efficient algorithm

for evaluating xn. In these circumstances it is probably best to study how a

specific example is evaluated using the first algorithm to see if this will help

us to get started. Conqider the evnluntinn of YIO In onr ctenwiqe nnnrnnrh we hnve-

=x2xx

=x3xx

PIO = = X9 XX

Studying these steps carefully, we see that x is increasing by one power at

each step. In trying to evaluate more efficiently, what are we really trying

to do? To evaluate more efficiently implies that we will need to take fewer

steps to complete the task. The question is just how can we do this? Looking

back at our example, we see that we could have generated x4 by simply

multiplying x2 by itself, for example,

Thiq reanireq illRt nnp mnltinlirntinn rnther thnn the two multinlicntinnq nqed

in our example above. In terms of power addition we have 2+2=4 com-

pared with 2+1+1 = 4. This new way of evaluating x4 may provide the lead

we need we Ghould inveqtionte further nlnno theqe lineq In one qenqe what this most recent example tells us is that we will have solved our problem

in the most efficient way when we discover the set of numbers that add to 10

in the least number of steps. (Remember, multiplication in this instance

translates into the addition of powers).

Some sets of numbers that add up to 10 are:

8+2 --

6+4

5+5

4+4+2

What we observe is that whichever one of these possibilities we choose we

are going to be faced with a smaller Dower evaluation problem that needs to be solved efficiently. Also since adding three numbers is not going to be as

efficient as adding two numbers, our "best" solution to the problem is not

likely to come from adding sets like 4+4+2. This leads us to the question as

to what is the pair of numbers that'we can choose to add to 10 that leaves us

with the smallest smaller power evaluation problem?

Suppose we choose 8 and 2 as our pair of powers to generate (i.e.

= If thic npprl tn apnprntp Y8 "Ihioh already close to before we could complete the task. Putting it another way,

we need to ask what is the "smallest" pair of numbers that we can choose that add up to 10? The answer to this question has to be two 5s. For example,

= Ito

All other combinations, e.g. 6+4, etc., leave us with a larger smaller Dower

VC.&DV A 1 D, U u 1 F.A...'VVVI

evaluation problem, once we have generated we can go directly to by

simply multiplying x5 by itself.

Our next concern is to try to work out how to compute x5 efficiently.

Again we can try the power-halving approach. Unfortunately, half of 5 is 2.5

which is not an integral power. Our only useful alternative in this case is to

oenprntp Y5 Y2 tn Y4 thpn nn thot rpclllt Y

example,

The steps to compute are therefore:

x2 = x xx

With this scheme we have used only four rather than nine multiplications to

evaluate x10. On this basis, it would be reasonable to expect that for larger

powclb the sav Iligs woulu ve Illucll y catel. We are still quite a long way from coming to terms with the implementa-

tion of this algorithm, so let us consider another example to see what

generalizations we can make. Consider the case of evaluating x23. In working

out the steps required to compute we actually started with the final power

and worked backwards. We can trv the same idea with thiq Recond examnle

x23 = x22 xx

a 1 v *All

=x10xx

x10=x5

x5 xx

x 4 xx2 2 = x xx

Here we can see that onlv 7 multiDlications have been reauired to raise a

number to the power 23. We can also see after studying these last two

examples that a definite pattern has evolved.

At each stage in the power generation process, one of two conditions

apply:

(a) Where we have an odd power it must have been generated from the

power that is one less (e.g. x23 = xnxx). (b) Where we have an even power, it can be computed from a power that is

half its size (e.g. x22

These last two statements caoture the essence of the algorithm. This means

  • 11

  1. a part that determines the multiplication strategy, and

  2. a second part that actually does the power evaluation.

To map out the multiplication procedure. we can start with the Dower

integer-divide the current power by 2 and repeat the even/odd determina-

tion procedure. From our two examples we can see that this whole process

must be continued until 2 is reached. The even/odd information can be

recorded in an array by storing a 1 for odd and a 0 for even powers.

For our second example we would have:

23 1 x arm Yll WL&J

T o enrrv the qeonnd nnrt nf the nlonr;thm (; e the nower

-1 tiony, we need to workforwaras rather than backwards. This Implies that we

must start with the highest element in the d array (in our example d[4]) and

work back down to d[l].

Starting out with our product p equal to 1 we can proceed with the

power evaluation using the following rule: