Abstract
Base extension is an important operation in residue number systems. The method for base extension proposed in this paper approaches the solution through an approximation which is correct in nearly all cases. Rare corrences of uncertainties about the correctness of the result are detected and corrected using iterations. The novel method is superior to the method proposed by Shenoy and Kumaresan [5] as it does not need the help of an additional redundant modulus. For a special class of problems the latter method cannot be used at all. The presented base extension provides a unique tool with time complexity of log2 n withn denoting the amount of moduli.
Zusammenfassung
In Restklassenzahlensystemen ist die Operation Basiserweiterung von Bedeutung. Die Methode zur Basiserweiterung, wie in dieser Arbeit vorgeschlagen, bedient sich einer Näherungslösung, welche in fast allen Fällen korrekt ist. Das seltene Auftreten von Unsicherheiten bezüglich der Korrektheit des Ergebnisses wird erkantt und durch Iteration korrigiert. Diese neue Methode braucht im Gegensatz zur Methode von Shenoy und Kumaresan keinen zusätzlichen redundanten Modul und ist in dieser Hinsicht besser, da für eine spezielle Problemklasse die Methode überhaupt erst anwendbar wird. In diesem Fall besitzt das vorgestellte Verfahren eine Zeitkomplexität von log2 n, wobein die Anzahl der Moduln darstellt.
Similar content being viewed by others
References
Dickson, L. E.: History of the theory of numbers, Chap. XIV, New York: Chelsea 1952.
Knuth, D. E.: The art of computer programming, vol. 2. Reading, Mass.: Addison-Wesley 1969.
Lüneburg, H.: Vorlesungen über Zahlentheorie. In: Trost, E. (Hrsg.) Elemente der Mathematik vom höheren Standpunkt, Band VIII. Basel: Birkhäuser 1978.
Shoenfeld, L.: Sharper bounds for the Chebyshev functions ϑ(x) and ψ(x); II. Math. Comp.30, 337–360 (1976).
Shenoy, A. P., Kumaresan, R.: Fast base extension using a redundant modulus in RNS, IEEE Transactions on Computers38 (2), 292–297 (1989).
Szabo, N. S., Tanaka, R. I.: Residue arithmetic and its applications to computer technology. New York: McGray-Hill 1967.
Taylor, F. J.: Residue arithmetic: a tutorial with examples computer. IEEE17, 50–62 (1984).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Posch, K.C., Posch, R. Base extension using a convolution sum in residue number systems. Computing 50, 93–104 (1993). https://doi.org/10.1007/BF02238608
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02238608