From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wg0-f41.google.com (mail-wg0-f41.google.com [74.125.82.41]) (using TLSv1 with cipher RC4-MD5 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id E2533200681 for ; Fri, 4 May 2012 11:26:44 -0700 (PDT) Received: by wgbds1 with SMTP id ds1so1493569wgb.4 for ; Fri, 04 May 2012 11:26:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:from:to:cc:in-reply-to:references:content-type:date :message-id:mime-version:x-mailer:content-transfer-encoding; bh=YcmUfvLbWIJAnkABs1HXRkYHef318fMbnBhUM+moW28=; b=ZdpCf9hRiDnHN6ijZY2i7CMq+r+wmzpOI+2ftdW+mUpcRVmxpLExm8WOcdOz792Yml Pboh0P9btuPZ4pEudZQIag5IlO607XpvXv2tmJwOH+R82Y4bkyIXD0ZABkeRWNIkmiKj 9T3ayiipy+9qft22YbqRxgnVKYC4Fs/ZNH0N6bKCxGf/iUh0hWNoP7n3AhfKC9Jbz+3L r54UTHJbDnGVIZeOhJ1E0lw0atIsh/vzghUngIVRn6s5WY34A8UNYK6/MV5osMFDgFl2 lWc7AsOhm3NzX2TSHC55z0Iz/9WYns2F9v4xIf6u/YndVQ0jpdzeHIfS7J+ObhbeQRwz TLpg== Received: by 10.216.205.41 with SMTP id i41mr4220236weo.96.1336156002153; Fri, 04 May 2012 11:26:42 -0700 (PDT) Received: from [172.28.131.195] ([74.125.122.49]) by mx.google.com with ESMTPS id fl2sm17612098wib.2.2012.05.04.11.26.38 (version=SSLv3 cipher=OTHER); Fri, 04 May 2012 11:26:40 -0700 (PDT) From: Eric Dumazet To: Dave Taht In-Reply-To: <1336153652.3752.361.camel@edumazet-glaptop> References: <4FA3F248.3070101@freedesktop.org> <4FA3F50D.7080406@freedesktop.org> <1336146993.3752.354.camel@edumazet-glaptop> <1336153652.3752.361.camel@edumazet-glaptop> Content-Type: text/plain; charset="UTF-8" Date: Fri, 04 May 2012 20:26:36 +0200 Message-ID: <1336155996.3752.368.camel@edumazet-glaptop> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 7bit Cc: codel@lists.bufferbloat.net Subject: Re: [Codel] fp sqrt vis int sqrt? X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 May 2012 18:26:45 -0000 On Fri, 2012-05-04 at 19:47 +0200, Eric Dumazet wrote: > On Fri, 2012-05-04 at 10:23 -0700, Dave Taht wrote: > > > In looking over the (lack of) compiler support for fp in the kernel, > > it seems simplest to load up a table from userspace for the > > interval/sqrt(count) calculation. > > Well, you could have a small table (not from userspace, thats really not > needed at all) for the 16 first sqrt values. > > More over, for the first sqrt values you can use reciprocal divide so > that we dont have a divide anymore (see include/linux/reciprocal_div.h), > and you can have a very precise sqrt this way, not an integral one. > > With count >= 16, the error you mention becomes small. proof of concept You can see the integer approximation, using only a multiply is pretty good compared to a float computation, # ./try 1 val=16777216 sqrt=4096 rec=4294967295 interval/sqrt(1)=100000000 integer approx :99999999 2 val=33554432 sqrt=5792 rec=3037327360 interval/sqrt(2)=70710678 integer approx :70718288 3 val=50331648 sqrt=7094 rec=2479869952 interval/sqrt(3)=57735026 integer approx :57738971 4 val=67108864 sqrt=8192 rec=2147483648 interval/sqrt(4)=50000000 integer approx :50000000 5 val=83886080 sqrt=9158 rec=1920966656 interval/sqrt(5)=44721359 integer approx :44725990 6 val=100663296 sqrt=10033 rec=1753436160 interval/sqrt(6)=40824829 integer approx :40825366 7 val=117440512 sqrt=10836 rec=1623494656 interval/sqrt(7)=37796447 integer approx :37799930 8 val=134217728 sqrt=11585 rec=1518534656 interval/sqrt(8)=35355339 integer approx :35356140 9 val=150994944 sqrt=12288 rec=1431658496 interval/sqrt(9)=33333333 integer approx :33333396 10 val=167772160 sqrt=12952 rec=1358262272 interval/sqrt(10)=31622776 integer approx :31624507 11 val=184549376 sqrt=13584 rec=1295069184 interval/sqrt(11)=30151134 integer approx :30153179 12 val=201326592 sqrt=14188 rec=1239937024 interval/sqrt(12)=28867513 integer approx :28869533 13 val=218103808 sqrt=14768 rec=1191239680 interval/sqrt(13)=27735009 integer approx :27735710 14 val=234881024 sqrt=15325 rec=1147940864 interval/sqrt(14)=26726124 integer approx :26727581 15 val=251658240 sqrt=15863 rec=1109008384 interval/sqrt(15)=25819888 integer approx :25821113 cat try.c #include #include typedef unsigned int u32; typedef unsigned long long u64; static inline u32 reciprocal_divide(u32 A, u32 R) { return (u32)(((u64)A * R) >> 32); } unsigned long int_sqrt(unsigned long x) { unsigned long op, res, one; op = x; res = 0; one = 1UL << (32 - 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; } u32 reciprocal_value(u32 k) { u64 val = (1LL << 32) + (k - 1); val = val/k; return (u32)val; } int main() { unsigned long l, val, sq; unsigned interval = 100000000; u32 rec; for (l = 1 ; l < 16; l++) { val = (l << 24); sq = int_sqrt(val) ; rec = reciprocal_value(sq) << 12; if (!rec) rec = ~0U; printf("%lu val=%lu sqrt=%lu rec=%u\n", l, val, sq, rec); printf("interval/sqrt(%u)=%u integer approx :%u\n", l, (u32)(interval/sqrt(l)), reciprocal_divide(interval, rec)); } }