Archive for the ‘Mathematics’ Category

Old Regression by Leonardo da Pisa

Saturday, June 11th, 2011

After reading this blog post I thought a bit about endianness (big-endian is just bad), and while having a shower a theory came into my mind: Maybe Arabs had little-endian integers (meaning least-significant bit first) but wrote (and still do) from right to left (meaning least-significant bit/digit at the right). And when Leonardo da Pisa (Fibonacci) brought Arabic numerals to Europe, he wrote in the same style, not flipping the digits, hence establishing big-endian. In fact I could verify that with Wikipedia. But I also noticed that this “bug” has been there before, Indians write from left to right (Wikipedia told me about a coin in Brahmi written from right to left, but that was before there were any numerals), and they have always used big-endian. Thus Arabs fixed that issue (maybe not knowingly), but stupid Europeans did not get why big-endian is stupid. Furthermore, big-endian numerals look more like those stupid Roman numerals, and our usual way of vocalising them is like in Roman times. And because of Leonardo da Pisa there are those stupid architectures using big-endian representation (fortunately not x86, amd64), causing non-portability, byte-order-marks and all that stupid stuff. And left-shifts could actually be left-shifts and right-shifts could be right-shifts.

Short list of arguments for little-endian:

  • Value of a digit d at position i is simply d·b**i (b is the base). That would obviously be the most natural representation if you would implement integers by using bit-arrays. It does not depend on the length, no look-ahead required.
  • You can simply add numbers from left to right (no right-alignment for summation).
  • For radix sort you can begin from left.
  • Simple cast between longer and shorte integers without moving any bits.
  • You do not need words like “hundred”, “ten-million”, “billiard” etc., because you can interprete a sequence online without look-ahead.
  • Repeating modulo and integer division by the base gives little-endian-representation.
  • The least-significant bits carry more interesting number theoretical information.

Well, big-endian is more like lexicographic order, although I am not sure if it is clearly better for natural languages. For division you have to start with the most-significant bit, but—hey—division is obviously not as important as all the other operations where you start with the least-significant bit. Of course sometimes little-endian is not a good notation, for measurements one should use floating point numbers (in a decimal world called “scientific notation”) and the mantissa should start with the most-significant bit/digit, after the exponent to avoid look-ahead (unlike the scientific notation).

If Leonardo da Pisa would have thought a bit about what he is doing, there would not be all those drawbacks! Just my thoughts about that regression. ;)

Spoj: SCRAPER

Tuesday, April 5th, 2011

Yet another Spoj-problem: SCRAPER. Short description of the problem (shorter than the official one): F (F?5·10?) floors in a scyscraper ([0,F[), E (E<100) elevators with a min-floor X?[0,F[ and an increment Y. Now you should decide if you can use the elevators to get from floor A to floor B. My solution (it took some time to fix all bugs, because I am out of practice): Two elevators ((X?, Y?) and (X?, Y?)) are “adjacent” if there is a common floor, i.e. {x ? [X?, F[ ? [X?, F[ | x ? X? (Y?) ? x ? X? (Y?)} ? ø. If we are able to compute the adjacency, we can simply use a depth-first-search to check if there is a path between A and B (identifying all elevators visiting a certain floor is trivial). How to check it? Without loss of generality X??X?. Let d := X? - X?. If the elevator 0 wants to reach a floor visited by elevator 1, the number of Y?-steps f has to comply with Y?·f ? d (Y?). We can compute a solution for f by using the extended Euclidean algorithm. It can solve the equation a·Y? + b·Y? = gcd(Y?, Y?) =: g, and there exists a solution for f iff g|d. If this is the case, we can conclude Y?/g·a ? 1 (Y?) ? Y?/g·a·d ? d, that looks like our previous equation, now we know that f ? a·d/g. We can perform a “plain” integer division, because, since g|d. For the computed f we want to know if there exists any n such that X? ? X?+Y?·f+n·lcm(Y?, Y?) < F (adding n·lcm(Y?, Y?) floors does not change anything). We can perform that quite simply by comparing the expression with X? for the biggest possible n (where the expression is smaller than F): X? ? F-1 - ((F-1 - (X?+Y?·f)) % lcm(Y?,Y?)). That's it. I used some caching and handled special cases for the extended Euclidean algorithm for optimisation, but that is not that interesting. Here you can get the source-code, but of course you should try to solve it yourself and you should not have even read this text!

What is special about the number 36?

Saturday, March 5th, 2011

It is the smallest natural number which is not an element of the list of special numbers at the German Wikipedia. By the way: The smallest special number seems to be -2, while -0.5 seems to be the smallest value of a Unicode-digit (༳, u0f33, TIBETIAN DIGIT HALF ZERO).