On Thu, Nov 30, 2006 at 03:05:07PM +0200, Johann Spies wrote:
> I want to be able to parse very large .gz and .bz2 files and it will be
> nice if I can avoid (b|g)unzipping them before parsing them on a
> line-input basis.  There is no line_in function in the Zip-libraries as
> far as I can see.
>
> I know it is easy to handle this when the file can be read into memory
> as a string which can then be splitted up into a string list with "\n"
> as separator.  But how do I do that when I read a file into a string
> buffer which do not contain the whole file?

As with the first reply, the answer is to use Unix.open_process_in to
g/bunzip the file.

If you take a look at our Weblogs library
(http://merjis.com/developers/weblogs) you'll see some code in there I
wrote which can sniff the file type of an external file and then
automatically read the file in line-by-line, either through an
external g/bunzip program, or directly if the file isn't compressed.

Rich.

--
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

On Thu, Nov 30, 2006 at 10:53:31PM +0000, Sylvain Le Gall wrote:
> What about :
>
> My.test (FileUtil.Not(FileUtil.Size_not_null)) "xaa";;
>
> or
>
> not(My.test FileUtil.Size_not_null "xaa");;
>
> Is it what you need ?

Yes, thanks.

Regards
Johann
--
Johann Spies          Telefoon: 021-808 4036
Informasietegnologie, Universiteit van Stellenbosch

      "Who is like unto thee, O LORD, among the gods? who is
       like thee, glorious in holiness, fearful in praises,
       doing wonders?"             Exodus 15:11

If the signature name of a module is conventionally written in capital
letters why doesn't the Ocaml reference manual strictly adhere to this
convention?  What is supposed to be good style when writing programs?

For example: Here
http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.OrderedType.html
we find
module type OrderedType = sig .. end

insted of
module type ORDEREDTYPE = sig .. end

I am having some trouble trying Brian's module in my code:
  module MinHeap(Ord: Map.OrderedType) = struct

This is a functor that takes a structure that adheres to the
Map.OrderedType signature and returns a structure.

Could you please give me an example of how to use it in a hypothetical
module M that I want to define?

thanks.

On Fri, 1 Dec 2006, drehman27 wrote:

> If the signature name of a module is conventionally written in capital
> letters why doesn't the Ocaml reference manual strictly adhere to this
> convention?  What is supposed to be good style when writing programs?

Because it's not really a convention?  I know that they use it in the
manual in section 2, but that doesn't make it gospel.  It's a bit like
insisting that good style is words_written_like_this instead of
wordsWrittenLikeThis.  I suppose it would be nice if the manual was more
consistant that way, but it's not like it's something enforced by the
language.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers.  We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

          -- Neko Case

Life is unfair.  Kill yourself or get over it.
 	 -- Black Box Recorder

On Fri, 1 Dec 2006, drehman27 wrote:

> I am having some trouble trying Brian's module in my code:
> module MinHeap(Ord: Map.OrderedType) = struct
>
> This is a functor that takes a structure that adheres to the
> Map.OrderedType signature and returns a structure.
>
> Could you please give me an example of how to use it in a hypothetical
> module M that I want to define?

Well, I haven't looked too much at the minheap code, so I'll use the Map
module which uses the Map.OrderedType module type.

Essentially, you need to make sure that the structure you are wanting to
work with in the structure satisfies the requirements of Map.OrderedType.
I.e. it needs to have a type t that represents the type that we wish to
order, and it needs an ordering function, compare, that computes a ranking
on elements of type t according to some total order.  Then you feed that
module into the functor as an argument, and out pops a module that works
with your type.  Note, of course, that your module need only support those
two pieces as far as Map (and MinHep) are concerned, but it can do more,
if your wish.  For example:

module OT =
    struct
      type dir = Hubba | Bubba
      type t = dir * string

      let compare a b =
        match a,b with
        | (Hubba,_),(Bubba,_) -> 1
        | (Bubba,_),(Hubba,_) -> -1
        | (Hubba,s),(Hubba,t) -> Pervasives.compare s t
        | (Bubba,s),(Bubba,t) -> Pervasives.compare (String.length s)
(String.length t)

      let flip = function
      | (Hubba,s) -> (Bubba,s)
      | (Bubba,s) -> (Hubba,s)
    end

module MyMap = Map.Make(OT)

let mm = MyMap.empty
let mm = MyMap.add (OT.Hubba,"hooligan") 99 mm
let mm = MyMap.add (OT.Bubba,"a pint of berries") ~-7 mm
let x = MyMap.find (OT.Hubba,"hooligan") mm

(* and, assuming the minheap code was in a file called heap.ml and
compiled separately *)

module MyHeap = Heap.MinHeap(OT)

(* or if you just stuck his code in your current file *)

module MyHeap = MinHeap(OT)

let mh = MyHeap.empty
let mh = MyHeap.add mh (OT.Hubba,"apple")
let mh = MyHeap.add mh (OT.Bubba,"zebra")
let x = MyHeap.head mh

Note that for fairly simple things, you don't need to predefine the module
first.  This is convenient but usially harder to read:

module MyHeap =
    MinHeap(
      struct
        type t = string
        let compare a b =
          Pervasives.compare (String.length a) (String.length b)
      end);;

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers.  We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

          -- Neko Case

Life is unfair.  Kill yourself or get over it.
 	 -- Black Box Recorder

--- In ocaml_beginners@yahoogroups.com, "William D. Neumann"
<wneumann@...> wrote:

>
> (* and, assuming the minheap code was in a file called heap.ml and
> compiled separately *)
>
> module MyHeap = Heap.MinHeap(OT)
>

I put the minheap code in a file called minheap.ml but in my main file
I was trying to call the functor with MinHeap(MyModule) instead of
Minheap.MinHeap(MyModule) !!!
I was getting a hard time with this one. Thanks.

> first.  This is convenient but usially harder to read:
>
> module MyHeap =
>    MinHeap(
>      struct
>        type t = string
>        let compare a b =
>          Pervasives.compare (String.length a) (String.length b)
>      end);;
>

This is nice for short structures.

On Fri, 1 Dec 2006, drehman27 wrote:

> I put the minheap code in a file called minheap.ml but in my main file
> I was trying to call the functor with MinHeap(MyModule) instead of
> Minheap.MinHeap(MyModule) !!!
> I was getting a hard time with this one. Thanks.

You have to always rememder that when you put something in a file,
filename.ml, the entire contents of that file is implicitly placed inside
a module Filename.  And if you want to access any of those types and
values for a different file you need to either open Filename, or
explicitly specify Filname.whatever.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers.  We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

          -- Neko Case

Life is unfair.  Kill yourself or get over it.
 	 -- Black Box Recorder

On Fri, Dec 01, 2006 at 03:22:06PM -0000, drehman27 wrote:
> I am having some trouble trying Brian's module in my code:
>  module MinHeap(Ord: Map.OrderedType) = struct
>
> This is a functor that takes a structure that adheres to the
> Map.OrderedType signature and returns a structure.
>
> Could you please give me an example of how to use it in a hypothetical
> module M that I want to define?

Take Brian's code and save it in a file called 'minheap.ml' and
compile it like so:

   ocamlc -c minheap.ml

Then take the following and put it into a file called 'test.ml':

   open Minheap;;

   module StringHeap = MinHeap (String);;

   let heap = StringHeap.empty;;
   let heap = StringHeap.add heap "test";;
   prerr_endline ("The head of the heap is " ^ StringHeap.head heap);;

Then compile the test program using:

   ocamlc -c test.ml
   ocamlc minheap.cmo test.cmo -o test

and you can now run it:

   ./test
   >>> The head of the heap is test

In more detail what happens is that the functor MinHeap is looking for
a module which has a signature of Map.OrderedType.  If you look at
map.mli (from stdlib) you will see that this signature just requires a
'type t' and a 'val compare : t -> t -> int'.  Many standard modules
in the stdlib provide these basic functions.  In the test program
above, I chose the String module.

You can also define your own module.  For example:

   module BoolHeap = MinHeap (struct
	 type t = bool
	 let compare = compare
   end);;

which is a heap over booleans.

Rich.

--
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

If I try the following code it compiles fine

type r = { n : int; mutable x : float }

module MyMinHeap = Minheap.MinHeap(
struct
   type t = r
   let compare r1 r2 = if r1.n = r2.n then 0 else if r1.x < r2.x then
-1 else 1
end)

but if I move the type expression inside the structure expression like
this

module MyMinHeap = Minheap.MinHeap(
struct
   type t = { n : int; mutable x : float }
   let compare r1 r2 = if r1.n = r2.n then 0 else if r1.x < r2.x then
-1 else 1
end)

I get the following error:

This functor has type
functor (Ord : Map.OrderedType) ->
   sig
     type t = Minheap.MinHeap(Ord).t = Empty | Tree of int * t * Ord.t * t
     val height : t -> int
     val make : t -> Ord.t -> t -> t
     val join : t -> t -> t
     val join3 : Ord.t -> t -> t -> t -> t
     val empty : t
     val add : t -> Ord.t -> t
     val head : t -> Ord.t
     val remhead : t -> t
     val to_list : t -> Ord.t list
   end
The parameter cannot be eliminated in the result type.
  Please bind the argument to a module identifier.

On Fri, Dec 01, 2006 at 02:32:41PM -0000, drehman27 wrote:
> If the signature name of a module is conventionally written in capital
> letters why doesn't the Ocaml reference manual strictly adhere to this
> convention?  What is supposed to be good style when writing programs?
>
> For example: Here
> http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.OrderedType.html
> we find
> module type OrderedType = sig .. end
>
> insted of
> module type ORDEREDTYPE = sig .. end

The only rule is that the module name has to begin with a capital
letter.  Personally I'm glad they didn't use ORDEREDTYPE, because it's
very hard to read.

Rich.

--
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

On Fri, Dec 01, 2006 at 09:12:10AM +0000, Richard Jones wrote:
> On Thu, Nov 30, 2006 at 03:05:07PM +0200, Johann Spies wrote:
> > I want to be able to parse very large .gz and .bz2 files and it will be
> > nice if I can avoid (b|g)unzipping them before parsing them on a
> > line-input basis. There is no line_in function in the Zip-libraries as
> > far as I can see.
> >
> > I know it is easy to handle this when the file can be read into memory
> > as a string which can then be splitted up into a string list with "\n"
> > as separator. But how do I do that when I read a file into a string
> > buffer which do not contain the whole file?
>
> As with the first reply, the answer is to use Unix.open_process_in to
> g/bunzip the file.
>
> If you take a look at our Weblogs library
> (http://merjis.com/developers/weblogs) you'll see some code in there I
> wrote which can sniff the file type of an external file and then
> automatically read the file in line-by-line, either through an
> external g/bunzip program, or directly if the file isn't compressed.

Thanks Rich and all the others who replied. I was looking at
Unix.open_process_in but was uncertain how to use it in this
case.  I will look at your code.

It would be easy to just read the files from the commandline with
something like "zcat *.gz | ocamlprogram_to_parse_files" but the header of
each log file is different and I need to parse that seperately to be
able to identify the correct data.

Regards
Johann
--
Johann Spies          Telefoon: 021-808 4036
Informasietegnologie, Universiteit van Stellenbosch

      "Behold, happy is the man whom God correcteth.
       Therefore despise thou not the chastening of the
       Almighty."         Job 5:17

Hello,

I have the following code snippet (simplified):

.....................................................
type node = { mutable chld  : edge symlist  }
and edge = { parent : node ; child : node }


let null_node =
          let rec n = { chld = c }
          and     e = { parent=n ; child=n }
          and     c = empty e 	 <----- error
          in
             n
.....................................................

My problem is that "empty" is a function that creates an empty "list".
For this list I have the following definition:

.....................................................
type 'a cell = { ptr: 'a cell array ;
                   mutable data: 'a      }

type 'a symlist = {
                    mutable size: int  ;
                   mutable endc : 'a cell ;
                mutable hiddenc : 'a cell    }

(* Create a new list cell *)
let a_cell empty_val =
          let rec cell = { ptr=p; data=empty_val}
          and        p = [|cell; cell|]
          in
             cell


let empty empty_val =
          let end_c  = a_cell empty_val in
          let hidd_c = a_cell empty_val
          in
            end_c.ptr.(0)  <- hidd_c ;
            end_c.ptr.(1)  <- hidd_c ;
            hidd_c.ptr.(0) <- end_c ;
            hidd_c.ptr.(1) <- end_c ;
            {size=0 ; endc=end_c ; hiddenc=hidd_c }
.....................................................

My question is: why is this is the above a problem? It seems like all
types can be identified by the compiler. How can I solve this?

TIA.
Hugo F.

Hello,

I am collecting examples of pieces of codes leading to
compilation errors difficult  to interpret for newbies.

If you have experienced such difficulties could you please send me :
the  erroneous code, the error message and  the corrected code.

Thanks
François Colonna

.. and the official FAQ is worth looking at too:

http://caml.inria.fr/resources/doc/faq/index.en.html
http://caml.inria.fr/pub/old_caml_site/FAQ/FAQ_EXPERT-eng.html

Rich.

--
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

On Mon, Dec 04, 2006 at 11:53:41AM +0100, Francois Colonna wrote:
> I am collecting examples of pieces of codes leading to
> compilation errors difficult  to interpret for newbies.
>
> If you have experienced such difficulties could you please send me :
> the  erroneous code, the error message and  the corrected code.

Martin Jambon has been collecting such a list here:
http://www.ocaml-tutorial.org/common_error_messages

Rich.

--
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

The sphere online judge has an apparently simple problem which has
never been solved in ocaml before.

http://www.spoj.pl/problems/MUL/

I'm trying to be the first, but perhaps someone else on this board
would like to give it a try. We can make it a group effort also.

One tip I have is that using the nums library won't be fast enough.
But the code for such an entry will give you a start. I've also tried
doing array multiplication and that isn't fast enough. We'll need a
VERY fast algorithm to make an ocaml submission good enough.

open Num

let multiply n =
   for i=1 to n do
     Scanf.scanf
       "\n%s %s"
       (fun num1str num2str ->
     let num1 = num_of_string num1str in
     let num2 = num_of_string num2str in
     print_endline
       (string_of_num
          (mult_num num1 num2))
       )
   done;;

Scanf.scanf "%i" multiply;
exit 0;

Here is an interesting related discussion:
http://groups.google.com/group/comp.lang.functional/browse_thread/thread/d716440\
93332cf87/313e6ab8393a64f5

Does this mean that caml cannot meet this challenge?

Hello,

Le lun 04 déc 2006 10:29:30 CET,
Hugo Ferreira <hmf@...> a écrit :

> type node = { mutable chld  : edge symlist  }
> and edge = { parent : node ; child : node }
>
>
> let null_node =
>          let rec n = { chld = c }
>          and     e = { parent=n ; child=n }
>          and     c = empty e 	 <----- error

> My question is: why is this is the above a problem? It seems like all
> types can be identified by the compiler. How can I solve this?
>

This has nothing to do with types. There are some syntactic
restrictions on what you can put in a recursive definition of
non-functional values. These are detailed in section 7.3 of the
reference manual. Basically, you can have data constructors, so that
(manually) inlining the definition of empty might work.
--
E tutto per oggi, a la prossima volta.
Virgile

Hi,

Virgile Prevosto wrote:
> Hello,
>
> Le lun 04 déc 2006 10:29:30 CET,
> Hugo Ferreira <hmf@...> a écrit :
>
>> type node = { mutable chld  : edge symlist  }
>> and edge = { parent : node ; child : node }
>>
>>
>> let null_node =
>>          let rec n = { chld = c }
>>          and     e = { parent=n ; child=n }
>>          and     c = empty e 	 <----- error
>
>> My question is: why is this is the above a problem? It seems like all
>> types can be identified by the compiler. How can I solve this?
>>
>
> This has nothing to do with types.

I see.

  > There are some syntactic
> restrictions on what you can put in a recursive definition of
> non-functional values. These are detailed in section 7.3 of the
> reference manual.

I read this over several times. Still cannot figure out what is the
problem (although I think it is because my example is immediately
linked" because "empty e" is a let rec itself).

  > Basically, you can have data constructors, so that
> (manually) inlining the definition of empty might work.

Ok doing that "solves" the problem.


(venting....) doesn't it bother anyone that a polymorphic data structure
   (in my case an imperative style symmetric list) that is coded for
reuse simply cannot (re)used? This seems odd. Must I always resort to
*manual* inlining the code!? Maybe I am going about it the wrong way.

Thanks for the info.

Regards,
Hugo F.

On Mon, Dec 04, 2006 at 09:28:03PM -0000, jshaw10 wrote:
> The sphere online judge has an apparently simple problem which has
> never been solved in ocaml before.
>
> http://www.spoj.pl/problems/MUL/

I get
    "                                          Forbidden

    You don't have permission to access /problems/MUL/ on this server."

Regards
Johann
--
Johann Spies          Telefoon: 021-808 4036
Informasietegnologie, Universiteit van Stellenbosch

      "Go ye therefore, and teach all nations, baptizing them
       in the name of the Father, and of the Son, and of the
       Holy Ghost; Teaching them to observe all things
       whatsoever I have commanded you; and, lo, I am with
       you alway, even unto the end of the world. Amen."
             Matthew 28:19,20

Le mar 05 déc 2006 08:06:53 CET,
Hugo Ferreira <hmf@...> a écrit :

> > non-functional values. These are detailed in section 7.3 of the
> > reference manual.
>
> I read this over several times. Still cannot figure out what is the
> problem (although I think it is because my example is immediately
> linked" because "empty e" is a let rec itself).
>

No. empty e is an application which involves one of the recursively
defined variables, hence it is not "statically constructive with
respect to " e.


> (venting....) doesn't it bother anyone that a polymorphic data
> structure (in my case an imperative style symmetric list) that is

This annoyance is here to ensure that the compiled code is correct, i.e.
that attempting to access 'e' will result in something that looks like
a value of the expected type and not an arbitrary bunch of code (like
the one coding the application of an arbitrary function for instance.
On the other hand, applying a data constructor is OK, since it would
simply result in a tag and pointers to the arguments).

> coded for reuse simply cannot (re)used? This seems odd. Must I always
> resort to *manual* inlining the code!? Maybe I am going about it the
> wrong way.

I guess that camlp4 could help in your case, with a rule that'd look
like the one for defining infix symbol here:
http://martin.jambon.free.fr/pa_infix.ml.html
But this will be quite complicated (basically, you'd have write a
grammar rule that perform the substitution of the actual argument to
the parameter of the function). I'm not aware of a syntax extension
that does that, but maybe it exists somewhere. You might also be
interested in Meta-Ocaml (http://www.metaocaml.org/), but I don't know
that project enough to say something relevant on it.

--
E tutto per oggi, a la prossima volta.
Virgile

I want to be able to do this on the command line

program -i someinputfile -o someoutputfile *.log

where for example *.log expands to
1.log
2.log
3.log

and in the end I want the program to handle a file list where the
anonymous arguments were added to the specified input file:

["someinputfile"; "1.log"; "2.log"; "3.log"]

In getop.mli I read:



{1 Command line specification}
    A specification lists the possible options and describe what to do
    when they are found; it also gives the action for anonymous arguments
    and for the special option - (a single dash alone).

I could not find any reference on how this is done nor any example.

I have tried, in the light of the above paragraph to adapt the example
(sample.ml) provided with the getopt-library like this:

Original

let specs =
[
   ( 'x', "execute", None, Some (fun x -> Printf.printf "execute %s\n" x));
   ( 'I', "include", None, (append includ));
   ( 'o', "output",  None, (atmost_once output (Error "only one output")));
   ( 'a', "archive", (set archive true), None);
   ( 'u', "update",  (set update  true), None);
   ( 'v', "verbose", (incr verbose), None);
   ( 'X', "",        Some bip, None);
   ( 'w', "wait",    Some wait, None)

]

Adapted:

let specs =
[
   ( 'x', "execute", None, Some (fun x -> Printf.printf "execute %s\n" x));
   ( 'I', "include", None, (append includ));
   ( '-', "",  None, (append includ));
   ( 'o', "output",  None, (atmost_once output (Error "only one output")));
   ( 'a', "archive", (set archive true), None);
   ( 'u', "update",  (set update  true), None);
   ( 'v', "verbose", (incr verbose), None);
   ( 'X', "",        Some bip, None);
   ( 'w', "wait",    Some wait, None)

]

But my that made noimpact.

I prefer Getopt to Arg because I could not figure out how to use Arg to
be able to concat short options (e.g. -vap for -v -a -p ).

I wish I could figure out how to use anonymous arguments ... :)

Regards
Johann

--
Johann Spies          Telefoon: 021-808 4036
Informasietegnologie, Universiteit van Stellenbosch

      "Go ye therefore, and teach all nations, baptizing them
       in the name of the Father, and of the Son, and of the
       Holy Ghost; Teaching them to observe all things
       whatsoever I have commanded you; and, lo, I am with
       you alway, even unto the end of the world. Amen."
             Matthew 28:19,20

Virgile,

Appreciate the feedback. I will stick to "manual inlining" otherwise I
will never see the end of this project.

Regards,
Hugo F.


Virgile Prevosto wrote:
> Le mar 05 déc 2006 08:06:53 CET,
> Hugo Ferreira <hmf@...> a écrit :
>
>>> non-functional values. These are detailed in section 7.3 of the
>>> reference manual.
>> I read this over several times. Still cannot figure out what is the
>> problem (although I think it is because my example is immediately
>> linked" because "empty e" is a let rec itself).
>>
>
> No. empty e is an application which involves one of the recursively
> defined variables, hence it is not "statically constructive with
> respect to " e.
>
>
>> (venting....) doesn't it bother anyone that a polymorphic data
>> structure (in my case an imperative style symmetric list) that is
>
> This annoyance is here to ensure that the compiled code is correct, i.e.
> that attempting to access 'e' will result in something that looks like
> a value of the expected type and not an arbitrary bunch of code (like
> the one coding the application of an arbitrary function for instance.
> On the other hand, applying a data constructor is OK, since it would
> simply result in a tag and pointers to the arguments).
>
>> coded for reuse simply cannot (re)used? This seems odd. Must I always
>> resort to *manual* inlining the code!? Maybe I am going about it the
>> wrong way.
>
> I guess that camlp4 could help in your case, with a rule that'd look
> like the one for defining infix symbol here:
> http://martin.jambon.free.fr/pa_infix.ml.html
> But this will be quite complicated (basically, you'd have write a
> grammar rule that perform the substitution of the actual argument to
> the parameter of the function). I'm not aware of a syntax extension
> that does that, but maybe it exists somewhere. You might also be
> interested in Meta-Ocaml (http://www.metaocaml.org/), but I don't know
> that project enough to say something relevant on it.
>

On Tue, Dec 05, 2006 at 11:36:09AM +0200, Johann Spies wrote:
> I want to be able to do this on the command line
>
> program -i someinputfile -o someoutputfile *.log

Sometimes asking a question helps me to get think clear ...

> But my that made noimpact.

but not if I type nonsense like this :(  Apologies for that.


Anyhow after reading getop.ml again I saw that the second argument to
parse_cmdline is actually my solution:

parse_cmdline specs (fun x -> includ := x::!includ);

solved my problem.

Regards
Johann
--
Johann Spies          Telefoon: 021-808 4036
Informasietegnologie, Universiteit van Stellenbosch

      "Go ye therefore, and teach all nations, baptizing them
       in the name of the Father, and of the Son, and of the
       Holy Ghost; Teaching them to observe all things
       whatsoever I have commanded you; and, lo, I am with
       you alway, even unto the end of the world. Amen."
             Matthew 28:19,20

The link should work fine - it works even though I'm not logged in.
Well anyway, you can just go to http://www.spoj.pl/ and browse to
problem number 31.

I've gotten a little more information about the run time of the
solutions I've tried on the spoj system:

-bignum solutions require 4.5 seconds
-array solutions require >30 seconds

The array solution is probably so bad because of the issues discussed
in the link I gave in my first post in this thread.

[This is getting off-topic, but..]

JShaw> The array solution is probably so bad because of the issues discussed
JShaw> in the link I gave in my first post in this thread.

On principle I'd be surprised if that'll be a problem: you're only
multiplying two numbers at a time, and never getting to data sets on the
scale mentioned in that thread --- a 10,000 digit number should be
representable in about 4kB (modulo Ocaml int issues).

More than that you should be looking at smart algorithms: for large
numbers, the obvious high-school long-multiplication algorithm is very
inefficient --- O(n^2) in digits compared with (*very* theoretical)
numbers of O(n.log(n)) for FFT-style algorithms.

From what I understand from a 2-year-old post, Ocaml's Bignum has
quadratic performance on multiplication.  MLGMP and Numerix both seem to
have subquadratic performance.  So if the competition gives you access
to either of those you should be sorted.  Alternatively, you can do-it-
yourself, using something like this:

   http://numbers.computation.free.fr/Constants/Algorithms/fft.html

It will all depend on the number of digits in the numbers in the problem
set though, and FFT may have too high an overhead since it only
practically wins once you reach about 10,000 digits, the maximum for the
MUL problem.  Conditionally using a few levels of Karatsuba on the
bignum version could shave over half the time off though, again
depending on overhead and number size (theoretically it should be more
than ten times faster at 5,000 digits, but overheads would get in the
way I expect).  This might at least put you in at the tail end of the
competition with your current code.

   http://mathworld.wolfram.com/KaratsubaMultiplication.html

Conrad

On Tue, 5 Dec 2006, jshaw10 wrote:

> I've gotten a little more information about the run time of the
> solutions I've tried on the spoj system:
>
> -bignum solutions require 4.5 seconds
> -array solutions require >30 seconds
>
> The array solution is probably so bad because of the issues discussed
> in the link I gave in my first post in this thread.

OK, well after looking at the problem specification, I can tell that
whoever submitted it is a bit off their rocker.  The spec calls for up to
1000 multiplications of up to two 10000 digit numbers to be completed in
under 2 seconds.  OK...

Using Schonhage-Strassen multiplication, this is going to require on the
order of 0.8x10^9 operations.  That's ignoring constant factors, that's
assuming the data has already been read in and converted to a workable
format.

Of course, the conversion is the part that kills you anyway.  Using a
randomly generated file of 1000 pairs of numbers at most 10000 digits long
(the average length is about 5000 digits, as expected) simply converting
from strings to numbers and back again takes about 47 seconds on my
machine (not sure what the theoretical running time is on string -> number
conversion, but I don't care too much, it's not going to be cheap).

Now, obviously, whoever submitted this is not using an input set that
comes anywhere near the limits of the spec, but even so, his numbers just
don't jibe...

Anyway, we have the two big issues of string -> number conversion and what
multiplication algorithm OCaml is using under the hood for its nums.  I'm
guessing that it's not Schonhage-Strassen, Karatsuba, or FFT, but I might
be wrong.  If that's the case, unless you can call out to another library,
like gmp or numerix (I might try that after lunch), you're going to need
to code it up yourself (which would likekly be painful). Unless, of course
the data gives you a lot of shortcuttable solutions (lots of 0s and 1s in
the data set).

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers.  We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

          -- Neko Case

Life is unfair.  Kill yourself or get over it.
 	 -- Black Box Recorder

William> simply converting from strings to numbers
William> and back again takes about 47 seconds on my machine

How about using a radix-10000 bignum implementation (10^8<2^31, ditto
4*10^8 --- good for Karatsuba...)?

Conrad

On Tue, 5 Dec 2006, Conrad Hughes wrote:

> How about using a radix-10000 bignum implementation (10^8<2^31, ditto
> 4*10^8 --- good for Karatsuba...)?

I don't suppose you have one lying around...

BTW: in case anyone cares GMP provides an approximate 15x speedup,
dropping my test time from ~75 seconds to ~5 seconds.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers.  We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

          -- Neko Case

Life is unfair.  Kill yourself or get over it.
 	 -- Black Box Recorder