My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
June 4th, 2013, 01:27 AM   #11
Member
 
Joined: May 2013

Posts: 34
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."
phillip1882 is offline  
 
June 4th, 2013, 05:44 AM   #12
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
June 4th, 2013, 05:48 AM   #13
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
June 4th, 2013, 07:03 AM   #14
Member
 
Joined: May 2013

Posts: 34
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.
phillip1882 is offline  
June 4th, 2013, 07:13 AM   #15
Global Moderator
 
CRGreathouse's Avatar
 
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.)
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
power, size, tower



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Set size is relative - Same topology of negative size sets BenFRayfield Applied Math 4 December 21st, 2013 10:58 PM
Height of the tower rakmo Algebra 3 March 28th, 2013 05:20 AM
Size of subset of power set.... cknapp Applied Math 3 December 16th, 2007 09:32 AM
What is a Tower? picco Abstract Algebra 1 October 27th, 2007 08:22 PM
THE LEANING TOWER OF PISA Arley Calculus 0 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.