An Improved DNA-Sticker Addition Algorithm and Its Application to Logarithmic Arithmetic

摘要

The sticker model of computation, implemented using robotic processing of DNA, manipulates in parallel many bitstrings, called strands, that are contained in a limited number of tubes. Prior sticker-addition algorithms are patterned on digital-electronic full-adders that generate carry bits, each of which must be saved in the strand, which involves wasting the strand or using a clear operation (whose biochemical implementation may be problematic). This paper proposes a new sticker-addition algorithm which does not need to record the carry bits. Instead, which tube holds a particular strand implicitly describes whether or not a carry is required. The speed and number of tubes needed are about half that needed by the prior approach. An example is given for real-valued Euclidian norms using the Logarithmic Number System.