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 a and a bit b.
• Initialize using the Init(bool, bool, Direction, Direction) method. You must pass the bits a and b and 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 c is 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 a and a bit b (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 a and the two chain directions, plus the bit b and the marked MSB of a for 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 a and a bit b.
• Initialize using the Init(bool, bool, Direction, Direction) method. You must pass the bits a and b and 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 a and a bit b. The highest-value 1-bit of a must be marked.
• Initialize using the Init(bool, bool, bool, Direction, Direction) method. You must pass the bits a and b, the marked MSB of a and 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 c using Bit_C() and the remainder bit a using Bit_A(). After each iteration, you can also read the current bit a and the shifted bit b using 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 a and a bit b.
• Initialize using the Init(bool, Direction, Direction) method. You must pass the bit a and 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 a and a bit b. The highest-value 1-bit of a must be marked.
• Initialize using the Init(bool, bool, bool, Direction, Direction) method. You must pass the bits a and b, the marked MSB of a and 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 c using Bit_C(). After each iteration, you can also read the bit a and the shifted bit b using Bit_A() and Bit_C().
• If an overflow has occurred, HaveOverflow() will return true after 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 a and a bit b.
• Initialize using the Init(bool, bool, Direction, Direction) method. You must pass the bits a and b and 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 c is thereafter available through Bit_C() for each amoebot on the chain.

Enums

SubBinOps.Mode

SubComparison.ComparisonResult