Fast arithmetic in algorithmic self-assembly

DOI10.1007/978-3-319-08123-6_20zbMATH Open1415.68089arXiv1303.2416OpenAlexW1670603247MaRDI QIDQ2003452FDOQ2003452

Yanyan Li

Publication date: 8 July 2019

Published in: Natural Computing, Unconventional Computation and Natural Computation (Search for Journal in Brave)

Abstract: 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(sqrtn)$ 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(sqrtn)$ 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(logn)$ average case time with a simultaneous $O(sqrtn)$ 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.

Full work available at URL: https://arxiv.org/abs/1303.2416

zbMATH Keywords

computational geometryalgorithmic self-assemblyaddertile-assembly model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Other nonclassical models of computation (68Q09)

Cites Work

• Self-assembly with Geometric Tiles
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Randomized Self-assembly for Approximate Shapes
• Combinatorial optimization problems in self-assembly
• The Tile Complexity of Linear Assemblies
• One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
• Running time and program size for self-assembled squares
• Complexities for Generalized Models of Self-Assembly
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Title not available (Why is that?)
• Title not available (Why is that?)
• Intrinsic universality in tile self-assembly requires cooperation
• Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
• Randomized Self-Assembly for Exact Shapes
• Title not available (Why is that?)
• Fuel Efficient Computation in Passive Self-Assembly
• The Longest Run of Heads
• Fast arithmetic in algorithmic self-assembly
• Arithmetic computation in the tile assembly model: addition and multiplication

Cited In (9)

• Fuel Efficient Computation in Passive Self-Assembly
• Fast arithmetic in algorithmic self-assembly
• Title not available (Why is that?)
• Flipping Tiles: Concentration Independent Coin Flips in Tile Self-Assembly
• Covert computation in self-assembled circuits
• Parallel Computation Using Active Self-assembly
• Concentration independent random number generation in tile self-assembly
• Parallel computation using active self-assembly
• Title not available (Why is that?)

This page was built for publication: Fast arithmetic in algorithmic self-assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003452)