From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA27062; Mon, 14 Jun 2004 17:31:29 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA26210 for ; Mon, 14 Jun 2004 17:31:28 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i5EFVQSH015361 for ; Mon, 14 Jun 2004 17:31:27 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id i5EFVLG21695; Mon, 14 Jun 2004 10:31:21 -0500 (CDT) Date: Mon, 14 Jun 2004 10:37:29 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: John Hughes cc: caml-list@inria.fr Subject: Re: [Caml-list] More or bignums/ints In-Reply-To: <20040611193818.0A43457251@twix.cs.brown.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 40CDC4CE.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 bignums:01 bignums:01 debugger:01 supplies:99 entails:01 overflows:01 shootout:01 mlton:01 bignum:01 -like:01 compiler:01 ints:01 ints:01 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 11 Jun 2004, John Hughes wrote: > I've read the May interchange in CWN that started with the question > > > I have made a web search to understand which kind of support for > > bignums is available for OCaml... > > and found it interesting. I'll be teaching a few weeks of ML as part > of a first-year course at Brown University, and we've used SML in > previous years. SML/NJ works OK, but we'd like a debugger, so I've > looked at OCaml as a possible alternative. I was a little depressed > to find (by trial and error) that "int" doesn't mean "integer" but > rather "element of Z/nZ for some very large n, represented with > integer notation, including negative signs." Yep. Generally mod 2^n for some n. This is because this is what the hardware supplies for fast integer arithemetic. "Fixing" this, so that ints are real (mathematical) integers entails a *huge* performance cost, for very little gain. > > I think I can live with this if only there's some way to write > something like this (pseudo-ML/Java): > > fun fact(0) = 1 > | fact(n) = try { > n * fact(n-1) > } > catch (IntegerOverflow e) ... > There are two problems with this: 1) most CPUs don't support throwing exceptions on integer overflows, because 2) the CPU throwing an exception is incredibly expensive (two complete pipeline drains (the same cost as a mispredicted branch), and two task switches (into and back out of the OS)). You might be able to modify the ocaml compiler to add overflow checking code. Most CPUs have a "jump on overflow" instruction. But currently, an integer add takes at most 2 instructions (the second instruction to deal with the tag bit), and often only one. This change would cause an add instruction to take at least two, maybe three, instructons- for a signifigant performance hit (this is assuming that the throwing the exception code is factored out). How big of a performance hit, I don't know. I note that on the Great Language Shootout page, SML/NJ has a much lower performance score than Ocaml or MLton. Note that the numeric people have exactly the same problem, and are more likely to hit it than your average code. > > What I don't think I can bear is to use the sorts of "bignum"-like > libraries that make me write things like > > y = x bigadd big-unit > > to mean > > y = x + 1 > > because our students will actually be writing some code that has > a good deal of arithmetic in it. Define new operators. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners