Monday, October 27, 2008

Project Euler p99

Project Euler problem 99 description:
Comparing two numbers written in index form like 2^11 and 3^7 is not difficult, as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.

However, confirming that 632382^518061 > 519432^525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.
The trick of solution is not to compare whole numbers (because raising to power will be too much CPU time and memory consuming operation), instead we can compare logarithms of numbers. So actually we will compare LOG(number^power). Ok, but we still have to do power operation ? Well, no more ! By applying known logarithm formula: LOG(number^power) = power*LOG(number). So we are comparing power*LOG(number). This is very fast operation.
Problem solution is found in a 3.7 ms. Solution Python code:

import time as tm
import math as m

t1 = tm.time()*1000
f=open('base_exp.txt', 'r')
l=[i.strip().split(",")+[n+1] for (n,i) in enumerate(f.readlines())]
l = map(lambda i: (int(i[0]),int(i[1]), i[2]), l)
l = map(lambda (x,a,n): (a*m.log(x), n), l)
max = max(l)
t2 = tm.time()*1000

print max,t2-t1,'ms'

Have fun!

No comments:

Post a Comment

Comment will be posted after comment moderation.
Thank you for your appreciation.