linux-kernel - Re: [PATCH] : A better approach to compute int_sqrt in lib/int

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20080716220556.GI31126@csclub.uwaterloo.ca>
Date:	Wed, 16 Jul 2008 18:05:56 -0400
From:	lsorense@...lub.uwaterloo.ca (Lennart Sorensen)
To:	Soumyadip Das Mahapatra <soumya.linux@...oo.com>
Cc:	peterz@...radead.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c

On Wed, Jul 16, 2008 at 02:35:56PM -0700, Soumyadip Das Mahapatra wrote:
> Thanks Peter for noticing :-)
> Sorry, I should have it explained before. Really sorry
> for that. Here are they...
> 
> 0 It is better because 
>          o it uses only one loop instead of two
>          o contains no division operator (older version has two)
>             which are surely comparatively slow task in computer
> 
> 0 Currently find . -name '*.[ch]' | xargs grep int_sqrt gives me this
>         ....
>         ./fs/nfs/write.c:       nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10);
>         ./drivers/video/fbmon.c:        h_period = int_sqrt(h_period);
>         ./mm/page_alloc.c:      min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
>         ./mm/oom_kill.c:        s = int_sqrt(cpu_time);
>         ./mm/oom_kill.c:        s = int_sqrt(int_sqrt(run_time));
>         ....
>   So this function works in critical computing sections like frame-buffer, paging.
>   Which means betterment of this function should not be ignored.
>   Besides, if there is a better way to do things then why should not we do that ?
> 
> Anyways thanks :-)

It is also very inaccurate:

int_sqrt(9380489) returns 3062 with the old code and 146574 with the new
code.  I wonder which one is closer to right.  It seems as soon as the
input is 2^22 or higher, the new code goes all to hell and starts
returning 2^16-1 or similarly silly values rather than 2^11-1 or
similar.

Here is how I tested:

(compiled with gcc -Wall -O2 -std=c99)

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#define BITS_PER_LONG 32

unsigned long old_int_sqrt(unsigned long x) {
	unsigned long op, res, one;

	op = x;
	res = 0;

	one = 1UL << (BITS_PER_LONG - 2);
	while (one > op)
		one >>= 2;

	while (one != 0) {
		if (op >= res + one) {
			op = op - (res + one);
			res = res +  2 * one;
		}
		res /= 2;
		one /= 4;
	}
	return res;
}

unsigned long new_int_sqrt(unsigned long x) {
	unsigned long ub, lb, m;
	lb = 1;				/* lower bound */
	ub = (x >> 5) + 8;		/* upper bound */
	do {
		m = (ub + lb) >>  1;	/* middle value */
		if((m * m) > x)
			ub = m - 1;
		else
			lb = m + 1;
	} while(ub >= lb);

	return lb - 1;
}

int main() {
	unsigned long i;
	unsigned long old;
	unsigned long new;
	for(i=0;i<10000000;i++) {
		old=old_int_sqrt(i);
		new=new_int_sqrt(i);
		if(new!=old) {
			printf("sqrt(%lu)= %lu(new)->%llu %lu(old)->%llu",i,new,(unsigned long long)new*(unsigned long long)new,old,(unsigned long long)old*(unsigned long long)old);
			if(llabs((unsigned long long)new*(unsigned long long)new - (unsigned long long)i) < llabs((unsigned long long)old*(unsigned long long)old - (unsigned long long)i)) {
				printf(" (new is best)\n");
			} else {
				printf(" (old is best)\n");
			}
		}
	}
	return 0;
}

Example output:
sqrt(9380468)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380469)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380470)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380471)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380472)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380473)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380474)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380475)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380476)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380477)= 146574(new)->21483937476 3062(old)->9375844 (old is best)
sqrt(9380478)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

-- 
Len Sorensen
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/