Relaxed algorithms for \(p\)-adic numbers
type: Item
instance of: scholarly article
title: Relaxed algorithms for \(p\)-adic numbers
zbMATH Open document ID: 1247.11152
author: Jérémy Berthomieu
author: Joris van der Hoeven
author: Grégoire Lecerf
published in: Journal de Théorie des Nombres de Bordeaux
publication date: 2012-08-31T00:00:00Z
full work available at URL: https://eudml.org/doc/219803
review text: The main theme of this paper is to replace the standard \textit{zealous} algorithms for \(p\)--adic numbers by new \textit{lazy} algorithms. The standard algorithms compute with truncated \(p\)--adic expansions at a precision specified by the user, combined with Newton-Hensel lifting techniques; they have an efficient asymptotic cost. The principle of lazy algorithms appeared for formal power series. It has advantages to solve implicit equations and does not need any choice from the user, but the first versions had a more expensive asymptotic cost than zealous algorithms. Here the Authors apply progress due to van der Hoeven to the case of \(p\)--adic numbers. They study in detail the elementary arithmetical operations and the computation of \(k\)--th roots. They have implemented their algorithms in the C++ library algebraix of Mathemagix.
reviewed by: Maurice Mignotte
Mathematics Subject Classification ID: 11Y40
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 6075047
zbMATH Keywords: \(p\)-adic numbers
zbMATH Keywords: power series
zbMATH Keywords: algorithms
describes a project that uses: gmp
describes a project that uses: Kronecker
describes a project that uses: PARI/GP
describes a project that uses: FLINT
describes a project that uses: Mathemagix
describes a project that uses: SageMath
MaRDI profile type: Publication
OpenAlex ID: W1987316492
cites work: Fast Algorithms for Manipulating Formal Power Series
cites work: Q3497179
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: A concise proof of the Kronecker polynomial system solver from scratch
cites work: Effective procedures in field theory
cites work: Q3549597
cites work: Hensel and Newton Methods in Valuation Rings
cites work: Q4406533
cites work: Q4226932
cites work: Fast evaluation of holonomic functions
cites work: Fast evaluation of holonomic functions near and in regular singularities
cites work: Relax, but don't be too lazy
cites work: Efficient accelero-summation of holonomic functions
cites work: New algorithms for relaxed multiplication
cites work: Newton's method and FFT trading
cites work: Q3433195
cites work: Q4138813
cites work: Q2770573
cites work: Fast multiplication of large numbers
cites work: Q3676233
DOI: 10.5802/JTNB.777
description: scientific article; zbMATH DE number 6075047