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.
This is a problem where logarithmic representation of number can be used. We compute power not for numbers, but for their logarithmic representation. And they consumes way less RAM. Also, this is much faster. In fact, John Napier invented logarithms to ease multiplication operation.
Since we only need info, which number is bigger, logarithmic representations are enough: they obey this law as well.
#!/usr/bin/env python3 import math def read_file(filename): f=open(filename,"r") ar=f.readlines() f.close() return [item.rstrip() for item in ar] tmp=123**45 print ("generic algo:", tmp) # log with other base would also work! # but here using natural log base for simplicity tmp=math.log(123)*45 print ("using log: ", math.exp(tmp)) x=math.log(632382)*518061 y=math.log(519432)*525806 assert x>y lst=read_file ("p099_base_exp.txt") line=1 _max=0 max_line=None for l in lst: t=l.split(",") x,y = int(t[0]),int(t[1]) r=math.log(x)*y if r>_max: max_line=line _max=r #print (line, x, y, r) line=line+1 print (max_line, _max)
The result:
generic algo: 11110408185131956285910790587176451918559153212268021823629073199866111001242743283966127048043 using log: 1.111040818513185e+94 709 6919995.552420337
Spoiler: Wolfram Mathematica can operate on such big numbers without additional assistance. In fact, I first solved this problem using it.
BTW, we can verify Project Euler's author's statement about "as both numbers contain over three million digits" using decimal logarithm instead of natural:
#!/usr/bin/env python3 import math tmp=math.log(632382, 10)*518061 print (tmp)
3005261.2406258043
This coincides with Wolfram Mathematica's output. This number has 3005261 decimal digits. All correct.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.