* [Caml-list] Big_int comparisons @ 2004-02-01 19:42 Yaron M. Minsky 2004-02-02 12:23 ` Alain.Frisch 0 siblings, 1 reply; 5+ messages in thread From: Yaron M. Minsky @ 2004-02-01 19:42 UTC (permalink / raw) To: Caml List 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Caml-list] Big_int comparisons 2004-02-01 19:42 [Caml-list] Big_int comparisons Yaron M. Minsky @ 2004-02-02 12:23 ` Alain.Frisch 2004-02-02 12:34 ` Yaron M. Minsky 2004-02-03 9:52 ` skaller 0 siblings, 2 replies; 5+ messages in thread From: Alain.Frisch @ 2004-02-02 12:23 UTC (permalink / raw) To: Yaron M. Minsky; +Cc: Caml List 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Caml-list] Big_int comparisons 2004-02-02 12:23 ` Alain.Frisch @ 2004-02-02 12:34 ` Yaron M. Minsky 2004-02-02 13:36 ` Alain.Frisch 2004-02-03 9:52 ` skaller 1 sibling, 1 reply; 5+ messages in thread From: Yaron M. Minsky @ 2004-02-02 12:34 UTC (permalink / raw) To: Alain.Frisch; +Cc: Caml List 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Caml-list] Big_int comparisons 2004-02-02 12:34 ` Yaron M. Minsky @ 2004-02-02 13:36 ` Alain.Frisch 0 siblings, 0 replies; 5+ messages in thread From: Alain.Frisch @ 2004-02-02 13:36 UTC (permalink / raw) To: Yaron M. Minsky; +Cc: Caml List 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Caml-list] Big_int comparisons 2004-02-02 12:23 ` Alain.Frisch 2004-02-02 12:34 ` Yaron M. Minsky @ 2004-02-03 9:52 ` skaller 1 sibling, 0 replies; 5+ messages in thread From: skaller @ 2004-02-03 9:52 UTC (permalink / raw) To: Alain.Frisch; +Cc: Yaron M. Minsky, Caml List 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2004-02-03 9:51 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2004-02-01 19:42 [Caml-list] Big_int comparisons Yaron M. Minsky 2004-02-02 12:23 ` Alain.Frisch 2004-02-02 12:34 ` Yaron M. Minsky 2004-02-02 13:36 ` Alain.Frisch 2004-02-03 9:52 ` skaller
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).