This is a small program I’ve come up with, with the intention of finding the root of a perfect square. I wanted some comments on the performance impact, as well as the use of resources.

square_root.c 
#include "square_root.h"

static uint64_t power(uint8_t base, uint8_t exp) {
    uint64_t result = 1;

    while (exp--) {
        result *= base;
    }

    return result;
}

static uint64_t seed(uint64_t radicand) {
    uint64_t a = radicand;
    uint64_t n = 0;

    while (radicand /= 100) {
        a = radicand;
        ++n;
    }

    return ((a < 10)
        ? ((0.28 * a) + 0.89)
        : ((0.089 * a) + 2.8)) * power(10, n);
}

static uint64_t heron(uint64_t x, uint64_t s) {
    while (s != power(x, 2)) {
        x = (x + (s / x)) / 2;
    }

    return x;
}

uint16_t square_root(uint64_t radicand) {
    return heron(seed(radicand), radicand);
}
square_root.h 
#ifndef SQUARE_ROOT_H
#define SQUARE_ROOT_H

#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>

uint16_t square_root(uint64_t radicand);

#endif
  • @drspod
    9•22 days ago
    • if square_root takes a uint64_t argument then it should return a uint32_t
    • x = (x + (s / x)) / 2; This update of the test value uses integer divisions which means it is not guaranteed to converge (due to the truncation moving your approximation further away than the previous iteration). You should also check that x > 0 to avoid accidental division by zero.
    • it looks like seed is trying to calculate pow(10, log_100(x)) in some way, but it has bugs, for example a < 10 is true for radicand values of 100-999, 10000-99999, 1000000-9999999 etc. which probably isn’t what you want. An easier way to estimate a starting value for the first iteration would be to take a number that has half as many bits as the input, since we know that if a number X uses K bits then its square root will use K/2 bits. You can use a method to calculate the position of the most significant set bit in the input and then use 2^(k/2) as the seed.
    • for ease of readability and checking correctness, I would recommend that you don’t use implicit casts to float for arithmetic and avoid implicit casts back to integers with the results. Declare floating point variables when you want floating point arithmetic and then use explicit casts back to ints to make it clear to the reader (reviewer) that any truncation of the result is intentional. This is considered good practice when writing C. You can compile with -Wall -Werror (with gcc) to enforce those checks and make them compile errors that you must fix.
    • @velox_vulnusOP
      1•21 days ago

      This is going to take a bit longer to grasp, because I converted the formula from Wikipedia, and I don’t remember doing this in my high school or college before.