Fast Arithmetic in Algorithmic Self-Assembly
| Autor: | Xingsi Zhong, Robert T. Schweller, Michael Sherman, Alexandra Keenan |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Average-case complexity
Computational Geometry (cs.CG) FOS: Computer and information sciences 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) 01 natural sciences Upper and lower bounds Square (algebra) Combinatorics Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Time complexity Mathematics F.1.1 F.2.0 Computational geometry Binary logarithm Computer Science Applications Computer Science - Computational Complexity 010201 computation theory & mathematics Theory of computation Computer Science - Computational Geometry 020201 artificial intelligence & image processing Multiplication |
| DOI: | 10.48550/arxiv.1303.2416 |
| Popis: | In this paper we consider the time complexity of computing the sum and product of two $n$-bit numbers within the tile self-assembly model. The (abstract) tile assembly model is a mathematical model of self-assembly in which system components are square tiles with different glue types assigned to tile edges. Assembly is driven by the attachment of singleton tiles to a growing seed assembly when the net force of glue attraction for a tile exceeds some fixed threshold. Within this frame work, we examine the time complexity of computing the sum or product of 2 n-bit numbers, where the input numbers are encoded in an initial seed assembly, and the output is encoded in the final, terminal assembly of the system. We show that the problems of addition and multiplication have worst case lower bounds of $\Omega(\sqrt{n})$ in 2D assembly, and $\Omega(\sqrt[3]{n})$ in 3D assembly. In the case of addition, we design algorithms for both 2D and 3D that meet this bound with worst case run times of $O(\sqrt{n})$ and $O(\sqrt[3]{n})$ respectively, which beats the previous best known upper bound of O(n). Further, we consider average case complexity of addition over uniformly distributed n-bit strings and show how to achieve $O(\log n)$ average case time with a simultaneous $O(\sqrt{n})$ worst case run time in 2D. For multiplication, we present an $O(n^{5/6})$ time multiplication algorithm which works in 3D, which beats the previous best known upper bound of O(n). As additional evidence for the speed of our algorithms, we implement our addition algorithms, along with the simpler O(n) time addition algorithm, into a probabilistic run-time simulator and compare the timing results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|