Re: [Caml-list] More or bignums/ints

[Brian Hurt <bhurt@spnz.org>]

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