Possible improvement to mul about hops HOT 8 CLOSED

Thanks for bringing this to my attention @bawolk and for the kind words about the project. I think you have a good point and wonder if it's OK with you if we reopen this issue? If so could you please paste in your original comments? (or file a new issue).

from hops.

I withdrew my comment for two reasons. First, I wanted to dig deeper into the project to see what the ramifications would be of using Indet as a marker that all further coefficients are zero. Second, I started working from your master branch and discovered that you had switched to a fascinating integer packing algorithm for mul. I want to make sure I understand that algorithm before I make any concrete suggestions.

I am using hops in connection with my reading of Sedgewick and Flajolet's "Analytic Combinatorics"(2009). To that end I have added four new transforms, SEQ, PSET, MSET, and CYC for my personal use. These are key transforms associated with some of the basic constructions in their theory. (See p. 27.) These four transforms are apparently known as Pólya operators: the quasi-inverse, modified Pólya exponential, Pólya exponential, and Pólya logarithm respectively. (See p. 34) The structure of your project makes adding new transforms a breeze!

By the way, thanks for the heads-up on jq only supporting IEEE 754 64-bit numbers. I naively tried to use jq '.seq | .[250] to extract a 72 digit coefficient number 250. This python one-liner is more successful:
python -c 'import json, sys; print json.load(sys.stdin)["seq"][250]'

from hops.

Thanks for explaining why you withdrew your comment; that makes a lot of sense.

Regarding Indent it's not a marker that all further coefficients are zero. Rather it is a marker of a coefficient that is unknown/indeterminate, but finite (in contrast with DZ). It's main purpose is to allow us to define generating functions by functional equations. E.g. "solving" f=1+2*x*f is done by letting f=O(1)=[Indet,..] and then iterating: f = 1+x*f = 1+2*x*O(1) = 1+O(x) = [1,Indet,...];
f = 1+x*f = 1+2*x*(1+O(x)) = 1+2*x+O(x^2) = [1,2,Indet,...]; etc.

Here's another way to observe the difference between filling the tail with Indents and filling it with zeros:

> let f = series (Proxy :: Proxy 4) [1,1]
> f
series (Proxy :: Proxy 4) [Val (1 % 1),Val (1 % 1),Indet,Indet]
> f^2
series (Proxy :: Proxy 4) [Val (1 % 1),Val (2 % 1),Indet,Indet]

> let g = polynomial (Proxy :: Proxy 4) [1,1]
> g
series (Proxy :: Proxy 4) [Val (1 % 1),Val (1 % 1),Val (0 % 1),Val (0 % 1)]
> g^2
series (Proxy :: Proxy 4) [Val (1 % 1),Val (2 % 1),Val (1 % 1),Val (0 % 1)]

As an aside I'm not sure it was the right decision to include DZ as an option on the coefficient level, or if it would have been better to let the eval function deal with the possibility of division by zero.

Regarding the implementation of multiplication, any suggestions to improve it's performance are most welcome. The Kronecker substitution trick is indeed very neat; it basically delegates the problem to the bignum library. My implementation seems rather slow on the example you provided though.

Thanks for showing how to use python instead of jq. That's very useful and news to me.

You mentioned that you had some problems compiling the whole project. Let me know if there is anything I can do to make it easier.

Best of luck with your Analytic Combinatorics studies. It's a great book to learn from. If you would like to open pull requests for the transformations you add at some point that would be very welcome too.

from hops.

The whole project actually compiles quite nicely using stack build after an initial execution of stack init. My initial issue arose from my failure to have pandoc installed on my system.

I'm sure I'm missing something, but doesn't f = O(1)= [0,..] and then iterating work just as well? Along these lines, the current use of Indet causes the following, which to me is counter intuitive:

$ hops  '(1/(1-{0,2}))'
{"hops":"(1/(1-{0,2}))","seq":[1,2]}
$  hops  '(1/(1-2*x))'
{"hops":"(1/(1-2*x))","seq":[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]}

Obviously {0,2} is being treated as series, with the corresponding use of Indef, rather than a polynomial. But with no recursion in sight here, wouldn't a polynomial make more sense?

I wondered about DZ as well. I wish I knew more about the underlying algorithms for pattern matching, Does an additional data constructor reduce efficiency since more cases have to be considered? Would adding still another data constructor, say Zero, to signify the end of the non-zero polynomial terms, slow things down even further?

from hops.

To follow up on my query regarding whether Indet is needed for interating recursive functions, I changed the definition of nil in GF.hs to be nil = polynomial (Proxy :: Proxy n) []. All of your tests passed!

from hops.

I think you're right, starting with [0,...] when iterating would work just as well. Good point!

I have a second motivation for keeping Indent however. A common use case for me is that I'm investigating some mostly unknown sequence (enumerating some combinatorial objects). Maybe I only know the first 7 terms, say. I then want to be able to apply different transformations to this sequence and still know how many terms I can trust. E.g. say that I know that the sequence starts 1,1,2,5,18,77,362.

Viewing this as (the start of) an ogf, let's call it f, we can for instance look at f/(1-2*x)

$ hops '{1,1,2,5,18,77,362}/(1-2*x)' | jq '.seq=(.seq|@csv)'
{
  "hops": "{1,1,2,5,18,77,362}/(1-2*x)",
  "seq": "1,3,8,21,60,197,756"
}

and discover that this sequence is in the OEIS:

$ hops '{1,1,2,5,18,77,362}/(1-2*x)' | sloane | jq '.name'
"Boustrophedon transform of natural numbers, cf. A000027."

On the other hand, viewing f as a polynomial we have

$ hops '(1+x+2*x^2+5*x^3+18*x^4+77*x^5+362*x^6)/(1-2*x)' | jq '.seq=(.seq|@csv)'
{
  "hops": "(1+x+2*x^2+5*x^3+18*x^4+77*x^5+362*x^6)/(1-2*x)",
  "seq": "1,3,8,21,60,197,756,1512,3024,6048,12096,24192,48384,96768,193536"
}

which is less helpful, and looking up this sequence in the OEIS wouldn't give a hit. I guess one could track the precision in a separate parameter thought and maybe still be able to get rid of Indent.

I'm not sure what the impact on performance is of having Indent and DZ in the data type. Pattern matching is very fast in Haskell though. One would need to benchmark to find out, I guess.

from hops.

I modified your parser to accept polynomials like [0,1,1] Thus

$ hops '1/(1-[0,1,1])'
{"hops":"1/(1-[0,1,1])","seq":[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]}
$ hops '1/(1-{0,1,1})'
{"hops":"1/(1-{0,1,1})","seq":[1,1,2]}

At a minimum, this makes entering certain polynomials much easier:

$ hops '[1,1,2,5,18,77,362]/(1-2*x)' | jq '.seq=(.seq|@csv)'
{
  "hops": "[1,1,2,5,18,77,362]/(1-2*x)",
  "seq": "1,3,8,21,60,197,756,1512,3024,6048,12096,24192,48384,96768,193536"
}

I'm not sure if there would be any general interest in such a feature.

from hops.

That's neat. Please do submit a pull request.

If you'd like to write a few lines about it in the tutorial that would be great too, and maybe fix my confusing wording about {1,2,3} specifying a finite sequence while you're doing it. If you don't feel like working with the docs, then no worries.

from hops.