A Newton-Free, Digit-Recurrence Approach to nn-th Root Extraction Using Balanced Numeral Systems

A Newton-Free, Digit-Recurrence Approach to n-th Root Extraction Using Balanced Numeral Systems Balaji G* November 15, 2025 Abstract Introduction: This paper presents a complete departure from iterative refinement techniques such as Newton–Raphson for high-precision computation of n-th roots. By leveraging the structural properties of balanced numeral systems, the approach eliminates traditional reliance on floating-point arithmetic and iterative corrections. Methodology: The framework is divided into two parts: 1. Foundational Theory: Lattice completion values and affine-invariant digit extraction in balanced bases. 2. Dual Computation Methods: ˆ Balanced Error Decoding: Direct extraction of digits from the balanced representation of the residual N − xp. ˆ Progressive Digit-Appending Method: Structured digit appending via rational approximations, yielding roots without high-precision arithmetic. Execution: Both methods operate in O(log P) steps for P-digit accuracy, support arbitrary odd radices, and emit digits sequentially without full-precision storage. The schemes are carry-free, deterministic, and utilize only integer operations. Applications: Enables real-time root extraction for cryptographic primes, mathematical constants, and embedded systems under constraints of precision, memory, or side-channel resistance. Conclusion and Significance: This work establishes the first complete Newton-free framework for n-th root computation, combining theoretical rigor with algorithmic efficiency. It is presented as a practical alternative to series-based and iterative methods in computationally critical domains. Keywords: n-th root algorithms, balanced numeral systems, error decoding, rational approximation, digit-recurrence, cryptographic arithmetic, Newton-free computation *ORCID: 0009-0003-9412-0002 1