著者

徳丸 雄一 藤原 暁宏

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.23, pp.25-32, 2007-03-09

参考文献数

20

---

本研究では DNA計算を用いて浮動小数点数の演算を行うアルゴリズムを提案する. まずはじめに DNAによる浮動小数点表現を定義する. 本研究で取り扱う浮動小数点数は符号部 指数部 仮数部から構成され 符号部は1ビットの2進数であり また 指数部と仮数部は それぞれqビットとmビットの2進数であるものとする. 次に 浮動小数点数対に対して加算を行う2つのアルゴリズムを提案する. 1つ目のアルゴリズムはO(m^{2})種類のDNAを用いることによりO(log m)ステップで実行可能であり 2つ目のアルゴリズムはO(m^{2}2^{m})種類のDNAを用いることによりO(1)ステップで実行可能である. また O(n)個の対に対する浮動小数点数の加算を行うアルゴリズムも提案する. このアルゴリズムは O(nm^{2}2^{m})種類のDNAを用いることにより O(1)ステップで実行可能である. また最後に 浮動小数点数の乗算を行うアルゴリズムを提案する. このアルゴリズムO(m^{2})種類のDNAを用いることによりO(log m)ステップで実行可能である.In this paper, we consider procedures for floating point arithmeticoperations with DNA molecules. We first propose data structure for representing floating point numbers with DNA molecules. The floatingpoint number consists of a sign bit, an exponent and a mantissa. We assume that the exponent and the mantissa are binary numbers of q andm bits, respectively. We next propose two procedures for an addition of floating point numbers. The first procedure executes an addition inO(log m) steps using O(m^{2}) DNA strands, and the second procedure executes an addition in O(1) steps using O(m^{2}2^{m}) DNA strands. Wealso propose a procedure for additions of O(n) pairs of two floating point numbers. The procedure executes O(n) additions simultaneously inO(1) steps using O(nm^{2}2^{m}) DNA strands. We finally propose a procedure for a multiplication of a pair of two floating pointnumbers. The procedure executes a multiplication in O(log m) steps using O(m^{2}) DNA strands.