[Caml-list] Problem with the old Num implementation of ocaml (fwd)

[Caml-list] Problem with the old Num implementation of ocaml (fwd)

[Thomas Fischbacher]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 4863 bytes --]


The following pieces of email I just submitted to the Debian Bug Tracking 
System; Sven Luther (the Debian Maintainer) recommended to also forward it 
to this list, as this may be of interest to more people...

---------- Forwarded message ----------
Date: Thu, 18 Dec 2003 21:15:40 +0100 (CET)
From: Thomas Fischbacher <tf@cip.physik.uni-muenchen.de>
To: submit@bugs.debian.org
Subject: Problem with the old Num implementation of ocaml


Package:  ocaml 
Version: 3.06-21
Severity: grave


Please note that this bug concerns the "old" Num implementation that was 
removed in a recent update. I nevertheless use(d) it as I am right 
now doing research for a new string theory paper and wanted to 
consistently use one and the same somewhat environment throughout the 
process. Nevertheless, I suppose this affects all versions having the old num 
implementation (next thing I'll do is to upgrade my entire system to the 
new implementation and check the behaviour of that one for some large test 
calculations).

The attachment will reproduce a condition where doing the same calculation 
(which is purely functional to the outside and does not use global state 
or side effects, but involves Num) many times in sequence will give 
different results.

As you see, about half of this file is data; I did not manage to find a 
smaller test case creating that condition. Although I consider this highly
unlikely, this piece of code may involve an "int"-type related integer 
overflow. (Nevertheless, even so, subsequent identical calculations should 
not give different results...)


On my system(*), the output of a num_ocaml interpreter built as described 
in the Num section of the documentation, but also including the Unix 
module is:

0 ==> -12747938802280433395210374808335212773156996019062242486412495785350259890027861091589626807758181401556588623046875/764762496031801254357991532266868085634832685275244705613839817948600630474284529321916381431208558769420593384116260078281979735715302794541235545562947747053568
1 ==> -24799801902139948285742077521010897923261300584495629346339410063333039539280530883995185222932342824043982837509521484375/4156317913216311164989084414493848291493655898235025573988259880155438209099372441966936855604394341138155398826718804773271628998452732579028454051972542103552
2 ==> -39148920061803210956691061036397438426365134774540146675772774556810648122275561412271743926625375084180283661376953125/2294287488095403763073974596800604256904498055825734116841519453845801891422853587965749144293625676308261780152348780234845939207145908383623706636688843241160704
3 ==> -39148920061803210956691061036397438426365134774540146675772774556810648122275561412271743926625375084180283661376953125/2294287488095403763073974596800604256904498055825734116841519453845801891422853587965749144293625676308261780152348780234845939207145908383623706636688843241160704
4 ==> -24799801902139948285742077521010897923261300584495629346339410063333039539280530883995185222932342824043982837509521484375/4156317913216311164989084414493848291493655898235025573988259880155438209099372441966936855604394341138155398826718804773271628998452732579028454051972542103552
5 ==> -24799801902139948285742077521010897923261300584495629346339410063333039539280530883995185222932342824043982837509521484375/4156317913216311164989084414493848291493655898235025573988259880155438209099372441966936855604394341138155398826718804773271628998452732579028454051972542103552
6 ==> -39148920061803210956691061036397438426365134774540146675772774556810648122275561412271743926625375084180283661376953125/2294287488095403763073974596800604256904498055825734116841519453845801891422853587965749144293625676308261780152348780234845939207145908383623706636688843241160704
7 ==> -39148920061803210956691061036397438426365134774540146675772774556810648122275561412271743926625375084180283661376953125/2294287488095403763073974596800604256904498055825734116841519453845801891422853587965749144293625676308261780152348780234845939207145908383623706636688843241160704
8 ==> -39148920061803210956691061036397438426365134774540146675772774556810648122275561412271743926625375084180283661376953125/2294287488095403763073974596800604256904498055825734116841519453845801891422853587965749144293625676308261780152348780234845939207145908383623706636688843241160704
9 ==> 0
- : unit = ()

The correct result is zero.

(*) uname -a

Linux djinn 2.4.23 #6 Thu Dec 4 18:13:28 CET 2003 i686 GNU/Linux


I would like to know whether this can be confirmed.

-- 
regards,                  tf@cip.physik.uni-muenchen.de              (o_
Dr. Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)              V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                     (Debian GNU)


===================

Re: [Caml-list] Problem with the old Num implementation of ocaml (fwd) (PR#1989)

[Damien Doligez]

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

On Friday, December 19, 2003, at 11:17 AM, Thomas Fischbacher wrote:

> Please note that this bug concerns the "old" Num implementation that 
> was
> removed in a recent update.

This bug is in fact in the ML part of the Num library, which is common
to both the old and new Num implementations.  I think it dates back to
Caml Light.

> The attachment will reproduce a condition where doing the same 
> calculation
> (which is purely functional to the outside and does not use global 
> state
> or side effects, but involves Num) many times in sequence will give
> different results.

This "nondeterminism" comes from using a Nat.nat with an uninitialised
digit, using whatever was already in memory at that address.

> arithmetics I am using? Yet to me it seems plausible that some serious
> issue may have been overlooked here, since I suppose very few people 
> use
> ratio arith (in contrast to bignum-only arith, which has applications 
> for,
> e.g., RSA).

Indeed, the bug is in the big-int part of the library (arbitrary 
precision
signed integers).


Thank you for your well-delimited bug report with a reproducible test
case.  It was rather easy to find the bug with it.

I enclose a patch, which should work on 3.06 and on 3.07pl2.

-- Damien


[-- Attachment #2: patch-fischbacher.txt --]
[-- Type: text/plain, Size: 499 bytes --]

*** otherlibs/num/big_int.ml.old	Sat Dec 27 23:45:12 2003
--- otherlibs/num/big_int.ml	Sat Dec 27 23:38:44 2003
***************
*** 178,183 ****
--- 178,184 ----
    if i = monster_int
       then let res = create_nat size_res in
              blit_nat res 0 (bi.abs_value) 0 size_bi;
+             set_digit_nat res size_bi 0;
              mult_digit_nat res 0 size_res (bi.abs_value) 0 size_bi 
                             (nat_of_int biggest_int) 0;
              { sign = - (sign_big_int bi);

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

Re: [Caml-list] Problem with the Num implementation

[Christophe Raffalli]

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


I just use this thread to ask again a question ...

How to compute the best or at least a very good float interval 
containing a rational number with the num library ?

The float_of-num function is really not convincing (it is very slow 
because it does a translation to a decimal representation as string and 
look at all the digits !).

Remark: it should be possible to find a very good (may be not always the 
best) float interval in constant time !

This is usefull to implement lazy arithmetics (you compute with floating 
point interval until this is not enough and then you compute the exact 
value. But it is useful in some cases to compute an interval from the
rational number and it needs to be fast to be useful)


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

[-- Attachment #2: Type: application/pgp-signature, Size: 252 bytes --]

Re: [Caml-list] Problem with the old Num implementation of ocaml (fwd) (PR#1989)

[Thomas Fischbacher]

On Sat, 27 Dec 2003, Damien Doligez wrote:

> This bug is in fact in the ML part of the Num library, which is common
> to both the old and new Num implementations.  I think it dates back to
> Caml Light.
(...)
> This "nondeterminism" comes from using a Nat.nat with an uninitialised
> digit, using whatever was already in memory at that address.

Many thanks for your prompt action. (By the way, ocaml is a very nice tool 
for certain kinds of calculations in Superstring/M-Theory - see 
http://arxiv.org/abs/hep-th/0312262 .)

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

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