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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id B8E357F2AA for ; Fri, 21 Dec 2012 08:58:34 +0100 (CET) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of garrigue@math.nagoya-u.ac.jp) identity=pra; client-ip=133.6.130.5; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="garrigue@math.nagoya-u.ac.jp"; x-sender="garrigue@math.nagoya-u.ac.jp"; x-conformance=sidf_compatible Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of garrigue@math.nagoya-u.ac.jp) identity=mailfrom; client-ip=133.6.130.5; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="garrigue@math.nagoya-u.ac.jp"; x-sender="garrigue@math.nagoya-u.ac.jp"; x-conformance=sidf_compatible Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mailhost.math.nagoya-u.ac.jp) identity=helo; client-ip=133.6.130.5; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="garrigue@math.nagoya-u.ac.jp"; x-sender="postmaster@mailhost.math.nagoya-u.ac.jp"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ap4EAAIW1FCFBoIF/2dsb2JhbABFvgpzgh4BAQQBQwE1AgMLCzQSITYGE4gBAwkFozaEQAKFXw1MiQIHi22ETGGIY4tVgVaLN4URgwM X-IronPort-AV: E=Sophos;i="4.84,328,1355094000"; d="scan'208";a="187160660" Received: from rabbit.math.nagoya-u.ac.jp (HELO mailhost.math.nagoya-u.ac.jp) ([133.6.130.5]) by mail1-smtp-roc.national.inria.fr with ESMTP; 21 Dec 2012 08:58:32 +0100 Received: from mailhost.math.nagoya-u.ac.jp (localhost [127.0.0.1]) by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id 0A738635E; Fri, 21 Dec 2012 16:58:30 +0900 (JST) Received: from mailhost.math.nagoya-u.ac.jp (localhost [127.0.0.1]) by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id 8EBC83960; Fri, 21 Dec 2012 16:58:29 +0900 (JST) DomainKey-Signature: h=Received:Content-Type:Mime-Version:Subject:From:In-Reply-To:Date:Cc:Content-Transfer-Encoding:Message-Id:References:To:X-Mailer; b=; c=nofws; d=math.nagoya-u.ac.jp; q=; s=alpha Received: from tet.garrigue.jp (58x158x128x157.ap58.ftth.ucom.ne.jp [58.158.128.157]) by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTPSA id E94F3395E; Fri, 21 Dec 2012 16:58:28 +0900 (JST) Content-Type: text/plain; charset=windows-1252 Mime-Version: 1.0 (Mac OS X Mail 6.2 \(1499\)) From: Jacques Garrigue In-Reply-To: Date: Fri, 21 Dec 2012 16:58:45 +0900 Cc: caml-list@inria.fr Content-Transfer-Encoding: quoted-printable Message-Id: References: To: Thomas Braibant X-Mailer: Apple Mail (2.1499) Subject: Re: [Caml-list] Hashing failure On 2012/12/21, at 5:18, Thomas Braibant wrote: > Hi list, >=20 > I have a piece of code that looks like this. >=20 > let hkey =3D H.hash d in (* a custom hash function *) > let index =3D hkey mod (Array.length t.table) in > let bucket =3D t.table.(index) in (* 1 *) >=20 > the line marked with 1 was generating an index out of bounds > exception. It appeared that it was because index was negative, a > problem I knew of when using mod ... So I added an abs around index >=20 > let hkey =3D H.hash d in > let index =3D abs (hkey mod (Array.length t.table)) in > let bucket =3D t.table.(index) in (* 1 *) >=20 > But it yields the same exception... >=20 > This seemed completely unbelievable, till I realized that > - x mod y may return a negative value if x is less than 0 > - abs x may return a negative value if x is min_int What about just ensuring that your hash function returns a positive value to start with. An easy way to do that is let hkey =3D hkey land max_int This avoids using abs altogether. (I now understand why the standard hash function is 30-bit=85) Jacques Garrigue=