[Caml-list] Runtime overflow and what to do

[Caml-list] Runtime overflow and what to do

[Scott J,]

[-- Attachment #1: Type: text/plain, Size: 370 bytes --]

Hi,


suppose I use the following code for fact

let rec fact n = if n <= 1 then 1 else n * fact (n - 1) ;;

Because an integer number is represented by a fixed number of bytes I will
get a runtime overflow if n is chosen too large.

Is there in Ocamel a workaround to cope with this problem . Something like "
Onoverflow goto .. " in imperative languages.

Thx

Scott


[-- Attachment #2: Type: text/html, Size: 1402 bytes --]

Re: [Caml-list] Runtime overflow and what to do

[Maxence Guesdon]

On Thu, 10 Oct 2002 17:01:26 +0200
"Scott J," <jscott@planetinternet.be> wrote:

> let rec fact n = if n <= 1 then 1 else n * fact (n - 1) ;;
You can catch the Stack_overflow exception :

try fact 500000
with Stack_overflow -> -1

Is that what you want ?

-- 
Maxence Guesdon
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Maxence Guesdon]

> 
> suppose I use the following code for fact
> 
> let rec fact n = if n <= 1 then 1 else n * fact (n - 1) ;;
> 
> Because an integer number is represented by a fixed number of bytes I will
> get a runtime overflow if n is chosen too large.
> 
> Is there in Ocamel a workaround to cope with this problem . Something like "
> Onoverflow goto .. " in imperative languages.

Sorry, i replied too fast and did not answer your question, since you don't want to catch stack_overflow but be warned about an overflow during the computation of mult.

I don't know how to do that.

-- 
Maxence Guesdon
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Luc Maranget]

> Hi,
> 
> 
> suppose I use the following code for fact
> 
> let rec fact n = if n <= 1 then 1 else n * fact (n - 1) ;;
> 
> Because an integer number is represented by a fixed number of bytes I will
> get a runtime overflow if n is chosen too large.
> 
> Is there in Ocamel a workaround to cope with this problem . Something like "
> Onoverflow goto .. " in imperative languages.
> 
> Thx
> 
> Scott
> 
> 

There is no such feature as a Onoverflow goto, because
Ocaml (and not OCamel...) default integers are not << real >> integers,
but machine integers on some size (typically 31 or 63) bits.

This means that maxint + 1 is minint and basically this is the
behavior of C.

I guess the reason why is avoiding putting non-obvious tests
everywhere.

Most of the time you do not need those tests.
  * If you want ``real'' integers, you can use some arbitrary
    precision library (Num, etc.), overflow detection would  not help
    here anyway.

  * If you want to be warned on overflow, you have to devise the tests
    by yourself, and then you can use an exception as your
    Onoverflow goto
     An easy one :

expection Overflow

let protected_incr x =
  let y = x+1 in
  if y > x then y
  else raise Overflow

try
  .... incr (..)
with
| Overflow -> ... do whatever you can ... 

Hope it helps.

--Luc
               

    
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Sven LUTHER]

On Thu, Oct 10, 2002 at 05:21:13PM +0200, Luc Maranget wrote:
> > Hi,
> > 
> > 
> > suppose I use the following code for fact
> > 
> > let rec fact n = if n <= 1 then 1 else n * fact (n - 1) ;;
> > 
> > Because an integer number is represented by a fixed number of bytes I will
> > get a runtime overflow if n is chosen too large.
> > 
> > Is there in Ocamel a workaround to cope with this problem . Something like "
> > Onoverflow goto .. " in imperative languages.
> > 
> > Thx
> > 
> > Scott
> > 
> > 
> 
> There is no such feature as a Onoverflow goto, because
> Ocaml (and not OCamel...) default integers are not << real >> integers,
> but machine integers on some size (typically 31 or 63) bits.

But it is the lower bit that is ignored, no, si i guess incrementing an
ocaml integer by 1, correspond to incrementing the machine integer by
two, and would set the overflow flag in the processor status register
all the same, would it not ? 

The flag is then ignored, but it is set all the same, at least until it
is overriden by some other calculation.

Friendly,

Sven Luther
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Xavier Leroy]

> But it is the lower bit that is ignored, no, si i guess incrementing an
> ocaml integer by 1, correspond to incrementing the machine integer by
> two, and would set the overflow flag in the processor status register
> all the same, would it not ? 

Yes, except that not all processors have overflow flags.  The Alpha
and the MIPS don't, for instance.  Integer arithmetic modulo a power
of 2 is unpleasant for certain applications (and very useful for
others, e.g. hash functions and cryptography), but this is really all
what today's processors offer.

- Xavier Leroy
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Scott J,]

[-- Attachment #1: Type: text/plain, Size: 1051 bytes --]

Hi,

So it is not easy, perhaps even impossible if the processor doesn't set a
flag .

e.g. fact n begins first with a lis of negative numbers (after overflow)
then comes again a list with positive numbers and then it remains = 0

Scott
  ----- Original Message -----
  From: Xavier Leroy
  To: Sven LUTHER
  Cc: Luc Maranget ; Scott J, ; caml-list@inria.fr
  Sent: Thursday, October 10, 2002 8:57 PM
  Subject: Re: [Caml-list] Runtime overflow and what to do


  > But it is the lower bit that is ignored, no, si i guess incrementing an
  > ocaml integer by 1, correspond to incrementing the machine integer by
  > two, and would set the overflow flag in the processor status register
  > all the same, would it not ?

  Yes, except that not all processors have overflow flags.  The Alpha
  and the MIPS don't, for instance.  Integer arithmetic modulo a power
  of 2 is unpleasant for certain applications (and very useful for
  others, e.g. hash functions and cryptography), but this is really all
  what today's processors offer.

  - Xavier Leroy

[-- Attachment #2: Type: text/html, Size: 2583 bytes --]

Re: [Caml-list] Runtime overflow and what to do

[Florian Hars]

Scott J, wrote:
> Because an integer number is represented by a fixed number of bytes I 
> will get a runtime overflow if n is chosen too large.

You have to check explicitly:

# exception Overflow;;
exception Overflow
# let fact n =
    let rec fact_r acc n =
     if n = 1 then acc
     else if max_int / acc > (n-1) then fact_r (acc * n) (n - 1)
     else raise Overflow
    in
    fact_r 1 n;;
val fact : int -> int = <fun>
# fact 12;;
- : int = 479001600
# fact 13;;
Exception: Overflow.

Yours, Florian

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Sven LUTHER]

On Fri, Oct 11, 2002 at 12:17:15AM +0200, Scott J, wrote:
> Hi,
> 
> So it is not easy, perhaps even impossible if the processor doesn't set a
> flag .
> 
> e.g. fact n begins first with a lis of negative numbers (after overflow)
> then comes again a list with positive numbers and then it remains = 0

No, it is easy, but you have to check at each iteration, as was proposed
here previously.

Friendly,

Sven Luther
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Sven LUTHER]

On Thu, Oct 10, 2002 at 08:57:16PM +0200, Xavier Leroy wrote:
> > But it is the lower bit that is ignored, no, si i guess incrementing an
> > ocaml integer by 1, correspond to incrementing the machine integer by
> > two, and would set the overflow flag in the processor status register
> > all the same, would it not ? 
> 
> Yes, except that not all processors have overflow flags.  The Alpha
> and the MIPS don't, for instance.  Integer arithmetic modulo a power

Didn't know that. (Mostly i know about powerpc and M68K assembly only).

Mmm, Is that why these processors are faster on number crunshing ? Or
better said, a consequence of designing these processors fro being fast
at number crunshing ?

> of 2 is unpleasant for certain applications (and very useful for
> others, e.g. hash functions and cryptography), but this is really all
> what today's processors offer.

Did you ever got hand on a MAJC processor, which supposedly has an extra
bit for GC purpose, or something such ?

Friendly,

Sven Luther
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Alessandro Baretta]

Scott J, wrote:
> Hi,
>  
> So it is not easy, perhaps even impossible if the processor doesn't set 
> a flag .
>  
> e.g. fact n begins first with a lis of negative numbers (after overflow) 
> then comes again a list with positive numbers and then it remains = 0
>  
> Scott

If your problem is only the factorial function, then you can 
calculate statically (i.e. at source-code writing time) the 
value of the maximum integer whose factorial will fit in 
O'Caml's representation of integers, and test against that, 
once and for all, before entering the recursive calculation.

exception overflow
let max_fact_arg = ...

let fact =
let rec rec_fact n =
   if n <= 0 then 1
   else n * rec_fact (n-1)
in function
| x when x <= max_fact_arg -> rec_fact n
| _ -> raise Overflow

This strategy allows to incur in hardly any runtime costs 
for the check, and it also allows you prove more easily that 
your program will not raise runtime Overflow exceptions (the 
precondition for not entering the exception raising branch 
does not have to be propagated out of a recursive function 
call).

Alex

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[John Carr]

> If your problem is only the factorial function, then you can 
> calculate statically (i.e. at source-code writing time) the 
> value of the maximum integer whose factorial will fit in 
> O'Caml's representation of integers, and test against that, 
> once and for all, before entering the recursive calculation.

OCaml supports 32 and 64 bit integers.  Is it possible to detect at
compile time the size of the maximum integer?

In the case of factorial, you could almost as easily optimize the
function to a table lookup.

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Sven LUTHER]

On Sat, Oct 12, 2002 at 12:13:32PM -0400, John Carr wrote:
> 
> > If your problem is only the factorial function, then you can 
> > calculate statically (i.e. at source-code writing time) the 
> > value of the maximum integer whose factorial will fit in 
> > O'Caml's representation of integers, and test against that, 
> > once and for all, before entering the recursive calculation.
> 
> OCaml supports 32 and 64 bit integers.  Is it possible to detect at
> compile time the size of the maximum integer?

val max_int : int

   The greatest representable integer.

Says the doc.

BTW, i compile the sparc debian package on a sparc64 box which
advertizes as a sparc box. Will i get access to the 64 bit integers in
this case or not ?

Friendly,

Sven Luther
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[John Prevost]

>>>>> "sl" == Sven LUTHER <luther@dpt-info.u-strasbg.fr> writes:

    sl> On Sat, Oct 12, 2002 at 12:13:32PM -0400, John Carr wrote:

    >> OCaml supports 32 and 64 bit integers.  Is it possible to
    >> detect at compile time the size of the maximum integer?

    sl> val max_int : int

    sl>    The greatest representable integer.

But that's at runtime.  Which, actually, is the best you can
do--bytecode compiled things might run on any architecture.  Native
compiled things you can rely on more.  But if you want to compile this
knowledge in, you'll have to have some configure script that
determines the word size and chooses which version to compile.

John.

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Xavier Leroy]

> So it is not easy, perhaps even impossible if the processor doesn't set a
> flag .

It is possible, but slow and not pretty!  For example, here is Caml
code that performs integer addition and detects overflows:

exception Integer_overflow

let no_overflow_add a b = 
  if (a lxor b) lor (a lxor (lnot (a+b))) < 0  (* no kidding! *)
  then a + b
  else raise Integer_overflow

Multiplication is left as an exercise for the readers :-)

My advice would be to use bignums; they are a bit slower, but at least
you get the exact result in all cases.

- Xavier Leroy
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Xavier Leroy]

> OCaml supports 32 and 64 bit integers.  Is it possible to detect at
> compile time the size of the maximum integer?

What about:

        echo "print_int Sys.word_size" > /tmp/caml$$
        WORDSIZE=`ocaml /tmp/caml$$`
        rm -f /tmp/caml$$

WORDSIZE will be set to 32 or 64, depending on the platform.

- Xavier Leroy
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Xavier Leroy]

> BTW, i compile the sparc debian package on a sparc64 box which
> advertizes as a sparc box. Will i get access to the 64 bit integers in
> this case or not ?

The short answer is: it depends on the C compiler.  Caml integers
correspond to the C "long int" type, with one bit reserved for GC
purposes.  So, if the C compiler maps "long int" to 64-bit integers,
you get 63-bit Caml ints; if it chooses 32-bit integers for "long int",
you get 31-bit Caml ints.  Often, this can be controlled via flags to
the C compiler.

The above is for the bytecode interpreter.  For the native-code
compiler, the current Sparc code emitter mandates 32-bit integers.

- Xavier Leroy
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Sven LUTHER]

On Sun, Oct 13, 2002 at 11:31:30AM +0200, Xavier Leroy wrote:
> > BTW, i compile the sparc debian package on a sparc64 box which
> > advertizes as a sparc box. Will i get access to the 64 bit integers in
> > this case or not ?
> 
> The short answer is: it depends on the C compiler.  Caml integers
> correspond to the C "long int" type, with one bit reserved for GC
> purposes.  So, if the C compiler maps "long int" to 64-bit integers,
> you get 63-bit Caml ints; if it chooses 32-bit integers for "long int",
> you get 31-bit Caml ints.  Often, this can be controlled via flags to
> the C compiler.

Ok, ...

Which would be the relevant flags ?

i get (from the build log) :

...

Checking the sizes of integers and pointers...
OK, this is a regular 32 bit architecture.
64-bit "long long" integer type found (printf with "%ll").
This is a big-endian architecture.
Doubles must be doubleword-aligned.
64-bit integers must be doubleword-aligned.

...

Configuration for the bytecode compiler:
        C compiler used........... gcc
        options for compiling..... -fno-defer-pop -Wall -Wno-unused -D_FILE_OFFSET_BITS=64 -D_REENTRANT
        options for linking.......  -Wl,-E  -lm -ldl -lcurses -lpthread
        shared libraries are supported
        options for compiling..... -fPIC -fno-defer-pop -Wall -Wno-unused -D_FILE_OFFSET_BITS=64 -D_REENTRANT
        command for building...... gcc -shared -o lib.so -Wl,-rpath,/a/path objs

So i suppose this is not using 64 bit mode.

More importantly, i suppose code compiled in this fashion for 64 bit
sparcs will not build on 32 bit sparc boxes, if these kind of boxes are
still available anyway.

> The above is for the bytecode interpreter.  For the native-code
> compiler, the current Sparc code emitter mandates 32-bit integers.

Would it be much work to build a 64-bit integers target ?

Friendly,

Sven Luther
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Xavier Leroy]

> Which would be the relevant flags ?

No idea.  If you're interested, you figure them out :-)

> More importantly, i suppose code compiled in this fashion for 64 bit
> sparcs will not build on 32 bit sparc boxes, if these kind of boxes are
> still available anyway.

Yes (to both).  I still don't have access to a 64-bit SPARC machine.

> > The above is for the bytecode interpreter.  For the native-code
> > compiler, the current Sparc code emitter mandates 32-bit integers.
> 
> Would it be much work to build a 64-bit integers target ?

A few days for someone who knows the SPARC64 assembly language well.

- Xavier Leroy
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Daniel de Rauglaudre]

Hi,

On Sun, Oct 13, 2002 at 11:25:37AM +0200, Xavier Leroy wrote:

> Multiplication is left as an exercise for the readers :-)

Much more complicated... I tried that a long time ago when I was
writting a PostScript interpreter, but I found no solution.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Sven LUTHER]

On Sun, Oct 13, 2002 at 11:57:25AM +0200, Xavier Leroy wrote:
> > Which would be the relevant flags ?
> 
> No idea.  If you're interested, you figure them out :-)

Ok, ...

Still i have difficulties understanding how this work, in my idea
bytecode was build once run everywhere, how does this go with your
statement that it can be made to use 64bit integers by a compiler
switch ?

Mmm, maybe you are speaking about ocamlrun only ?

> > More importantly, i suppose code compiled in this fashion for 64 bit
> > sparcs will not build on 32 bit sparc boxes, if these kind of boxes are
> > still available anyway.
> 
> Yes (to both).  I still don't have access to a 64-bit SPARC machine.

Do you want access ? I can try to arrange that if you want. To an hppa
machine also.

> > > The above is for the bytecode interpreter.  For the native-code
> > > compiler, the current Sparc code emitter mandates 32-bit integers.
> > 
> > Would it be much work to build a 64-bit integers target ?
> 
> A few days for someone who knows the SPARC64 assembly language well.

Ok, ...

Friendly,

Sven Luther
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Pierre Weis]

> > So it is not easy, perhaps even impossible if the processor doesn't set a
> > flag .
> 
> It is possible, but slow and not pretty!

I must precise that even if the code to implement arithmetics with
overflow checks can be considered as ``not pretty'', its usage is
absolutely easy and transparent in Caml: just write a specialized
module for arithmetics with overflow checks (say ``Cautious_arith'')
that redefines ( + ), ( - ), ( * ), ( / ), min, etc, along the lines
sketched by Xavier for addition (by the way, writing such a module is
a very pleasant home exercise); once you have written the
Cautious_arith module, write your application code as usual.

Now, if you want overflow checks just add

open Cautious_arith

at the beginning of your module and recompile.

If you changed your mind, and want to recover the normal speed of
integer arithmetic operations, just remove the open directive and
recompile!

This is an elegant and clean application of very basic operators
redefinition that not so many programming languages offer.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Pierre Weis]

> Hi,
> 
> On Sun, Oct 13, 2002 at 11:25:37AM +0200, Xavier Leroy wrote:
> 
> > Multiplication is left as an exercise for the readers :-)
> 
> Much more complicated... I tried that a long time ago when I was
> writting a PostScript interpreter, but I found no solution.

(* [lenght_of_int] is the maximum number of bits in an integer. *)
let length_of_int = Sys.word_size - 2;;

let ( * ) n m =
 if num_bits_int n + num_bits_int m < length_of_int
 then n * m else raise (Overflow ("*", string_of_int n, string_of_int m))

(* [num_bits_int n] returns the number of significant bits of an
   integer. *)

Just to let people play with the writting of the module :),
num_bits_int is left as an exercise to the interested readers (3 lines
of Caml code using trivial bit shuffling).

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Daniel de Rauglaudre]

Hi,

On Sun, Oct 13, 2002 at 12:29:58PM +0200, Pierre Weis wrote:

> let ( * ) n m =
>  if num_bits_int n + num_bits_int m < length_of_int
>  then n * m else raise (Overflow ("*", string_of_int n, string_of_int m))

Does it work with negative numbers? And with multiplication between a
positive and a negative number?

> Just to let people play with the writting of the module :),
> num_bits_int is left as an exercise to the interested readers (3 lines
> of Caml code using trivial bit shuffling).

I am interested in knowing it, because I already searched that.
Without a loop or a predefined array of powers of two, I don't
know how to do that.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Pierre Weis]

Hi again,

> On Sun, Oct 13, 2002 at 12:29:58PM +0200, Pierre Weis wrote:
> 
> > let ( * ) n m =
> >  if num_bits_int n + num_bits_int m < length_of_int
> >  then n * m else raise (Overflow ("*", string_of_int n, string_of_int m))
> 
> Does it work with negative numbers? And with multiplication between a
> positive and a negative number?

Yes it does.

> > Just to let people play with the writting of the module :),
> > num_bits_int is left as an exercise to the interested readers (3 lines
> > of Caml code using trivial bit shuffling).
> 
> I am interested in knowing it, because I already searched that.
> Without a loop or a predefined array of powers of two, I don't
> know how to do that.

Nor did I. I think there exists processors that do have an instruction
to implement this function but this is not the general case: you need
to write a loop or use a predefined array of powers of two or write a
dichotomic algorithm or whatever...

For instance:

let num_bits_int n =
  let rec num_bits n = if n = 0 then 0 else succ (num_bits (n lsr 1)) in
  num_bits (abs n);;

(No dichotomy, here. Experiments with a dichotomic algorithm is also
interesting, but deciding which is faster is difficult since
benchmarking is almost impossible: the results are too much dependant
of the value of integers manipulated in the program.)

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[John Carr]

>Would it be much work to build a 64-bit integers target ?

Try http://www.mit.edu/~jfc/ocaml-sparc64.tar.gz
This tar file contains diffs and new code generation
files for 64 bit SPARC.  You will need to apply the
.diff files with patch and move the other files into
the appropriate directories (replacing the existing
files without the "64" suffix), and probably do some
editing of config/Makefile.  I have not tested this
on Linux.  Contact me if you need help.

If there is a lot of interest I can try to package this
in a more immediately useful form.  I stopped work on
the 64 bit code generator before finishing the packaging.

A note of caution: 64 bits is not necessarily better than 32.
Unlike C, OCaml does not allow you to declare a 32 bit object
in 64 bit mode, so memory use will approximately double.
Performance executing out of cache will improve slightly,
or significantly when using floating point, but the increased
cache miss rate may make the program slower overall.

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Xavier Leroy]

> [Overflow checking in integer multiplication]

> (* [lenght_of_int] is the maximum number of bits in an integer. *)
> let length_of_int = Sys.word_size - 2;;
> 
> let ( * ) n m =
>  if num_bits_int n + num_bits_int m < length_of_int
>  then n * m else raise (Overflow ("*", string_of_int n, string_of_int m))
> 
> (* [num_bits_int n] returns the number of significant bits of an
>    integer. *)

Hmmph... this definition raises Overflow when computing
min_int * 1, or (min_int / 2) * 2, while these products are actually
representable within a machine integer...

Apologies for nit-picking; I couldn't resist!

- Xavier Leroy
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Michel Quercia]

Le Dimanche 13 Octobre 2002 18:14, Xavier Leroy a écrit :

> > [Overflow checking in integer multiplication]
> > let ( * ) n m =
> >  if num_bits_int n + num_bits_int m < length_of_int
> >  then n * m else raise (Overflow ("*", string_of_int n, string_of_int m))
> Hmmph... this definition raises Overflow when computing
> min_int * 1, or (min_int / 2) * 2, while these products are actually
> representable within a machine integer...

What about this one ?

let mul a b =
  if a = 0 then 0
  else
    let x = a*b in
    let q = x/a and r = x mod a in
    if (q = b) & (r = 0) then x else raise Overflow


-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://michel.quercia.free.fr (maths)
http://pauillac.inria.fr/~quercia (informatique)
mailto:michel.quercia@prepas.org

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Chris Hecker]

>        echo "print_int Sys.word_size" > /tmp/caml$$
>         WORDSIZE=`ocaml /tmp/caml$$`
>         rm -f /tmp/caml$$

We clearly need a "-eval" switch to ocaml, like perl's -e/n/p.  :)

Chris

  

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Jacques Garrigue]

From: Chris Hecker <checker@d6.com>
> >        echo "print_int Sys.word_size" > /tmp/caml$$
> >         WORDSIZE=`ocaml /tmp/caml$$`
> >         rm -f /tmp/caml$$
> 
> We clearly need a "-eval" switch to ocaml, like perl's -e/n/p.  :)

The above can be reduced to one line, without temporary file.
In fact, I feel more like we would need a "-silent" option, to get rid
of prompts and types (this is already the default with scripts).

echo "print_int Sys.word_size;;" | \
ocaml | grep "^# ." | sed -e "s/# //" -e "s/- :.*//"

A shorter but more specific approach is

echo "Sys.word_size;;" | ocaml | grep "# -" | sed -e "s/.*= //"

Jacques Garrigue
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Scott J,]

[-- Attachment #1: Type: text/plain, Size: 1380 bytes --]

Hi,

I am following the discussion. But do not understand this. Is this a
solution to eliminate overhead in integer arithmetic.

Personnally I thought to try to capture the overflow status flag for the
pentium processor on my Windows XP.

Thx

Scott
  ----- Original Message -----
  From: Jacques Garrigue
  To: checker@d6.com
  Cc: caml-list@inria.fr
  Sent: Monday, October 14, 2002 11:46 AM
  Subject: Re: [Caml-list] Runtime overflow and what to do


  From: Chris Hecker <checker@d6.com>
  > >        echo "print_int Sys.word_size" > /tmp/caml$$
  > >         WORDSIZE=`ocaml /tmp/caml$$`
  > >         rm -f /tmp/caml$$
  >
  > We clearly need a "-eval" switch to ocaml, like perl's -e/n/p.  :)

  The above can be reduced to one line, without temporary file.
  In fact, I feel more like we would need a "-silent" option, to get rid
  of prompts and types (this is already the default with scripts).

  echo "print_int Sys.word_size;;" | \
  ocaml | grep "^# ." | sed -e "s/# //" -e "s/- :.*//"

  A shorter but more specific approach is

  echo "Sys.word_size;;" | ocaml | grep "# -" | sed -e "s/.*= //"

  Jacques Garrigue
  -------------------
  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

[-- Attachment #2: Type: text/html, Size: 3300 bytes --]

Re: [Caml-list] Runtime overflow and what to do

[Tim Freeman]

From: Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>
>The above can be reduced to one line, without temporary file.
>In fact, I feel more like we would need a "-silent" option, to get rid
>of prompts and types (this is already the default with scripts).
>
>echo "print_int Sys.word_size;;" | \
>ocaml | grep "^# ." | sed -e "s/# //" -e "s/- :.*//"

The following is simpler and works on Unix systems that have /dev/fd:

   echo "print_int Sys.word_size;;" | ocaml /dev/fd/0

I agree that a "-silent" option would be prettier than this, and it
would work on systems that don't have /dev/fd.

-- 
Tim Freeman       
tim@fungible.com
GPG public key fingerprint ECDF 46F8 3B80 BB9E 575D  7180 76DF FE00 34B1 5C78 
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Stefano Zacchiroli]

On Mon, Oct 14, 2002 at 07:05:57AM -0700, Tim Freeman wrote:
>    echo "print_int Sys.word_size;;" | ocaml /dev/fd/0

Cool! Could you explain the trick?

If I understood correctly /dev/fd/x is a pointer to /proc/self/fd/x, so
the ocaml process try to read the script from /proc/self/fd/0 that is
its standard input i.e. the output of the echo command.

But why the standard ocaml toplevel message wont be printed?

TIA,
Cheers.

-- 
Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy
zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro
"I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!" -- G.Romney
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Alain Frisch]

On Mon, 14 Oct 2002, Stefano Zacchiroli wrote:

> >    echo "print_int Sys.word_size;;" | ocaml /dev/fd/0
>
> But why the standard ocaml toplevel message wont be printed?

Because the ocaml toplevel is quiet when it evaluates a script
whose name is given on its command line.

-- Alain

-------------------
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

[Caml-list] new ocaml switches (was Re: Runtime overflow and what to do)

[Chris Hecker]

>The above can be reduced to one line, without temporary file.
>In fact, I feel more like we would need a "-silent" option, to get rid
>of prompts and types (this is already the default with scripts).

Yes, I agree with -silent too!  The only problem with using the pipe for 
everything is that Win2k's echo passes the quotes along to ocaml, so you need:

echo Sys.word_size | ocaml

Sadly, this means you'll need different commands on unix versus nt.  -eval 
would avoid that problem to a large extent, except in that case quoting 
inside a string is different between the two systems, so you're stil kind 
of hosed.  We probably need all of these switches!

Would -silent not print anything that wasn't "printed" from the script, or 
would it only print the types?  Maybe we need -Q for printing nothing 
(script must print to stdout), -qq for printing only values, and -q for 
printing types and values.  Or something.  And -e[val] for evaluating a 
string (should support multiple of them on a single command like perl does, 
which is handy).  Not sure if there are equivalents for perl -n & -p that 
we'd want...ocaml is a bit heavy for quick scripting like this, so -eval 
might be enough.

Chris

-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Pierre Weis]

> > [Overflow checking in integer multiplication]
> 
> > (* [lenght_of_int] is the maximum number of bits in an integer. *)
> > let length_of_int = Sys.word_size - 2;;
> > 
> > let ( * ) n m =
> >  if num_bits_int n + num_bits_int m < length_of_int
> >  then n * m else raise (Overflow ("*", string_of_int n, string_of_int m))
> > 
> > (* [num_bits_int n] returns the number of significant bits of an
> >    integer. *)
> 
> Hmmph... this definition raises Overflow when computing
> min_int * 1, or (min_int / 2) * 2, while these products are actually
> representable within a machine integer...
> 
> Apologies for nit-picking; I couldn't resist!
> 
> - Xavier Leroy

Well spotted, thank you very much!

As a reward, note that your overflow test on addition raises overflow
when computing (max_int + 1) - 1, while this sum is actually
representable within a machine integer...

Sure, computer arithmetics is tricky!

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Xavier Leroy]

> As a reward, note that your overflow test on addition raises overflow
> when computing (max_int + 1) - 1, while this sum is actually
> representable within a machine integer...

More nit picking: max_int + 1 isn't representable, and (machine)
addition evaluates it to min_int, which is clearly a case of overflow.

- Xavier Leroy
-------------------
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

Re: [Caml-list] Runtime overflow and what to do

[Pierre Weis]

> More nit picking: max_int + 1 isn't representable, and (machine)
> addition evaluates it to min_int, which is clearly a case of overflow.

Oups!

Given that max_int has the intended definition, max_int + 1 is
evidently an overflow ...

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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