3

I am really confused about the computation speed of Matlab or Octave.

How is it possible to give the result of a computation like 5^5^5^5 (= 2.351*10^87 if you wanna know) instantly?

I found some results about the speed for matrix computations (this article), but nothing about other matters. And this is not the explanation (my (naive) implementation in Python is running for about 5 minutes right now).

Community
  • 1
  • 1
Happy
  • 1,815
  • 2
  • 18
  • 33
  • There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs. – jonrsharpe Jan 29 '14 at 21:57
  • 1
    Do you want to calculate `5^(5^(5^5))` or `((5^5)^5)^5 = 2.351*10^87`? – tom Jan 29 '14 at 22:01
  • Which algorithm are you using for multiplication? School method, Karatsuba, using FFT? – rendon Jan 29 '14 at 22:02
  • @jonrsharpe: I am aware of your comment but maybe is it possible to give some leads or whatever? I wonder how to reduce my question. Do you think focus on power is a good idea? – Happy Jan 29 '14 at 22:02
  • @tom: absolutely not, this is an example – Happy Jan 29 '14 at 22:03
  • @rendon: the basic exponentiation by squaring algorithm. Do you think this is the only explanation? – Happy Jan 29 '14 at 22:04
  • @Happy Maybe I misunderstood your question. Are you implementing your own exponentiation algorithm or using the python builtin operations? – rendon Jan 29 '14 at 22:06
  • @rendon Mine, [this one](https://en.wikipedia.org/wiki/Exponentiation_by_squaring), the basic method. – Happy Jan 29 '14 at 22:07
  • @Happy OK, that is for the exponentiation part, but how you multiply two number, i.e. Are you implementing your own multiplications algorithm or using python `*` operator (`a * b`)? – rendon Jan 29 '14 at 22:11
  • 1
    5^5^5^5 is not 2.351*1087. It's about 1.3357*102184. Exponentiation is right associative. 5^5^5^5 is short for 5^(5^(5^5)). ((5^5)^5)^5 is a much easier number to calculate. That's just 55*5*5=5125. – David Hammen Jan 30 '14 at 09:01
  • @DavidHammen According to Wolfram Alpha, it's actually a number with that many digits. – Teepeemm Jan 30 '14 at 14:38
  • And since it is a number with that many digits, no program is going to be able to print out the answer, regardless of how fast it can compute it. – Teepeemm Jan 30 '14 at 15:20
  • @Teepeemm - You're correct. 5^5^5^5 is not 1.3357*10^2184. That's the number of decimal digits in 5^5^5^5. You are wrong that it can't be printed. 5^5^5^5: I just printed it! – David Hammen Jan 30 '14 at 17:29

1 Answers1

3

5^5^5^5 doesn't require so many operations after all. For example, at each power step, say a^b, you can compute exp(log(a)*b), which gives the same result.

I'm not saying this is necessarily how Matlab does it, and there may be numerical precision issues. But this illustrates that a multiple-power operation is not so hard as its direct computation would suggest.

As for numerical precision:

>> format long
>> 5^5^5^5
ans =
    2.350988701644576e+087
>> exp(log(exp(log(exp(log(5)*5))*5))*5)
ans =
    2.350988701644561e+087

The relative error is

>> 1 - (5^5^5^5 / exp(log(exp(log(exp(log(5)*5))*5))*5))
ans =
   -6.661338147750939e-015

which is not very far from eps.

Luis Mendo
  • 110,752
  • 13
  • 76
  • 147