From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1030349AbXCFV6i (ORCPT ); Tue, 6 Mar 2007 16:58:38 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1030334AbXCFV6i (ORCPT ); Tue, 6 Mar 2007 16:58:38 -0500 Received: from 74-93-104-97-Washington.hfc.comcastbusiness.net ([74.93.104.97]:55341 "EHLO sunset.davemloft.net" rhost-flags-OK-FAIL-OK-OK) by vger.kernel.org with ESMTP id S1030327AbXCFV6h (ORCPT ); Tue, 6 Mar 2007 16:58:37 -0500 Date: Tue, 06 Mar 2007 13:58:34 -0800 (PST) Message-Id: <20070306.135834.26100913.davem@davemloft.net> To: shemminger@linux-foundation.org Cc: rkuhn@e18.physik.tu-muenchen.de, andi@firstfloor.org, dada1@cosmosbay.com, jengelh@linux01.gwdg.de, linux-kernel@vger.kernel.org, netdev@vger.kernel.org Subject: Re: [RFC] div64_64 support From: David Miller In-Reply-To: <20070306102941.32471d57@freekitty> References: <20070306144529.GA2004@one.firstfloor.org> <84C47260-4B57-4568-8197-58F438A6F737@e18.physik.tu-muenchen.de> <20070306102941.32471d57@freekitty> X-Mailer: Mew version 5.1.52 on Emacs 21.4 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org From: Stephen Hemminger Date: Tue, 6 Mar 2007 10:29:41 -0800 > /* calculate the cubic root of x using Newton-Raphson */ > static uint32_t ncubic(uint64_t a) > { > uint64_t x; > > /* Initial estimate is based on: > * cbrt(x) = exp(log(x) / 3) > */ > x = 1u << (fls64(a)/3); > > /* Converges in 3 iterations to > 32 bits */ > > x = (2 * x + div64_64(a, x*x)) / 3; > x = (2 * x + div64_64(a, x*x)) / 3; > x = (2 * x + div64_64(a, x*x)) / 3; > > return x; > } Indeed that will be the fastest variant for cpus with hw integer division. I did a quick sparc64 port, here is what I got: Function clocks mean(us) max(us) std(us) total error ocubic 529 0.35 15.16 0.66 545101 ncubic 498 0.33 12.83 0.36 576263 acbrt 427 0.28 11.04 0.33 547562 hcbrt 393 0.26 10.18 0.47 2410