2

Exponents are used to represent multiplying by a number over and over. but big numbers, like $6^8$ are hard to calculate. is there any simple way to calculate big numbers of the form $x^y$? ($y>0$ and is whole)

mathreadler
  • 25,824
Alexander Day
  • 885
  • I think english speakers say "integer" for something in $\mathbb{N}$. Did you get "whole" on google translate ? – Vincent Apr 19 '17 at 12:27
  • @Vincent: Actually English speakers say "integer" for something in $\mathbb Z$. Of course $\mathbb N\subset\mathbb Z$, so formally you are right. More to the point, also the term "whole number" is somethimes used in English text, as explained on Wikipedia (see the end of the second paragraph). – celtschk Apr 19 '17 at 12:37
  • Given that "calculating" those numbers usually just means to bring them into a certain form which is then considered "the" result, one way to calculate that number is to just declare that decimal numbers are not special, and therefore you can just write $6^8$ in base $6$, which gives $100,000,000$ :-) – celtschk Apr 19 '17 at 12:41
  • 1
    @Vincent "Whole number" is a common phrase for integer but mostly used by non-mathematicians. It is rare in serious mathematics. I think "whole" in this context without the following "number" is less common. So, "$2/3$ is not a whole number" sounds quite natural to me but "$3/2$ is not whole" sounds less natural. P.S. I am a native speaker born in London. – badjohn Apr 19 '17 at 12:50

2 Answers2

1

One short cut is to notice that $x^4 = (x^2)^2$ so it can be done with two multiplications rather than the obvious 3. The savings get bigger for higher powers $x^{16} = (((x^2)^2)^2)^2$ - four multiplications instead of 15. In those simple examples, the power is itself a power of 2 but you can do things such as $x^{17} = x(((x^2)^2)^2)^2$. Expressing $y$ in binary can help you plot an efficient combination of squaring and multiplying by $x$.

badjohn
  • 8,204
  • interesting! i actually study binary, so these answers are going to be useful! – Alexander Day Apr 20 '17 at 12:15
  • @AlexanderDay Write out some numbers in binary. Then try to find the most efficient calculation in my style and compare them. You should see a pattern. Depending on the relative cost of multiplication and division, you could consider overshooting and coming back. E.g. $x^{15}$ as $x(x(xx^2)^2)^2$ or $(((x^2)^2)^2)^2 / 2$. 6 multiplications v 4 multiplications and 1 division. – badjohn Apr 20 '17 at 12:29
1

One classic way is iterated squaring. Start with 1.

  1. Write the exponent in binary form
  2. Loop over digits starting with most significant-1:
    • if 1: multiply with x
    • if 0: don't multiply with x
  3. Square the number, go to next digit and iterate 2 until we run out of digits.

Let's take example $9 = (1001)_2$

We start with most significant 1 bit:

  1. it is 1, so we multiply with x, we now have $x$

  2. new iteration, so we square, and we have $x^2$

  3. digit nr 2 is 0, so we just square $(x^2)^2=x^4$
  4. digit nr 3 is 0, so we just square $(x^4)^2 = x^8$
  5. last digit is 1 so we multiply with x: $x(x^8) = x^9$
mathreadler
  • 25,824