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 for Android: free password hash cracker in your pocket

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

Message-ID: <20080717181059.GL31126@csclub.uwaterloo.ca>
Date:	Thu, 17 Jul 2008 14:10:59 -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 :-)

So so far the line:
        if((m * m) > x)
overflows easily in which case the result is wrong.

Also at least on my Athlon 2500, this new algorithm takes 3.5 times
longer than the old one to get result when doing all square roots from 0
to 200000000, which is no improvement.

-- 
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/