Cedric's challenge, C port and analytic attempt

I was a bit disappointed that the C port of the previous code wasn't quite as fast as another approach which cached more state instead of generating the i'th value. The second attempt, using the bcd lists was comparable to John Wilson's Java version (1.3 seconds rather that 1.5 reported by the Java), and an attempt using bitsets a bit slower. Timings on Eee pc 900, Ubuntu hardy heron. The code is nrnat2.c.

The biggest jumps are between 9(descending digits) and 10(ascending) and 10(descending) and 12(ascending). Generating those four values will give the largest jump in a range.

The number of values will be the total of combinations: 9 + 9 * 9 + 9 * 9 * 8 ... up to the max value.

The total for 1..9 is 9*(9+1)/2 = 45;
For numbers 10 to 98 there are 9 numbers starting with each digit, so you have 450*9 for the first digit, and 9 lots of a odd sum, where there's one digit missing - so 9 * 45 - 45 for taking one digit out each time (the range is 0..9 instead of 1..9).

That gives a total up to 10 of 45

Up to 100 we get the 45 up to 10, 45 * 10 * 9 for the first digit shifted once repeated 9 times, and 40 * 9 for the second digit repeated 9 times (as the first digit is always non-zero, it biases the remaining digit's average by 0.5 from 4.5 to 4). So total for up to 100 is 45 + 45 * 10 * 9 + 40 * 9 = 4455.

Up to 1000 we get the values so far, 45 * 100 * 9 * 8 for the first digit shifted twice repeated 9 * 8 times - the number of combinations of the other digits. The remaining digits occur the same number of times as each other in each position and once for each value of the first digit, so you get 40 * 9 * 8 * 11 from them, so total is (4455 + 45 * 100 * 9 * 8 + 40 * 9 * 8 * 11) = 360135.

Similarly sum up to 10000 is (360135 + 45 * 1000 * 9 * 8 * 7 + 40 * 9 * 8 * 7 * 111) = 25277895

Simplifying, the sum of the values with n digits is (9!/(9-(n-1))!) * ( 45 * pow(10, n-1) + 40 * floor(pow(10, n-1) / 9) ) and the maximum jump is floor( ( 1203456789-1029876543 ) / pow(10, 10-n) )


Pete

I hate everybody

Well, every programming language I've ever used anyway.

Not a lot to report, I've faded off of doing the wide-finder thing as the MPI ruby code was about as good as I could expect in elegance, and I'm more interested in other stuff at the moment. It did get me annoyed with C++ again, in that its primary mechanisms for specialisation - template metaprogramming and single dispatch polymorphism - aren't quite a good fit for the problems I want to solve, - the boost::regex version was much slower, and shouldn't be. I want to have good enough performance and clarity and open objects when developing and strongly typed interfaces when building libraries and extensible grammar and access to the low-level machine when bit-twiddling (tbray9.cpp uses a better 8-wide '\n' scan, adapted off this zero-in-word hack; parallelising it with pthreads or MPI is a left to the reader.) I don't want to have to use unhygienic macros; and this discussion of units in measures in Java's verbose, strict, non-expressive generics made me think about kin, my pet lisp+prolog+strong types language again.

So most of this week I've either been thinking how to make fast VList based stack work for a fork+join worker model, or playing with a higher level language which looks a bit like python with strongly type annotations - I prefer infix syntax, Dylan has always been a bit wierd looking to me, and I don't want JavaScript's C-like braces. Python got a bit interesting when it looked like it was drifting towards lisp-land, but then drifted away again.

One thing that struck reading the dylan manual (it's always worth looking at how other languages do things) was its convention that

    bar(foo)

and

    foo.bar

were the same thing. If that was combined with a strong form of memoization such that writing

    bar(foo) := baz

guaranteed that in future

    bar(foo) == baz

you would get the ability to define dynamic fields in objects, similar to what JavaScript and other associative object based languages offer, as they could be written in the dot syntax as:

    foo.bar := baz
  ------------------
    foo.bar == baz

Assuming type specialisation on the function trace path is also cached, lookup becomes a single hashtable access. You do lose locality, but if you want performance you'd have to add it as a field on the object's class, though I hate that - language features shouldn't be used for indirect effects; type safety and performance optimisation should be orthogonal, and lack of locality saps performance (though it depends on context - if you're iterating over lots of objects, accessing the same field, the locality could be better than if you had a conventional C++ (different fields in the same object local, different objects anywhere) or JavaScript (different fields in the same object possibly local, using a hashtable, or similar).

As an aside, recursively rewriting the slot accessor form

    x.f.g
 == (x.f).g
 == f(x).g
 == g(f(x))

Which, although apparently missing from the DRM, is the opposite of the normal math interpretation of (g o f)(x) = g(f(x)). Pity. Now I also hate Dylan.

My more recent ramblings about kin are on kintab.net; I've thought a bit about what I'd need to do units and measures nicely, and have been going through SCIP coding up what the examples would look like in infix notation, which is a useful test for conciseness and clarity.


Pete

(N+1)^2 = N^2 + 2N + 1

My mind drifted when sitting on the loo at work the other day, making patterns on the cubicle tiles...



(changed title to more clearly reflect the idea that adding a row to two adjacent edges then one tile creates a new square, which the animation shows if you're viewing in a SVG enabled browser, such as Firefox or Opera.)