isqrt

isqrt.c

#include <stdio.h>
#include <stdint.h>

uint64_t myisqrt(uint64_t n) {
	int i;
	uint64_t r, tmp;
	
	r = 0;
	for(i = 64/2-1; i >= 0; i--) {
		tmp = r | (1 << i);
		if(tmp*tmp <= n) r = tmp;
	}

	return r;
}

void test_myisqrt(uint64_t n) {
	uint64_t r;
	r = myisqrt(n);
	printf("isqrt(%lu) = %lu, -^2 = %lu\n", n, r, r*r);
}

int main(void) {
	test_myisqrt(0);
	test_myisqrt(1);
	test_myisqrt(2);
	test_myisqrt(3);
	test_myisqrt(2*2);
	test_myisqrt(3241*3241);
	test_myisqrt(3242*3242);
	test_myisqrt(3243*3243);
	test_myisqrt(55*55);
	test_myisqrt(55*55+100);
}