• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example

Mika Hirvensalo, Juhani Karhumäki, Alexander Rabinovich, Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example. TUCS Technical Reports 651, Turku Centre for Computer Science, 2004.

Abstract:

We consider an algorithmic problem of computing the first, i.e., the most meaningful digits of 2<SUP>n</SUP> (at base 3) and of the <I>n</I>th Fibonacci number. While the decidability is trivial, efficient algorithms for those problems are not immediate. We show, based on Baker's inapproximability results of transcendental numbers that both of the above problems can be solved in polynomial time with respect to the
length of <I>n</I>. We point out that our approach works also for much
more general expressions of algebraic numbers.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHiKaRa04a,
  title = {Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example},
  author = {Hirvensalo, Mika and Karhumäki, Juhani and Rabinovich, Alexander},
  number = {651},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2004},
  keywords = {Efficient computability, Linear forms of logarithms, Baker theory},
  ISBN = {952-12-1485-6},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication