My Math Forum Power Tower Size

 Number Theory Number Theory Math Forum

 June 4th, 2013, 01:27 AM #11 Member   Joined: May 2013 Posts: 35 Thanks: 1 Re: Power Tower Size based on further analysis of the problem; the right most 3 powers are the only 3 you need to concern yourself with so long as they are not equal. beyond that, a number would have to be bigger than 1 followed by 10 trillion zeros to have a significant impact on the problem. so my algorithm would be... Code: import math input1 = raw_input("what's your tower A?") input2 = raw_input("what's your tower B?") input1 = input1.split() input2 = input2.split() i = len(input1) j = len(input2) if i < j: while i > -1: if input1[i] != input2[i]: break else: while j > -1: if input1[j] != input2[j]: break if i == -1 or j == -1 and i ==j: print "towers are equal." elif i == -1 or j == -1: if i > j: print "tower 1 is bigger." else: print "tower 2 is bigger." i = j j = i a = input1[i] b = input1[i-1] if len(input1) < 3: valueA = a*math.log(b,10) else: c= input[i-3] valueA = a*math.log(b,10) +math.log(math.log(c,10),10) a = input2[i-1] b = input2[i-2] if len(input2) <3: valueB = a*math.log(b,10) else: c= input[i-3] valueB = a*math.log(b,10) +math.log(math.log(c,10),10) if valueA > valueB: print "tower A is bigger." else: print "tower B is bigger."
June 4th, 2013, 05:44 AM   #12
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Power Tower Size

Quote:
 Originally Posted by phillip1882 2^1000000 is not exponential length. its a number. numbers have fixed length, not exponential.
You don't understand the problem, then. You're asked to find a solution which takes time << L^n where n is fixed and L is the total length of the input. So you won't be able to write out the full decimal form of the numbers, because that will grow at least exponentially with the size of the inputs.

June 4th, 2013, 05:48 AM   #13
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Power Tower Size

Quote:
 Originally Posted by phillip1882 beyond that, a number would have to be bigger than 1 followed by 10 trillion zeros to have a significant impact on the problem.
Almost all of the inputs will be bigger than that, though. Even a small tower like 9^9^9^9 has far more.

I agree that taking logarithms repeatedly is the main approach, but the corner cases are still hard to handle.

June 4th, 2013, 07:03 AM   #14
Member

Joined: May 2013

Posts: 35
Thanks: 1

Re: Power Tower Size

Quote:
 You don't understand the problem, then. You're asked to find a solution which takes time << L^n where n is fixed and L is the total length of the input. So you won't be able to write out the full decimal form of the numbers, because that will grow at least exponentially with the size of the inputs.
i agree, i wont be able to write out the result of the inputs. if you are doubling the input size, then i would agree, its exponential. i don't see that anywhere in the problem, the problem simply asks to evaluate a power tower, and each power can be done in log n time, but whatever.
Quote:
 Almost all of the inputs will be bigger than that, though. Even a small tower like 9^9^9^9 has far more. I agree that taking logarithms repeatedly is the main approach, but the corner cases are still hard to handle.
okay you don't get what i'm saying.
let's take two big powers and compare them.
is 2^3^4^5^6^7 greater than or less than 7^6^5^4^3^2?

5^6^7can be "evaluated" as 6*log 7 +log log 5 = 5.292.
4^3^2 can be "evaluated" as 2*log 3 + log log 4 =0.734.
now, if went to evaluating 4 exponents i would get the following.
4^5^6^7 ~ log(6^7*log 5 +log log 4) = 5.292
5^4^3^2 ~ log(3^2*log 4 +log log 5) = 0.721
as you can see, adding the fourth exponent hardly affects the problem at all. i may as well ignore the two additions and just evaluate the two left hand sides.
in order for the fourth exponent to matter the value itself would have to be really large. if i wanted to evaluate the 5th exponent, the value would have to be monstrous in order to effect the problem one iota.

June 4th, 2013, 07:13 AM   #15
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Power Tower Size

Quote:
 Originally Posted by phillip1882 i agree, i wont be able to write out the result of the inputs. if you are doubling the input size, then i would agree, its exponential. i don't see that anywhere in the problem, the problem simply asks to evaluate a power tower, and each power can be done in log n time, but whatever.
It's explicit in the question:

Is this problem in the class P?
If yes, then what is the algorithm solving it in polynomial time?
Otherwise, what is the fastest algorithm that can solve it?

The asker wants a polytime-solution, so in particular you can't write out the numbers in their full form.

Quote:
 Originally Posted by phillip1882 okay you don't get what i'm saying.
I perfectly understand the taking of logarithms here -- in fact I believe I was the first one to mention it on this thread. (Not that this means much, it's the obvious way to solve such a problem.) But there are plenty of examples of powers that are close to each other. For example, which is larger, 3^6586818670 or 2^10439860591?

(To make the problem harder you could also allow the tetration operator explicitly, which would allow you to describe larger towers with a small length. Then you wouldn't even be able to take the requisite number of logarithms at all, let alone at high precision.)

 Tags power, size, tower

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post BenFRayfield Applied Math 4 December 21st, 2013 10:58 PM rakmo Algebra 3 March 28th, 2013 05:20 AM cknapp Applied Math 3 December 16th, 2007 09:32 AM picco Abstract Algebra 1 October 27th, 2007 08:22 PM Arley Calculus 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top