4,494
edits
Boolean: Difference between revisions
Jump to navigation
Jump to search
m
Text replacement - "</source>" to "</syntaxhighlight>"
(→Boolean optimization: Clarify that SIMD ISAs are less convenient for boolean algorithms) |
m (Text replacement - "</source>" to "</syntaxhighlight>") |
||
| (2 intermediate revisions by the same user 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 99: | Line 99: | ||
* [[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"] | ||