From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <eric.dumazet@gmail.com>
Received: from mail-bk0-f43.google.com (mail-bk0-f43.google.com
	[209.85.214.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 259C1200681
	for <codel@lists.bufferbloat.net>; Fri,  4 May 2012 11:50:21 -0700 (PDT)
Received: by bkty5 with SMTP id y5so5610114bkt.16
	for <codel@lists.bufferbloat.net>; Fri, 04 May 2012 11:50:20 -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=Ob/8q420vyeGm2MJIwvfVk+Gp0LC0tzXkux4oumhWtc=;
	b=cBKxf3qOXllwu4vOU8zxzDuBWz54ABEosuXCa4zS2vzPcvg9lkqsX360pV5zQBHFbd
	Ap5nmAxG+4j2lOn1h6f+e5Q9PdFI7mBVFDnWGSbhkoxCPtQcDVlX1KuVRRESOiGePMgm
	zkDnZ9INTrTd5eNlfY5dMWYueJkDAxTIqf17+cKbS7JtYnxMK5jP/74oZGNcj4fMquql
	d05ri6TLRmY/eO8YMT04hG0UR+XLNllJkXKZFrCS3BxRa3wSvAglnL69Kqwy9e2JPgUT
	3XD8Ni9Fu2Ua0Yzq7tAz/9oDBGFBGuEV/1mOGaxSx0nqushoFoFXip62bXqRZGTFlXXb
	+WwA==
Received: by 10.205.128.8 with SMTP id hc8mr2524960bkc.17.1336157420122;
	Fri, 04 May 2012 11:50:20 -0700 (PDT)
Received: from [172.28.131.195] ([74.125.122.49])
	by mx.google.com with ESMTPS id gm18sm18511426bkc.7.2012.05.04.11.50.17
	(version=SSLv3 cipher=OTHER); Fri, 04 May 2012 11:50:18 -0700 (PDT)
From: Eric Dumazet <eric.dumazet@gmail.com>
To: Dave Taht <dave.taht@gmail.com>
In-Reply-To: <CAA93jw7t4pA7Z_pxLTVoVa6+DujMd3D+Km5m2PKHspyjWL6D9w@mail.gmail.com>
References: <CAA93jw49KZZHBfb47cGN7tTxw8RbGzHHEVodhdpzmbOp78CREQ@mail.gmail.com>
	<4FA3F248.3070101@freedesktop.org>
	<CAA93jw4wzVLrMOq+RzP2FTHCHaPrFAY06xJX=Q94nPO0z2-OcQ@mail.gmail.com>
	<4FA3F50D.7080406@freedesktop.org>
	<1336146993.3752.354.camel@edumazet-glaptop>
	<CAA93jw7Mo0QdhgKk2p+LeT_esv6TSA2qhgK5Xg7YzcDHX=z3WA@mail.gmail.com>
	<1336153652.3752.361.camel@edumazet-glaptop>
	<1336155996.3752.368.camel@edumazet-glaptop>
	<CAA93jw7t4pA7Z_pxLTVoVa6+DujMd3D+Km5m2PKHspyjWL6D9w@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"
Date: Fri, 04 May 2012 20:50:16 +0200
Message-ID: <1336157416.3752.378.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 <codel.lists.bufferbloat.net>
List-Unsubscribe: <https://lists.bufferbloat.net/options/codel>,
	<mailto:codel-request@lists.bufferbloat.net?subject=unsubscribe>
List-Archive: <https://lists.bufferbloat.net/private/codel>
List-Post: <mailto:codel@lists.bufferbloat.net>
List-Help: <mailto:codel-request@lists.bufferbloat.net?subject=help>
List-Subscribe: <https://lists.bufferbloat.net/listinfo/codel>,
	<mailto:codel-request@lists.bufferbloat.net?subject=subscribe>
X-List-Received-Date: Fri, 04 May 2012 18:50:22 -0000

On Fri, 2012-05-04 at 11:39 -0700, Dave Taht wrote:
> Heh. I'd only gotten as far as
> 
> #include <stdio.h>
> #include <math.h>
> main() {
> 
> 
> 
> 
> 
> before your mail arrived.

Yep, so maybe we can use a precomputed table of 25 values (100 bytes),
using the reciprocal trick to get precise integer approximation.

(interval/sqrt(count)). 

So that control_law() has no multiply or divide to do, just a lookup in
the array.

Then for count values >= 25, either we can afford an error less than 20%
using the q->sqrt_count maintained in // with q->count, either we
compute the reciprocal each time we change q->count. 

(cost : one divide + int_sqrt() call )
plus one multiply in control_law()

Not sure we need to be ultra precise.