Solution to storing HUGE numbers in a variable

[sravan953]

Hey all,

I'm working on a program where I calculate powers of two upto 60. I've made my own formula for calculating it which is: 10^([value of log 2 here]*y), where 'y' is any power as big as, say, 31. So here it is:

two=0.301029995664
final=math.pow(10,(two*n))-1

Now... as the value of 'y' gets bigger and bigger, the numbers are displayed as, for example: 2.19902325555e+12

How do I make the prog display the WHOLE number instead of e+12 and stuff?

Thanks a ton people...

[TrustyTony]

Why such a complicated way for simple calculation (directly 2**power). If you multiply by two, you get each concecutive power of two. I do not know why you say huge either, as numbers you give are quite small.

Here is my code (with alternative in commented form) for smallest powers of two upto 2**1000 :

two_to=1
for power in range(1001):
    print "2 to %i = %i\n" % (power,two_to) ## extra line change for bigger numbers
##    two_to*=2
    two_to=two_to<<1 # shift left one bit

[sravan953]

Can you please the '<<' part in detail? How does it work and what does it do!?

[jcao219]

You can do this

longnumber = long(longnumber)
#and it should display the whole thing

The << is operation left-shift.

[TrustyTony]

It adds one zero to binary number:
1<<1=0b10=2
2<<1=0b100=4

This operation is in the fastest class of instructions, so using it is considered efficient coding.

It is equivalent to the multiply by 2:
=*2

[TrustyTony]

As I tested in Python 2.6 is also possible to say:

two_to <<= 1

instead of

two_to = two_to << 1

Using long() hits soon the inaccuracy of float numbers:

two=0.301029995664
two_to = 1
for power in range(1001):
    print "2 to %i = %i\n" % (power,two_to) ## extra \n for long numbers
    final=long(10**(two*power)) ## NO -1
    assert final == two_to, "Inaccurate 2**%i: wrong %i != %i" % (power, final, two_to)
##    two_to *= 2
    two_to <<= 1 # shift left one bit
""" Last line of output:
AssertionError: Inaccurate 2**40: wrong 1099511627777 != 1099511627776
"""

Maybe does not give best impression of your program if it gives odd value for power of two!

[sravan953]

Well, here's the whole program:

import math

def prime(n):
    c=0

    for x in range(1,n):
        if(n%x==0):
            c+=1

    if(c==1):
        mersenne(n)

def mersenne(n):
    t=2
    
    for x in range(1,n):
        t=t<<1

    t=t-1
 
    n=str(n)
    print(n+" -- "+str(len(n)))
    print

for x in range(10000):
    prime(x)

raw_input()

When I ran this piece of code, I got numbers of length upto 3003... now I face another obstacle, how do I check if this number is a prime? I know there are many algorithms out there, but those are incomprehensible for me, and hence I am not attempting to incorporate them into my program. I came up with this final version, which, lol, doesn't work:

import math

def prime(n):
    c=0

    for x in range(1,n):
        if(n%x==0):
            c+=1

    if(c==1):
        mersenne(n)

def mersenne(n):
    t=2
    
    for x in range(1,n):
        t=t<<1

    t=t-1

    primality(t)

def primality(n):
    c=0
    l=int(math.sqrt(n))
    
    for x in range(1,l):
        if(n%x==0):
            c+=1

    if(c==1):
        n=str(n)
        print(n+" -- "+str(len(n)))
        print

for x in range(10000):
    prime(x)

raw_input()

This "primality test" doesn't work. So please tell me what I should do.

Thanks!

[TrustyTony]

For mersenne numbers you should use Lucas-Lehmer test:
http://rosettacode.org/wiki/Lucas-Lehmer_test#Python

from sys import stdout
from math import sqrt, log
 
def is_prime ( p ):
  if p == 2: return True # Lucas-Lehmer test only works on odd primes
  elif p <= 1 or p % 2 == 0: return False
  else:
    for i in range(3, int(sqrt(p))+1, 2 ): 
      if p % i == 0: return False
    return True
 
def is_mersenne_prime ( p ):
  if p == 2:
    return True
  else:
    m_p = ( 1 << p ) - 1
    s = 4
    for i in range(3, p+1): 
      s = (s ** 2 - 2) % m_p
    return s == 0
 
precision = 20000   # maximum requested number of decimal places of 2 ** MP-1 #
long_bits_width = precision / log(2) * log(10)
upb_prime = int( long_bits_width - 1 ) / 2    # no unsigned #
upb_count = 45      # find 45 mprimes if int was given enough bits #
 
print (" Finding Mersenne primes in M[2..%d]:"%upb_prime)
 
count=0
for p in range(2, upb_prime+1): 
  if is_prime(p) and is_mersenne_prime(p):
    print("M%d"%p),
    stdout.flush()
    count += 1
  if count >= upb_count: break
print

You can speed is_prime up if you know primes<n by checking only for prime factors in sieve generated for example by sieve of Eratosthenes saved/loaded in file.

[sravan953]

For mersenne numbers you should use Lucas-Lehmer test:
http://rosettacode.org/wiki/Lucas-Lehmer_test#Python

from sys import stdout
from math import sqrt, log
 
def is_prime ( p ):
  if p == 2: return True # Lucas-Lehmer test only works on odd primes
  elif p <= 1 or p % 2 == 0: return False
  else:
    for i in range(3, int(sqrt(p))+1, 2 ): 
      if p % i == 0: return False
    return True
 
def is_mersenne_prime ( p ):
  if p == 2:
    return True
  else:
    m_p = ( 1 << p ) - 1
    s = 4
    for i in range(3, p+1): 
      s = (s ** 2 - 2) % m_p
    return s == 0
 
precision = 20000   # maximum requested number of decimal places of 2 ** MP-1 #
long_bits_width = precision / log(2) * log(10)
upb_prime = int( long_bits_width - 1 ) / 2    # no unsigned #
upb_count = 45      # find 45 mprimes if int was given enough bits #
 
print (" Finding Mersenne primes in M[2..%d]:"%upb_prime)
 
count=0
for p in range(2, upb_prime+1): 
  if is_prime(p) and is_mersenne_prime(p):
    print("M%d"%p),
    stdout.flush()
    count += 1
  if count >= upb_count: break
print

You can speed is_prime up if you know primes<n by checking only for prime factors in sieve generated for example by sieve of Eratosthenes saved/loaded in file.

Like I said, I dont understand it a bit. :confused:
Any alternative solutions. Sorry for the trouble! >_>

[TrustyTony]

You could maybe rent all the computers of the world for next 100 000 years and try brute force?:-O

The proof of Lucas-Lehmer you can find for example in Knuth: The Art of Computer Programming Vol. 2: Seminumerical Algorithms, page 356.

[sravan953]

You could maybe rent all the computers of the world for next 100 000 years and try brute force?:-O

The proof of Lucas-Lehmer you can find for example in Knuth: The Art of Computer Programming Vol. 2: Seminumerical Algorithms, page 356.

:|

[TrustyTony]

To spell it out: There is not alternative of brute force with big prime numbers, that's why they are used as base for strong encrypting.