[Caml-list] Big_int comparisons

[Caml-list] Big_int comparisons

[Yaron M. Minsky]

Does anyone know why there's no support for Big_int comparisons?  I know
that Michel Quercia hacked them in at some point as part of his Numerix
package, so it doesn't appear to be impossible.

A second question: does anyone know whether the performance of Big_int
is now better than it was, and how it compares to the alternatives, such
as mlgmp and numerix?  I currently use numerix and am considering
dumping it for Big_int, in the interest of improving portability and
reducing compilation woes.  But I want to get an estimate of what kind
of performance hit I'll see.

Yaron

-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916


-------------------
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] Big_int comparisons

[Alain.Frisch]

On Sun, 1 Feb 2004, Yaron M. Minsky wrote:

> Does anyone know why there's no support for Big_int comparisons?

Do you mean the generic comparison functions ?  The reason is that the
type big_int is a Caml record type, and it is not possible to attach
custom comparison functions to the values of such types. One could imagine
adding a comparison function to the underlying nat objets (which are
custom blocks), which would allow using the generic comparison functions
on big_int objects. The problem is that even if the order on nat is the
natural order on non-negative integers, the induced order on big_int will
not be the natural order on integers. Even worse for the num type, which
admit several representation for the same numer.

This is annoying, because you cannot use the generic comparison functions
on large datastructures which contains somewhere deep in the structure
some nat, big_int or num. Even if you don't care about the meaning
of the ordering (you only need one ordering to implement some kind of
set).

A solution could be to allow attaching custom generic operations to
non-custom blocks (for instance, by boxing values in a block with a
special GC tag + the custom operations; i.e.: custom blocks whose content
is traced by the GC). This could be implemented with custom blocks by
registering/unregistering global roots, but I guess the performance would
be bad.


  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

Re: [Caml-list] Big_int comparisons

[Yaron M. Minsky]

On Mon, 2004-02-02 at 07:23, Alain.Frisch@ens.fr wrote:
> On Sun, 1 Feb 2004, Yaron M. Minsky wrote:
> 
> > Does anyone know why there's no support for Big_int comparisons?
> 
> Do you mean the generic comparison functions ?  The reason is that the
> type big_int is a Caml record type, and it is not possible to attach
> custom comparison functions to the values of such types. One could imagine
> adding a comparison function to the underlying nat objets (which are
> custom blocks), which would allow using the generic comparison functions
> on big_int objects. The problem is that even if the order on nat is the
> natural order on non-negative integers, the induced order on big_int will
> not be the natural order on integers. Even worse for the num type, which
> admit several representation for the same numer.

This confuses me, because as I mentioned, michel quercia appears to have
fixed this problem while working on Numerix.  Here's his patch:

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&threadm=fa.j11k5cv.r5cu86%40ifi.uio.no&rnum=1&prev=/groups%3Fq%3Dgroup:fa.caml%2Bauthor:michel%2Bauthor:quercia%2Bcompare%26hl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DUTF-8%26selm%3Dfa.j11k5cv.r5cu86%2540ifi.uio.no%26rnum%3D1

Also, what is going on with the Nat type?  It seems to be completely
undocumented.  Is Big_int built on Nat?  Are there efficiency reasons to
choose one or the other if both will do semantically? 

> This is annoying, because you cannot use the generic comparison functions
> on large datastructures which contains somewhere deep in the structure
> some nat, big_int or num. Even if you don't care about the meaning
> of the ordering (you only need one ordering to implement some kind of
> set).

Agreed.  Plus, I'm considering porting some code over from using Numerix
to using Big_int, and I'm concerned that I maybe introducing runtime
errors somewhere in my code, and it's hard to track down where they
might be.

> A solution could be to allow attaching custom generic operations to
> non-custom blocks (for instance, by boxing values in a block with a
> special GC tag + the custom operations; i.e.: custom blocks whose content
> is traced by the GC). This could be implemented with custom blocks by
> registering/unregistering global roots, but I guess the performance would
> be bad.

Is that what Michel did?

Yaron

-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916


-------------------
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] Big_int comparisons

[Alain.Frisch]

On Mon, 2 Feb 2004, Yaron M. Minsky wrote:

> This confuses me, because as I mentioned, michel quercia appears to have
> fixed this problem while working on Numerix.  Here's his patch:

The patch solves the problem for the nat type, not for big_int.
If you know the ordering won't be the natural one for big_int, it is ok,
but this might be confusing, and for this reason Xavier Leroy rejected a
similar patch I proposed.

If you read french:
http://caml.inria.fr/bin/caml-bugs/wish%20not%20granted?id=1445

Note the problem is only for comparison, not for hashing.

> > A solution could be to allow attaching custom generic operations to
> > non-custom blocks (for instance, by boxing values in a block with a
> > special GC tag + the custom operations; i.e.: custom blocks whose content
> > is traced by the GC). This could be implemented with custom blocks by
> > registering/unregistering global roots, but I guess the performance would
> > be bad.
>
> Is that what Michel did?

No.

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

Re: [Caml-list] Big_int comparisons

[skaller]

On Mon, 2004-02-02 at 23:23, Alain.Frisch@ens.fr wrote:
> On Sun, 1 Feb 2004, Yaron M. Minsky wrote:
> 
> > Does anyone know why there's no support for Big_int comparisons?
> 

> A solution could be to allow attaching custom generic operations to
> non-custom blocks 

The problem with this is you end up re-implementing Python,
i.e. having a 'vector' of generic functions for each type.
Another 'useful' generic operator is of course 'get next'
for containers (C++ iterators, Python sequence operators ..)

Now, Ocaml does provide the tools to deal with this in most cases:
functors (provided the genericity is not required to be run-time). 

The problem then would seem to be that
its hard to write functors for every data structure,
sub-data structure of the data stucture, etc.

At least part of the reason is that the functors
provide abstract types, so building a functor
to provide, for example, a comparator so you 
can put them in sets isn't immediately compatible
with other generic operations such as pattern matching.

It seems like the 'private' keyword is a step forward here:
a way to control representation invariants during construction
(or mutation) which doesn't prevent convenient algrebraic
type destructors like pattern matching being used: even though,
in principle, these operations may not retain their semantics,
for example a type

	int * int

representing a rational number admits the destructor

	fst v

which is not in fact a projection (since the type
is not a product).


-- 
John Max Skaller, mailto:skaller@tpg.com.au
snail:25/85c Wigram Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850. Checkout Felix: http://felix.sf.net




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