Advertisement
Published in:
2014 | OriginalPaper | Chapter
Modular Algorithm in Tile Self-assembly Model
Authors : Xiwen Fang, Xuejia Lai
Published in: Innovations in Bio-inspired Computing and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we propose a system computing
A
mod
B
for given
n
A
-bit binary integer
A
and
n
B
-bit binary integer
B
, which is the first system directly solving the modulus problem in tile assembly model. The worst-case assembly time of our system is Θ(
n
A
(
n
A
−
n
B
)) and the best-case assembly time is Θ(
n
A
).
Although the pre-existing division system which computes
A
/
B
can also be used to compute
A
mod
B
, the assembly time of this system is not ideal in some cases. Compared with the pre-existing division system, we achieved improved time complexity in our system. Our advantage is more significant if
n
A
is much greater than
n
B
.