I once read a programming book on Elliptic Curve Cryptography, which was invented by Dr. Neal Koblitz. So the book said - whatever is in the next 200 pages is considered trivial by mathematicians working in number theory. If you write it in the form of equations, this entire book will occupy less than half a page. It is basically a lemma and a few theorems. But this book is 200 pages long. Why ? Because it tells you how to implement that lemma and those theorems using C++.
So that's how that is.
Just yesterday I described to an intern how to generate the nth term of a Halton sequence in base k. So if you want the 17th term in base 3, well, decimal 17 = ternary 122, reflect 122 to get 221, then ternary 0.221 = decimal 0.926. So the answer is 0.926. Its very, very simple. High school math. The nth halton term is in fact given by a 1-line equation in mathematics.
Now he came back with scala code to do the same thing.
Look at this monster:
def Halton( n:Int, b:Int):Seq[Double] = {(1 to n).map( x=>Integer.toString(x,b).reverse.zipWithIndex.map(y=>(y._1-'0')*pow(b, -(y._2+1))).sum)}
Now it works & its functional programming & computes a million Halton terms in any base in 5 seconds and so on, but still, look at it. Is it anywhere close to the one line equation ? If I express what I want declaratively, will it be any simpler ? Not really. Why not ? Because a declaration like "1..n" means an imperative loop, a declaration like "convert 17 in decimal to ternary" means a whole bunch of divisons and remainders and aggregation, then a reflect means reversing a string, which implicitly means iterating over a character array and allocating new space for the reversed result, then a reconvert ternary to decimal means an iteration with powers of 10, where a power means other iteration over multiplication....jesus! This simple 1-line equation in math becomes hundreds of thousands of loops in practice. There's no getting around that. If you've gotten around it, you've just invented math!
That function definition is a monstrosity because it is poorly factored. Assuming pre-existing fromBase and toBase functions, here is a definition that in my opinion is easily readable and matches your verbal description:
halton b n = fromBase b (reverse digits) / b^(length digits)
where digits = toBase b n
Just to show there's nothing up my sleeve, here are the fromBase and toBase definitions:
toBase b 0 = []
toBase b n = (n `mod` b) : toBase b (n `div` b)
fromBase b [] = 0
fromBase b (n:ns) = n + b * fromBase b ns
They too read like how a mathematician would define them. (I abstained from use of foldr/unfoldr to make this clear.)
Edit: On second thought, it's easy to implement it as a direct recursion. I'll demonstrate it in C so I'm not accused of language chauvinism:
double halton(int b, int n)
{
return (n == 0) ? 0.0 : (n % b + halton(b, n / b)) / b;
}
Here the digit reversal is implicit in the recursion (the oldest programmer trick in the book).
This C code is self-contained and compiles to a tiny handful of machine code instructions, so it's hard to see how your statement that "this simple 1-line equation in math becomes hundreds of thousands of loops in practice" holds much water.
They talk about "active" or "runnable" maths. The programming languages they create aim to basically mirror mathematical expressions. This in turn makes the programming stack much smaller and easier to comprehend.
The only reason it's one line in math is that the rest of math is implicitly hiding in your brainstate. If you could extract that out it would be much bigger and uglier much like your expansion of this code into loops and memory manipulation, etc.
But what's your point? Code can do more wide ranging things and does so with fewer available symbols (no superscript for pow() operations), so it's wordier, but really it's not so far different. It may take a computer 200 pages of explained C++ but it takes a child months and years of schooling.
I imagine that the book might as well have used another (simpler) language. Now, as I see it, to understand the math, you need quite a lot of domain knowledge. A formula doesn't make sense out of context. Most statements written in programming languages do that, in a much higher degree.
Therefore, to actually do the ECC, I think it's quicker just to read the language specification of your (simple) language, than actually understand all of the math being the formulas. Granted, you wouldn't understand WHY it works. And that's my point. Comparing math to programming languages is like comparing apples to oranges.
So that's how that is.
Just yesterday I described to an intern how to generate the nth term of a Halton sequence in base k. So if you want the 17th term in base 3, well, decimal 17 = ternary 122, reflect 122 to get 221, then ternary 0.221 = decimal 0.926. So the answer is 0.926. Its very, very simple. High school math. The nth halton term is in fact given by a 1-line equation in mathematics.
Now he came back with scala code to do the same thing. Look at this monster:
def Halton( n:Int, b:Int):Seq[Double] = {(1 to n).map( x=>Integer.toString(x,b).reverse.zipWithIndex.map(y=>(y._1-'0')*pow(b, -(y._2+1))).sum)}
Now it works & its functional programming & computes a million Halton terms in any base in 5 seconds and so on, but still, look at it. Is it anywhere close to the one line equation ? If I express what I want declaratively, will it be any simpler ? Not really. Why not ? Because a declaration like "1..n" means an imperative loop, a declaration like "convert 17 in decimal to ternary" means a whole bunch of divisons and remainders and aggregation, then a reflect means reversing a string, which implicitly means iterating over a character array and allocating new space for the reversed result, then a reconvert ternary to decimal means an iteration with powers of 10, where a power means other iteration over multiplication....jesus! This simple 1-line equation in math becomes hundreds of thousands of loops in practice. There's no getting around that. If you've gotten around it, you've just invented math!