Exercism - Square Root

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

While Loops

While loops execute a block of code repeatedly as long as a condition is true. In Newton’s method, we use a while loop to iterate until the approximation converges.

void main() {
  int x = 10;
  int y = 5;
  
  // Continue until convergence (y >= x)
  while (y < x) {
    x = y;
    y = (x + 20 ~/ x) ~/ 2; // Newton's method formula
    print('x: $x, y: $y');
  }
  
  // Loop stops when y >= x (converged)
}

Integer Division

Integer division (~/) divides two numbers and returns an integer result, discarding any remainder. This is essential for Newton’s method to work with integers.

void main() {
  int radicand = 16;
  int guess = 5;
  
  // Newton's method formula using integer division
  int newGuess = (guess + radicand ~/ guess) ~/ 2;
  print(newGuess); // (5 + 16/5) / 2 = (5 + 3) / 2 = 4
  
  // Without integer division, we'd get a double
  double decimal = (guess + radicand / guess) / 2;
  print(decimal); // 4.1
}

Comparison Operators

Comparison operators allow you to compare values. In Newton’s method, we use < to check if the new approximation is still improving (converging).

void main() {
  int x = 10;
  int y = 5;
  
  // Check if still converging
  bool converging = y < x;
  print(converging); // true (y is less than x, so still improving)
  
  // Used in Newton's method loop
  while (y < x) {
    // Continue iterating
    x = y;
    y = (x + 16 ~/ x) ~/ 2;
  }
}

Arithmetic Operations

Basic arithmetic operations are used in Newton’s method formula: (guess + number/guess) / 2. This combines addition, division, and integer division.

void main() {
  int radicand = 16;
  int guess = 8;
  
  // Newton's method: (guess + radicand/guess) / 2
  int newGuess = (guess + radicand ~/ guess) ~/ 2;
  print(newGuess); // (8 + 16/8) / 2 = (8 + 2) / 2 = 5
  
  // Initial guess calculation
  int initialGuess = (radicand + 1) ~/ 2;
  print(initialGuess); // (16 + 1) / 2 = 8
}

Conditional Logic

You can use if statements to handle edge cases before performing calculations. For square root, we check if the number is 0 or 1.

void main() {
  int radicand = 1;
  
  // Handle edge cases: 0 and 1 are their own square roots
  if (radicand < 2) {
    print(radicand); // Return early for 0 or 1
  } else {
    // Perform Newton's method calculation
    print("Calculate using Newton's method");
  }
}

Introduction

We are launching a deep space exploration rocket and we need a way to make sure the navigation system stays on target.

As the first step in our calculation, we take a target number and find its square root (that is, the number that when multiplied by itself equals the target number).

The journey will be very long. To make the batteries last as long as possible, we had to make our rocket’s onboard computer very power efficient. Unfortunately that means that we can’t rely on fancy math libraries and functions, as they use more power. Instead we want to implement our own square root calculation.

Instructions

Your task is to calculate the square root of a given number.

Try to avoid using the pre-existing math libraries of your language.

As input you’ll be given a positive whole number, i.e. 1, 2, 3, 4…

You are only required to handle cases where the result is a positive whole number.

Some potential approaches:

Linear or binary search for a number that gives the input number when squared.
Successive approximation using Newton’s or Heron’s method.
Calculating one digit at a time or one bit at a time.

What is square root?

The square root of a number is a value that, when multiplied by itself, gives the original number. For example, the square root of 16 is 4, because 4 × 4 = 16.

Newton’s method (also known as the Babylonian method or Heron’s method) is an efficient algorithm for finding square roots. It uses iterative approximation, starting with an initial guess and refining it until convergence.

— Mathematics

How can we calculate square root?

To calculate the square root using Newton’s method:

Handle edge cases: If the number is 0 or 1, return it directly
Start with an initial guess (often the number itself or half of it)
Iteratively improve the guess using the formula: newGuess = (oldGuess + number / oldGuess) / 2
Continue until the guess converges (stops changing)
Return the integer part of the result

For example, finding √16:

Initial guess: 16
Iteration 1: (16 + 16/16) / 2 = (16 + 1) / 2 = 8.5 → 8
Iteration 2: (8 + 16/8) / 2 = (8 + 2) / 2 = 5
Iteration 3: (5 + 16/5) / 2 = (5 + 3) / 2 = 4
Result: 4 (since 4 × 4 = 16)

Solution (Newton’s Method - Recommended)

This solution uses Newton’s method (also known as the Babylonian method or Heron’s method), which is the most elegant and efficient approach for calculating square roots.

class SquareRoot {
  int squareRoot(int radicand) {
    if (radicand < 2) return radicand;
    
    int x = radicand;
    int y = (x + 1) ~/ 2;
    
    while (y < x) {
      x = y;
      y = (x + radicand ~/ x) ~/ 2;
    }
    
    return x;
  }
}

Let’s break down the solution:

if (radicand < 2) return radicand - Handles edge cases:
- If the number is 0 or 1, its square root is itself
- Returns early to avoid unnecessary calculations
int x = radicand - Initializes the first variable with the input number:
- This will hold the current approximation
int y = (x + 1) ~/ 2 - Calculates the initial guess:
- Uses integer division to get a starting point
- For large numbers, this is a reasonable initial approximation
- This is the first iteration of Newton’s method
while (y < x) - Iterates until convergence:
- The loop continues as long as the new guess y is less than the old guess x
- When y >= x, we’ve converged to the answer
- Newton’s method converges very quickly (typically 3-5 iterations)
Inside the loop:
- x = y - Updates the current approximation
- y = (x + radicand ~/ x) ~/ 2 - Calculates the next approximation using Newton’s method formula
- This formula: (guess + number/guess) / 2 is the core of Newton’s method
- Each iteration gets closer to the true square root
return x - Returns the final approximation:
- When the loop exits, x contains the integer square root
- This is the largest integer whose square is less than or equal to the input

Why Newton’s Method?

✅ Fastest convergence (O(log log n) complexity)
✅ Most elegant and concise code
✅ Excellent for all input sizes
✅ Mathematical elegance and historical significance

Alternative Solutions

Here are several different approaches to calculating square root, each with their own advantages:

Solution 1: Binary Search (Efficient and Clean)

class SquareRoot {
  int squareRoot(int radicand) {
    if (radicand == 0 || radicand == 1) return radicand;
    
    int left = 1;
    int right = radicand;
    int result = 0;
    
    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      int square = mid * mid;
      
      if (square == radicand) {
        return mid;
      } else if (square < radicand) {
        left = mid + 1;
        result = mid;
      } else {
        right = mid - 1;
      }
    }
    
    return result;
  }
}

Solution 2: Newton’s Method (Babylonian Method)

class SquareRoot {
  int squareRoot(int radicand) {
    if (radicand == 0 || radicand == 1) return radicand;
    
    int guess = radicand ~/ 2;
    
    while (guess * guess > radicand) {
      guess = (guess + radicand ~/ guess) ~/ 2;
    }
    
    return guess;
  }
}

Solution 3: Linear Search (Simple but slower)

class SquareRoot {
  int squareRoot(int radicand) {
    if (radicand == 0 || radicand == 1) return radicand;
    
    for (int i = 1; i <= radicand; i++) {
      if (i * i == radicand) return i;
      if (i * i > radicand) return i - 1;
    }
    
    return 0;
  }
}

Solution 4: Optimized Binary Search

class SquareRoot {
  int squareRoot(int radicand) {
    if (radicand < 2) return radicand;
    
    int left = 1;
    int right = radicand ~/ 2;
    
    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      int square = mid * mid;
      
      if (square == radicand) return mid;
      if (square < radicand) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return right;
  }
}

Solution 5: Bit-by-Bit Calculation

class SquareRoot {
  int squareRoot(int radicand) {
    if (radicand < 2) return radicand;
    
    int result = 0;
    int bit = 1 << 30; // Start with the highest bit
    
    while (bit > radicand) {
      bit >>= 2;
    }
    
    while (bit != 0) {
      if (radicand >= result + bit) {
        radicand -= result + bit;
        result = (result >> 1) + bit;
      } else {
        result >>= 1;
      }
      bit >>= 2;
    }
    
    return result;
  }
}

Solution Comparison

Newton’s Method (Recommended):

✅ Fastest convergence (typically 3-5 iterations)
✅ Most elegant and concise code
✅ Excellent for all input sizes
✅ Mathematical elegance

Binary Search:

✅ Easy to understand and implement
✅ Predictable performance
✅ Good for educational purposes
⚠️ Slightly slower than Newton’s method

Optimized Binary Search:

✅ Better initial bounds (starts at radicand ~/ 2)
✅ Same complexity as standard binary search
✅ Fewer iterations in practice
⚠️ Still slower than Newton’s method

Linear Search:

✅ Simplest to understand
✅ Straightforward implementation
⚠️ Slowest for large numbers
⚠️ Only suitable for small inputs

Bit-by-Bit:

✅ Very efficient for very large numbers
✅ Uses bit manipulation (power-efficient)
⚠️ Most complex to understand
⚠️ Harder to maintain

Recommendation

Newton’s Method is the recommended solution because it offers the best balance of:

Speed (fastest convergence)
Code elegance (most concise)
Readability (clear mathematical approach)
Efficiency (works well for all input sizes)

You can watch this tutorial on YouTube. So don’t forget to like and subscribe. 😉

Watch on YouTube