Mathematical backfires
Over the last few years I've racked my head on various mathematical problems. Some approaches are working well but most of my ideas are only worth for a mention because they either underlie an error in reasoning or might be solved in a not justifiable effort. At some point, there was also the case in which I have set up a formula and had to say in hindsight that the basic idea is already known - maybe I'm too late on this little blue ball. Despite everything, I want to share my basic approaches with you. Maybe you might find something useful in it.
Optimizing multiplication
Sure, multiplications are not as slow as divisions, but this does not mean, that we couldn't optimize it a bit. I had the basic idea, when I played with factors around powers of two. I think, most of you know, that we could express a simple multiplication in a optimized way, if the first factor is a power of two by:
x * n = (n << lb(x))
I thought, that it should be possible to find a way of optimizing every multiplication in that way, because if you move in small steps from a constant power of two, you have to subtract the difference on the other side like this:
256 * 41 = 10496 255 * 41 = 10455 // - 41 254 * 41 = 10414 // - 82
In a common matter, we could express this behavior with the following equation:
(256 - y) * 41 = 256 * 41 - 41y
To remove the remaining constants, we write the following equation with the approach from above like:
(2x - y) * n = (n << x) - yn
I still was at this position once before while I wrote this article. Then I thought, what a crap, I can't publish such a solution here, because it is a total failour. The only obvious optimization could be done with y = 1, so that we could say:
(2x - 1) * n = (n << x) - n
But the rest of the numbers wouldn't work, because we would ever have a multiply of n, which is complication of a simple multiplication, what was our initial situation.
As I said, I still deleted the whole stuff. But I wrote it again because I had an idea, where this approach could work. What is the constant 1 from the example above? Right. It's only the result of a power of two. So let's try to write the new equation with two powers of two:
(2x - 2y) * n = (n << x) - (n << y)
I think, now the formula is really intuitive. To give you after all a little proof, try the following:
(256 - 8) * 41 = (41 << 8) - (41 << 3)
Okay, we are far away from a common multiplication optimization, and our attempt could be called as failed. But we found a really simple way of optimizing integer multiplications where one factor could be splitted into two powers of two. I think this could be a good improvement in compilers - if it is still not in.
Optimizing floating numbers by fractions
Floating numbers are approximated inside of the computer by saving the significant and the exponent. With the third part the base - in our decimal system ever 10 - we are able to calculate the real number. If you need a better precision, you have to make sacrifice of losing memory, which also implies slower operations on these bigger memory allocations. This step is done by using the 64bit datatype double instead of float with 32bit. In theory, we could make a better use of these 64bit by using it as a container for a rational number. Maybe this sounds wired, but every real number - expecting irrational numbers (as the name suggests) - is able to transformed into a rational number. The following examples should demonstrate this:
The implimentation is straightforward and I use it from time to time in production. So how can we store our numerator and the denumerator? Simply by moving the numerator to the high part of a 64bit integer:
int_64 res = (n << 32) | d;
If you want to get the result as double, you have to roll back the operation with a right shift:
double res = (n >> 32) / (n & 0xFFFFFFFF);
As I said, I use this approach also in production. But this is only possible with a strict boundary for the numbers. And also the performance of this implementation lacks, because you should cancel the fraction very often; at best after every operation to avoid overflows. Some points of this approach is identical with my already published article storing small numbers in big ones, with the difference, that storing fractions inside of 64bit numbers are not so stable. In my PHP class xFraction I dig a little deeper with this idea, but also cancel after every operation.
By the way you are not bound on 64 bit numbers. You could also use two 16bit numbers inside of a dword or something else.
The size usage in comparison to double is not as good as I might have you believe in. Dependent on a signed or unsigned fraction you can use 31:32 or 32:32 bits (sure you could also use another ratio). This means, that you could have a maximum value of 2147483648/1 or as a minimum of 1/2147483648. On the opposite with double you are able to store 17 significant figures of a number - but as I said, you have not the accuracy of integers.
Let's call it only a halve failure; because if you know to work with the limitations, it is a good kind of improve the work with numbers.
Another attempt for float optimization
This is another attempt of storing floating numbers with regard to be accurate, memory gentle and fast. We know how an integer number is represented inside of the computer. By powers of two. This attempt is really simple and was only a 5minutes idea by defining, that every position of a binary string represents the inverse power of two.
In comparison of integers and inverse integers you could think about numbers as follows:
integer 100111:
inverse integer 100111:
But by inversing the meaning of every bit, you only inverse the whole number, so that this idea is only good for operations in a range of [0, 1]. The benefit of this is hard to the border of zero, because we can handle this with every other system much better.
Compression-Triangle
I had the idea of an ultimate compression-algorithm. Normally compression algorithms work by building up an index of repetitive phrases in a context and replace these large occurrences by a shorter reference to the index. Thus, the algorithm is better, if there are more similar phrases in the context.
But my idea of such an algorithm was a little different by storing the difference of two adjacent bits only. In theory you could save one bit with that approach. And then we could create the difference of the difference again and again and would save one bit per run in this recursive construct. We could stop compressing at some point, pack the rest and the number of runs in a handy format and it would result in a perfect compression. Wouldn't it be nice, storing a whole movie in a short string for example "D6KOAS87KOKO3F23ASDUWA5CX"?
But let's start at the beginning to figure out, that the idea will not work as expected. Forget the mention of differences for a while and focus on a little example where we only notice changes from one bit to another, means if there was a change, we write 1 and if not, we write 0. Let's use the number 31410 with the binary representation 1010101012. With that in mind we could write the following triangle:
(1) 1 0 1 0 1 0 1 0 1 (2) 1 0 1 0 1 0 1 0 (3) 1 0 1 0 1 0 1 (4) 1 0 1 0 1 0 (5) 1 0 1 0 1 (6) 1 0 1 0 (7) 1 0 1 (8) 1 0
If you want to reconstruct you have to start with 102 as initial value and run the algorithm 8 times to get the old initial value of 314. But this example was really easy because we only have 1 -> 0 and 0 -> 1 changes. In the real world we also have 0 -> 0 and 1 -> 1 too. My next idea was to represent the changes a little different, by bringing other symbols into the game:
(1) 1 0 0 1 1 0 1 0 1 (2) + - 0 + 0 - + - + (3) x x x x x x x
I symbolized the last row by x's, because we would start using other symbols for changes from "-" to "0" and so on. I tried this approach ones more with a incipiently blow up by represent every change with two bits. Maybe it would be possible to break it down later. The higher bit is only the indicator for the sign of the change. If both operand bits are equal, I decided to chooce the first bit in the style of the value of these bits.
(1) 1 0 0 1 1 0 1 0 1
(2) 11 00 01 10 11 01 11 01
-1 +0 +1 -0 -1 +1 -1 +1
As you see, the problem is the same, we relocate from a smaller bit stream to a bigger alphabet. If we would have 3 states per bit - for example by a base 3 computer, we were nevertheless not able to reduce the stream.
Tag weighting
This is not a failure in general, but rather a failure for myself because the derivated formular is already used in physics. I can't remember who published this formular too, if you know them, I would pleased to hear the name of them. The difference is, that I do not use the formular for physics, but for weighting a single element inside of a tag cloud to allow a floating transition depending on the variables. A passable solution was the following:
...where max_size and min_size are the boundaries of the font size and, max and min the boundaries of the number num which represents the current number we want to express in a certain font size range. As all Problems on this site are really old problems, I use now a logarithmic extension to calculate the font size of tag-cloud elements, which gives a better result - also for colorized clouds.
greatest proper power
The following solution is originated when I cogitated about factor out constants of square roots. Normally you would go over prime numbers, but I think this is really inconvenient. My wish was it to solve the problem without approximation. Lets look over an example:
I think this solution is not so trivial, so that you could say the answer immediately. Maybe it's clearer by
Or easier:
My first idea to find a formular for the problem was, that we search a multiple of two, so that we could multiply this number with another unknown. A formular of the first approach resulted in the following:
We could solve the equation for one unknown, but the rest is also an iterative job and an algorithm would become a complexity of O(x) or O(n/2). But let's think ones more about the whole problem. Is it really a multiple? No. It's a square, so that we get the following equation:
or transposed for x:
What have we done with that? Not many. The problem is still not solvable without approximation, but we've a complexity of O(log(n)). We could express the approximation with the following steps (as pseudocode):
initialize the result variable with one
initialize the counter variable with one
while forever
if the quadrat of the counter variable is bigger then the given value then
break
end if
if the result of the given number mod the calculated square of the counter is zero then
set the result variable to the counter variable
end if
add one to the counter
end while
return the result variable
With that functionality, it is possible to solve the problem of excluding the biggest possible number out of a square root. I dub the function of this method ggp(). To express these things in one step we could write the following equation (remember x = ggp(n)):
x * sqrt(52 / (x * x))
Our aim is not completely solved, so that this method is a good candidate of this collection. I wasn't able to find an equation to solve the problem with O(1).