25,161
edits
Changes
Created page with "'''Home * Programming * Space-Time Tradeoff''' FILE:vortex1_med.jpg|border|right|thumb|link=http://www.physorg.com/news8256.html|Space-time Vortex <ref>[h..."
'''[[Main Page|Home]] * [[Programming]] * Space-Time Tradeoff'''
[[FILE:vortex1_med.jpg|border|right|thumb|link=http://www.physorg.com/news8256.html|Space-time Vortex <ref>[http://www.physorg.com/news8256.html Space-time Vortex] from [http://www.physorg.com/ PhysOrg.com]</ref> ]]
'''Space-Time Tradeoff''' refers to providing [[Knowledge|knowledge]], information or [[Data|data]], where [[Memory|memory]] size competes with computation time. This tradeoff is a frequent issue in computer chess programming, for instance low level stuff to calculate or lookup single populated [[Bitboards|bitboards]] by square index, or a [[Distance|distance]] between two [[Squares|squares]]. Lookup tables are [https://en.wikipedia.org/wiki/Non-volatile_memory non-volatile] tables or initialized once at program startup, various [[Hash Table|hash tables]] and caches. Space-time tradeoff is also an issue in determining (almost) perfect knowledge from [[Interior Node Recognizer|interior node recognizers]] by [[Retrograde Analysis|retrograde analysis]], that is the application of [[Endgame Bitbases|endgame bit-]] or [[Endgame Tablebases|tablebases]] and various [https://en.wikipedia.org/wiki/Data_compression compression] techniques.
=Space-Time Tradeoffs=
There are multiple CPW pages where memory competes with computation:
* [[General Setwise Operations#BitbySquare|Bit by Square]]
* [[BitScan]]
* [[Distance]]
* [[Endgame Bitbases]]
* [[Endgame Tablebases]]
* [[Hash Table]]
* [[Kindergarten Bitboards]]
* [[KPK]]
* [[Square Attacked By#LegalityTest|Legality Test]]
* [[Magic Bitboards]]
* [[Manhattan-Distance]]
* [[Material Tables]]
* [[Population Count]]
* [[Rotated Bitboards]]
* [[Table-driven Move Generation]]
* [[The switch Approach]]
* [[Transposition Table]]
=See also=
* [[Algorithms]]
* [[Best-First]]
* [[Data]]
* [[Depth-First]]
* [[Dispersion and Distortion]]
* [[Knowledge]]
* [[Learning]]
* [[Memory]]
* [[Sequential Logic]]
=Publications=
* [https://en.wikipedia.org/wiki/Bloom_filter Burton H. Bloom] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362692 Space/time trade-offs in hash coding with allowable errors]''. Comm. of the ACM, Vol. 13, No. 7, [http://www.lsi.upc.edu/%7Ediaz/p422-bloom.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Bloom_filter Bloom filter from Wikipedia]</ref>
* [[Albert Zobrist]] and [[Frederic Roy Carlson]] ('''1977'''). ''Detection of Combined Occurrences''. Comm. of the ACM, Vol. 20, No. 1, pp. 31-35.
=External Links=
* [https://en.wikipedia.org/wiki/Space-time_tradeoff Space-time tradeoff from Wikipedia]
* [https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem Blum's speedup theorem from Wikipedia]
* [https://en.wikipedia.org/wiki/Algorithmic_efficiency Algorithmic efficiency from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28Information_theory%29 Shannon entropy from Wikipedia]
* [https://en.wikipedia.org/wiki/Computer_memory Computer memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Cache Cache from Wikipedia]
* [https://en.wikipedia.org/wiki/Lookup_table Lookup table from Wikipedia]
* [https://en.wikipedia.org/wiki/Database Database from Wikipedia]
* [https://en.wikipedia.org/wiki/Memory_management_unit Memory management unit from Wikipedia]
* [https://en.wikipedia.org/wiki/Volatile_memory Volatile memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Non-volatile_memory Non-volatile memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Random-access_memory Random-access memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Read-only_memory Read-only memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Memory_footprint Memory footprint from Wikipedia]
* [https://en.wikipedia.org/wiki/Moore%27s_law Moore's law from Wikipedia]
* [http://www.fourmilab.ch/documents/comp_mem_nat_life/ Computation, Memory, Nature, and Life] - Is digital storage the secret of life? by [https://en.wikipedia.org/wiki/John_Walker_%28programmer%29 John Walker]
* [https://en.wikipedia.org/wiki/Spacetime Spacetime from Wikipedia]
* [https://en.wikipedia.org/wiki/Philosophy_of_space_and_time Philosophy of space and time from Wikipedia]
* [http://www.quantonics.com/Einstein_Minkowski_Space_Time_Diagram.html Einstein Minkowski Space-Time Diagram]
* [https://en.wikipedia.org/wiki/Art_of_memory Art of memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Eureka:_A_Prose_Poem Eureka: A Prose Poem from Wikipedia]
* [[Videos#KingCrimson|King Crimson]] - [https://en.wikipedia.org/wiki/Thrak One Time], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: 1995 double trio: [[Videos#AdrianBelew|Adrian Belew]], [[Videos#BillBruford|Bill Bruford]], [[Videos#RobertFripp|Robert Fripp]], [https://en.wikipedia.org/wiki/Trey_Gunn Trey Gunn], [https://en.wikipedia.org/wiki/Tony_Levin Tony Levin], [https://en.wikipedia.org/wiki/Pat_Mastelotto Pat Mastelotto]
: {{#evu:https://www.youtube.com/watch?v=RhJKCW2_w3k|alignment=left|valignment=top}}
=References=
<references />
'''[[Programming|Up one Level]]'''
[[FILE:vortex1_med.jpg|border|right|thumb|link=http://www.physorg.com/news8256.html|Space-time Vortex <ref>[http://www.physorg.com/news8256.html Space-time Vortex] from [http://www.physorg.com/ PhysOrg.com]</ref> ]]
'''Space-Time Tradeoff''' refers to providing [[Knowledge|knowledge]], information or [[Data|data]], where [[Memory|memory]] size competes with computation time. This tradeoff is a frequent issue in computer chess programming, for instance low level stuff to calculate or lookup single populated [[Bitboards|bitboards]] by square index, or a [[Distance|distance]] between two [[Squares|squares]]. Lookup tables are [https://en.wikipedia.org/wiki/Non-volatile_memory non-volatile] tables or initialized once at program startup, various [[Hash Table|hash tables]] and caches. Space-time tradeoff is also an issue in determining (almost) perfect knowledge from [[Interior Node Recognizer|interior node recognizers]] by [[Retrograde Analysis|retrograde analysis]], that is the application of [[Endgame Bitbases|endgame bit-]] or [[Endgame Tablebases|tablebases]] and various [https://en.wikipedia.org/wiki/Data_compression compression] techniques.
=Space-Time Tradeoffs=
There are multiple CPW pages where memory competes with computation:
* [[General Setwise Operations#BitbySquare|Bit by Square]]
* [[BitScan]]
* [[Distance]]
* [[Endgame Bitbases]]
* [[Endgame Tablebases]]
* [[Hash Table]]
* [[Kindergarten Bitboards]]
* [[KPK]]
* [[Square Attacked By#LegalityTest|Legality Test]]
* [[Magic Bitboards]]
* [[Manhattan-Distance]]
* [[Material Tables]]
* [[Population Count]]
* [[Rotated Bitboards]]
* [[Table-driven Move Generation]]
* [[The switch Approach]]
* [[Transposition Table]]
=See also=
* [[Algorithms]]
* [[Best-First]]
* [[Data]]
* [[Depth-First]]
* [[Dispersion and Distortion]]
* [[Knowledge]]
* [[Learning]]
* [[Memory]]
* [[Sequential Logic]]
=Publications=
* [https://en.wikipedia.org/wiki/Bloom_filter Burton H. Bloom] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362692 Space/time trade-offs in hash coding with allowable errors]''. Comm. of the ACM, Vol. 13, No. 7, [http://www.lsi.upc.edu/%7Ediaz/p422-bloom.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Bloom_filter Bloom filter from Wikipedia]</ref>
* [[Albert Zobrist]] and [[Frederic Roy Carlson]] ('''1977'''). ''Detection of Combined Occurrences''. Comm. of the ACM, Vol. 20, No. 1, pp. 31-35.
=External Links=
* [https://en.wikipedia.org/wiki/Space-time_tradeoff Space-time tradeoff from Wikipedia]
* [https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem Blum's speedup theorem from Wikipedia]
* [https://en.wikipedia.org/wiki/Algorithmic_efficiency Algorithmic efficiency from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28Information_theory%29 Shannon entropy from Wikipedia]
* [https://en.wikipedia.org/wiki/Computer_memory Computer memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Cache Cache from Wikipedia]
* [https://en.wikipedia.org/wiki/Lookup_table Lookup table from Wikipedia]
* [https://en.wikipedia.org/wiki/Database Database from Wikipedia]
* [https://en.wikipedia.org/wiki/Memory_management_unit Memory management unit from Wikipedia]
* [https://en.wikipedia.org/wiki/Volatile_memory Volatile memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Non-volatile_memory Non-volatile memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Random-access_memory Random-access memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Read-only_memory Read-only memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Memory_footprint Memory footprint from Wikipedia]
* [https://en.wikipedia.org/wiki/Moore%27s_law Moore's law from Wikipedia]
* [http://www.fourmilab.ch/documents/comp_mem_nat_life/ Computation, Memory, Nature, and Life] - Is digital storage the secret of life? by [https://en.wikipedia.org/wiki/John_Walker_%28programmer%29 John Walker]
* [https://en.wikipedia.org/wiki/Spacetime Spacetime from Wikipedia]
* [https://en.wikipedia.org/wiki/Philosophy_of_space_and_time Philosophy of space and time from Wikipedia]
* [http://www.quantonics.com/Einstein_Minkowski_Space_Time_Diagram.html Einstein Minkowski Space-Time Diagram]
* [https://en.wikipedia.org/wiki/Art_of_memory Art of memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Eureka:_A_Prose_Poem Eureka: A Prose Poem from Wikipedia]
* [[Videos#KingCrimson|King Crimson]] - [https://en.wikipedia.org/wiki/Thrak One Time], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: 1995 double trio: [[Videos#AdrianBelew|Adrian Belew]], [[Videos#BillBruford|Bill Bruford]], [[Videos#RobertFripp|Robert Fripp]], [https://en.wikipedia.org/wiki/Trey_Gunn Trey Gunn], [https://en.wikipedia.org/wiki/Tony_Levin Tony Levin], [https://en.wikipedia.org/wiki/Pat_Mastelotto Pat Mastelotto]
: {{#evu:https://www.youtube.com/watch?v=RhJKCW2_w3k|alignment=left|valignment=top}}
=References=
<references />
'''[[Programming|Up one Level]]'''
