Login or Sign Up to become a member!
LessThanDot Site Logo

LessThanDot

A Technical Community for IT Professionals

Less Than Dot is a community of passionate IT professionals and enthusiasts dedicated to sharing technical knowledge, experience, and assistance. Inside you will find reference materials, interesting technical discussions, and expert tips and commentary. Once you register for an account you will have immediate access to the forums and all past articles and commentaries.

LTD Social Sitings

Lessthandot twitter Lessthandot Linkedin Lessthandot facebook Lessthandot rss

Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.

Highly Rated Users

Forum
No Posts Rated

Top 50
Given
Received

Forum Statistics

Users
Members:
1875
Members Online:
2
Guests Online:
79

Total Post History
Posts:
81446
Topics:
18714

7-Day Post History
New Posts:
0
New Topics:
0
Active Topics:
0

Our newest member
konam534As

Other

FAQ
All times are UTC [ DST ]

Google Ads

code optimization?

Mind Boggling Puzzles, to keep that grey matter in shape...
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Please wait...

code optimization?

Postby phillip1882 on Mon Aug 22, 2011 3:44 pm

hey guys, working on a programming problem, thought maybe you could help.
here's what i have so far.
  1. #test whether a given number is prime using rabin-miller test.
  2. import random
  3. import math
  4. n = int(input("what value would you like to check for primality?\n"))
  5. s = 0
  6. d = n-1
  7. while d&1 == 0:
  8.    d = d >>1
  9.    s += 1
  10. iter = math.log(math.log(n))
  11. i = 0
  12. while i < iter:
  13.    start = 1
  14.    witness = int(math.sqrt(n)*random.random()+1)
  15.    value = witness
  16.    while start < d:
  17.       if start <<1 < d:
  18.          value *= value
  19.          start = start<<1
  20.       else:
  21.          d -= start
  22.          value = value*witness
  23.          start = 1
  24.       if value > n: #don't need to do this quite so often.
  25.          value %= n
  26.    check = False
  27.    if value == 1:
  28.       check = True
  29.    elif n-value == 1:
  30.       check = True
  31.    else:
  32.       r = 1
  33.       while r <s:  
  34.          value *= value
  35.          value %= n
  36.          r += 1
  37.          if n-value == 1:
  38.             check = True
  39.             break
  40.    if not check:
  41.       print(n,"is composite,",witness,"is a witness.")
  42.       break
  43.    else:
  44.       i += 1
  45.       print(n,"is probably prime by",witness)
  46.  

basically what i would like from you is ways i could improve the code.
already i see several points. one, i could add a faster multiplication function.
second, as i point out in the code, i don't have to do that modulus operation quite so often. and is there a way to speed up that operation as well?
finally, i would like of method of writing very large numbers in a compact format while still being able to do operations on them. any suggestions?
User avatar
phillip1882
Apprentice
Apprentice
LTD Bronze - Rating: 22
 
Posts: 19
Joined: Mon Mar 14, 2011 11:05 pm
Location: florida
Unrated

Re: code optimization?

Postby gmmastros on Mon Aug 22, 2011 3:55 pm

There are only 78,498 prime numbers between 2 and 1,000,000. I would be tempted to pre-calculate all the primes and then do a simple database lookup.
-George
User avatar
gmmastros
LTD Admin
LTD Admin
LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630
LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630
LTD Gold - Rating: 1630LTD Gold - Rating: 1630
 
Posts: 2367
Joined: Tue Oct 09, 2007 5:19 pm
Unrated

Re: code optimization?

Postby SQLDenis on Mon Aug 22, 2011 5:12 pm

There are a couple of solutions here: Topic1938: LTD Puzzle 4: Finding Prime Numbers
User avatar
SQLDenis
LTD Admin
LTD Admin
LTD Gold - Rating: 3467LTD Gold - Rating: 3467LTD Gold - Rating: 3467LTD Gold - Rating: 3467LTD Gold - Rating: 3467
LTD Gold - Rating: 3467LTD Gold - Rating: 3467LTD Gold - Rating: 3467LTD Gold - Rating: 3467LTD Gold - Rating: 3467
LTD Gold - Rating: 3467LTD Gold - Rating: 3467LTD Gold - Rating: 3467
 
Posts: 21784
Joined: Wed Oct 10, 2007 6:43 pm
Location: Princeton, New Jersey, USA,World, Solar System, Milky Way, Universe and Beyond
Unrated

Re: code optimization?

Postby phillip1882 on Mon Aug 22, 2011 9:05 pm

having prime numbers below 1,000,000 is nice, i can do that quite easily.
but here i would like to test for large primes; namely around 2^5000000-2^6000000 range.
(the largest probable prime is 2^4583176 +2131)
User avatar
phillip1882
Apprentice
Apprentice
LTD Bronze - Rating: 22
 
Posts: 19
Joined: Mon Mar 14, 2011 11:05 pm
Location: florida
Unrated

Re: code optimization?

Postby gmmastros on Mon Aug 22, 2011 11:13 pm

I see. In that case, please ignore my earlier suggestion.
-George
User avatar
gmmastros
LTD Admin
LTD Admin
LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630
LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630LTD Gold - Rating: 1630
LTD Gold - Rating: 1630LTD Gold - Rating: 1630
 
Posts: 2367
Joined: Tue Oct 09, 2007 5:19 pm
Unrated

Re: code optimization?

Postby MHGlassman on Tue Aug 23, 2011 12:48 am

phillip1882 wrote:(the largest probable prime is 2^4583176 +2131)


Are you saying that is the largest probable prime that you have found or that is the largest one period?

There is, of course, no largest prime. Assuming there were, you could multiply together all of known primes and add 1 to the product. This number would be prime to every known prime, contradicting the assumption that there is a largest prime. Therefore, there is no largest prime. :thumright:
"The trouble with quotes on the Internet is that it's 
difficult to determine whether or not they are genuine."
-- Abraham Lincoln
User avatar
MHGlassman
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 115LTD Bronze - Rating: 115LTD Bronze - Rating: 115
 
Posts: 72
Joined: Tue Jun 17, 2008 7:58 pm
Location: Englewood, CO, USA

Re: code optimization?

Postby AlexCuse on Thu Aug 25, 2011 2:29 pm

I'm not sure what this algorithm is called, but I found it in one of the supplemental docs on the project euler website (made available on problems page after you solve #7 - finding the 10001st prime).

  1. let isPrime n =
  2.     let rec checkRemaining composite i num =
  3.         if composite then false
  4.         elif i*i > num then true else
  5.         checkRemaining (num % i = 0I || num % (i + 2I) = 0I) (i + 6I) num
  6.  
  7.     if n<=1I then false
  8.     elif n = 2I || n = 3I then true
  9.     elif n &&& 1I = 0I || n % 3I = 0I then false //even or multiple of 3
  10.     else checkRemaining false 5I n


Never used the method you posted, but this has been reasonably fast for me, going well into the billions. I encourage you to read the document on the Project Euler site (http://projecteuler.net) and see if this works for you.
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1031LTD Gold - Rating: 1031LTD Gold - Rating: 1031LTD Gold - Rating: 1031LTD Gold - Rating: 1031
LTD Gold - Rating: 1031LTD Gold - Rating: 1031LTD Gold - Rating: 1031LTD Gold - Rating: 1031LTD Gold - Rating: 1031
LTD Gold - Rating: 1031
 
Posts: 5523
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated