Namespace AS2.Subroutines.BinaryOps
Classes
BinOpUtils
General helper methods for binary operations on amoebot chains.
SubAddition
Implements binary addition for two numbers a, b stored in the same chain.
Computes a new binary number c := a + b and optionally determines
whether the chain length was insufficient to compute all bits of c.
This procedure requires at least 1 pin and it always uses the "outermost / leftmost" pin when traversing the chain. If an amoebot occurs on the chain multiple times, its predecessor and successor directions must be different for all occurrences.
Usage:
-
Establish a chain of amoebots such that each amoebot knows its predecessor and successor
(except the start and end amoebots). Each amoebot should store a bit
aand a bitb. -
Initialize using the Init(bool, bool, Direction, Direction) method.
You must pass the bits
aandband the two chain directions. The chain start should have no predecessor and the end should have no successor. - Call SetupPinConfig(PinConfiguration) to modify the next pin configuration.
- Call ActivateSend() in the same round to start the procedure.
- After this, call ActivateReceive(), SetupPinConfig(PinConfiguration) and ActivateSend() in this order in every round.
- The procedure can be paused after each ActivateReceive() call and resumed by continuing with SetupPinConfig(PinConfiguration) in some future round.
-
Call IsFinishedAdd() after ActivateReceive() to check whether the
addition is finished. Running another iteration after this, until IsFinishedOverflow()
returns
true, will make the overflow result available. -
The addition result
cis thereafter available through Bit_C() for each amoebot on the chain.
SubBinOps
Wrapper for several operations on a chain storing one or two binary counters.
Implements MSB detection, comparison, addition, subtraction, multiplication and division with remainder. Only one of these operations can be performed at a time. This wrapper is implemented such that all subroutines share their state attribute, making it very memory efficient.
This procedure requires at least 2 pins and it always uses the "outermost / leftmost" pins when traversing the chain. If an amoebot occurs on the chain multiple times, its predecessor and successor directions must be different for all occurrences.
Usage:
-
Establish a chain of amoebots such that each amoebot knows its predecessor and successor
(except the start and end amoebots). Each amoebot should store a bit
aand a bitb(if an operation for two counters is required). -
Initialize using the Init(Mode, bool, Direction, Direction, bool, bool) method.
You must pass the mode of operation, the bit
aand the two chain directions, plus the bitband the marked MSB ofafor some operations. The chain start should have no predecessor and the end should have no successor. - Call SetupPinConfig(PinConfiguration) to modify the pin configuration.
- Call ActivateSend() in the same round to start the procedure.
- After this, call ActivateReceive(), SetupPinConfig(PinConfiguration) and ActivateSend() in this order in every round.
- The procedure can be paused after each ActivateReceive() call and resumed by continuing with SetupPinConfig(PinConfiguration) in some future round.
- Call IsFinished() after ActivateReceive() to check whether the procedure is finished. The result is thereafter available through one of the interface methods, such as ResultBit(). If the operation has an optional overflow check (addition/subtraction) that you want to use, call IsFinishedOverflow() instead.
SubComparison
Implements binary comparison for two numbers a, b stored in the same chain.
Determines whether a > b, a < b or a = b and makes the result available to all amoebots on the chain.
This procedure requires at least 2 pins and it always uses the "outermost / leftmost" pins when traversing the chain. If an amoebot occurs on the chain multiple times, its predecessor and successor directions must be different for all occurrences.
Usage:
-
Establish a chain of amoebots such that each amoebot knows its predecessor and successor
(except the start and end amoebots). Each amoebot should store a bit
aand a bitb. -
Initialize using the Init(bool, bool, Direction, Direction) method.
You must pass the bits
aandband the two chain directions. The chain start should have no predecessor and the end should have no successor. - Call SetupPinConfig(PinConfiguration) to modify the pin configuration.
- Call ActivateSend() in the same round to start the procedure.
- After this, call ActivateReceive(), SetupPinConfig(PinConfiguration), and ActivateSend() in this order in every round.
- The procedure can be paused after each ActivateReceive() call and resumed by continuing with SetupPinConfig(PinConfiguration) in some future round.
- Call IsFinished() after ActivateReceive() to check whether the comparison is finished.
- The comparison result is thereafter available through Result() for each amoebot on the chain.
SubDivision
Implements binary division for two numbers a, b stored in the same chain.
Computes two new binary numbers c := a / b and d := a mod b. It is
required that a >= b and b > 0 holds when the subroutine starts.
This procedure requires at least 2 pins and it always uses the 2 "outermost / leftmost" pins when traversing the chain. If an amoebot occurs on the chain multiple times, its predecessor and successor directions must be different for all occurrences.
Usage:
-
Establish a chain of amoebots such that each amoebot knows its predecessor and successor
(except the start and end amoebots). Each amoebot should store a bit
aand a bitb. The highest-value 1-bit ofamust be marked. -
Initialize using the Init(bool, bool, bool, Direction, Direction) method.
You must pass the bits
aandb, the marked MSB ofaand the two directions. The start should have no predecessor and the end should have no successor. - Call SetupPinConfig(PinConfiguration) to modify the pin configuration.
- Call ActivateSend() in the same round to start the procedure.
- After this, call ActivateReceive(), SetupPinConfig(PinConfiguration) and ActivateSend() in this order in every round.
- The procedure can be paused after each ActivateReceive() call and resumed by continuing with SetupPinConfig(PinConfiguration) in some future round.
- Call IsFinished() after ActivateReceive() to check whether the division is finished.
-
You can read the quotient bit
cusing Bit_C() and the remainder bitausing Bit_A(). After each iteration, you can also read the current bitaand the shifted bitbusing Bit_A() and Bit_C().
SubMSBDetection
Implements a simple procedure to find the MSB of a binary counter.
Determines the highest-value 1-bit of a binary counter, if there is one, and identifies the chain's start as the MSB otherwise.
This procedure requires at least 1 pin and it always uses the "outermost / leftmost" pin when traversing the chain. If an amoebot occurs on the chain multiple times, its predecessor and successor directions must be different for all occurrences.
Usage:
-
Establish a chain of amoebots such that each amoebot knows its predecessor and successor
(except the start and end amoebots). Each amoebot should store a bit
aand a bitb. -
Initialize using the Init(bool, Direction, Direction) method.
You must pass the bit
aand the two chain directions. The chain start should have no predecessor and the end should have no successor. - Call SetupPinConfig(PinConfiguration) to modify the pin configuration.
- Call ActivateSend() in the same round to start the procedure.
- After this, call ActivateReceive(), SetupPinConfig(PinConfiguration), and ActivateSend() in this order in every round.
- The procedure can be paused after each ActivateReceive() call and resumed by continuing with SetupPinConfig(PinConfiguration) in some future round.
- Call IsFinished() after ActivateReceive() to check whether the procedure is finished. The result is thereafter available through IsMSB() for each amoebot on the chain.
SubMultiplication
Implements binary multiplication for two numbers a, b stored in the same chain.
Computes a new binary number c := a * b. If the binary representation of
c does not fit into the chain, only the lowermost bits are computed and an
overflow is detected.
This procedure requires at least 2 pins and it always uses the 2 "outermost / leftmost" pins when traversing the chain. If an amoebot occurs on the chain multiple times, its predecessor and successor directions must be different for all occurrences.
Usage:
-
Establish a chain of amoebots such that each amoebot knows its predecessor and successor
(except the start and end amoebots). Each amoebot should store a bit
aand a bitb. The highest-value 1-bit ofamust be marked. -
Initialize using the Init(bool, bool, bool, Direction, Direction) method.
You must pass the bits
aandb, the marked MSB ofaand the two directions. The start should have no predecessor and the end should have no successor. - Call SetupPinConfig(PinConfiguration) to modify the pin configuration.
- Call ActivateSend() in the same round to start the procedure.
- After this, call ActivateReceive(), SetupPinConfig(PinConfiguration), and ActivateSend() in this order in every round.
- The procedure can be paused after each ActivateReceive() call and resumed by continuing with SetupPinConfig(PinConfiguration) in some future round.
- Call IsFinished() after ActivateReceive() to check whether the multiplication is finished.
-
You can read the result bit
cusing Bit_C(). After each iteration, you can also read the bitaand the shifted bitbusing Bit_A() and Bit_C(). -
If an overflow has occurred, HaveOverflow() will return
trueafter the procedure has finished.
SubSubtraction
Implements binary subtraction for two numbers a, b stored in the same chain.
Computes a new binary number c := a - b and optionally determines
whether an overflow occurred, i.e., the result was less than 0.
This procedure requires at least 1 pin and it always uses the "outermost / leftmost" pin when traversing the chain. If an amoebot occurs on the chain multiple times, its predecessor and successor directions must be different for all occurrences.
Usage:
-
Establish a chain of amoebots such that each amoebot knows its predecessor and successor
(except the start and end amoebots). Each amoebot should store a bit
aand a bitb. -
Initialize using the Init(bool, bool, Direction, Direction) method.
You must pass the bits
aandband the two chain directions. The chain start should have no predecessor and the end should have no successor. - Call SetupPinConfig(PinConfiguration) to modify the pin configuration.
- Call ActivateSend() in the same round to start the procedure.
- After this, call ActivateReceive(), SetupPinConfig(PinConfiguration) and ActivateSend() in this order in every round.
- The procedure can be paused after each ActivateReceive() call and resumed by continuing with SetupPinConfig(PinConfiguration) in some future round.
-
Call IsFinishedSub() after ActivateReceive() to check whether the
subtraction is finished. Running another iteration after this, until IsFinishedOverflow()
returns
true, will make the overflow result available. -
The subtraction result
cis thereafter available through Bit_C() for each amoebot on the chain.