Division / Modulo scale poorly.

[paholg]

Due to an exponentially scaling issue, these operations seem to scale linearly (instead of logrithmically).

We should try to fix this at some point, or at least pay attention to it if Rust improvements fix it for us.

[llogiq]

Is this because we first shift left the divisor?

[paholg]

This is because sometimes where clauses scale exponentially. Other operators (I think multiplication at least) had similar issues, but I was able to find a way to structure them so as to get linear where-clause scaling. I have not found a way to structure division for that.

The division algorithm is fine.

[paholg]

This reddit post contains a workaround that may be useful here.

[paholg]

So far, the workaround in that post seems to not help here:

http://i.imgur.com/TBraHHK.png

[paholg]

On recent builds, at least 1.12.0-nightly (2ad5ed07f 2016-07-08), this is much better (although still linear):

http://i.imgur.com/oZt8JlH.png

Note: the old and new here are not comparing compiler versions, but typenum versions. This chart should be compared to the previous one.

[paholg]

I'm playing with this, on the div branch. So far, I seem to have made it worse:

http://i.imgur.com/a8Jb7i3.png

It does fix dimensioned issue 22 though, so I guess I'll play with it more and see if I can make it faster.

[paholg]

I just found out about this, which looks very interesting and may eventually fix this issue for us.

[ranma42]

Another approach might be to use a more efficient algorithm to compute the division.
Newton-Raphson can double the number of exact digits at each iteration, therefore converging very fast (at the expense of performing 2 multiplications per iteration) and it is commonly used for fast float division. Its application to integer values (including caveats and efficient implementations) is studied in the paper available at https://www.microsoft.com/en-us/research/publication/software-integer-division/

I would be willing to experiment with implementing it, but I would need some guidance.

[paholg]

@ranma42 I've skimmed through it, and it looks interesting. I'd be happy to help with any guidance you need.

Note that typenum's unsigned integers are variable precision, so we don't have to worry about keeping everying in e.g. 32 bits as they do. Also, our signed integers are not two's complement, but are just unsigned integers with a sign flag, so it's enough to implement just for unsigned integers.

The current division algorithm starts at line 1121 of uint.rs, and may give some idea of how to translate an algorithm to Rust's type system, but I'd be happy to help with any specifics.

[ranma42]

I started working on it :)
I wrote a Rust implementation of the algorithm to easily find bugs/issues/interesting cases). It felt very natural to split the implementation in a computation of the reciprocal approximation and then to use it to compute the final division result.

I started implementing the reciprocal at a type level here ranma42@c1a9674 , but even with just 6 iterations the compiler gets very slow. Am I doing something wrong?
How could I trace/debug what is going on?

[paholg]

I've finally had a chance to look at. I don't see anything that stands out, but I also don't really understand the algorithm.

It seemed like there were a few different versions in the paper you linked; if you could relate the exact algorithm you're using, I could at least provide a set of eyes to check that the implementation matches the algorithm.

As far as tracing/debugging what's happening, I don't have any great approaches. When things have blown up on me, I've just refactored until I get something that works. It's not a great method, but I don't know of any others without taking a deep dive into Rust's type-system code.

[ranma42]

This is the implementation I used for my experiments, based on "Figure 5: UNR recurrence method" in the aforementioned paper.

The main differences are:

• I split off the computation of the reciprocal approximation z
• in addition to the original loop-based implementation I did a recursive (purely functional) implementation as I expected it to be much easier to translate into type-level computations.

My tentative implementation of reciprocal approximation at type level is supposed to be a straightforward translation of the fun_rcp function in the gist.

[paholg]

This appears fixed in the latest nightly:

https://i.imgur.com/xWee44h.png

Thanks to @llogiq for pointing out this reddit post to me.