4,494
edits
Boolean: Difference between revisions
Jump to navigation
Jump to search
m
Text replacement - "</source>" to "</syntaxhighlight>"
(→Boolean optimization: Incomplete list of APLs with bit Booleans) |
m (Text replacement - "</source>" to "</syntaxhighlight>") |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 7: | Line 7: | ||
The result of a [[comparison]] such as [[Less Than]] is always composed of Booleans. Because Booleans are numbers, arithmetic functions can be used on them directly, for example by [[sum]]ming a result [[vector]] to find out how many times the comparison was true: | The result of a [[comparison]] such as [[Less Than]] is always composed of Booleans. Because Booleans are numbers, arithmetic functions can be used on them directly, for example by [[sum]]ming a result [[vector]] to find out how many times the comparison was true: | ||
< | <syntaxhighlight lang=apl> | ||
3 1 4 1 5 9 2 < 5 | 3 1 4 1 5 9 2 < 5 | ||
1 1 1 1 0 0 1 | 1 1 1 1 0 0 1 | ||
+/ 3 1 4 1 5 9 2 < 5 | +/ 3 1 4 1 5 9 2 < 5 | ||
5 | 5 | ||
</ | </syntaxhighlight> | ||
With [[index origin]] 0, Booleans can also be used as [[Index|indices]] into an array. | With [[index origin]] 0, Booleans can also be used as [[Index|indices]] into an array. | ||
< | <syntaxhighlight lang=apl> | ||
⎕IO←0 | ⎕IO←0 | ||
'-+'[3 1 4 1 5 9 2 < 5] | '-+'[3 1 4 1 5 9 2 < 5] | ||
++++--+ | ++++--+ | ||
</ | </syntaxhighlight> | ||
The use of numbers for Booleans also allows functions to be extended from a Boolean domain to a more general domain. The function [[Compress]] was originally defined to take a Boolean left argument and use it as a filter for the right argument (removing right argument values corresponding to 0), but has generally now been replaced by an extension called [[Replicate]] which can copy right argument values multiple times. | The use of numbers for Booleans also allows functions to be extended from a Boolean domain to a more general domain. The function [[Compress]] was originally defined to take a Boolean left argument and use it as a filter for the right argument (removing right argument values corresponding to 0), but has generally now been replaced by an extension called [[Replicate]] which can copy right argument values multiple times. | ||
< | <syntaxhighlight lang=apl> | ||
1 1 1 1 0 0 1 / '3141592' | 1 1 1 1 0 0 1 / '3141592' | ||
31412 | 31412 | ||
0 4 1 2 0 0 0 / '3141592' | 0 4 1 2 0 0 0 / '3141592' | ||
1111411 | 1111411 | ||
</ | </syntaxhighlight> | ||
== Boolean functions == | == Boolean functions == | ||
| Line 35: | Line 35: | ||
{|class=wikitable | {|class=wikitable | ||
! < | ! <syntaxhighlight lang=apl inline>f 0</syntaxhighlight> !! <syntaxhighlight lang=apl inline>f 1</syntaxhighlight> !! Function | ||
|- | |- | ||
| 0 || 0 || Constant 0 | | 0 || 0 || Constant 0 | ||
| Line 41: | Line 41: | ||
| 0 || 1 || Identity | | 0 || 1 || Identity | ||
|- | |- | ||
| 1 || 0 || < | | 1 || 0 || <syntaxhighlight lang=apl inline>~</syntaxhighlight> [[Not]] | ||
|- | |- | ||
| 1 || 1 || Constant 1 | | 1 || 1 || Constant 1 | ||
| Line 47: | Line 47: | ||
{|class=wikitable | {|class=wikitable | ||
! < | ! <syntaxhighlight lang=apl inline>0 f 0</syntaxhighlight> !! <syntaxhighlight lang=apl inline>0 f 1</syntaxhighlight> !! <syntaxhighlight lang=apl inline>1 f 0</syntaxhighlight> !! <syntaxhighlight lang=apl inline>1 f 1</syntaxhighlight> !! Function | ||
|- | |- | ||
| 0 || 0 || 0 || 0 || Constant 0 | | 0 || 0 || 0 || 0 || Constant 0 | ||
|- | |- | ||
| 0 || 0 || 0 || 1 || < | | 0 || 0 || 0 || 1 || <syntaxhighlight lang=apl inline>∧</syntaxhighlight> [[And]], <syntaxhighlight lang=apl inline>⌊</syntaxhighlight> [[Minimum]] , <syntaxhighlight lang=apl inline>×</syntaxhighlight> [[Times]] | ||
|- | |- | ||
| 0 || 0 || 1 || 0 || < | | 0 || 0 || 1 || 0 || <syntaxhighlight lang=apl inline>></syntaxhighlight> [[Greater Than]] | ||
|- | |- | ||
| 0 || 0 || 1 || 1 || Left argument | | 0 || 0 || 1 || 1 || Left argument | ||
|- | |- | ||
| 0 || 1 || 0 || 0 || < | | 0 || 1 || 0 || 0 || <syntaxhighlight lang=apl inline><</syntaxhighlight> [[Less Than]], <syntaxhighlight lang=apl inline>|</syntaxhighlight> [[Residue]] | ||
|- | |- | ||
| 0 || 1 || 0 || 1 || Right argument | | 0 || 1 || 0 || 1 || Right argument | ||
|- | |- | ||
| 0 || 1 || 1 || 0 || < | | 0 || 1 || 1 || 0 || <syntaxhighlight lang=apl inline>≠</syntaxhighlight> [[Not Equal]] | ||
|- | |- | ||
| 0 || 1 || 1 || 1 || < | | 0 || 1 || 1 || 1 || <syntaxhighlight lang=apl inline>∨</syntaxhighlight> [[Or]], <syntaxhighlight lang=apl inline>⌈</syntaxhighlight> [[Maximum]] | ||
|- | |- | ||
| 1 || 0 || 0 || 0 || < | | 1 || 0 || 0 || 0 || <syntaxhighlight lang=apl inline>⍱</syntaxhighlight> [[Nor]] | ||
|- | |- | ||
| 1 || 0 || 0 || 1 || < | | 1 || 0 || 0 || 1 || <syntaxhighlight lang=apl inline>=</syntaxhighlight> [[Equal]] | ||
|- | |- | ||
| 1 || 0 || 1 || 0 || Right argument negation | | 1 || 0 || 1 || 0 || Right argument negation | ||
|- | |- | ||
| 1 || 0 || 1 || 1 || < | | 1 || 0 || 1 || 1 || <syntaxhighlight lang=apl inline>≥</syntaxhighlight> [[Greater Than or Equal]], <syntaxhighlight lang=apl inline>*</syntaxhighlight> [[Power]] | ||
|- | |- | ||
| 1 || 1 || 0 || 0 || Left argument negation | | 1 || 1 || 0 || 0 || Left argument negation | ||
|- | |- | ||
| 1 || 1 || 0 || 1 || < | | 1 || 1 || 0 || 1 || <syntaxhighlight lang=apl inline>≤</syntaxhighlight> [[Less Than or Equal]], <syntaxhighlight lang=apl inline>!</syntaxhighlight> [[Binomial]] | ||
|- | |- | ||
| 1 || 1 || 1 || 0 || < | | 1 || 1 || 1 || 0 || <syntaxhighlight lang=apl inline>⍲</syntaxhighlight> [[Nand]] | ||
|- | |- | ||
| 1 || 1 || 1 || 1 || Constant 1 | | 1 || 1 || 1 || 1 || Constant 1 | ||
| Line 94: | Line 94: | ||
* Dyalog Blog: [[Marshall Lochbaum]], [https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrinking-time/ "Expanding Bits in Shrinking Time"] | * Dyalog Blog: [[Marshall Lochbaum]], [https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrinking-time/ "Expanding Bits in Shrinking Time"] | ||
Because they are so small relative to CPU registers, Booleans can make [[wikipedia:SIMD|SIMD]] (Single Instruction Multiple Data) techniques viable even in processors with no dedicated SIMD unit. Programming in this way is called [[wikipedia:SWAR|SWAR]] (SIMD Within a Register), and is considerably easier when working with bit Booleans than when working with integers. | Because they are so small relative to CPU registers, Booleans can make [[wikipedia:SIMD|SIMD]] (Single Instruction Multiple Data) techniques viable even in processors with no dedicated SIMD unit. Programming in this way is called [[wikipedia:SWAR|SWAR]] (SIMD Within a Register), and is considerably easier when working with bit Booleans than when working with integers. While most processors now have SIMD registers and instructions, current SIMD implementations don't provide all the bitwise operations that are available for ordinary registers, such as addition or bitwise shifts on entire registers. Boolean SWAR programming can be useful to more easily develop algorithms which are fast (often beating dedicated SIMD optimizations with each Boolean stored in a byte) while remaining architecture independent. | ||
== External links == | == External links == | ||
* [[Bob Smith]], [http://www.sudleyplace.com/APL/boolean.pdf "Boolean Functions"] | * [[Bob Smith]], [http://www.sudleyplace.com/APL/boolean.pdf "Boolean Functions"] | ||
* Jonathan Barman, [http://archive.vector.org.uk/trad/v011/barman011_127.pdf APL and Partitioned Data] (a follow-up on Smith's paper) | |||
* [[Eugene McDonnell]], [https://www.jsoftware.com/papers/eem/caret.htm "The Caret and the Stick Functions"] (on classifying Boolean functions). | * [[Eugene McDonnell]], [https://www.jsoftware.com/papers/eem/caret.htm "The Caret and the Stick Functions"] (on classifying Boolean functions). | ||
* [[Phil Last]], [http://archive.vector.org.uk/art10501140 "Boolean Reductions"] | * [[Phil Last]], [http://archive.vector.org.uk/art10501140 "Boolean Reductions"] | ||
* [[John Scholes]], [https://www.dyalog.com/blog/2014/10/data-driven-conditionals-2/ "Data-driven Conditionals"] | * [[John Scholes]], [https://www.dyalog.com/blog/2014/10/data-driven-conditionals-2/ "Data-driven Conditionals"] | ||
{{APL features}}[[Category:Numbers]] | |||