In this paper we present two efficient methods for reconstructing a rational number from several residue-modulus pairs, some of which may be incorrect. One method is a natural generalization of that presented by Wang et al. in (Wang et al., 1982) (for reconstructing a rational number from correct modular images), and also of an algorithm presented in Abbott (1991) for reconstructing an integer value from several residue-modulus pairs, some of which may be incorrect. The other method is heuristic, but much easier to apply; it may be viewed as a generalization of Monagan's MQRR (Monagan, 2004). We compare our heuristic method with that of Böhm et al. (2015). Our method is clearly preferable when the rational to be reconstructed is unbalanced.

Fault-tolerant modular reconstruction of rational numbers

Abbott, John
2017

Abstract

In this paper we present two efficient methods for reconstructing a rational number from several residue-modulus pairs, some of which may be incorrect. One method is a natural generalization of that presented by Wang et al. in (Wang et al., 1982) (for reconstructing a rational number from correct modular images), and also of an algorithm presented in Abbott (1991) for reconstructing an integer value from several residue-modulus pairs, some of which may be incorrect. The other method is heuristic, but much easier to apply; it may be viewed as a generalization of Monagan's MQRR (Monagan, 2004). We compare our heuristic method with that of Böhm et al. (2015). Our method is clearly preferable when the rational to be reconstructed is unbalanced.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0747717116300773-main.pdf

accesso chiuso

Descrizione: Fault-tolerant
Tipologia: Documento in versione editoriale
Dimensione 358.99 kB
Formato Adobe PDF
358.99 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11567/898671
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact