Fast arithmetics using Chinese remaindering

Davida, George, Litow, Bruce, and Xu, Guanguu (2009) Fast arithmetics using Chinese remaindering. Information Processing Letters, 109 (13). pp. 660-662.

[img] PDF (Published Version)
Restricted to Repository staff only

View at Publisher Website: http://dx.doi.org/10.1016/j.ipl.2009.02....

Abstract

In this paper, some issues concerning the Chinese remaindering representation are discussed. A new converting method, which is an efficient probabilistic algorithm based on a recent result of von zur Gathen and Shparlinski U. von zur Gathen, I. Shparlinski, GCD of random linear forms. Algorithmica 46 (2006) 137-148), is described. An efficient refinement of the NC1 division algorithm of Chiu. Davida and Litow IA. Chiu, G. Davida. B. Litow, Division in logspace-uniform NCl, Theoret Informatics App!. 35 (2001) 259-275] is given, where the number of moduli is reduced by a factor of logn.

Item ID: 11231
Item Type: Article (Refereed Research - C1)
Keywords: parallel algorithm; Chinese remaindering representation
ISSN: 1872-6119
Date Deposited: 17 May 2010 04:05
FoR Codes: 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080299 Computation Theory and Mathematics not elsewhere classified @ 75%
08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 25%
SEO Codes: 97 EXPANDING KNOWLEDGE > 970108 Expanding Knowledge in the Information and Computing Sciences @ 100%
Citation Count from Web of Science Web of Science 1
Downloads: Total: 3
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page