if (n:int) < 0 then (-n) > 0 is FALSE

if (n:int) < 0 then (-n) > 0 is FALSE

[Pal-Kristian Engstad]

Using OCaml 3.08.3 on the following function:

let pow x n =
  let rec aux x n acc =
    if n == 0 then acc
    else if n == 1 then acc *. x
    else if n land 1 == 0 then aux (x*.x) (n/2) acc
    else aux (x*.x) ((n-1)/2) (x*.acc)
  in
    if n >= 0 then
      aux x n 1.0
    else
      1.0 /. (aux x (-n) 1.0)
;;

I tested this function with

# pow 1.0 (1024 * 1024 * 1024)

To find that it loops forever. The reason is that 1024*1024*1024=2^30 
cannot be represented as a positive number on 32-bit platforms, hence it 
silently converts it to -1073741824, or -2^30. The reason this loops 
again is that -n = -(-20^30) = -20^30......, still negative!

This is obviously a bug - has it since been fixed? But more alarmingly - 
why is there no warning?

Thanks,

PKE.

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), Lead Programmer, ICE
team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Most of us would do well to remember that there is a reason Carmack
is Carmack, and we are not Carmack.",
                       Jonathan Blow, 2/1/2006, GD Algo Mailing List

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Jonathan Roewen]

It's not a bug -- you're relying on 32bit ints when OCaml has only
31bit ints (on 32-bit arch). In C (for example), if you use a plain
int (I believe it'll default to signed), you get the exact same
behaviour when the number overflows 2^31.

The only difference here is that unlike C and many other languages,
OCaml has no unsigned numeric type. However, even if it were unsigned,
you still can't avoid a hard limit on maximum integer value.

My recommendation would be to use the Nums library so you don't get
overflow errors, or do an overflow check and throw an exception.

Jonathan

On 12/8/06, Pal-Kristian Engstad <pal_engstad@naughtydog.com> wrote:
> Using OCaml 3.08.3 on the following function:
>
> let pow x n =
>  let rec aux x n acc =
>    if n == 0 then acc
>    else if n == 1 then acc *. x
>    else if n land 1 == 0 then aux (x*.x) (n/2) acc
>    else aux (x*.x) ((n-1)/2) (x*.acc)
>  in
>    if n >= 0 then
>      aux x n 1.0
>    else
>      1.0 /. (aux x (-n) 1.0)
> ;;
>
> I tested this function with
>
> # pow 1.0 (1024 * 1024 * 1024)
>
> To find that it loops forever. The reason is that 1024*1024*1024=2^30
> cannot be represented as a positive number on 32-bit platforms, hence it
> silently converts it to -1073741824, or -2^30. The reason this loops
> again is that -n = -(-20^30) = -20^30......, still negative!
>
> This is obviously a bug - has it since been fixed? But more alarmingly -
> why is there no warning?
>
> Thanks,
>
> PKE.
>
> --
> Pål-Kristian Engstad (engstad@naughtydog.com), Lead Programmer, ICE
> team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
> Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.
>
> "Most of us would do well to remember that there is a reason Carmack
> is Carmack, and we are not Carmack.",
>                       Jonathan Blow, 2/1/2006, GD Algo Mailing List
>
>
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Mattias Engdegård]

>It's not a bug -- you're relying on 32bit ints when OCaml has only
>31bit ints (on 32-bit arch). In C (for example), if you use a plain
>int (I believe it'll default to signed), you get the exact same
>behaviour when the number overflows 2^31.

(Signed overflow is not legal in C (undefined behaviour), and a decent
compiler will warn this can be detected statically.)

Of course it is a bug - a design bug, since the behaviour is intended
and documented, but still a bug. But getting numbers, even integers,
right in every respect is hard, and involves trade-offs between
performance, correctness and convenience.

I would love to have a fast unboxed integer type that automatically
overflows to bignum, but it would be a tad slower than the current "int".

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Brian Hurt]

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

Mattias Engdegård wrote:

>>It's not a bug -- you're relying on 32bit ints when OCaml has only
>>31bit ints (on 32-bit arch). In C (for example), if you use a plain
>>int (I believe it'll default to signed), you get the exact same
>>behaviour when the number overflows 2^31.
>>    
>>
>
>(Signed overflow is not legal in C (undefined behaviour), and a decent
>compiler will warn this can be detected statically.)
>
>Of course it is a bug - a design bug, since the behaviour is intended
>and documented, but still a bug. But getting numbers, even integers,
>right in every respect is hard, and involves trade-offs between
>performance, correctness and convenience.
>
>I would love to have a fast unboxed integer type that automatically
>overflows to bignum, but it would be a tad slower than the current "int".
>  
>

I find it interesting that the languages I know use fixed-size integers 
(Ocaml, C, C++, Java, C#, Fortran, Pascal) are at or near the top of the 
great computer language shootout, while the languages I know don't 
(Perl, Python) are near the bottom.  Not that I'm saying that this is 
the case, it's just an interesting dichotomy.

Brian


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

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[skaller]

On Thu, 2006-12-07 at 20:43 +0100, Mattias Engdegård wrote:
> >It's not a bug -- you're relying on 32bit ints when OCaml has only
> >31bit ints (on 32-bit arch). In C (for example), if you use a plain
> >int (I believe it'll default to signed), you get the exact same
> >behaviour when the number overflows 2^31.
> 
> (Signed overflow is not legal in C (undefined behaviour), and a decent
> compiler will warn this can be detected statically.)

It can be detected statically? I'd sure like to know how
(without polluting the user with hundreds of spurious warnings).

> Of course it is a bug - a design bug, since the behaviour is intended
> and documented, but still a bug. But getting numbers, even integers,
> right in every respect is hard, and involves trade-offs between
> performance, correctness and convenience.

Hmmm. In the usual full word register operations most CPU
have an overflow flag which a single conditional branch can
detect. Given branch prediction the branch is unlikely to be
taken the cost of detection is probably extremely small,
provided you have control at the assembler level.

Ocaml has slighly messier representation with one less
bit, but i guess overflow detection wouldn't be so hard
or all that expensive -- but I could be wrong, perhaps
someone on Ocaml team has looked at this can can comment?


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Mattias Engdegård]

>> (Signed overflow is not legal in C (undefined behaviour), and a decent
>> compiler will warn this can be detected statically.)

s/warn/warn when/ (sorry)

>Hmmm. In the usual full word register operations most CPU
>have an overflow flag which a single conditional branch can
>detect. Given branch prediction the branch is unlikely to be
>taken the cost of detection is probably extremely small,
>provided you have control at the assembler level.

Even well-predicted branches are not free. They pollute the BTB, make
the code bigger (consuming I-cache), consume various resources
(decoding, instruction queue, ALU, rename registers etc) and as
integer operations are very common these all add up.

The ideal architecture in this regard would be one with optionally
trapping integer instructions, and very fast user-mode traps.

>Ocaml has slighly messier representation with one less
>bit, but i guess overflow detection wouldn't be so hard
>or all that expensive -- but I could be wrong, perhaps
>someone on Ocaml team has looked at this can can comment?

I suppose it wouldn't be impossible to add a compiler flag to change
the integer overflow semantics from wrapping to trapping.
Doing so for constant expressions (the original complaint in this thread)
would probably be less work.

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Jon Harrop]

On Thursday 07 December 2006 19:43, Mattias Engdegård wrote:
> Of course it is a bug

I wouldn't call it a bug. It looks like modulo arithmetic to me.

> I would love to have a fast unboxed integer type that automatically
> overflows to bignum, but it would be a tad slower than the current "int".

How can it be both unboxed and allow overflow to a bignum? Would you generate 
int and bigint versions of all functions and then bail to the bigint version 
if anything overflowed?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Mattias Engdegård]

>I wouldn't call it a bug. It looks like modulo arithmetic to me.

Let's not make a virtue of necessity. The type "int" was likely designed
with the intent to provide a type that could be used for actual integers
in a variety of circumstances, while giving good performance. The modulo
semantics is rarely useful (especially the 30-bit signed variety) but
is the price paid for reasonable performance with a simple implementation.

>> I would love to have a fast unboxed integer type that automatically
>> overflows to bignum, but it would be a tad slower than the current "int".
>
>How can it be both unboxed and allow overflow to a bignum? Would you generate 
>int and bigint versions of all functions and then bail to the bigint version 
>if anything overflowed?

This is just what Lisp implementations have done for decades.

Yes, it means that code must be prepared to handle either version
(unless the compiler can prove that this is not necessary).
Generating two versions of all functions is neither necessary nor sufficient.

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Brian Hurt]

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

Mattias Engdegård wrote:

>>I wouldn't call it a bug. It looks like modulo arithmetic to me.
>>    
>>
>
>Let's not make a virtue of necessity. The type "int" was likely designed
>with the intent to provide a type that could be used for actual integers
>in a variety of circumstances, while giving good performance. The modulo
>semantics is rarely useful (especially the 30-bit signed variety) but
>is the price paid for reasonable performance with a simple implementation.
>  
>
Actually, the modulo behavior comes out of how the CPU designers made 
the CPUs work decades ago.  It was very easy for them to just drop all 
those extra bits (or not even compute them).  And, of course, now that 
behavior is cast in stone...

Brian


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

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[skaller]

On Fri, 2006-12-08 at 13:37 -0500, Brian Hurt wrote:
> Mattias Engdegård wrote:
> > > I wouldn't call it a bug. It looks like modulo arithmetic to me.
> > >     
> > 
> > Let's not make a virtue of necessity. The type "int" was likely designed
> > with the intent to provide a type that could be used for actual integers
> > in a variety of circumstances, while giving good performance. The modulo
> > semantics is rarely useful (especially the 30-bit signed variety) but
> > is the price paid for reasonable performance with a simple implementation.
> >   
> Actually, the modulo behavior comes out of how the CPU designers made
> the CPUs work decades ago.  It was very easy for them to just drop all
> those extra bits (or not even compute them).  And, of course, now that
> behavior is cast in stone...

More precisely I think: CPU's have always preserved the information
in flags. The culprit here, as usual, is the C programming language.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] if (n:int) < 0 then (-n) > 0 is FALSE

[Martin Jambon]

On Thu, 7 Dec 2006, Pal-Kristian Engstad wrote:

> To find that it loops forever. The reason is that 1024*1024*1024=2^30
> cannot be represented as a positive number on 32-bit platforms, hence it
> silently converts it to -1073741824, or -2^30. The reason this loops
> again is that -n = -(-20^30) = -20^30......, still negative!
>
> This is obviously a bug - has it since been fixed? But more alarmingly -
> why is there no warning?

For what it's worth, you can have a look at "Overflow":

  http://sebastien.ailleret.perso.cegetel.net/caml/

(I haven't tried it)


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr