From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yw0-f43.google.com (mail-yw0-f43.google.com [209.85.213.43]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id F01D2200681 for ; Fri, 4 May 2012 08:14:21 -0700 (PDT) Received: by yhkk6 with SMTP id k6so3621878yhk.16 for ; Fri, 04 May 2012 08:14:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:organization:user-agent:mime-version:to :cc:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=Fl95yF5gHtVCgZjq2VWHeeRzDdg2FNtna4ehgjShiIY=; b=bGkB0aXZ5G75tV84uBKazj6CjIU0RuSqMMpbPzmuuyMIrgPB1Cxyxch9vfiIXvzwA3 WbvlLAe7Om+up56yb7bHl+CvK8o+EPi9Bm48dAEEOg4ROM53nDKIwEs/4KPeLNJY+QG3 lC61RxKV++hTaKPqKF9SLC/TIoZVEbRJbWscw9KimmAii+QNqe6siYwYMrbF6+K1JZdY OOE/ffhrKYR/BwxAmTv7mMD/rqavNVcrOE3BVDubT8heoCu80MeG+XEt6uAGbwA3cf/6 vwD4SAtbiILjuuK59dj2uxuojFj1xn0wuH2fCFHioFlsvjB0QSD3yiStTzrzdedrjI0S X0ZQ== Received: by 10.236.78.72 with SMTP id f48mr8369493yhe.121.1336144460929; Fri, 04 May 2012 08:14:20 -0700 (PDT) Received: from [10.0.0.4] (c-24-218-179-128.hsd1.ma.comcast.net. [24.218.179.128]) by mx.google.com with ESMTPS id r5sm13741708ani.19.2012.05.04.08.14.19 (version=SSLv3 cipher=OTHER); Fri, 04 May 2012 08:14:20 -0700 (PDT) Sender: Jim Gettys Message-ID: <4FA3F248.3070101@freedesktop.org> Date: Fri, 04 May 2012 11:14:16 -0400 From: Jim Gettys Organization: Bell Labs User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:11.0) Gecko/20120329 Thunderbird/11.0.1 MIME-Version: 1.0 To: Dave Taht References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 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 15:14:22 -0000 On 05/04/2012 11:11 AM, Dave Taht wrote: > The linux kernel has no floating point in it, so I'd substituted the > internal int_sqrt as a substitute, > just to get something to work. > > static inline ktime_t control_law(const struct codel_sched_data *q, ktime_t t) > { > return ktime_add_ns(t, q->interval / int_sqrt(q->count)); > } > > Often ns2 models use floating point. Having not seen the model I don't > know that for sure. > > The series for an integer sqrt is far more 'chunky' than a fp one. > > int sqrt 1,2,3,4 = 1 1 1 2 > fp sqrt 1 2 3 4 = 1 1.4.1 1.73 2 > > and gets even more chunky as you get larger values, eg, sqrt(36 > through 48) = 6, sqrt(49) = 7 > > So we could precalculate the interval/sqrt(count) using floating point > in the control law calculation, > early, during qdisc setup, thus neatly avoiding both the divide and > sqrt in the control law path. > > Or we could do fixed point. > > Kathie: In the sim, in various simulations, what is the dynamic range > of count? And is it floating point sqrt? > The Wikipedia article on fast inverse sqrt is enlightening on computing this really fast. See: http://en.wikipedia.org/wiki/Fast_inverse_square_root This has little to do with whether an integer or floating point value is better algorithmically. - Jim