Tutorials/Coding Life simulators/bitwise SWAR Life - Revision history

Confocal: state → cell state

2023-09-04T13:01:49Z

state → cell state

← Older revision		Revision as of 13:01, 4 September 2023
Line 1:		Line 1:
	<!--I am here forgoing the reiteration of long global statements in the program when functions call global-affecting inner functions-->		<!--I am here forgoing the reiteration of long global statements in the program when functions call global-affecting inner functions-->
	So you've decided to make a [[Life]] simulator that encodes [[state]]s as integers' binary representations? Excellent!		So you've decided to make a [[Life]] simulator that encodes [[cell state]]s as integers' binary representations? Excellent!
	==Prerequisites==		==Prerequisites==
	This will be teaching it in Python (using only the standard library), however the idea can be implemented irrespective of language. Note that though Python is often considered slow (due to being an interpreted language), bitwise operators on its integers take fixedly many Python instructions, so the only thing that changes as they become arbitrarily long is the underlying C implementation, which is much more efficient. This allowed David Buchanan's implementation to run at 1080p60fps (that is, 124416000 cells/second) on his machine.		This will be teaching it in Python (using only the standard library), however the idea can be implemented irrespective of language. Note that though Python is often considered slow (due to being an interpreted language), bitwise operators on its integers take fixedly many Python instructions, so the only thing that changes as they become arbitrarily long is the underlying C implementation, which is much more efficient. This allowed David Buchanan's implementation to run at 1080p60fps (that is, 124416000 cells/second) on his machine.

TYCF at 12:57, 4 September 2023

2023-09-04T12:57:24Z

← Older revision		Revision as of 12:57, 4 September 2023
Line 1:		Line 1:
	<!--I am here forgoing the reiteration of long global statements in the program when functions call global-affecting inner functions-->		<!--I am here forgoing the reiteration of long global statements in the program when functions call global-affecting inner functions-->
	So you've decided to make a Life simulator that encodes ~~states~~ as integers' binary representations? Excellent!		So you've decided to make a [[Life]] simulator that encodes [[state]]s as integers' binary representations? Excellent!
	==Prerequisites==		==Prerequisites==
	This will be teaching it in Python (using only the standard library), however the idea can be implemented irrespective of language. Note that though Python is often considered slow (due to being an interpreted language), bitwise operators on its integers take fixedly many Python instructions, so the only thing that changes as they become arbitrarily long is the underlying C implementation, which is much more efficient. This allowed David Buchanan's implementation to run at 1080p60fps (that is, 124416000 cells/second) on his machine.		This will be teaching it in Python (using only the standard library), however the idea can be implemented irrespective of language. Note that though Python is often considered slow (due to being an interpreted language), bitwise operators on its integers take fixedly many Python instructions, so the only thing that changes as they become arbitrarily long is the underlying C implementation, which is much more efficient. This allowed David Buchanan's implementation to run at 1080p60fps (that is, 124416000 cells/second) on his machine.

Confocal: /* External links */ cat

2023-03-10T08:09:29Z

External links: cat

← Older revision		Revision as of 08:09, 10 March 2023
Line 459:		Line 459:

	[[Category:Tutorials]]		[[Category:Tutorials]]
			[[Category:Algorithms]]

HotdogPi: Category:Tutorials

2023-02-10T17:59:14Z

Category:Tutorials

← Older revision		Revision as of 17:59, 10 February 2023
Line 457:		Line 457:
	* David Buchanan's [https://gist.github.com/DavidBuchanan314/acae2aab38953759aacc114b417ed0b9 gzip_swar_life.py] (Github gist), Life-only		* David Buchanan's [https://gist.github.com/DavidBuchanan314/acae2aab38953759aacc114b417ed0b9 gzip_swar_life.py] (Github gist), Life-only
	** DroneBetter's [https://gist.github.com/DroneBetter/4f5d775e7c37f062ce750d4a8fefc84a fork of which], a working implementation of everything more explained here		** DroneBetter's [https://gist.github.com/DroneBetter/4f5d775e7c37f062ce750d4a8fefc84a fork of which], a working implementation of everything more explained here

			[[Category:Tutorials]]

DroneBetter: Add table of functions in prerequisites at beginning (instead of explaining some simple ones and assuming knowledge of comparably obscure ones), enact proposals and improved diagram from my dear friend Redstoneboi from the forums

2022-12-28T18:03:27Z

Add table of functions in prerequisites at beginning (instead of explaining some simple ones and assuming knowledge of comparably obscure ones), enact proposals and improved diagram from my dear friend Redstoneboi from the forums

Show changes

DroneBetter: minor corrections of forgone words (it seems as though I deleted them by accident)

2022-12-27T21:33:26Z

minor corrections of forgone words (it seems as though I deleted them by accident)

← Older revision		Revision as of 21:33, 27 December 2022
Line 14:		Line 14:
	We know the amount to shift left and right to displace by one cell, four bits, so we add to the state itself shifted by 4 left and right. It will be encoded with consecutive rows concatenated, so to shift the state up and down we will shift by four bits times the width. (We can enact the summing in one dimension then the other to only have four shift-and-OR operations instead of eight.)		We know the amount to shift left and right to displace by one cell, four bits, so we add to the state itself shifted by 4 left and right. It will be encoded with consecutive rows concatenated, so to shift the state up and down we will shift by four bits times the width. (We can enact the summing in one dimension then the other to only have four shift-and-OR operations instead of eight.)

	Once we have this summed list, we would like a function that maps specific sum values to 0001 and others to 0000, we can whether a cell's sum value matches a given value by XORing it with the value's NOT (so that only cells with the value become 1111) then "folding" by ANDing with itself shifted right by two bits (such that the third and fourth 1s remain so only if the first and second are also), then one bit (such that the fourth 1 depends on all four), then discarding the preceding three by ANDing with 0001. This all seems at first a very arbitrary way to do it but each operation can be done across all cells simultaneously by enacting it upon the entire integer. This can be done once for value 0011 and again for 0100 (ANDed with the original state to ensure only on cells with four neighbours including themselves remain on), then these can be ORed together to yield the state after an iteration.		Once we have this summed list, we would like a function that maps specific sum values to 0001 and others to 0000, we can determine whether a cell's sum value matches a given value by XORing it with the value's NOT (so that only cells with the value become 1111) then "folding" by ANDing with itself shifted right by two bits (such that the third and fourth 1s remain so only if the first and second are also), then one bit (such that the fourth 1 depends on all four), then discarding the preceding three by ANDing with 0001. This all seems at first a very arbitrary way to do it but each operation can be done across all cells simultaneously by enacting it upon the entire integer. This can be done once for value 0011 and again for 0100 (ANDed with the original state to ensure only on cells with four neighbours including themselves remain on), then these can be ORed together to yield the state after an iteration.

	A problem with this way is that the leftmost cell in a row will believe the rightmost one in an adjacent row to be to its left, so there will be horizontal toroidal scrolling but not quite aligned with a square, and the top and bottom edges will be bounded. To fix this, we will create a one-cell margin along each edge, that we can put shifted copies of the inside of the opposing edge into to get aligned toroidal scrolling as well (and even reverse them to get other manifolds (Möbius strips, Klein bottles and real projective planes)).		A problem with this way is that the leftmost cell in a row will believe the rightmost one in an adjacent row to be to its left, so there will be horizontal toroidal scrolling but not quite aligned with a square, and the top and bottom edges will be bounded. To fix this, we will create a one-cell margin along each edge, that we can put shifted copies of the inside of the opposing edge into to get aligned toroidal scrolling as well (and even reverse them to get other manifolds (Möbius strips, Klein bottles and real projective planes)).
Line 66:		Line 66:
	manifold=(2,2)		manifold=(2,2)
	FPS=10		FPS=10
	</pre>Our simulator will work with arbitrary INT rules, but recognise OT ones as such to simulate in the more efficient way. (You could also make special-case optimisations for other things like INT rules [[von Neumann neighbourhood\|von Neumann rules]].)		</pre>Our simulator will work with arbitrary INT rules, but recognise OT ones as such to simulate in the more efficient way. (You could also make special-case optimisations for other things like INT rules encoding [[von Neumann neighbourhood\|von Neumann rules]].)
	The index of each of the 512 neighbourhood states is the number of which it's the binary representation, ie.<pre>		The index of each of the 512 neighbourhood states is the number of which it's the binary representation, ie.<pre>
	oo		oo

DroneBetter: you did not see anything (it was a uhhh misclick)

2022-12-27T20:35:14Z

you did not see anything (it was a uhhh misclick)

← Older revision		Revision as of 20:35, 27 December 2022
Line 4:		Line 4:
	This will be teaching it in Python (using only the standard library), however the idea can be implemented irrespective of language. Note that though Python is often considered slow (due to being an interpreted language), bitwise operators on its integers take fixedly many Python instructions, so the only thing that changes as they become arbitrarily long is the underlying C implementation, which is much more efficient. This allowed David Buchanan's implementation to run at 1080p60fps (that is, 124416000 cells/second) on his machine.		This will be teaching it in Python (using only the standard library), however the idea can be implemented irrespective of language. Note that though Python is often considered slow (due to being an interpreted language), bitwise operators on its integers take fixedly many Python instructions, so the only thing that changes as they become arbitrarily long is the underlying C implementation, which is much more efficient. This allowed David Buchanan's implementation to run at 1080p60fps (that is, 124416000 cells/second) on his machine.

	Bitwise operators are functions represented by single infix symbols, like +, -, * and /, except mapping boolean logical functions across bits of numbers' binary representations. ~ maps NOT, and by [https://en.wikipedia.org/wiki/Two's_complement two's complement] is equivalent to taking -1 minus the input (which is useful for reflecting [https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF upper-exclusive zero-indexed] list indices<ref group="n">ie. if you have an x position, x, in a width-n chessboard you're reflecting horizontally, it will be mapped to n+~x</ref>), \| maps OR, ^ maps XOR, & maps AND and << and >> shift the first parameter left and right respectively by numbers of bits corresponding with the second (ie. ~~0b10101~~<<2=0b10100), right-shifts truncating noninteger parts (so they correspond with multiplications and floor-divisions respectively by 2**(their second input)).		Bitwise operators are functions represented by single infix symbols, like +, -, * and /, except mapping boolean logical functions across bits of numbers' binary representations. ~ maps NOT, and by [https://en.wikipedia.org/wiki/Two's_complement two's complement] is equivalent to taking -1 minus the input (which is useful for reflecting [https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF upper-exclusive zero-indexed] list indices<ref group="n">ie. if you have an x position, x, in a width-n chessboard you're reflecting horizontally, it will be mapped to n+~x</ref>), \| maps OR, ^ maps XOR, & maps AND and << and >> shift the first parameter left and right respectively by numbers of bits corresponding with the second (ie. 0b101<<2=0b10100), right-shifts truncating noninteger parts (so they correspond with multiplications and floor-divisions respectively by 2**(their second input)).

	A reasonably good grasp of Python, in particular its list comprehensions and lambda functions, is helpful.		A reasonably good grasp of Python, in particular its list comprehensions and lambda functions, is helpful.

DroneBetter: Terribly sorry, I forgot that the shifts could be the other way around (now I should look quite the fool)

2022-12-27T18:57:07Z

Terribly sorry, I forgot that the shifts could be the other way around (now I should look quite the fool)

← Older revision		Revision as of 18:57, 27 December 2022
Line 292:		Line 292:
	It seems odd that we should set the second shift value to 0 then subtract twice the calculation for the first one's value from its value instead of only setting it to -(1<<i), however this function shown above only works for power-of-2 values of WIDTH and HEIGHT, it allows us to make others work (and implement our optimisations for them) by adding to and subtracting from only the first shift value then generating the second from that. In between the line assigning exceeding and the one amending the shifts, we will add<pre>		It seems odd that we should set the second shift value to 0 then subtract twice the calculation for the first one's value from its value instead of only setting it to -(1<<i), however this function shown above only works for power-of-2 values of WIDTH and HEIGHT, it allows us to make others work (and implement our optimisations for them) by adding to and subtracting from only the first shift value then generating the second from that. In between the line assigning exceeding and the one amending the shifts, we will add<pre>
	if exceeding:		if exceeding:
	endShifts=[0-exceeding//2,~~--0--~~exceeding//2]		endShifts=[-exceeding//2,exceeding//2]
	for i,m in enumerate(masks):		for i,m in enumerate(masks):
	#print(m[0][1])		#print(m[0][1])
Line 319:		Line 319:
	* common is the minimum value if they have the same sign, after the end shift has been brought forwards, the loop from the beginning stops once they have not and there is no longer anything to carry through.		* common is the minimum value if they have the same sign, after the end shift has been brought forwards, the loop from the beginning stops once they have not and there is no longer anything to carry through.

	The endShifts line ~~is slightly suspicious~~, ~~but in Python~~ floor division ~~takes~~ precedence ~~over subtraction but not negation,~~ so ~~if we~~ would ~~like to negate~~ exceeding//2 ~~and put~~ -exceeding//2, it ~~will be equivalent to~~ (-exceeding)//2~~, and floor means 'towards minus infinity'~~. (~~The second part uses~~ the [https://bugs.python.org/issue43255#msg387248 spaceship operator] ~~to achieve ceilingdiv~~.)		The endShifts line works because, while floor division (that rounds towards minus infinity) shares precedence with regular so would be enacted before subtraction (ie. 0-exceeding//2=0-(exceeding//2)), negation supersedes it (ie. -exceeding//2=(-exceeding)//2). (See the [https://bugs.python.org/issue43255#msg387248 spaceship operator].)

	Now we must only execute it to define our functions reverseBitsX() and reverseBitsY()<pre>		Now we must only execute it to define our functions reverseBitsX() and reverseBitsY()<pre>

DroneBetter: Create (if anyone knows how to do inline code excerpts (without line breaks) or make the code blocks not show nested boxes, I will greatly appreciate it)

2022-12-27T18:50:55Z

Create (if anyone knows how to do inline code excerpts (without line breaks) or make the code blocks not show nested boxes, I will greatly appreciate it)

Show changes