Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] More or bignums/ints
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-06-14 (15:31)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] More or bignums/ints
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 

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 

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: