[Math][Python] Project Euler #99 and logarithmic representation

From their website:

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):

    return [item.rstrip() for item in ar]

print ("generic algo:", tmp)
# log with other base would also work!
# but here using natural log base for simplicity
print ("using log:   ", math.exp(tmp))

assert x>y

lst=read_file ("p099_base_exp.txt")
for l in lst:
    x,y = int(t[0]),int(t[1])
    if r>_max:
    #print (line, x, y, r)

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)

This coincides with Wolfram Mathematica's output. This number has 3005261 decimal digits. All correct.

(the post first published at 20220728.)

List of my other blog posts.

Subscribe to my news feed

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.