On the construction of the square roots of natural numbers

Introduction

This repository contains a Java program that explores a rational sequence designed to approximate square roots of positive integers.

The idea originated from a topology of metric space course, where I was challenged to find a rational sequence that converges to the square root of two. Later, inspired by Euler’s method for approximating square roots, I derived a general expression for computing square roots using a sequence.

To verify its accuracy and convergence properties, I implemented this Java program to generate and analyze the sequence for different values. Since manual calculations quickly became impractical (e.g., for n=5, the sequence produces extremely large values), this program automates the process and provides insights into its behavior.

A more detailed theoretical discussion, including mathematical proofs, is available in a separate LaTeX-written article in another repository which is for now still private for some reasons.

---

This project is a research-based implementation of a rational sequence that approximates the square root of any positive number.
It combines mathematical rigor and high-performance Java code to demonstrate how a dense subset of ℚ (rational numbers) can be used to approach any real number √n with extreme precision.

---

About this program :

In this repository, I'm just going to cover the algorithm part of the main idea.

Java Version and dependencies

This program is written in Java 22 and uses Maven as dependency manager. Make sure you have JDK 22 installed before running it.

In addition to being written in Java 22 and using Maven as a dependency manager, this program also relies on GMP (GNU Multiple Precision Arithmetic Library) and JNA (Java Native Access). Instead of using BigInteger.gcd, the program leverages GMP for high-performance arithmetic operations, particularly for computing greatest common divisors (GCD) efficiently. This significantly improves performance when dealing with very large numbers in fraction operations.

Installation requirements :

To properly run this program, make sure the following dependencies are installed on your system:

• Windows: Install GMP using MSYS2 or manually compile it.

• Linux:

  • Debian/Ubuntu:

    sudo apt install libgmp-dev
    

  • Arch Linux:

    sudo pacman -S gmp
    

  • Fedora:

    sudo dnf install gmp-devel
    

• MacOS: Install GMP via Homebrew:

  brew install gmp
  

Additionally, JNA is managed via Maven, so no manual installation is required. However, ensure that your Java environment is correctly set up to load native libraries.

About the class Fraction:

Indeed, as we are using Java while dealing with rational numbers, I preferred to implement my owned version of what we define by rational number in programming : fractions.

The program provides an object called Fraction which represents fraction in mathematical world.

So by doing :

Fraction oneHalf = new Fraction(1,2);

It will be similar on doing :

$$ x=\frac{1}{2} $$

The program provides some default fraction such as Fraction.ZEROand Fraction.ONEwhich are the zero fraction and the one fraction.

In mathematical world, the Fraction.ZERO is just :

$$ q\in\mathbb{N}^{*},\quad 0 = \frac{0}{q} = \frac{0}{1} $$

And the Fraction.ONEis just :

$$ p\in\mathbb{N}^{*}, \quad 1 = \frac{p}{p} = \frac{1}{1} $$

The fraction Fraction acts exactly as a mathematical fraction does. So, all operation provided by the filed :

$$ (\mathbb{Q}, +, \ \cdot \ ) $$

is available.

About the Test Data

To verify the accuracy of the sequence, we compare our results with high-precision values from reliable external sources.

All test data used in this repository come from trusted mathematical sources:

• NASA's Astronomy Picture of the Day (APOD) numerical data repository

Here are the data files and their sources:

File Name	Source
sqrt_2.txt	NASA - sqrt2.10mil
sqrt_3.txt	NASA - sqrt3.1mil
sqrt_5.txt	NASA - sqrt5.1mil
sqrt_6.txt	NASA - sqrt6.1mil
sqrt_7.txt	NASA - sqrt7.1mil

These sources provide extremely precise approximations of well-known mathematical constants. Since NASA rely on precise calculations for research and space exploration, their datasets are considered highly accurate.

By using these sources, we ensure that the program's results are tested against verified, high-precision values, reinforcing the reliability of the algorithm.

About tests precision :

4/5 of the tests found in the test package have exactly ONE MILLION (1,000,000) decimal places. The test for square root of 2 is about SIX MILLION (6,000,000) decimal places.

Mathematical remarks about the tests:

As we can notice in tests done in the test package, we can see that :

$$ \vert \sqrt{2} - x_{23} \vert < 10^{-6.10^{6}} $$

$$ \vert \sqrt{3} - x_{20} \vert < 10^{-10^{6}} $$

$$ \vert \sqrt{5} - x_{21} \vert < 10^{-10^{6}} $$

$$ \vert \sqrt{6} - x_{20} \vert < 10^{-10^{6}} $$

$$ \vert \sqrt{7} - x_{20} \vert < 10^{-10^{6}} $$

About the SquareRoots

SquareRoot and SquareRootSub implement an abstract class called Sequence, which is the super class of all sequences that are going to be used in this program. That SquareRoot class is where This repository focuses in.

According to its implementation, we can find the expression of the sequence in the SquareRoots kThValue method which gives us the k-th value of the square root sequence. The natural mathematical notation will be

$$ x_k $$

The mathematical expression of this sequence is the following :

$$ \text{Let } m\in\mathbb{N}^{*}. \$$

$$ \text{Let } \mathcal{S} \text{ be the set of all perfect square. }. \\\ $$

$$ \text{Now, let } c \text{ be the smallest perfect square greater or equal to } m \Longleftrightarrow \ c^{2} = \min_{s\in \mathcal{S}, s \geq m} \lbrace s - m \rbrace $$

$$ \text{Let $(a_n)_{n\in\mathbb{N}^{*}}$ be a sequence defined by the following recursion : } \qquad $$

$$ (a_n) \ : \quad \begin{cases} a_1 = \frac{2c}{c^{2}-m} \\\ a_2 = \frac{4c\left(c^{2} + m\right)}{\left(c^{2}-m\right)^{2}} \\\ a_{n+2} = a_{n+1}\cdot\left(\frac{a_{n+1}^{2}}{a_{n}^{2}} - 2\right) \end{cases} $$

Then the final sequence that gives us the square root of m is the following :

$$ \therefore \quad \sqrt{m} = c-\lim_{n \longrightarrow +\infty} \sum_{k = 1}^{n}{\frac{1}{a_k}} $$

$$ = c-\sum_{n = 1}^{\infty}{\frac{1}{a_n}} = \lim_{n \longrightarrow +\infty} x_n \$$

$$ \text{Where } (x_n) \text{ is defined by : } \\\ x_n = c - \sum_{k = 1}^{n}{\frac{1}{a_k}} $$

Where the SquareRootSub class represents the sequence

$$ (a_{n})_{\mathbb{N^{*}}} $$

and the SquareRoot class represents the sequence

$$ (x_{n})_{\mathbb{N^{*}}} $$

Author: Abegà Razafindratelo