From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id C7AF87FA6B for ; Tue, 25 Oct 2016 18:58:56 +0200 (CEST) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=toilatung90@gmail.com; spf=Pass smtp.mailfrom=toilatung90@gmail.com; spf=None smtp.helo=postmaster@mail-lf0-f50.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of toilatung90@gmail.com) identity=pra; client-ip=209.85.215.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="toilatung90@gmail.com"; x-sender="toilatung90@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of toilatung90@gmail.com designates 209.85.215.50 as permitted sender) identity=mailfrom; client-ip=209.85.215.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="toilatung90@gmail.com"; x-sender="toilatung90@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-lf0-f50.google.com) identity=helo; client-ip=209.85.215.50; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="toilatung90@gmail.com"; x-sender="postmaster@mail-lf0-f50.google.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3A7z2xhxx4gtwiWjfXCy+O+j09IxM/srCxBDY+r6Qd?= =?us-ascii?q?0eIQIJqq85mqBkHD//Il1AaPBtSBrawbwLOO7ujJYi8p2d65qncMcZhBBVcuqP?= =?us-ascii?q?49uEgeOvODElDxN/XwbiY3T4xoXV5h+GynYwAOQJ6tL2PbrnD61zMOABK3bVMz?= =?us-ascii?q?fbWvXNCNxJ3viqibwN76W01wnj2zYLd/fl2djD76kY0ou7ZkMbs70RDTo3FFKK?= =?us-ascii?q?x8zGJsIk+PzV6nvp/jtLYqySlbuuog+shcSu26Ov1gFf0LRAghZioO48DkqQPE?= =?us-ascii?q?VU/Hw3oXUmwbllAAVw3E5xHzU5O3qSz3ufZn3zGyPMvqQLRyUjOnufRFUhjt3R?= =?us-ascii?q?saMTFxznyfutF5iuoPvBWgoxVj3ojbMdm9O/93f6ebdtQfEzkSFv1NXjBMV9vv?= =?us-ascii?q?J7AECPAMaKMB99Hw?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0D2AAD3jg9YhjLXVdFcHAEBBAEBCgEBF?= =?us-ascii?q?wEBBAEBCgEBgkg8AQEBAQE7On0HpCyMUYJYhRaCBx+GAgKBagdBEgEBAQEBAQE?= =?us-ascii?q?BAQEBEgEBAQgLCwkdMIIzBAEVAQSCEQEBAwESER0BCBMdAQMBCwYDAgs3AgIhA?= =?us-ascii?q?QERAQUBHAYTIogWAQMPCJdjj02BMj8yi0aBa4JfBYNmChknDVODGQEBAQEBAQQ?= =?us-ascii?q?BAQEBAQEBGAIGEIsCgkeBRwsRAYMgglsBBIElAZFZAYE4hSkrCAEBgSYIi0yDH?= =?us-ascii?q?ZADiG6EGoI/Ex6BESUBUINBDxELgVQ8NIVxX4FBAQEB?= X-IPAS-Result: =?us-ascii?q?A0D2AAD3jg9YhjLXVdFcHAEBBAEBCgEBFwEBBAEBCgEBgkg?= =?us-ascii?q?8AQEBAQE7On0HpCyMUYJYhRaCBx+GAgKBagdBEgEBAQEBAQEBAQEBEgEBAQgLC?= =?us-ascii?q?wkdMIIzBAEVAQSCEQEBAwESER0BCBMdAQMBCwYDAgs3AgIhAQERAQUBHAYTIog?= =?us-ascii?q?WAQMPCJdjj02BMj8yi0aBa4JfBYNmChknDVODGQEBAQEBAQQBAQEBAQEBGAIGE?= =?us-ascii?q?IsCgkeBRwsRAYMgglsBBIElAZFZAYE4hSkrCAEBgSYIi0yDHZADiG6EGoI/Ex6?= =?us-ascii?q?BESUBUINBDxELgVQ8NIVxX4FBAQEB?= X-IronPort-AV: E=Sophos;i="5.31,546,1473112800"; d="scan'208,217";a="198140249" Received: from mail-lf0-f50.google.com ([209.85.215.50]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 25 Oct 2016 18:58:21 +0200 Received: by mail-lf0-f50.google.com with SMTP id f134so51624589lfg.2 for ; Tue, 25 Oct 2016 09:58:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=J/FQFhr2JTuUa+7DKMzhbUpohdmhYKxuE/8htucLDvo=; b=mwYKaSXy+k+IuFiOf4VAJIA363YJjqAn3P09l5WkXD8XHdP64uzXapuV3EAC/3LbiY XeYBEziT0HjjcQuSq8gvuIG7EyIU0EelJQTohKlSVlrSUSKUNx9B3Z4IkWhgk66I46YW Kw5Ys17W+xbsatOoblwK8NKeQLchcnTAjiBOvucc5ed6V+5YSxsGosuzvKK+0qCdfGPQ 8J7SY0ybpxhXW5J8NZLKFe5WwBBHE5uvIqM3OnAe/Pv4F4ZeMHi9XBbbvu325MEsRe2C da/QLUAsg+cIvXmf/pyjAo76BZqtCCxh3VdOKKuTwwz+Kz1Z+6FVkxY2eBlJ5I2l9PiI PGfQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=J/FQFhr2JTuUa+7DKMzhbUpohdmhYKxuE/8htucLDvo=; b=IrHFArDzdCxGhswGcxl3zCQqtFxN23PNgMop62SxmIeTYzk+bB8BCjXLHwImNprTPx sNUJHvLYQkLe0lId/cWy9uXpatMb7Hfm9o9iS4dqA4djcD3jVh+eLUQRUm2dlE5kmhZT hY2voE1Ej/SnkpHTGQpiJt6KNsWMJvBFF8c4qrbulCxdevE/t8qwNnx2EqYbj+nR++Ju Kc7YbkVlOiTLJ6Ei48sUbLc1qzT8rgPqYrkhHMtt42MNU68ZV9356Ib6cwIbrGttmE2P H86yY0gyGqBdFKeCWItK6Oy+hElgIbqSgd0TdCbz/6zmgqZRdvFtfTIBEG1li1DPUVxT KBWQ== X-Gm-Message-State: ABUngvdk85GJjgIxa5x07HUHpgknYVppOLkzKiTHspSEWoiQuv26zvmqooFo32cztByIY62ZqiF7WcMlxP5++Q== X-Received: by 10.25.141.19 with SMTP id p19mr10953541lfd.56.1477414700682; Tue, 25 Oct 2016 09:58:20 -0700 (PDT) MIME-Version: 1.0 Received: by 10.25.24.206 with HTTP; Tue, 25 Oct 2016 09:58:19 -0700 (PDT) In-Reply-To: <0F7D3B1B3C4B894D824F5B822E3E5A172CFA06ED@IRSMSX102.ger.corp.intel.com> References: <0F7D3B1B3C4B894D824F5B822E3E5A172CFA061B@IRSMSX102.ger.corp.intel.com> <25995371-4f79-352b-35fe-7edb92de8161@normalesup.org> <0F7D3B1B3C4B894D824F5B822E3E5A172CFA06ED@IRSMSX102.ger.corp.intel.com> From: Tung Vu Xuan Date: Tue, 25 Oct 2016 18:58:19 +0200 Message-ID: To: "Soegtrop, Michael" Cc: Jacques-Henri Jourdan , "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=001a114022286b93b9053fb36a89 Subject: Re: [Caml-list] Approximations when converting from string to float --001a114022286b93b9053fb36a89 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hi, Thanks for suggestions. Since I am using a library for interval arithmetic [1], your idea becomes easier for me. let intv_of_big_int bi =3D let n =3D Big_int.num_bits_big_int bi in if n <=3D 53 then let bi_float =3D Big_int.float_of_big_int bi in {low=3Dbi_float;high=3Dbi_float} else begin let n =3D n - 53 in (* Extract top 53 bits of x *) let top =3D Big_int.shift_right_big_int bi n in let top_float =3D Big_int.float_of_big_int top in (* interval [2, 2] *) let two_I =3D {low=3D2.;high=3D2.} in (* interval: [2, 2]**n *) let two_I_to_n =3D pow_I_i two_I n in (* compute upper bound of mantissa, represented as an intv *) (* interval arithmetic is needed because rounding error might occur *) let mantissa_upper_bound_intv =3D {low=3Dtop_float;high=3Dtop_float} = +$ one_I in (* intv of mantissa *) let mantissa_intv =3D {low=3Dtop_float; high=3Dmantissa_upper_bound_i= ntv.high} in (* compute final interval *) mantissa_intv *$ two_I_to_n end [1] Alliot, J.M., Gotteland, J.B., Vanaret, C., Durand, N., Gianazza, D.: Implementing an interval computation library for OCaml on x86/amd64 architectures. In: ICFP. ACM (2012) Thanks again, Tung. On Tue, Oct 25, 2016 at 5:28 PM, Soegtrop, Michael < michael.soegtrop@intel.com> wrote: > Dear Jacques-Henri, > > > > if the number is cut off after n digits, the upper and lower bounds I > suggested are the (truncated integer)*10^(#cut-off-digits) and (truncated > integer+1)*10^(#cut-off-digits). The true number is obviously between > these two. Since the integer has higher precision than the mantissa in the > case of cut off, this is only a fraction of a mantissa bit. The errors you > get by multiplying with the powers of 10 is likely larger in most cases. > > > > In the case you mentioned, 2^70=3D1180591620717411303424 and 32 bit one > would truncate after > > > > 1180591620 * 10^12 > > > > Maxima gives > > > > is(1180591620 * 10^12 <=3D 2^70); > > true > > > > is(1180591621 * 10^12 >=3D 2^70); > > true > > > > As I said, this method doesn=E2=80=99t give the tightest bounds possible,= but it > gives you true upper and lower bounds without multi precision arithmetic. > It gives 0 intervals e.g. for integers which fit in the mantissa, but not > for large exact powers of 2. > > > > > Moreover, it is not possible to implement interval arithmetic with > OCaml, since you cannot change the rounding mode without a bit of C... > > > > It should be possible to make the powers of 10 tables such that this works > even with round to nearest, but it would likely be easier to make a C > library for this. > > > > Of cause it is a good question if I/O is the right place to save > performance and waste precision. On the other hand you lose only 2 or 3 > bits and you know what the precision is. I would think most applications > are such that the required precision is not exactly an IEEE precision, so > that these 2 or 3 bits are ok. I used this method once in an embedded > platform, where multi precision arithmetic was not an option, and this was > a good compromise. > > > > Best regards, > > > > Michael > > Intel Deutschland GmbH > Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany > Tel: +49 89 99 8853-0, www.intel.de > Managing Directors: Christin Eisenschmid, Christian Lamprechter > Chairperson of the Supervisory Board: Nicole Lau > Registered Office: Munich > Commercial Register: Amtsgericht Muenchen HRB 186928 > --=20 Tung Vu Xuan, Japan Advanced Institute of Science and Technology, Mobile: (+81) 080 4259 9135 - (+84) 01689934381 Hometown: Bac Ninh Email: toilatung90@gmail.com --001a114022286b93b9053fb36a89 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Hi,=C2=A0

Thanks for suggestions. Since= I am using a library for interval arithmetic [1], your idea becomes easier= for me.

let intv_of_big_int bi =3D=C2=A0
=C2=A0 =C2=A0 let n =3D Big_int.num_bits_big_int bi in
=C2= =A0 =C2=A0 if n <=3D 53 then=C2=A0
=C2=A0 =C2=A0 =C2=A0 let bi= _float =3D Big_int.float_of_big_int bi in
=C2=A0 =C2=A0 =C2=A0 {l= ow=3Dbi_float;high=3Dbi_float}
=C2=A0 =C2=A0 else begin
=C2=A0 =C2=A0 =C2=A0 let n =3D n - 53 in
=C2=A0 =C2=A0 =C2=A0 (*= Extract top 53 bits of x *)
=C2=A0 =C2=A0 =C2=A0 let top =3D Big= _int.shift_right_big_int bi n in

=C2=A0 =C2=A0 =C2= =A0 let top_float =3D Big_int.float_of_big_int top in
=C2=A0 =C2= =A0 =C2=A0 (* interval [2, 2] *)
=C2=A0 =C2=A0 =C2=A0 let two= _I =3D {low=3D2.;high=3D2.} in
=C2=A0 =C2=A0 =C2=A0 (* interval: = [2, 2]**n *)
=C2=A0 =C2=A0 =C2=A0 let two_I_to_n =3D pow_I_i two_= I n in

=C2=A0 =C2=A0 =C2=A0 (* compute upper bound= of mantissa, represented as an intv *)
=C2=A0 =C2=A0 =C2=A0 (* i= nterval arithmetic is needed because rounding error might occur *)
=C2=A0 =C2=A0 =C2=A0 let mantissa_upper_bound_intv =3D {low=3Dtop_flo= at;high=3Dtop_float} +$ one_I in

=C2=A0 =C2=A0 =C2= =A0 (* intv of mantissa *)
=C2=A0 =C2=A0 =C2=A0 let mantissa_intv= =3D {low=3Dtop_float; high=3Dmantissa_upper_bound_intv.high} in
=
=C2=A0 =C2=A0 =C2=A0=C2=A0
=C2=A0 =C2=A0 =C2=A0 (* compute f= inal interval=C2=A0*)
=C2=A0 =C2=A0 =C2=A0 mantissa_intv *$ two_I= _to_n
=C2=A0 =C2=A0 end

[1] Alliot= , J.M., Gotteland, J.B., Vanaret, C., Durand, N., Gianazza, D.: Implementing an interval computation library for OCaml on x86/amd64 architectures. In: I= CFP. ACM (2012)

Thanks again,
Tung.
=

On Tue, Oct= 25, 2016 at 5:28 PM, Soegtrop, Michael <michael.soegtrop@intel.c= om> wrote:

Dear Jacques-Henri,

=C2=A0

if the number is cut off = after n digits, the upper and lower bounds I suggested are the (truncated i= nteger)*10^(#cut-off-digits) and (truncated integer+1)*10^(#cut-off-di= gits). The true number is obviously between these two. Since the integer has high= er precision than the mantissa in the case of cut off, this is only a fract= ion of a mantissa bit. The errors you get by multiplying with the powers of= 10 is likely larger in most cases.

=C2=A0

In the case you mentioned= , 2^70=3D1180591620717411303424 and 32 bit one would truncate after<= u>

=C2=A0

=C2=A0

Maxima gives

=C2=A0

=C2=A0

As I said, this method do= esn=E2=80=99t give the tightest bounds possible, but it gives you true uppe= r and lower bounds without multi precision arithmetic. It gives 0 intervals e.g. for integers which fit in the mantissa, but not for large= exact powers of 2.

=C2=A0

> Moreover, it is not = possible to implement interval arithmetic with OCaml, since you cannot chan= ge the rounding mode without a bit of C...

=C2=A0

It should be possi= ble to make the powers of 10 tables such that this works even with round to= nearest, but it would likely be easier to make a C library for this.

=C2=A0

Of cause it is a good que= stion if I/O is the right place to save performance and waste precision. On= the other hand you lose only 2 or 3 bits and you know what the precision is. I would think most applications are such that the requir= ed precision is not exactly an IEEE precision, so that these 2 or 3 bits ar= e ok. I used this method once in an embedded platform, where multi precisio= n arithmetic was not an option, and this was a good compromise.

=C2=A0

Best regards,

=

=C2=A0

Michael

Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, ww= w.intel.de
Managing Directors: Christin Eisenschmid, Christian Lamprechter
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928




--
Tung Vu Xuan,
Japan Advanced Institute of Science a= nd Technology,
Mobile: (+81) 080 4259 9135 - =C2=A0(+84) 016= 89934381
Hometown: Bac Ninh
--001a114022286b93b9053fb36a89--