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.
Forum Search
Forum Statistics
UsersTotal Post History
 Posts:
 81456
 Topics:
 18718
7Day Post History
 New Posts:
 0
 New Topics:
 0
 Active Topics:
 0
Our newest member
Other

FAQ
All times are UTC [ DST ]
code optimization?
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
7 posts • Page 1 of 1
Please wait...
code optimization?
hey guys, working on a programming problem, thought maybe you could help.
here's what i have so far.
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?
here's what i have so far.
 #test whether a given number is prime using rabinmiller test.
 import random
 import math
 n = int(input("what value would you like to check for primality?\n"))
 s = 0
 d = n1
 while d&1 == 0:
 d = d >>1
 s += 1
 iter = math.log(math.log(n))
 i = 0
 while i < iter:
 start = 1
 witness = int(math.sqrt(n)*random.random()+1)
 value = witness
 while start < d:
 if start <<1 < d:
 value *= value
 start = start<<1
 else:
 d = start
 value = value*witness
 start = 1
 if value > n: #don't need to do this quite so often.
 value %= n
 check = False
 if value == 1:
 check = True
 elif nvalue == 1:
 check = True
 else:
 r = 1
 while r <s:
 value *= value
 value %= n
 r += 1
 if nvalue == 1:
 check = True
 break
 if not check:
 print(n,"is composite,",witness,"is a witness.")
 break
 else:
 i += 1
 print(n,"is probably prime by",witness)
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?

phillip1882  Apprentice
 Posts: 19
 Joined: Mon Mar 14, 2011 11:05 pm
 Location: florida
Re: code optimization?
There are only 78,498 prime numbers between 2 and 1,000,000. I would be tempted to precalculate all the primes and then do a simple database lookup.
George

gmmastros  LTD Admin

 Posts: 2369
 Joined: Tue Oct 09, 2007 5:19 pm
Re: code optimization?
There are a couple of solutions here: Topic1938: LTD Puzzle 4: Finding Prime Numbers
Denis The SQL Menace
Personal and/or non database related blog
Personal and/or non database related blog

SQLDenis  LTD Admin

 Posts: 21784
 Joined: Wed Oct 10, 2007 6:43 pm
 Location: Princeton, New Jersey, USA,World, Solar System, Milky Way, Universe and Beyond
Re: code optimization?
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^50000002^6000000 range.
(the largest probable prime is 2^4583176 +2131)
but here i would like to test for large primes; namely around 2^50000002^6000000 range.
(the largest probable prime is 2^4583176 +2131)

phillip1882  Apprentice
 Posts: 19
 Joined: Mon Mar 14, 2011 11:05 pm
 Location: florida

gmmastros  LTD Admin

 Posts: 2369
 Joined: Tue Oct 09, 2007 5:19 pm
Re: code optimization?
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.
"The trouble with quotes on the Internet is that it's Abraham Lincoln
difficult to determine whether or not they are genuine."

MHGlassman  Senior Apprentice
 Posts: 72
 Joined: Tue Jun 17, 2008 7:58 pm
 Location: Englewood, CO, USA
Re: code optimization?
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).
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.
 let isPrime n =
 let rec checkRemaining composite i num =
 if composite then false
 elif i*i > num then true else
 checkRemaining (num % i = 0I  num % (i + 2I) = 0I) (i + 6I) num
 if n<=1I then false
 elif n = 2I  n = 3I then true
 elif n &&& 1I = 0I  n % 3I = 0I then false //even or multiple of 3
 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

AlexCuse  LTD Admin

 Posts: 5524
 Joined: Tue Oct 09, 2007 5:26 pm
 Location: Pennsylvania, US
7 posts • Page 1 of 1
LTD Social Sitings
Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.