Thoughts about numeric roles in Perl 6

There was a big discussion about potential numeric classes/roles in Perl 6 on #perl6 a few days ago. Most of it went right over my head, I fear. But I've kept on thinking about it in the days since, and it seems to me there is a pretty simple and mathematically sound layout for the roles. (Instead of worrying about coming up with beautiful names, I'm just going to stick "Role" onto the name of each mathematical concept.) This is a quick high level sketch which I have made no attempt to implement.

The biggest role would be ComplexRole, capturing the idea of numbers with real and imaginary parts (either or both of which might be zero), and implementing a slew of standard mathematical functions that work on complex numbers.

Then there would be a subset RealRole of ComplexRole where { $^z.im == 0.0 }. The most notable added method would be Num, but there would probably also be a lot of RealRole-specific mathematical functions, as they can be a lot simpler than the complex equivalents.

I don't know how to express is as a where, but the RationalRole subset of RealRole would mostly just add numerator and denominator methods. And finally we would have subset IntegerRole of RationalRole where { $^q.denominator == 1 }.

The idea would be that the classes would be built up in the opposite order than this (or not related at all), using the logical computer programming approach, with these roles applied on top to give a mathematical structure. So you'd define a rational class as two integers, then define numerator and denominator methods for the RationalRole, a Num method for the RealRole, and an imaginary method for the ComplexRole.

I'm not sure how practical this is to actually implement in Perl 6, but it seems like it would be a nice way to capture these notions. I'm presuming most of the mathematical functions would be implemented on ComplexRole and RealRole, so this would provide a simple way of plugging any new math types you defined into a full library of math functions.

Update: I've started work on implementing B-spline knot vectors and basis functions in Perl 6, but it will be a few more days before I have something worth posting.

Detecting Squares Cheaply

So, moritz_ on #Perl6 asked about detecting squares cheaply, ie without just calling sqrt. A quick Google search led me to Detecting Squares, which has a nice discussion on quick filters you can use. moritz_ got me thinking about looking at the same problem in more computer-oriented terms. It's quickest to compute if you can just look at the least significant byte of the number instead of computing mod 100 (as the above page suggests). So here's a quick and dirty Perl 5 program to find the magic numbers:

That determines there are 44 numbers that repeat if you look at the first hundred thousand squares mod 256. And in fact, you don't need to look at nearly that number. Say your number N = 256n + m, where m is less than 256. Then N squared is 65536n^2 + 512nm + m^2, which is congruent to m^2 mod 256. That is to say, the least significant byte of N is the only byte which contributes to the least significant byte of N squared.

This means that given a random number, you can determine 212 out of 256 times (about 82%) that the number is not a square by doing a simple table lookup on the last byte of the number.

(I think a really pretty little Perl 6 program could also be used to demonstrate it, but I'm not going to try while my Perl 6 build is broken.)