Comments on A Neighborhood of Infinity: Fast forwarding lrand48()

good

2011-12-12T21:44:37.300-08:00

good

Alexey, I assume you are my Alexey :-) I can'...

2011-06-03T07:30:27.720-07:00

Alexey, I assume you are my Alexey :-)

I can't believe I re-implemented binary exponentiation for my Collatz monoid when I could have just used this trick!

Of course if the preludes class hierarchy made more sense it'd probably have been more obvious....

@Alexey, At the very least you can generalise you...

2011-05-30T09:44:33.700-07:00

@Alexey,

At the very least you can generalise your type signature. If you do that then you can reuse the code to do other stuff fast. For example, you can use the ideas here http://goo.gl/AjHPM to perform very fast regexp matches against strings that are very long repeating patterns.

Fun fun! pow :: Integral a => Affine -> a -...

2011-05-30T08:04:56.543-07:00

Fun fun!

pow :: Integral a => Affine -> a -> Affine
x0 `pow` y0
| y0 < 0 = error "Negative exponent"
| y0 == 0 = 1
| otherwise = f x0 y0
where
-- f : x0 ^ y0 = x ^ y
f x y
| even y = f (x `mappend` x) (y `quot` 2)
| y == 1 = x
| otherwise = g (x `mappend` x) ((y - 1) `quot` 2) x
-- g : x0 ^ y0 = (x ^ y) `mappend` z
g x y z
| even y = g (x `mappend` x) (y `quot` 2) z
| y == 1 = x `mappend` z
| otherwise = g (x `mappend` x) ((y - 1) `quot` 2) (x `mappend` z)

(Haven't compiled it.)

@Alexey, Yes. The correct way to implement this w...

2011-05-30T07:07:26.156-07:00

@Alexey,

Yes. The correct way to implement this would be through Monoid but I think Data.Monoid lacks the binary power algorithm. Maybe it appears in another library.

For number 3: When Affine is an instance of Num w...

2011-05-30T03:21:24.364-07:00

For number 3:

When Affine is an instance of Num we are able to use the efficient implementation of (^), which does better than repeatedly multiplying through.

http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Real.html#%5E

It take advantage of the fact that x^2y = (x*x)^y and x^(2y+1) = x(x*x)^y.

For number 3: By having Affine be an instance of ...

2011-05-30T03:17:31.560-07:00

For number 3:

By having Affine be an instance of Num, we can use the efficient implementation of (^), which does better than repeated multiplication.

http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Real.html#%5E

It takes advantage of the fact that x^2y = (x*x)^y and x^(2y+1) = x(x*x)^y.

I've used this trick, in speeding up lossy au...

2011-05-29T07:51:52.517-07:00

I've used this trick, in speeding up lossy audio codec. It's a little strange to find a random number generator in an audio codec, but they're there for a perfectly good reason - one piece of white noise sounds much like another, so the codec will simply transmit noise-like pieces of the audio as 'there is some noise here'. In order to pass the conformance tests, however, you need to generate the same sequence of random numbers.