Problem #97

Now this prob­lem was inter­est­ing! It asked for us to find the last 10 dig­its of a very large Mersenne Prime dis­cov­ered in 2004 of the form 28433×27830457+1.

I solved this prob­lem three dif­fer­ent ways. The first was by my own logic, the other two, due to some research. My thought was that cal­cu­lat­ing 2n can be done in a loop that mul­ti­plies the pre­vi­ous value by 2 on each iter­a­tion. Rais­ing it to the 7,830,457th power though would not only take for­ever, but could be hard to store in mem­ory. So I fig­ured that we really only care about the last 10 dig­its. This meant I could mul­ti­ple the pre­vi­ous value by 2 on each iter­a­tion, but store for the next iter­a­tion a con­sist­ing of only the last ten dig­its. Python’s list syn­tax of [-10:] came in mighty handy for this.

My Method
==============
Result: 8739992577
Time: 9.89434504509

def my_method():
    print ““
    print “My Method“
    print “==============“
    last=“2”
    start = time.time()
    for p in range(2,7830458):
        last = str(int(last)*2)
        last = last[-10:]
    result =  str(28433*int(last)+1)
    stop = time.time()
    print “Result: “+result[-10:]
    print “Time: “+str(stop-start)

It was fairly quick, sub 10 sec­onds, but not as fast as it could be.

The next method I tried was to uti­lize the bit­wise shift oper­a­tor. I saw this for a C++ solu­tion in the forums after solv­ing it and won­dered if Python had a bit­wise shift. Turns out it does. Hav­ing a base of 2 for the pow­ers is what makes this pos­si­ble. Rather than mul­ti­ply­ing a num­ber by 2, we can shift it’s binary value to the left by one posi­tion for the same affect. CPU’s are typ­i­cally faster at bit shift­ing than they are at mul­ti­ply­ing. This solu­tion took less than 2 sec­onds! That’s quite an improvement.

Bit­wise Method
==============
Result: 8739992577
Time: 1.6119530201

def bit­wise():
    print ““
    print “Bit­wise Method“
    print “==============“
    start = time.time()
    ans = 1
    for n in range(1,7830458):
        ans = ans « 1
        ans = ans % 10000000000
    ans = ans * 28433
    ans = ans % 10000000000
    ans = ans + 1
    stop = time.time()
    print “Result: “+str(ans)
    print “Time: “+str(stop-start)

I’m not sure how, but I ended up read­ing this arti­cle on OSIX about quickly cal­cu­lat­ing inte­ger pow­ers. It pro­posed a func­tion in C# that used recur­sion to cal­cu­late a power in O(logn) time rather than the O(n) time that the first two meth­ods imple­mented. I trans­lated the code to Python, and sure enough, it solves this prob­lem in less than half of a second!

Power Method
==============
Result: 8739992577
Time: 0.471854925156

def get_power(a,n): # a^n
    if n==0:
        return 1
    if a==0:
        return 0
    if n%2==0:
        return get_power(a*a, n/2)
    else:
        return a*get_power(a*a, n/2)
    return 0

def power():
    print ““
    print “Power Method“
    print “==============“
    start = time.time()
    value = get_power(2,7830457)
    ans = 28433*value+1
    ans = ans % 10000000000
    stop = time.time()
    print “Result: “+str(ans)
    print “Time: “+str(stop-start)

One thought on “Problem #97

  1. Pingback: Problem #53 « rarmknecht

Leave a Reply