From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p05GMTQW022043 for ; Wed, 5 Jan 2011 17:22:29 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmIBAO8pJE1KfVM2kWdsb2JhbACVXjGGAgGICQgVAQEBAQkLCgcRBCCncIl4ghiEZi6FcQEBAwWFRwSLCg X-IronPort-AV: E=Sophos;i="4.60,278,1291590000"; d="scan'208";a="72178014" Received: from mail-gw0-f54.google.com ([74.125.83.54]) by mail3-smtp-sop.national.inria.fr with ESMTP; 05 Jan 2011 17:22:22 +0100 Received: by gwj21 with SMTP id 21so7476276gwj.27 for ; Wed, 05 Jan 2011 08:22:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:date:message-id :subject:from:to:content-type; bh=ONNAEu3IE2qWAMUaya0z+CC/fHttX+ZAgdHe1f6Z3qg=; b=b3+PqD6BTSHdeHKgYlnuV7DcexuedQYoWwHor79CIiOslW1+MhR/gSdYblOQNv/V5Q V9qKiAXLvx8JsR+8noOiXEY4lKIshu2V2yxqz4olQHBBhhbNDwj06rar1orff5eWPMrT Vhv6J14XIdmxOLoF90mdEfJ/XyEqejhsGphLw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type; b=Vy8mq1p1TgSbYtOjIetPuWunAFi4LGgvZPP10iU7Vsux1ZKKe6SqnurrBo4LbBrejZ MYBlz2uNz2m7MOvHWsCL1ylKZosJY/wsH5L2H3M0K3p/fZuSUKg5ygzIpX+C+IuMYO+B Cy6ttAM8yBAABoqfrgOD00uUfsnTE+23qd1UM= MIME-Version: 1.0 Received: by 10.90.72.16 with SMTP id u16mr862131aga.146.1294244542268; Wed, 05 Jan 2011 08:22:22 -0800 (PST) Received: by 10.90.67.15 with HTTP; Wed, 5 Jan 2011 08:22:20 -0800 (PST) Date: Wed, 5 Jan 2011 18:22:20 +0200 Message-ID: From: Eray Ozkural To: caml-list@inria.fr Content-Type: multipart/alternative; boundary=00163630e96331c37604991bca3e Subject: [Caml-list] Fixed-point arithmetic on 32-bit architectures --00163630e96331c37604991bca3e Content-Type: text/plain; charset=ISO-8859-1 Hello there, I'm using fixed-point arithmetic in an algorithm. I am troubled by the inefficiency of the fixed-point multiplication and division operations on 32-bit architectures. On the Intel 64-bit architecture, I can use the Nativeint module and it's quite fast, on 32-bit I had to use the Int64 module (for the necessary shifts and mul/div's) and I encountered a significant slowdown, naturally. is there a preferred way of performing fixed point arithmetic with ocaml on 32-bit architectures that I might be overlooking? Best, -- Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara http://groups.yahoo.com/group/ai-philosophy --00163630e96331c37604991bca3e Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hello there,

I'm using fixed-point arithmetic in an = algorithm. I am troubled by the inefficiency of the fixed-point multiplicat= ion and division operations on 32-bit architectures. On the Intel 64-bit ar= chitecture, I can use the Nativeint module and it's quite fast, on 32-b= it I had to use the Int64 module (for the necessary shifts and mul/div'= s) and I encountered a significant slowdown, naturally. is there a preferre= d way of performing fixed point arithmetic with ocaml on 32-bit architectur= es that I might be overlooking?

Best,

--
Eray Ozkural, PhD candidate.= =A0 Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosoph= y

--00163630e96331c37604991bca3e-- From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p05GYdgH022647 for ; Wed, 5 Jan 2011 17:34:39 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Au0AAEcsJE3RVdg2kGdsb2JhbACDd5Fnjj0IFQEBAQEJCQwHEQQgp3SJPDyCGIRmLoVzAQEDBYEcgzd0BIRohiKGFA X-IronPort-AV: E=Sophos;i="4.60,278,1291590000"; d="scan'208";a="84260194" Received: from mail-qw0-f54.google.com ([209.85.216.54]) by mail4-smtp-sop.national.inria.fr with ESMTP; 05 Jan 2011 17:34:34 +0100 Received: by qwj9 with SMTP id 9so15984230qwj.27 for ; Wed, 05 Jan 2011 08:34:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=u7JJybF/IFjW1+5DyfvjMP9otoepegEUMm4HadDzqrs=; b=xOhctedd5al4yzNnvIeU+WUMOy505zm58ShjinJ0H92kW8b/7k6iPGgURX6azH7i56 h7Qmz1xxlKWcZbgu/dGcucrX2b75ScEdZzzhJeo2eBrn95gxms+USbY+gdr8sxzdTYSk ARG3HPAnbgrbmiIUJSeo+FAByhZ/vn/ODgcqA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=th+jgfai7Hc/mkOiTwNEdJS7ArUR/pgLwOurGGbVx/tI+5uq+X/K1w82YYg9kFo9xv RKZzgpnErLUCzBkYemLre1D/tx0hOH6zJNc5jRofvZm4dRQut3Uut7cm0P12zB3asFtb AfIx8FJrpTH/ooULY6Zzb1sZDHGZZ9AEYH2e0= MIME-Version: 1.0 Received: by 10.229.216.143 with SMTP id hi15mr20396430qcb.27.1294245273426; Wed, 05 Jan 2011 08:34:33 -0800 (PST) Received: by 10.229.106.203 with HTTP; Wed, 5 Jan 2011 08:34:33 -0800 (PST) In-Reply-To: References: Date: Wed, 5 Jan 2011 11:34:33 -0500 Message-ID: From: Niki Yoshiuchi To: Eray Ozkural Cc: caml-list@inria.fr Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p05GYdgH022647 Subject: Re: [Caml-list] Fixed-point arithmetic on 32-bit architectures What range of numbers are you hoping to represent and what operations are you commonly performing on them? If it's possible for you to represent your numbers as 24.8 fixed-point (for example) and you are mostly adding and subtracting, then I would recommend using 32 bit integers and casting to 64 bit for multiplication and division. Alternatively you can try and be clever about your shifting instead of casting (shifting the multiplicand instead of the product, or doing a half shift on each multiplicand, etc). On Wed, Jan 5, 2011 at 11:22 AM, Eray Ozkural wrote: > Hello there, > I'm using fixed-point arithmetic in an algorithm. I am troubled by the > inefficiency of the fixed-point multiplication and division operations on > 32-bit architectures. On the Intel 64-bit architecture, I can use the > Nativeint module and it's quite fast, on 32-bit I had to use the Int64 > module (for the necessary shifts and mul/div's) and I encountered a > significant slowdown, naturally. is there a preferred way of performing > fixed point arithmetic with ocaml on 32-bit architectures that I might be > overlooking? > Best, > -- > Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara > http://groups.yahoo.com/group/ai-philosophy > > From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p05IciJu026041 for ; Wed, 5 Jan 2011 19:38:44 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjkBANhJJE3RVaG2kWdsb2JhbACVW4YzAYgJCBUBAQEBCQsKBxEEIKgJiXiCGIReLoVzAQEDBYVHBIsKhhQ X-IronPort-AV: E=Sophos;i="4.60,278,1291590000"; d="scan'208";a="84292322" Received: from mail-gx0-f182.google.com ([209.85.161.182]) by mail4-smtp-sop.national.inria.fr with ESMTP; 05 Jan 2011 19:38:15 +0100 Received: by gxk8 with SMTP id 8so6662005gxk.27 for ; Wed, 05 Jan 2011 10:38:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type; bh=XrkK92R+K6800BTDgx6OHhvgheWtppwDy2rzpMRSflg=; b=GV+CqjSisEakxASQRuR/NXb6ZWpML6PilO3b49ADYE5IT12Ja/sm+e3OjauGkX05k8 axK72P29P0n4Kz3NePrihCZ+QppPkw4kd64U7v0RWqnzxTCir6qwLYvG/aaPeaRNnNq1 P7At9rI8qcSlv2lcigKuMNbxKFCvfYoYaQnOk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=HKmmpxOyw1fM1Oh8kZAKcWee3Vov1MBUg/RM2Ujb+VVBqUG3cdGHmBK81BvYJHsCD1 tQlcmlR2GHKPcUA3PtIE/trKsKBmsmIM/kLPN5OEJpN48Ft+dIBAqA+Aa2UGbfFJvrcW cr3vsef++Nf1d5di13gwobaUhSvs+WH9eIQ4U= MIME-Version: 1.0 Received: by 10.91.21.33 with SMTP id y33mr1026120agi.92.1294252694446; Wed, 05 Jan 2011 10:38:14 -0800 (PST) Received: by 10.90.67.15 with HTTP; Wed, 5 Jan 2011 10:38:13 -0800 (PST) In-Reply-To: References: Date: Wed, 5 Jan 2011 20:38:13 +0200 Message-ID: From: Eray Ozkural To: Niki Yoshiuchi Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=001485f8617a1a24d004991db09f Subject: Re: [Caml-list] Fixed-point arithmetic on 32-bit architectures --001485f8617a1a24d004991db09f Content-Type: text/plain; charset=ISO-8859-1 Hi there, Thank you for your reply Niki. The range of numbers is usually between 0 and 1, because I'm mostly working on normalized vectors. I was using 22 bits for the decimal part but unfortunately multiplication is a common operation. I was converting to Int64 for multiplication. I thought about half-shifting but then I didn't try it because I thought there might be lost precision, on second thought it might work for me though, perhaps I can define it as another (risky) operation. Right-shifting each operand 11 bits before multiplication would save me from using any Int64 ops, or if I am certain that each operand is smaller than 1 I could shift right fewer bits initially to save some precision. A good way to do that would be to have an assert that gets turned on in debug builds. The safe multiplication was defined as: let mul x y = Int64.to_int (Int64.shift_right (Int64.mul (Int64.of_int x) (Int64.of_int y) ) q) where q = 22 for me. On Wed, Jan 5, 2011 at 6:34 PM, Niki Yoshiuchi wrote: > What range of numbers are you hoping to represent and what operations > are you commonly performing on them? If it's possible for you to > represent your numbers as 24.8 fixed-point (for example) and you are > mostly adding and subtracting, then I would recommend using 32 bit > integers and casting to 64 bit for multiplication and division. > Alternatively you can try and be clever about your shifting instead of > casting (shifting the multiplicand instead of the product, or doing a > half shift on each multiplicand, etc). > > On Wed, Jan 5, 2011 at 11:22 AM, Eray Ozkural > wrote: > > Hello there, > > I'm using fixed-point arithmetic in an algorithm. I am troubled by the > > inefficiency of the fixed-point multiplication and division operations on > > 32-bit architectures. On the Intel 64-bit architecture, I can use the > > Nativeint module and it's quite fast, on 32-bit I had to use the Int64 > > module (for the necessary shifts and mul/div's) and I encountered a > > significant slowdown, naturally. is there a preferred way of performing > > fixed point arithmetic with ocaml on 32-bit architectures that I might be > > overlooking? > > Best, > > -- > > Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, > Ankara > > http://groups.yahoo.com/group/ai-philosophy > > > > > -- Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara http://groups.yahoo.com/group/ai-philosophy http://myspace.com/arizanesil http://myspace.com/malfunct --001485f8617a1a24d004991db09f Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Hi there,

Thank you for your reply Niki.

The range of numbers is usually between 0 and 1, becau= se I'm mostly working on
normalized vectors.

I was using 22 bits for the decimal part but unfortunately multiplica= tion is
a common operation. I was converting to Int64 for multiplicatio= n. I thought
about half-shifting but then I didn't try it bec= ause I thought there might be lost
precision, on second thought it might work for me though, perhaps I ca= n define
it as another (risky) operation. Right-shifting each ope= rand 11 bits before multiplication
would save me from using any I= nt64 ops, or if I am certain that each operand is
smaller than 1 I could shift right fewer bits initially to save some p= recision. A=A0
good way to do=A0that would be to have an assert t= hat gets turned on in debug builds.

The safe = multiplication was defined as:

=A0=A0let mul x y =3D
=A0=A0 =A0Int64.to_int= =A0
=A0=A0 =A0 =A0(Int64.shift_right=A0
=A0=A0 =A0 =A0 = =A0 (Int64.mul (Int64.of_int x) (Int64.of_int y) ) q)

<= div>where q =3D 22 for me.

On Wed, Jan 5, 2011 at 6:34 PM, Niki Y= oshiuchi <aplusbi= @gmail.com> wrote:
What range of numbers are you hoping to represent and what operations
are you commonly performing on them? =A0If it's possible for you to
represent your numbers as 24.8 fixed-point (for example) and you are
mostly adding and subtracting, then I would recommend using 32 bit
integers and casting to 64 bit for multiplication and division.
Alternatively you can try and be clever about your shifting instead of
casting (shifting the multiplicand instead of the product, or doing a
half shift on each multiplicand, etc).

On Wed, Jan 5, 2011 at 11:22 AM, Eray Ozkural <examachine@gmail.com> wrote:
> Hello there,
> I'm using fixed-point arithmetic in an algorithm. I am troubled by= the
> inefficiency of the fixed-point multiplication and division operations= on
> 32-bit architectures. On the Intel 64-bit architecture, I can use the<= br> > Nativeint module and it's quite fast, on 32-bit I had to use the I= nt64
> module (for the necessary shifts and mul/div's) and I encountered = a
> significant slowdown, naturally. is there a preferred way of performin= g
> fixed point arithmetic with ocaml on 32-bit architectures that I might= be
> overlooking?
> Best,
> --
> Eray Ozkural, PhD candidate.=A0 Comp. Sci. Dept., Bilkent University, = Ankara
> http://groups.yahoo.com/group/ai-philosophy
>
>



--
Eray Ozkura= l, PhD candidate.=A0 Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/g= roup/ai-philosophy
http://myspace.com/arizanesil= http://myspace.com/malfunct
--001485f8617a1a24d004991db09f--