Example code - Prime numbers optimization - Revision history

WikiSysop at 09:55, 20 June 2024

2024-06-20T09:55:20Z

← Older revision		Revision as of 11:55, 20 June 2024
Line 1:		Line 1:
	This is going to be a long, but quite instructive rant about various optimization ideas and techniques.<br>		This is going to be a long, but quite instructive rant about various optimization ideas and techniques.<br>
	Let us start with my "classic" prime number generator. The idea is to see how long time is takes to find/generate the primes between 0 and 100000000 (100 millions) and use that as a measure for performance. I need to point out that the basic speed of the computer plays a big role in getting these numbers.		Let us start with my "classic" prime number generator. The idea is to see how long time it takes to find/generate the primes between 0 and 100000000 (100 millions) and use that as a measure for performance. I need to point out that the basic speed of the computer plays a big role in getting these numbers.

	We know that primes are integers which can only be divided by 1 and the primes itself. Therefore it is an obvious idea to evaluate if a number is a prime by starting to divide it by 2, 3, 4 ...n all the way up to the number itself and if it can be divided at any point, it is not a prime.<br>		We know that primes are integers which can only be divided by 1 and the primes itself and are larger than 1. Therefore it is an obvious idea to evaluate if a number is a prime by starting to divide it by 2, 3, 4 ...n all the way up to the number itself and if it can be divided at any point, it is not a prime.<br>
	This basic idea can be improved in various ways.		This basic idea can be improved in various ways.
	* It is not necessary to divide ~~with~~ all the numbers up to n (the prospective prime). It is sufficient to divide with the numbers up to sqrt(n). This is because for any number where '''bignum * smallnum = n''' it also goes that '''smallnum * bignum = n''', which means we only need to find the small number ~~which~~ is a divisor, to identify ~~the number~~ as not-prime. ~~The small number will always be less or equal~~ to sqrt(n), ~~and the big number will always~~ be ~~greater~~ or equal to sqrt(n)~~. sqrt(n) is the equilibrium~~.		* It is not necessary to divide by all the numbers up to n (the prospective prime). It is sufficient to divide with the numbers up to sqrt(n). This is because for any number where '''bignum * smallnum = n''' it also goes that '''smallnum * bignum = n''', which means we only need to find the small number that is a divisor, to identify n as not-prime. When considering pairs of numbers that multiply to n, once you reach sqrt(n) the factors starts repeating in reverse order. This means for every factor pair, at least one of them needs to be less or equal to sqrt(n).
	* All even numbers do not need to be checked. They are all not-primes, except 2. This means the sequence of numbers you test for division of n are odd, i.e. 3, 5, 7, 9, 11 ... sqrt(n).		* All even numbers do not need to be checked. They are all not-primes, except 2. This means the sequence of numbers you test for division of n are odd, i.e. 3, 5, 7, 9, 11 ... sqrt(n).
	* Actually, this can be improved as you only have to divide n by the primes in the testing, not all odd numbers. If you can divide n with an odd number, which is not a prime, then the odd number is a composite of at least two other smaller numbers, which you have tested for earlier.		* Actually, this can be improved as you only have to divide n by the primes in the testing, not all odd numbers. If you can divide n with an odd number, which is not a prime, then the odd number is a composite of at least two other smaller numbers, which you have tested for earlier.
Line 89:		Line 89:

	== The sieve of Eratosthanes ==		== The sieve of Eratosthanes ==
	This old Greek figured out another method for computing the primes until "some number". You initialize a list n long with just True on every position. The True means 'this is a prime' for the number given by the position. Initially position 0 and 1 is set to False, as they are obviously not primes. Now you find the next True in the list, which would be a position 2. When a True is found, then go through the entire list in jumps of the number/position and ~~the~~ the value to False. The first time this happens is with 2, so position 4, 6, 8... will be set to False. These are the even numbers or more importantly the numbers that can be divided by 2 and are therefore not primes - they are composite numbers. The next position/number in the list is 3, so run through the list in jumps of 3 and set the value to False at the position, i.e. 6 (already False), 9, 12 (already False), 15 ...<br>		This old Greek figured out another method for computing the primes until "some number". You initialize a list n long with just True on every position. The True means 'this is a prime' for the number given by the position. Initially position 0 and 1 is set to False, as they are obviously not primes. Now you find the next True in the list, which would be a position 2. When a True is found, then go through the entire list in jumps of the number/position and the value to False. The first time this happens is with 2, so position 4, 6, 8... will be set to False. These are the even numbers or more importantly the numbers that can be divided by 2 and are therefore not primes - they are composite numbers. The next position/number in the list is 3, so run through the list in jumps of 3 and set the value to False at the position, i.e. 6 (already False), 9, 12 (already False), 15 ...<br>
	Continue this pattern until the next True position is more than sqrt(n), at which point you can stop for the reasons already stated for the previous method.<br>		Continue this pattern until the next True position is more than sqrt(n), at which point you can stop for the reasons already stated for the previous method.<br>
	The sieve is really about eliminating all composite numbers in the list more than finding primes. It is of course the same thing, but from different viewpoints.		The sieve is really about eliminating all composite numbers in the list more than finding primes. It is of course the same thing, but from different viewpoints.

WikiSysop: /* The sieve of Eratosthanes */

2024-06-18T10:00:18Z

The sieve of Eratosthanes

← Older revision		Revision as of 12:00, 18 June 2024
Line 181:		Line 181:
	A memory optimization could be to use the entire bytearray as a bit vector, instead of the 0/1 byte vector use now. This will expand memory capacity, i.e. how many primes we could find, but at the cost of performance; semi-complicated position calculation and bit modification would have to be done, and slicing could not be used.		A memory optimization could be to use the entire bytearray as a bit vector, instead of the 0/1 byte vector use now. This will expand memory capacity, i.e. how many primes we could find, but at the cost of performance; semi-complicated position calculation and bit modification would have to be done, and slicing could not be used.

	Please do not think that code you read here was something I "just made". I spend a long time trying ~~various~~ ideas, making mistakes underway.		Please do not think that code you read here was something I "just made". I spend a long time trying variations of these ideas, making mistakes underway. What you see is the best version of a particular optimization idea.

	The code was run like:		The code was run like:
	time python3 mycode.py > resultfile.txt		time python3 mycode.py > resultfile.txt

WikiSysop: /* The sieve of Eratosthanes */

2024-06-18T09:52:18Z

The sieve of Eratosthanes

← Older revision		Revision as of 11:52, 18 June 2024
Line 184:		Line 184:

	The code was run like:		The code was run like:
	time ~~python~~ mycode.py > resultfile.txt		time python3 mycode.py > resultfile.txt

WikiSysop: /* The sieve of Eratosthanes */

2024-06-18T09:51:48Z

The sieve of Eratosthanes

← Older revision		Revision as of 11:51, 18 June 2024
Line 174:		Line 174:
	array[ii::i] = [1] ((size // i) - i +1)		array[ii::i] = [1] ((size // i) - i +1)
	return [i for i in range(size+1) if not array[i]]		return [i for i in range(size+1) if not array[i]]

			for i in eratosthenes4(100000000):
			print(i)
	</pre>		</pre>

Line 179:		Line 182:

	Please do not think that code you read here was something I "just made". I spend a long time trying various ideas, making mistakes underway.		Please do not think that code you read here was something I "just made". I spend a long time trying various ideas, making mistakes underway.

			The code was run like:
			time python mycode.py > resultfile.txt

WikiSysop: /* The sieve of Eratosthanes */

2024-06-18T09:49:46Z

The sieve of Eratosthanes

← Older revision		Revision as of 11:49, 18 June 2024
Line 100:		Line 100:
	array = [True] * size		array = [True] * size
	array[0] = array[1] = False		array[0] = array[1] = False
	for i in range(int(size**0.5)):		for i in range(int(size**0.5)+1):
	if array[i]:		if array[i]:
	# A prime, now get rid of all composites where this prime is a divisor		# A prime, now get rid of all composites where this prime is a divisor
Line 120:		Line 120:
	array = bytearray(size)		array = bytearray(size)
	array[0] = array[1] = 1		array[0] = array[1] = 1
	for i in range(int(size**0.5)):		for i in range(int(size**0.5)+1):
	if array[i] == 0:		if array[i] == 0:
	# A prime, now get rid of all composites where this prime is a divisor		# A prime, now get rid of all composites where this prime is a divisor
Line 143:		Line 143:
	with		with
	for j in range(i*i, size, i):		for j in range(i*i, size, i):
	This is not extremely obvious. If, say 7, is the prime we found, then we start with eliminating 14, 21, 28, 35, 42, i.e. 7*n where 1 < n < 7. However, these numbers have already been eliminated earlier by other primes; 2, 3 & 5.<br>		This is not extremely obvious. If, say 7, is the prime, p, we found, then we start with eliminating 14, 21, 28, 35, 42, i.e. p*n where 1 < n < p. However, these numbers have already been eliminated earlier by other primes; 2, 3 & 5. The insight is that all the numbers from 2 (0 & 1 does not count here) up to - but not including - p has already been through the sieve. The numbers 1 < n < p are simply primes or composite primes (2 or more primes multiplied together) and as they are smaller than p, they have already been through the procedure/sieve.<br>

	Time: 11.9 sec.		Time: 11.9 sec.
Line 151:		Line 151:
	array = bytearray(size)		array = bytearray(size)
	array[0] = array[1] = 1		array[0] = array[1] = 1
	for i in range(int(size**0.5)):		for i in range(int(size**0.5)+1):
	if array[i] == 0:		if array[i] == 0:
	# A prime, now get rid of all composites where this prime is a divisor		# A prime, now get rid of all composites where this prime is a divisor
Line 164:		Line 164:
	When we have lists or bytearrays, we can use slicing, or more specifically slice assignment. In other words, the inner loop can be replaced with a slice assignment. This trick works only because it is a very regular piece of the bytearray we replace. Good trick, nonetheless.		When we have lists or bytearrays, we can use slicing, or more specifically slice assignment. In other words, the inner loop can be replaced with a slice assignment. This trick works only because it is a very regular piece of the bytearray we replace. Good trick, nonetheless.

	Time: 7.4 sec.		Time: 7.5 sec.
	<pre>		<pre>
	def eratosthenes4(size):		def eratosthenes4(size):
	size += 1 # Adjust for zero based list		array = bytearray(size+1) # Adjust for zero based list
	~~array = bytearray(size)~~
	array[0] = array[1] = 1		array[0] = array[1] = 1
	for i in range(int(size**0.5)):		for i in range(int(size**0.5)+1):
	if array[i] == 0:		if array[i] == 0:
	# A prime, now get rid of all composites where this prime is a divisor		# A prime, now get rid of all composites where this prime is a divisor
	array[ii:~~size~~:i] = [1] (((size~~-1)~~ // i) - i +1)		array[ii::i] = [1] ((size // i) - i +1)
	return [i for i in range(size) if not array[i]]		return [i for i in range(size+1) if not array[i]]
	</pre>		</pre>

			A memory optimization could be to use the entire bytearray as a bit vector, instead of the 0/1 byte vector use now. This will expand memory capacity, i.e. how many primes we could find, but at the cost of performance; semi-complicated position calculation and bit modification would have to be done, and slicing could not be used.

			Please do not think that code you read here was something I "just made". I spend a long time trying various ideas, making mistakes underway.

WikiSysop: /* The sieve of Eratosthanes */

2024-06-17T15:11:42Z

The sieve of Eratosthanes

← Older revision		Revision as of 17:11, 17 June 2024
Line 166:		Line 166:
	Time: 7.4 sec.		Time: 7.4 sec.
	<pre>		<pre>
	~~from math import ceil~~
	def eratosthenes4(size):		def eratosthenes4(size):
	size += 1 # Adjust for zero based list		size += 1 # Adjust for zero based list

WikiSysop: /* The sieve of Eratosthanes */

2024-06-17T15:11:25Z

The sieve of Eratosthanes

← Older revision		Revision as of 17:11, 17 June 2024
Line 166:		Line 166:
	Time: 7.4 sec.		Time: 7.4 sec.
	<pre>		<pre>
			from math import ceil
	def eratosthenes4(size):		def eratosthenes4(size):
	size += 1 # Adjust for zero based list		size += 1 # Adjust for zero based list
	array = bytearray(size)		array = bytearray(size)
	array[0] = array[1] = 1		array[0] = array[1] = 1
	~~pos = 2~~
	for i in range(int(size**0.5)):		for i in range(int(size**0.5)):
	if array[i] == 0:		if array[i] == 0:
	# A prime, now get rid of all composites where this prime is a divisor		# A prime, now get rid of all composites where this prime is a divisor
	array[ii:size:i] = [1] (~~ceil~~(size / i) - i)		array[ii:size:i] = [1] (((size-1) // i) - i +1)
	return [i for i in range(size) if not array[i]]		return [i for i in range(size) if not array[i]]
	</pre>		</pre>
	In the course we have seen a few times how the ''find'' method has been used for good performance boost. This method can also be used here. We need to find the 0's in the array and we know that primes occur less and less frequently as they get bigger. This means most of the places in the array are 1's. Why use a python loop to search? The internal loop in the ''find'' method is much more efficient.

WikiSysop: /* The sieve of Eratosthanes */

2024-06-17T14:37:14Z

The sieve of Eratosthanes

← Older revision		Revision as of 16:37, 17 June 2024
Line 139:		Line 139:
	Code not shown.		Code not shown.

			A common optimization is replacing
			for j in range(i+i, size, i):
			with
			for j in range(i*i, size, i):
			This is not extremely obvious. If, say 7, is the prime we found, then we start with eliminating 14, 21, 28, 35, 42, i.e. 7*n where 1 < n < 7. However, these numbers have already been eliminated earlier by other primes; 2, 3 & 5.<br>

			Time: 11.9 sec.
			<pre>
			def eratosthenes3(size):
			size += 1 # Adjust for zero based list
			array = bytearray(size)
			array[0] = array[1] = 1
			for i in range(int(size**0.5)):
			if array[i] == 0:
			# A prime, now get rid of all composites where this prime is a divisor
			for j in range(i*i, size, i):
			array[j] = 1
			return [i for i in range(size) if not array[i]]

			for i in eratosthenes3(100000000):
			print(i)
			</pre>

			When we have lists or bytearrays, we can use slicing, or more specifically slice assignment. In other words, the inner loop can be replaced with a slice assignment. This trick works only because it is a very regular piece of the bytearray we replace. Good trick, nonetheless.

			Time: 7.4 sec.
			<pre>
			def eratosthenes4(size):
			size += 1 # Adjust for zero based list
			array = bytearray(size)
			array[0] = array[1] = 1
			pos = 2
			for i in range(int(size**0.5)):
			if array[i] == 0:
			# A prime, now get rid of all composites where this prime is a divisor
			array[ii:size:i] = [1] (ceil(size / i) - i)
			return [i for i in range(size) if not array[i]]
			</pre>
	In the course we have seen a few times how the ''find'' method has been used for good performance boost. This method can also be used here. We need to find the 0's in the array and we know that primes occur less and less frequently as they get bigger. This means most of the places in the array are 1's. Why use a python loop to search? The internal loop in the ''find'' method is much more efficient.		In the course we have seen a few times how the ''find'' method has been used for good performance boost. This method can also be used here. We need to find the 0's in the array and we know that primes occur less and less frequently as they get bigger. This means most of the places in the array are 1's. Why use a python loop to search? The internal loop in the ''find'' method is much more efficient.

WikiSysop: /* The sieve of Eratosthanes */

2024-06-17T14:08:02Z

The sieve of Eratosthanes

← Older revision		Revision as of 16:08, 17 June 2024
Line 92:		Line 92:
	Continue this pattern until the next True position is more than sqrt(n), at which point you can stop for the reasons already stated for the previous method.<br>		Continue this pattern until the next True position is more than sqrt(n), at which point you can stop for the reasons already stated for the previous method.<br>
	The sieve is really about eliminating all composite numbers in the list more than finding primes. It is of course the same thing, but from different viewpoints.		The sieve is really about eliminating all composite numbers in the list more than finding primes. It is of course the same thing, but from different viewpoints.
			Part of what makes the sieve efficient is that we get rid of all the divisions, which take a lot of time.

	Time: 18.6 sec.		Time: 18.6 sec.

WikiSysop: /* The sieve of Eratosthanes */

2024-06-17T13:56:35Z

The sieve of Eratosthanes

← Older revision		Revision as of 15:56, 17 June 2024
Line 129:		Line 129:
	print(i)		print(i)
	</pre>		</pre>

			The return statement contains a comparison, which can be eliminated with an enumeration, or removed by a negation.
			* return [i for i, is_prime in enumerate(array) if not is_prime]
			* return [i for i in range(size) if not array[i]]
			It comes out to approximately the same improvement.

			Time: 12.2 sec.<br>
			Code not shown.

			In the course we have seen a few times how the ''find'' method has been used for good performance boost. This method can also be used here. We need to find the 0's in the array and we know that primes occur less and less frequently as they get bigger. This means most of the places in the array are 1's. Why use a python loop to search? The internal loop in the ''find'' method is much more efficient.